2 Probability and Random Processes ECS 315 Asst. Prof. Dr. Prapun Suksompong (ผศ.ดร.ประพันธ์สขสมปองุ ) [email protected]

0 downloads 22 Views 6MB Size

1

Course Website

Line Group

Before we start … Grab the free handouts Course syllabus Slides

Line group Make sure that you have the lecture notes either via Please join the ECS315

buying the hardcopy from the copy center or downloading a pdf copy from the course website 2

Probability and Random Processes ECS 315 Asst. Prof. Dr. Prapun Suksompong (ผศ.ดร.ประพันธ์ สุขสมปอง) [email protected]

Introduction Office Hours: BKD, 6th floor of Sirindhralai building

3

Wednesday Friday

14:30-15:30 14:30-15:30

Game and Gambling ECS 315

Asst. Prof. Dr. Prapun Suksompong (ผศ.ดร.ประพันธ์ สุขสมปอง) [email protected] Office Hours: BKD, 6th floor of Sirindhralai building

4

Wednesday Friday

14:30-15:30 14:30-15:30

Asst. Prof. Dr. Prapun Suksompong Chairperson of Electrical Engineering Program

(and Chairperson of Electronics and Communication Engineering Curriculum) at Sirindhorn International Institute of Technology (SIIT) Ph.D. from Cornell University, USA In Electrical and Computer Engineering Minor: Mathematics (Probability Theory) Research: Neuro-Information Theory

(Communications in Human Brain)

Current Research: Wireless Communications,

Localization, Game Theory 2009, 2013, and 2017 SIIT Best Teaching Awards 2017 SIIT Distinguished Teacher Award 2011 SIIT Research Award 2013 TU Outstanding Young Researcher Award

prapun.com 5

Course Syllabus

6

Course Website prapun.com

Current version

7

Earlier version

i Course Web Site Announcements References Handouts (Posted before corresponding

lectures; also available at the copy center) Annotated Notes/Slides (Posted after corresponding lectures) Calendar Exams HW due dates

Please check the course website regularly. 8

www2.siit.tu.ac.th/prapun/ecs315/

Course Web Site Announcements

The syllabus contains tentative information.

9

I will announce in class and on the website if there is any

change. You are responsible for making sure that you obtain this information. Come to classes on time and listen carefully for announcement(s). For those who want a preview of the class materials, old slides along with the notes and HW from earlier years are available on my web site (prapun.com).

Course Website: Notes & Slides Some PDF notes/slides will be posted before the corresponding lectures. Hard copies can also be purchased from the copy center.

10

In lecture, PDF notes/slides will be highlighted and annotated with examples / comments.

The slides and annotated notes will be posted after the corresponding lectures.

Course Website: Notes & Slides Some PDF notes/slides will be posted before the

corresponding lectures. Hard copies can also be purchased from the copy center.

In lectures… PDF notes/slides will be highlighted and annotated with

examples / comments. Put all of your energy into understanding the material.

The slides and annotated notes will be posted after the

corresponding lectures. Remind (email) me the day after the lecture if the

11

annotated notes/slides from the day before are still not posted on the web.

Course Organization Course Website:

http://www2.siit.tu.ac.th/prapun/ecs315/ Lectures: Tuesday Thursday

10:40-12:00 BKD 2506 13:00-14:20 BKD 3214

Tutorial/Exercise/Make-up sessions: Thursday

14:40-16:00 BKD 3214 (Shared with ECS332)

Textbook:

Probability and stochastic processes: a friendly introduction for

electrical and computer engineers

12

By Roy D.Yates and David J. Goodman 2nd Edition ISBN 978-0-471-27214-4 Library Call No. QA273 Y384 2005 Student Companion Site:

http://bcs.wiley.com/he-bcs/Books?action=index&itemId=0471272140&bcsId=1991

i The Thursday Sessions Shared with ECS332. The first 4-5 sessions will be used for ECS315

tutorial/review classes. Start from this Thursday.

Later, we will start using them as tutorial sessions. Will be conducted in Thai to help those who have problem

with English. Hopefully, you will ask more questions as well.

They can also be used for pre-announced make-up classes and

in-class exercises as well. 13

ECS 315: Course Outline 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 14

17.

Introduction, Set Theory, Classical Probability Combinatorics: Four Principles and Four Kinds of Counting Problems Probability Foundations Event-based Conditional Probability Event-based Independence Random variables, Support, Probability Distribution MIDTERM: 4 Oct 2018 TIME 09:00 - 11:00 Discrete Random Variables Families of Discrete Random Variables and Introduction to Poisson Processes Real-Valued Functions of a Random Variable Expectation, Moment, Variance, Standard Deviation Continuous Random Variables Families of Continuous Random Variables and Introduction to Poisson Processes Multiple Random Variables Correlation, Covariance, Limiting Theorems Mixed Random Variables, Introduction to Random Vectors and Random processes FINAL: 11 Dec 2018 TIME 09:00 - 12:00

[1] [1] [1] [1] [1] [2] [2] [2,10] [2] [2] [3] [3,10] [4-6] [4, 6, 7] [3, 5, 10]

Probability and

15

Randomness

“Les questions les plus importantes de la vie ne sont en effet, pour la plupart, que des problèmes de probabilité.”

“The most important questions of life are, for the most part, really only problems of probability.”

Pierre Simon Laplace (1749 - 1827) [https://en.wikipedia.org/wiki/Pierre-Simon_Laplace] [http://forvo.com/word/pierre-simon_laplace/ ]

16

“On voit, par cet Essai, que la théorie des probabilités n'est, au fond, que le bon sens réduit au calcul; elle fait apprécier avec exactitude ce que les esprits justes sentent par une sorte d'instinct, sans qu'ils puissent souvent s'en rendre compte.”

“One sees, from this Essay, that the theory of probabilities is basically just common sense reduced to calculus; it enables us to appreciate with exactness that which accurate minds feel with a sort of instinct, often without being able to account for it.”

Pierre Simon Laplace (1749 - 1827)

17

Levels of Study in Probability Theory Probability theory is the branch of mathematics

devoted to analyzing problems of chance.

18

Art of Guessing

1.

High School: classical

2.

Undergraduate: calculus

3.

Graduate: measure-theoretic

We are here!

More references Use ones that say probability

and random (or stochastic) processes If it has the word “statistics” in the title, it may not be rigorous enough for this class Many chapters will overlap our

class content. In which case, it provide a nice reading with beautiful/colorful figures.

If it has the word “measure” or

“ergodic” in there, it is probably too advanced.

19

More References (in Thai) ความน่าจะเป็ นและสถิติสาํ หรับวิศวกรรมไฟฟ้ า ผู้แต่ง: มานพ วงศ์สายสุวรรณ และคณะ ISBN : 9789740324164

ความน่าจะเป็ น :สําหรับวิทยาศาสตร์และ

วิศวกรรมศาสตร์ (PROBABILITY) ผู้แต่ง : สายชล สินสมบูรณ์ทอง ISBN : 9789740329053

ทฤษฎีความน่าจะเป็ น - Probability

Theory

ผู้เขียน: ผู้ช่วยศาสตราจารย์วัลลภ เฉลิมสุ

วิวัฒนาการ ISBN 9789749918760 20

Recommended Reading Understanding Probability: Chance Rules in 21

Everyday Life By Henk Tijms Call No. QA273 T48 2012 Cambridge University Press “Part One” provides many motivating examples and problems from everyday life “Part Two” teaches clearly and simply the mathematics of probability theory. Sample materials are available at the author’s website: http://personal.vu.nl/h.c.tijms/ http://www.cambridge.org/aus/catalogue/c atalogue.asp?isbn=9781107658561&ss=exc

2nd Edition (2007) 3rd Edition (2012)

Another Recommended Reading

The Drunkard's Walk The Drunkard's Walk: How

22

Randomness Rules Our Lives By Leonard Mlodinow Deals with randomness and people's inability to take it into account in their daily lives. A bestseller, and a “NY Times notable book of the year” Named “one of the 10 best science books of 2008” on Amazon.com. [Thai Translation: ชีวิตนี้ ฟ้ าลิขติ : การสุ่มเลือก ควบคุมบัญชา ทุกเรื่องราวในชีวิตของเรา]

Leonard Mlodinow Euclid’s Window: the Story of Geometry

from Parallel Lines to Hyperspace Feynman’s Rainbow: a Search for Beauty in Physics and in Life A Briefer History of Time

with Stephen Hawking an international best-seller that has appeared in 25 languages.

The Drunkard's Walk: How Randomness Rules our Lives Apart from books on popular science, he also has been a

screenwriter for television series, including Star Trek: The Next Generation and MacGyver.

23

Watch Mlodinow’s talk Delivered to Google employees About his book (“The Drunkard's Walk”)

24

http://www.youtube.com/watch?v=F0sLuRsu1Do

Watch Mlodinow’s talk A few years ago a man won the Spanish national lottery with a

25

ticket that ended in the number 48. Proud of his “accomplishment,” he revealed the theory that brought him the riches. “I dreamed of the number 7 for seven straight nights,” he said, “and 7 times 7 is 48.” Those of us with a better command of our multiplication tables might chuckle at the man’s error, but we all create our own view of the world and then employ it to filter and process our perceptions, extracting meaning from the ocean of data that washes over us in daily life. And we often make errors that, though less obvious, are just as significant as his. [Leonard Mlodinow, The Drunkard's Walk: How Randomness Rules Our Lives]

Examples Prelude to the Theory of Probability

26

Game 1: Seven Card Hustle 27

The Seven Card Hustle Take five red cards and two black cards from a pack. Ask your friend to shuffle them and then, without looking at the

faces, lay them out in a row.

Bet that they can’t turn over three red cards. Explain how the bet is in their favor. The first draw is 5 to 2 (five red cards and two black cards) in their

favor. The second draw is 4 to 2 (or 2 to 1 if you like) because there will be four red cards and two black cards left. The last draw is still in their favor by 3 to 2 (three reds and two blacks). The game seems heavily in their favor, but YOU, are willing to 28

offer them even money that they can’t do it!

The Seven Card Hustle Take five red cards and two black cards from a pack. Ask your friend to shuffle them and then, without looking at the

faces, lay them out in a row.

Bet that they can’t turn over three red cards. Explain how the bet is in their favor. The game seems heavily in their favor,

but YOU, are willing to offer them even money that they can’t do it! Even odds or even money means 1-to-1 odds.

29

[Lovell, 2006]

The Seven Card Hustle: Sol The correct probability that they can do it is 5 43 2 7 6 5 7

Do not worry too much about the math here. Some of you may be able to calculate the probability using knowledge from your high school years. We will review all of this later.

5 3 Alternatively, 5! 3! 4! 7 3! 2! 7! 3 5 4 3

1 7 65

2 7 30

[Lovell, 2006]

Game 2: Monty Hall Problem 31

Monty Hall Problem (MHP): Origin Problem, paradox, illusion Loosely based on the American television game show

Let’s Make a Deal. (Thai CH7 version: ประตูดวง.) The name comes from the show’s original host, Monty Hall. One of the most interesting mathematical brain teasers of recent times.

32

Monty Hall Problem (MHP): Origin

33

[https://www.youtube.com/watch?v=qcYf64aKDJo]

Monty Hall Problem: Math Version Animation with narration by Ron Clarke

34

[https://www.youtube.com/watch?v=mhlc7peGlGg]

Monty Hall Problem: Math Version Originally posed in a letter by Steve Selvin to the American

Statistician in 1975. A well-known statement of the problem was published in Marilyn vos Savant’s “Ask Marilyn” column in Parade magazine in 1990: “Suppose you're on a game show, and

35

you're given the choice of three doors: Behind one door is a car; behind the others, goats.You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?”

Marilyn vos Savant Vos Savant was listed in each edition of the

Guinness Book of World Records from 1986 to 1989 as having the “Highest IQ.” Since 1986 she has written “Ask Marilyn” Sunday column in Parade magazine Solve puzzles and answer questions from readers

36

[ http://www.marilynvossavant.com ]

MHP: Step 0 There are three closed doors. They look identical.

37

MHP: Step 0 Behind one of the doors is the star prize - a car. The car is initially equally likely to be behind each door.

Behind each of the other two doors is just a goat.

38

MHP: Step 1 Obviously we want to win the car, but do not

know which door conceals the car. We are asked to choose a door. That door remains closed for the time being.

39

“Pick one of these doors”

MHP: Step 2 The host of the show (Monty Hall), who knows what is behind

the doors, now opens a door different from our initial choice. He carefully picks the door that conceals a goat.

40

We stipulate that if Monty has a choice of doors to open, then he chooses randomly from among his options.

MHP: Step 3

“Do you want to switch doors?”

Monty now gives us the options of either 1. 2.

sticking with our original choice or switching to the one other unopened door.

After making our decision, we win whatever is behind our door.

41

Monty Hall Problem Assuming that our goal is to maximize our chances of winning the car, what decision should we make? Will you do better by

sticking with your first choice, or

by switching to the other remaining door? Make no difference?

42

Interactive Monty Hall

43

http://montyhallgame.shawnolson.net/ http://www.shodor.org/interactivate/activities/SimpleMontyHall/ http://www.math.uah.edu/stat/applets/MontyHallGame.xhtml http://scratch.mit.edu/projects/nadja/484178 http://www.math.ucsd.edu/~crypto/Monty/monty.html

Let’s play! 44

Interactive Monty Hall

45

[http://www.stayorswitch.com/]

Back to the boring administrative stuff! 46

Calendar

47

M 13‐Aug‐18 20‐Aug‐18 27‐Aug‐18 3‐Sep‐18 10‐Sep‐18 17‐Sep‐18 24‐Sep‐18 1‐Oct‐18 8‐Oct‐18 15‐Oct‐18 22‐Oct‐18 29‐Oct‐18 5‐Nov‐18 12‐Nov‐18 19‐Nov‐18 26‐Nov‐18 3‐Dec‐18 10‐Dec‐18

T 14‐Aug‐18 21‐Aug‐18 28‐Aug‐18 4‐Sep‐18 11‐Sep‐18 18‐Sep‐18 25‐Sep‐18 2‐Oct‐18 9‐Oct‐18 16‐Oct‐18 23‐Oct‐18 30‐Oct‐18 6‐Nov‐18 13‐Nov‐18 20‐Nov‐18 27‐Nov‐18 4‐Dec‐18 11‐Dec‐18

W 15‐Aug‐18 22‐Aug‐18 29‐Aug‐18 5‐Sep‐18 12‐Sep‐18 19‐Sep‐18 26‐Sep‐18 3‐Oct‐18 10‐Oct‐18 17‐Oct‐18 24‐Oct‐18 31‐Oct‐18 7‐Nov‐18 14‐Nov‐18 21‐Nov‐18 28‐Nov‐18 5‐Dec‐18 12‐Dec‐18

R 16‐Aug‐18 23‐Aug‐18 30‐Aug‐18 6‐Sep‐18 13‐Sep‐18 20‐Sep‐18 27‐Sep‐18 4‐Oct‐18 11‐Oct‐18 18‐Oct‐18 25‐Oct‐18 1‐Nov‐18 8‐Nov‐18 15‐Nov‐18 22‐Nov‐18 29‐Nov‐18 6‐Dec‐18 13‐Dec‐18

F 17‐Aug‐18 24‐Aug‐18 31‐Aug‐18 7‐Sep‐18 14‐Sep‐18 21‐Sep‐18 28‐Sep‐18 5‐Oct‐18 12‐Oct‐18 19‐Oct‐18 26‐Oct‐18 2‐Nov‐18 9‐Nov‐18 16‐Nov‐18 23‐Nov‐18 30‐Nov‐18 7‐Dec‐18 14‐Dec‐18

Lectures

Exams

Please Double-Check Exam Dates!

i Calendar (Google) Available on the course website.

48

i Help and Office Hours Get some help! Do not wait until the final exam time or after the grade is out. Right after lecture is always a good time to ask question.

Office Hours

Tentative Time: W,F 14:30-15:30 Check Google Calendar on the course website. Appointment can be made. Feel free to come to my office and chat! Don’t be shy. Office Hours: BKD, 6th floor of Sirindhralai building

49

Wednesday Friday

14:30-15:30 14:30-15:30

Grading System Coursework will be weighted as follows:

Assignments Class Discussion In-Class Exercises Midterm Examination

5% 5% 10% 35%

Final Examination (comprehensive)

45%

Late HW submission will be rejected. 50

Please Double-Check Exam Dates!

i Grading System

51

2013: CLASS GPA: 2.86

2014: CLASS GPA: 2.84

2016: CLASS GPA: 2.72

2017: CLASS GPA: 2.90

2015: CLASS GPA: 2.88

In-Class Exercises Most in-class exercises will occur without prior warning or

announcement.

Focus on the current topic under discussion.

Done in group to reduce pressure and provide opportunity for those who think they understand the course material to explain

to their friends and see whether they really know the material under consideration and for those who are falling behind to get an alternative explanation from their peers Note that you can’t be in exactly the same group every

time.

Have to change your group members every time. If you are with a friend before, then next time, form a group with

someone else.

52

i Class Discussion NOT the same as class attendance! If you come only to receive, you will fall asleep. Do not simply sit quietly in the class.

Need interaction between lecturer and students. Ask question when there is something that you don’t

understand. Don’t be shy! It is very likely that your friends don’t understand it as well.

If you already understand what I’m presenting, SHOW ME! Point out the errors/typos. I will raise many issues/questions in class. Try to comment on them. 53

Self-Evaluation Form Record what you have done. To be submitted right after the midterm and right after the final. ECS315: Self Evaluation 2018 (1)

54

Self-Evaluation Form: Example: Three times. On Aug 14, I played the Monty Hall game in class. I choose to “switch” but did not get the car. On Aug 21, I remind Dr.Prapun that the class time was already over. On Sep 13, Dr.Prapun worked on an example about intersection of sets. I raised my hand and answered “{3,4}” which was the correct answer.

Example: Twice.

55

On Aug 16, I sent an email to Dr.Prapun about a typo in the lecture note. On page 15, the note said 1+1 = 3. It should be 1+1=2. On Sep 14, In class, while we were working on page 24 of the lecture note, Dr.Prapun mistakenly wrote 55=30. It should be 56=30. I corrected him in class.

Self-Evaluation Form (Con’t) If you have legitimate reason for missing class on the day that

we have exercise, please indicate the date, exercise number, and the reason in the self-evaluation form. Make sure that you also submit/email supporting document/evidence to Dr.Prapun.

Example:

56

On Oct 18, we had Exercise 5 but I have to miss the class because I broke my leg and was hospitalized for two days. I have scanned the doctor's certificate and email it to Aj.Prapun on Oct 30.

Policy

Based on the clock on my computer. (This should be approx. the same as your phone’s and computer’s clocks if they are synchronized properly.)

We will start the class on time and will finish on time. I recommend arriving at least 3 minutes before the start time. Raise your hand and tell me immediately if I go over the time

limit. Does NOT mean that I will leave the room immediately after lecture. I will stay and answer questions.

Mobile phones must be turned off or set in silent mode. Attendance will be taken/given irregularly and randomly. Cheating will not be tolerated. Feel free to stop me when I talk too fast or too slow. 57

i

i Policy (con’t) I will surely make some mistakes in lectures / HW /

exams. Some amount of class participation scores will be reserved to

reward the first student who informs me about each of these mistakes. Grammatical errors are best informed/corrected after class.

Points on HW / exercises / exams are generally based on

your entire solution, not your final answer. You may get full credit even when you have the wrong final

answer. You may get zero even when you write down a right answer without justification. 58

Policy (con’t) Please stop me if I go over the time limit. Please stop me if I talk too fast. Please stop me if you have any question.

59

Warning This class is difficult. Keep up with the lectures. Make sure that you understand the concepts presented in the

lecture before you go home. I will evaluate your understanding of the course regularly

through In-class exercises/activities Exams

60

Difficulty in ECS315 Combinatorics (counting) Solving word problems Not the main focus of this class but unavoidable if you want to

solve/consider interesting questions

Calculus Can be messy

Concept of probability Most students do not learn probability until two or three

exposures to it.

Large number of definitions, formulas and equations No need to remember a lot of formulas if you understand them 61

Prerequisite Working knowledge of calculus Some MATLAB skills for doing HWs and understanding in-

class demo Frequency domain analysis (Fourier transform) Bell curve

Soon, we will need to find

62

1 2

e

x2 2

dx ?

1 x e 2 2

2

?

x

Remarks Get as much legitimate help as you can Participate actively in class and outside of class Record what you have done.

If you feel that the class is very easy, you might overlook

something. If you feel that the class is very difficult, you are probably not the only one who feel that way. Don’t give up. Chat with me. It takes me a long time to feel comfortable with these materials; yet, I

still make mistakes.

My notation can be different from the textbook. Every notation has some advantages and disadvantages. 63

Need More Examples or Practice? Textbook in the library: Schaum’s

outline of theory and problems of probability, random variables, and random processes / Hwei P. Hsu. Call No. QA273.25 H78 1997 Free pdf textbook: Introduction to Probability by Grinstead and Snell http://www.dartmouth.edu/~chance /teaching_aids/books_articles/proba bility_book/book.html 64

Easier References For those who feels that this course is difficult, here are some easier references.

More beautiful pictures. Less technical. Less applicable for content after the midterm. 65

Monty Hall Problem: a short revisit Assuming that our goal is to maximize our chances of winning the car, what decision should we make? Will you do better by

sticking with your first choice, or

by switching to the other remaining door? Make no difference?

66

Monty Hall Problem: vos Savant’s Answer

“You double your chances of winning by switching doors.”

67

[https://www.youtube.com/watch?v=OBpEFqjkPO8]

Monty Hall Problem: Controversy Approximately 10,000 readers, including nearly 1,000 with PhDs (many of them math

professors),

wrote to the magazine

claiming the published solution was wrong. “You blew it,” wrote a mathematician from George Mason

University. From Dickinson State University came this: “I am in shock that after being corrected by at least three mathematicians, you still do not see your mistake.” 68

[Mlodinow, 2008, p 42-45]

Controversy (2) From Georgetown: “How many irate mathematicians are

needed to change your mind?” And someone from the U.S. Army Research Institute remarked, “If all those Ph.D.s are wrong the country would be in serious trouble.” When told of this, Paul Erdős, one of the leading mathematicians of the 20th century, said, “That's impossible.” Then, when presented with a formal mathematical proof of the

correct answer, he still didn't believe it and grew angry. Only after a colleague arranged for a computer simulation in which Erdős watched hundreds of trials that came out 2-to-1 in favor of switching did Erdős concede that he was wrong. 69

Let’s learn some concepts so that we can analyze interesting examples!

70