Leonard Mlodinow 16 Euclid’s Window: the Story of Geometry from Parallel Lines to Hyperspace Feynman’s Rainbow: a Search for Beauty in Physics and in ...

0 downloads 24 Views 7MB Size

Dr. Prapun Suksompong [email protected]

Introduction Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 2

Course Organization Course Website:

http://www2.siit.tu.ac.th/prapun/ecs315/ Lectures: Tuesday 13:00-14:20 Thursday 10:40-12:00

BKD 3206 BKD 3206

Tutorial/make-up sessions: Monday 10:40-12:00 BKD 3206

Textbook: Probability and stochastic processes: a friendly introduction for

electrical and computer engineers

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: 4

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

Probability 10

“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)

11

“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)

12

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

devoted to analyzing problems of chance.

13

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 If it has the word “measure” or “ergodic” in there, it is probably too advanced. 14

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

15

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.

16

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

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

17

Examples Prelude to the Theory of Probability

18

Game 1: Seven Card Hustle 19

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 20

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.

21

[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

1 5 4 3 765 2 7 22

[Lovell, 2006]

Game 2: Monty Hall Problem 23

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.

24

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

25

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

26

[ http://www.marilynvossavant.com ]

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

27

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.

28

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.

29

“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.

30

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.

31

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?

32

Let’s play! 33

Interactive Monty Hall

34

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

Interactive Monty Hall The New York Times’s Version

http://www.nytimes.com/2008/04/08/science/08monty.html 35

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 50

Monty Hall Problem: a first 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?

51

Monty Hall Problem: vos Savant’s Answer

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

52

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.” 53

[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. 54

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

55

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

1 Probability and You Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 1

Life is random

2

In 2005, this fact

Life is random

3

showed up all over the world…

Life is random

4

Applications of Probability Theory The subject of probability can be traced back to the 17th

century when it arose out of the study of gambling games.

The range of applications extends beyond games into business

decisions, insurance, law, medical tests, and the social sciences. The stock market, “the largest casino in the world,” cannot do without it. The telephone network, call centers, and airline companies with their randomly fluctuating loads could not have been economically designed without probability theory. 5

“The Perfect Thing”

6

“The Perfect Thing”

7

Perfect?!...

8

What about the shuffle function?

http://ipod.about.com/od/advanceditunesuse/a/itunes-random.htm

http://www.cnet.com.au/itunes-just-how-random-is-random-339274094.htm

9

http://electronics.howstuffworks.com/ipod-shuffle2.htm

How to Interpret a Probability Many think that probabilities do not exist in real life. Nevertheless, a given or a computed value of the probability

of some event A can be used in order to make conscious decisions. Long-run frequency interpretation. If the probability of an event A in some actual physical

experiment is p, then we believe that if the experiment is repeated independently over and over again, then in the long run the event A will happen 100p% of the time.

10

Frequency Interpretation and LLN These assumptions are motivated by the frequency

interpretation of probability. If we repeat an experiment a large number of times then the

fraction of times the event A occurs will be close to P(A). If we let N(A, n) be the number of times A occurs in the first n trials then P A lim

n

N A, n n

Later on, this result will be a theorem called the law of

large numbers (LLN). 11

USA Currency Coins Penny = 1 cent

(Abraham Lincoln)

Nickel = 5 cents

(Thomas Jefferson)

12

Dime = 10 cents

(Franklin D. Roosevelt)

Quarter = 25 cents

(George Washington)

Coin Tossing: Relative Frequency N A, n n

1

1

0.8

0.8 0.6

0.6

0.4

0.4

0.2

If a fair coin is 0 flipped a large 2 4 6 n 1, 2, ,10 number of times, 1 the proportion of 0.8 heads will tend to 0.6 get closer to 1/2 as 0.4 the number of 0.2 tosses increases. 0 200

13

n 1, 2,

400

600

,1000

0.2 8

10

0

20

40

2

4

n 1, 2,

60

80

100

6

8

10

,100

1 0.8 0.6 0.4 0.2 800 1000

0

n 1, 2,

,10

6

5

x 10

Intersting behavior The difference between #H and #T will not be close to 0. 2500

2000

1500

1000

500

0

-500

1

2

3

4

5

6

7

8

9

10 5

x 10

14

Another trial 1

1

1000

0.8

0.8

800

0.6

0.6

0.4

0.4

0.2

600

0.2 400

0 2

4

6

8

10

0

20

40

60

80

100 200

1

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

0

200

400

600

800 1000

0

-200 -400

2

4

6

8

10 5

x 10

15

-600

1

2

3

4

5

6

7

8

9

10 5

x 10

Another trial 1

1

300

0.8

0.8

200

0.6

0.6

0.4

0.4

100

0.2

0

0.2 0 2

4

6

8

10

0

1

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

20

40

60

80

100 -100 -200 -300 -400

0

200

400

600

800 1000

0

-500

2

4

6

8

10 5

x 10

16

-600

1

2

3

4

5

6

7

8

9

10 5

x 10

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

2 Review of Set Theory Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 1

Venn diagram

2

Venn diagram: Examples

3

Partitions

4

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

3 Classical Probability Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 1

Real coins are biased From a group of Stanford researchers

2

http://gajitz.com/up-in-the-air-coin-tosses-not-as-neutral-as-you-think/ http://www.codingthewheel.com/archives/the-coin-flip-a-fundamentally-unfair-proposition http://www-stat.stanford.edu/~susan/papers/headswithJ.pdf

Example In drawing a card from a deck, there are 52 equally likely

outcomes, 13 of which are diamonds. This leads to a probability of 13/52 or 1/4.

3

The word “dice” Historically, dice is the plural of die. In modern standard English, dice is used as both the

singular and the plural.

4

Example of 19th Century bone dice

“Advanced” dice

5

[ http://gmdice.com/ ]

Dice Simulator http://www.dicesimulator.com/ Support up to 6 dice and also has some background

information on dice and random numbers.

6

Two Dice

7

Two-Dice Statistics

8

Two-Dice Statistics

9

Two Dice A pair of dice

10

Double six

Two dice: Simulation

[ http://www2.whidbey.net/ohmsmath/webwork/javascript/dice2rol.htm ]

11

Two dice Assume that the two dice are fair and independent. P[sum of the two dice = 5] = 4/36

12

Two dice Assume that the two dice are fair and independent.

13

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

4 Combinatorics Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 1

Heads, Bodies and Legs flip-book

2

Heads, Bodies and Legs flip-book (2)

3

One Hundred Thousand Billion Poems Cent mille milliards de poèmes

4

One Hundred Thousand Billion Poems (2)

5

[Greenes, 1977]

Example: Sock It Two Me

Jack is so busy that he's always throwing his socks into his top

drawer without pairing them. One morning Jack oversleeps. In his haste to get ready for school, (and still a bit sleepy), he reaches into his drawer and pulls out 2 socks. Jack knows that 4 blue socks, 3 green socks, and 2 tan socks are in his drawer. 1. What are Jack's chances that he pulls out 2 blue socks to match his blue slacks? 2. What are the chances that he pulls out a pair of matching socks? 6

“Origin” of Probability Theory Probability theory was originally inspired by gambling

7

problems. [http://www.youtube.com/watch?v=MrVD4q1m1 In 1654, Chevalier de Mere Vo] invented a gambling system which bet even money on case B on the previous slide. When he began losing money, he asked his mathematician friend Blaise Pascal to analyze his gambling system. Pascal discovered that the Chevalier's system would lose about 51 percent of the time. Pascal became so interested in probability and together with another famous mathematician, Pierre de Fermat, they laid the foundation of probability theory. best known for Fermat's Last Theorem

Example: 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 them can’t turn over three red cards. The probability that they CAN do it is

5 3 5 4 3 2 7 3 7 6 5 7

8

5 3 2 5! 3! 4! 5 4 3 1 765 7 7 3! 2! 7! 3

[Lovell, 2006]

Finger-Smudge on Touch-Screen Devices Fingers’ oily smear on the

screen Different apps gives different finger-smudges. Latent smudges may be usable to infer recently and frequently touched areas of the screen--a form of information leakage. [http://www.ijsmblog.com/2011/02/ipad-finger-smudge-art.html] 9

Lockscreen PIN / Passcode

10

[http://lifehacker.com/5813533/why-you-should-repeat-one-digit-in-your-phones-4+digit-lockscreen-pin]

Smudge Attack Touchscreen smudge may give away your password/passcode Four distinct fingerprints reveals the four numbers used for

passcode lock.

11

[http://www.engadget.com/2010/08/16/shocker-touchscreen-smudge-may-give-away-your-android-password/2]

Suggestion: Repeat One Digit Unknown numbers: The number of 4-digit different passcodes = 104

Exactly four different numbers: The number of 4-digit different passcodes = 4! = 24

Exactly three different numbers:

The number of 4-digit different passcodes = 3 4 2 36

Choose the number that will be repeated 12

Choose the locations of the two nonrepeated numbers.

News: Most Common Lockscreen PINs Passcodes of users of Big Brother Camera Security iPhone

app 15% of all passcode sets were represented by only 10 different passcodes

13

out of 204,508 recorded passcodes [http://amitay.us/blog/files/most_common_iphone_passcodes.php (2011)]

Even easier in Splinter Cell Decipher the keypad's code by the heat left on the buttons. Here's the keypad viewed with your thermal

goggles. (Numbers added for emphasis.) Again, the stronger the signature, the more recent the keypress. The code is 1456.

14

Actual Research University of California San Diego The researchers have shown that codes can be easily discerned

from quite a distance (at least seven metres away) and imageanalysis software can automatically find the correct code in more than half of cases even one minute after the code has been entered. This figure rose to more than eighty percent if the thermal camera was used immediately after the code was entered.

K. Mowery, S. Meiklejohn, and S. Savage. 2011. “Heat of the Moment: Characterizing the Efficacy of Thermal-Camera Based Attacks”. Proceedings of WOOT 2011. http://cseweb.ucsd.edu/~kmowery/papers/thermal.pdf http://wordpress.mrreid.org/2011/08/27/hacking-pin-pads-usingthermal-vision/

15

The Birthday Problem (paradox) How many people do you need to assemble before the

probability is greater than 1/2 that some two of them have the same birthday (month and day)? Birthdays consist of a month and a day with no year attached. Ignore February 29 which only comes in leap years Assume that every day is as likely as any other to be someone’s

birthday In a group of r people, what is the probability that two or

more people have the same birthday?

16

Probability of birthday coincidence Probability that there is at least two people who have the

same birthday in a group of r persons if r 365 1, 365 364 365 r 1 , if 0 r 365 1 365·365· · 365 r terms

17

Probability of birthday coincidence

18

The Birthday Problem (con’t) With 88 people, the probability is greater than 1/2 of having

three people with the same birthday. 187 people gives a probability greater than1/2 of four people having the same birthday

19

Birthday Coincidence: 2nd Version How many people do you need to assemble before the

probability is greater than 1/2 that at least one of them have the same birthday (month and day) as you?

In a group of r people, what is the probability that at least one

of them have the same birthday (month and day) as you?

20

Binomial Theorem ( x1 y1 ) ( x2 y2 ) x1 x2 x1 y2 y1 x2 y1 y2 ( x1 y1 ) ( x2 y2 ) ( x3 y3 ) x1 x2 x3 x1 x2 y3 x1 y2 x3 x1 y2 y3 y1x2 x3 y1x2 y3 y1 y2 x3 y1 y2 y3 x1 x2 x3 x y1 y2 y3 y

( x y) ( x y) xx xy yx yy x 2 2 xy y 2

( x y) ( x y) ( x y) xxx xxy xyx xyy yxx yxy yyx yyy 21

x3 3x 2 y 3xy 2 y 3

Distinct Passcodes (revisit) Unknown numbers: The number of 4-digit different passcodes = 104

Exactly four different numbers: The number of 4-digit different passcodes = 4! = 24

Exactly three different numbers:

The number of 4-digit different passcodes = 3 4 2 36

Exactly two different numbers: The number of 4-digit different passcodes =

Exactly one number:

4 4 4 + + = 14 3 2 1

The number of 4-digit different passcodes = 1

Check: 10 10 10 10 ⋅ 24 + ⋅ 36 + ⋅ 14 + ⋅ 1 = 10,000 3 4 2 1 22

Need more practice?

[ http://en.wikipedia.org/wiki/Poker_probability ]

Ex: Poker Probability

23

Success Runs (1/4) Suppose that two people are separately asked to toss a fair

coin 120 times and take note of the results. Heads is noted as a “one” and tails as a “zero”. Results: Two lists of compiled zeros and ones:

24

[Tijms, 2007, p 192]

Success Runs (2/4) Which list is more likely?

25

[Tijms, 2007, p 192]

Success Runs (3/4) Fact: One of the two individuals has cheated and has

fabricated a list of numbers without having tossed the coin. Which list is more likely be the fabricated list?

26

[Tijms, 2007, p 192]

Success Runs (4/4) Fact: In 120 tosses of a fair coin, there is a very large probability

that at some point during the tossing process, a sequence of five or more heads or five or more tails will naturally occur. The probability of this is approximately 0.9865.

In contrast to the second list, the first list shows no such sequence

of five heads in a row or five tails in a row. In the first list, the longest sequence of either heads or tails consists of three in a row. In 120 tosses of a fair coin, the probability of the longest sequence consisting of three or less in a row is equal to 0.000053 which is extremely small . Thus, the first list is almost certainly a fake. Most people tend to avoid noting long sequences of consecutive heads or tails. Truly random sequences do not share this human tendency! 27

[Tijms, 2007, p 192]

Fun Books…

28

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

Events-Based Probability Theory Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 1

Probability and Random Processes ECS 315 Dr. Prapun Suksompong [email protected]

5 Foundation of Probability Theory Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 2

Axioms of probability theory Abstractly, a probability

measure is a function that

assigns numbers to events, which satisfies the following assumptions: 1. Nonnegativity: For any event A, P A 0 2. Unit normalization: P() 1 3. If A1, A2, . . . , is an infinite sequence of (pairwise) disjoint events, then P Ai P( Ai ) i 1 i 1

3

Kolmogorov Andrey Nikolaevich Kolmogorov Soviet Russian mathematician Advanced various scientific fields

probability theory topology classical mechanics computational complexity.

1922: Constructed a Fourier series that diverges almost

everywhere, gaining international recognition. 1933: Published the book, Foundations of the Theory of Probability, laying the modern axiomatic foundations of probability theory and establishing his reputation as the world's leading living expert in this field. 4

I learn probability theory from

Eugene Dynkin

Terrence Fine 5

Philip Protter

Xing Guo

Gennady Samorodnitsky

Toby Berger

Rick Durrett

Not too far from Kolmogorov

You can be the 4th-generation

probability theorists 6

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

Event-Based Properties

7

Daniel Kahneman Daniel Kahneman Israeli-American psychologist 2002 Nobel laureate In Economics

Hebrew University, Jerusalem, Israel.

Professor emeritus of psychology and public affairs at

Princeton University's Woodrow Wilson School. With Amos Tversky, Kahneman studied and clarified the kinds of misperceptions of randomness that fuel many of the common fallacies. 8

[outspoken = given to expressing yourself freely or insistently]

K&T: Q1 Imagine a woman named Linda, 31 years old, single, outspoken, and very bright. In college she majored in philosophy. While a student she was deeply concerned with discrimination and social justice and participated in antinuclear demonstrations.

K&T presented this description to a group of 88 subjects and

asked them to rank the eight statements (shown on the next slide) on a scale of 1 to 8 according to their probability, with 1 representing the most probable and 8 the least.

9

[Daniel Kahneman, Paul Slovic, and Amos Tversky, eds., Judgment under Uncertainty: Heuristics and Biases (Cambridge: Cambridge University Press, 1982), pp. 90–98.]

[feminist = of or relating to or advocating equal rights for women]

K&T: Q1 - Results Here are the results - from most to least probable

10

K&T: Q1 – Results (2) At first glance there may appear to be nothing unusual in

these results: the description was in fact designed to be representative of an active feminist and unrepresentative of a bank teller or an insurance salesperson.

Most probable

Least likely 11

K&T: Q1 – Results (3) Let’s focus on just three of the possibilities and their average

ranks. This is the order in which 85 percent of the respondents ranked the three possibilities:

If nothing about this looks strange, then K&T have fooled you 12

K&T: Q1 - Contradiction The probability that two events will both occur can never be greater than the probability that each will occur individually!

13

K&T: Q2 K&T were not surprised by the result because they had given

their subjects a large number of possibilities, and the connections among the three scenarios could easily have gotten lost in the shuffle. So they presented the description of Linda to another group, but this time they presented only three possibilities: Linda is active in the feminist movement. Linda is a bank teller and is active in the feminist movement. Linda is a bank teller.

14

K&T: Q2 - Results To their surprise, 87 percent of the subjects in this trial also

incorrectly ranked the probability that “Linda is a bank teller and is active in the feminist movement” higher than the probability that “Linda is a bank teller”.

If the details we are given fit

our mental picture of

something, then the more details in a scenario, the more real it seems and hence the more probable we consider it to be even though any act of adding less-than-certain details to a conjecture

makes the conjecture less probable.

Even highly trained doctors make this error when analyzing

symptoms.

91 percent of the doctors fall prey to the same bias.

15

[Amos Tversky and Daniel Kahneman, “Extensional versus Intuitive Reasoning: The Conjunction Fallacy in Probability Judgment,” Psychological Review 90, no. 4 (October 1983): 293–315.]

Related Topic Page 34-37 Tversky and Shafir @

Princeton University

16

K&T: Q3 Which is greater: the number of six-letter English words having “n” as their fifth letter

or the number of six-letter English words ending in “-ing”?

Most people choose the group of words ending in “ing”. Why? Because words ending in “-ing” are easier to think of than generic six letter words having “n” as their fifth letter. The group of six-letter words having “n” as their fifth letter words includes all six-letter words ending in “-ing”. Psychologists call this type of mistake the availability bias In reconstructing the past, we give unwarranted importance to

memories that are most vivid and hence most available for retrieval.

17

[Amos Tversky and Daniel Kahneman, “Availability: A Heuristic for Judging Frequency and Probability,” Cognitive Psychology 5 (1973): 207–32.]

Misuse of probability in law It is not uncommon for experts in DNA analysis to testify at a

criminal trial that a DNA sample taken from a crime scene matches that taken from a suspect. How certain are such matches? When DNA evidence was first introduced, a number of experts testified that false positives are impossible in DNA testing. Today DNA experts regularly testify that the odds of a random person’s matching the crime sample are less than 1 in 1 million or 1 in 1 billion. In Oklahoma a court sentenced a man named Timothy Durham to more than 3,100 years in prison even though eleven witnesses had placed him in another state at the time of the crime.

18 [Mlodinow, 2008, p 36-37]

Lab/Human Error There is another statistic that is often not presented to the

jury, one having to do with the fact that labs make errors, for instance, in collecting or handling a sample, by accidentally mixing or swapping samples, or by misinterpreting or incorrectly reporting results. Each of these errors is rare but not nearly as rare as a random match. The Philadelphia City Crime Laboratory admitted that it had swapped the reference sample of the defendant and the victim in a rape case A testing firm called Cellmark Diagnostics admitted a similar error. 19 [Mlodinow, 2008, p 36-37]

Timothy Durham’s case It turned out that in the initial analysis the lab had failed to

completely separate the DNA of the rapist and that of the victim in the fluid they tested, and the combination of the victim’s and the rapist’s DNA produced a positive result when compared with Durham’s. A later retest turned up the error, and Durham was released after spending nearly four years in prison.

20 [Mlodinow, 2008, p 36-37]

DNA-Match Error + Lab Error Estimates of the error rate due to human causes vary, but

many experts put it at around 1 percent. Most jurors assume that given the two types of error—the 1 in 1 billion accidental match and the 1 in 100 lab-error match—the overall error rate must be somewhere in between, say 1 in 500 million, which is still for most jurors beyond a reasonable doubt.

21 [Mlodinow, 2008, p 36-37]

Wait!… Even if the DNA match error was extremely accurate + Lab

error is very small, there is also another probability concept that should be taken into account. More about this later. Right now, back to notes for more properties of probability measure.

22

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

6.1 Conditional Probability Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 1

Example Roll a fair dice

Sneak peek:

2

3

Disease Testing Suppose we have a diagnostic test for a particular disease

4

which is 99% accurate. A person is picked at random and tested for the disease. The test gives a positive result. Q1: What is the probability that the person actually has the disease? Natural answer: 99% because the test gets it right 99% of the times.

99% accurate test? If you use this test on many persons with the disease, the

test will indicate correctly that those persons have disease 99% of the time. False negative rate = 1% = 0.01

If you use this test on many persons without the disease, the

test will indicate correctly that those persons do not have disease 99% of the time. False positive rate = 1% = 0.01

5

Disease Testing Suppose we have a diagnostic test for a particular disease

6

which is 99% accurate. A person is picked at random and tested for the disease. The test gives a positive result. Q1: What is the probability that the person actually has the disease? Natural answer: 99% because the test gets it right 99% of the times. Q2: Can the answer be 1% or 2%? Q3: Can the answer be 50%?

A1: Q1: What is the probability that the person actually has the disease?

The answer actually depends on how common or how rare the disease is!

7

Why? Let’s assume rare disease. The disease affects about 1 person in 10,000.

Try an experiment with 106 people. Approximately 100 people will have the disease. What would the (99%-accurate) test say?

8

106

people

Test

Results of the test approximately

99 of them will test positive 1 of them will test negative 100 people w/ disease

989,901 of them will test negative 9,999 of them will test positive 999,900 people w/o disease 9

Results of the test 99 of them will test positive 1 of them will test negative 100 people w/ disease Of those who test positive, only

99 1% 99 9,999

actually have the disease!

989,901 of them will test negative 9,999 of them will test positive 999,900 people w/o disease 10

Bayes’ Theorem Using the concept of conditional probability and Bayes’ Theorem, you can show that the probability that a person will have the disease given that the test is positive is given by (1 pTE ) pD (1 pTE ) pD pTE (1 pD ) where, in our example, pD = 10-4 pTE = 1 – 0.99 = 0.01 11

Bayes’ Theorem Using the concept of conditional probability and Bayes’ Theorem, you can show that the probability that a person will have the disease given that the test is positive is given by (1 pTE ) pD 1 (1 pTE ) pD pTE (1 pD ) When different value of pD is assumed,

1 12

pD

In log scale… 0

10

-1

10

-2

10

-3

10

-4

10

-5

10

-6

10

13

-5

10

-4

10

-3

10 d

pD

-2

10

-1

10

0

10

Effect of pTE pTE = 1 – 0.99 = 0.01

1 0.9

pTE = 1 – 0.9 = 0.1

0.8 0.7

0.6

pTE = 1 – 0.5 = 0.5

0.5 0.4 0.3 0.2 0.1 0

14

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Wrap-up Q1: What is the probability that the person actually has the

15

disease? A1: The answer actually depends on how common or how rare the disease is! (The answer depends on the value of d.) Q2: Can the answer be 1% or 2%? A2:Yes. Q3: Can the answer be 50%? A3:Yes.

Example: A Revisit Roll a fair dice

Sneak peek:

16

Prosecutor’s fallacy Murder case “one of the biggest media events of 1994–95” “the most publicized criminal trial in American history”

O. J. Simpson At the time a well-known celebrity famous

both as a TV actor and as a retired professional football star. Defense lawyer: Alan Dershowitz Renowned attorney and Harvard Law

School professor 17

[Mlodinow, 2008, p. 119-121],[Tijms, 1007, Ex 8.7]

The murder of Nicole Nicole Brown was murdered at her home

in Los Angeles on the night of June 12, 1994. So was her friend Ronald Goldman.

The prime suspect was her (ex-)

husband O.J. Simpson. (They were divorced in 1992.)

18

Prosecutor* = a government official who conducts criminal prosecutions on behalf of the state

Prosecutors’ argument Prosecutors* spent the first ten days of the trial entering

evidence of Simpson’s history of physically abusing her and claimed that this alone was a good reason to suspect him of her murder. As they put it, “a slap is a prelude to homicide.”

19

prosecution = the lawyers acting for the state to put the case against the defendant batter = strike violently and repeatedly

Counterargument The defense attorneys argued that the prosecution* had

spent two weeks trying to mislead the jury and that the evidence that O. J. had battered Nicole on previous occasions meant nothing. Dershowitz’s reasoning: 4 million women are battered annually by husbands and

boyfriends in the US. In 1992, a total of 1,432, or 1 in 2,500, were killed by their (ex)husbands or boyfriends. Therefore, few men who slap or beat their domestic partners go on to murder them. True? Yes. 20

Convincing? Yes.

The verdict:

Not guilty for the two murders!

21

The verdict was seen live on TV by more than half of the U.S. population, making it one of the most watched events in American TV history.

Another number… It is important to make use of the crucial fact that Nicole Brown

was murdered. The relevant number is not the probability that a man who batters his wife will go on to kill her (1 in 2,500) but rather the probability that a battered wife who was murdered was murdered by her abuser. According to the Uniform Crime Reports for the United States and Its Possessions in 1993, the probability Dershowitz (or the prosecution) should have reported was this one: of all the battered women murdered in the United States in 1993, some 90 percent were killed by their abuser. That statistic was not mentioned at the trial. 22

A Simplified Diagram Physically abused by husband

Murdered by husband Murdered 23

Probability Comparison Physically abused by husband

1 in 2,500

Murdered by husband Murdered Physically abused by husband

90%

Murdered by husband Murdered

24

The Whole Truth … Dershowitz may have felt justified in misleading the jury

because, in his words, “the courtroom oath—‘to tell the truth, the whole truth and nothing but the truth’—is applicable only to witnesses.

Defense attorneys, prosecutors, and judges don’t take this

oath . . . indeed, it is fair to say the American justice system is built on a foundation of not telling the whole truth.” 25

Ex. Fair results from a biased coin A biased coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure: 1. Toss the coin twice. 2. If the results match, start over, forgetting both results. 3. If the results differ, use the first result, forgetting the second. Key idea: The probability of getting heads and then tails must be the same as the

probability of getting tails and then heads,

Assumptions: the coin is not changing its bias between flips and the two flips are

independent.

By excluding the events of two heads and two tails by repeating the procedure,

the coin flipper is left with the only two remaining outcomes having equivalent probability.

This procedure only works if the tosses are paired properly; if part of a pair is

reused in another pair, the fairness may be ruined.

26

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

6.2 Independence Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 1

Example: Club & Black

clubs diamonds

hearts

spades

2

Example: Black & King

clubs diamonds

hearts

spades

3

Sally Clark

[http://www.sallyclark.org.uk/] [http://en.wikipedia.org/wiki/Sally_Clark] [http://www.timesonline.co.uk/tol/comment/obituaries/article1533755.ece] 4

Sally Clark Falsely accused of the murder

sons.

of her two

Clark's first son died suddenly within a few

weeks of his birth in 1996. After her second son died in a similar manner, she was arrested in 1998 and tried for the murder of both sons. The case went to appeal, but the convictions

and sentences were confirmed in 2000. Released in 2003 by Court of Appeal Wrongfully imprisoned for more than 3 years Never fully recovered from the effects of this appalling miscarriage of justice. 5

Misuse of statistics in the courts Her prosecution was controversial due to statistical

evidence This evidence was presented by a

2

1 8 10 8500

medical expert witness Professor Sir Roy Meadow, Meadow testified that the frequency of sudden infant death syndrome (SIDS, or “cot death”) in families having some of the characteristics of the defendant’s family is 1 in 8500.

He went on to square this figure to obtain a value of 1 in

6

73 million for the frequency of two cases of SIDS in such a family.

Royal Statistical Society “This approach is, in general, statistically invalid.” “It would only be valid if SIDS cases arose independently

within families, an assumption that would need to be justified empirically. “ “There are very strong a priori reasons for supposing that the assumption will be false.” “There may well be unknown genetic or environmental factors that predispose families to SIDS, so that a second case within the family becomes much more likely.” [http://www.rss.org.uk] 7

Aftermath Clark's release in January 2003 prompted the Attorney

General to order a review of hundreds of other cases. Two other women convicted of murdering their children had their convictions overturned and were released from prison. Trupti Patel, who was also accused of murdering her three children, was acquitted in June 2003. In each case, Roy Meadow had testified about the unlikelihood of multiple cot deaths in a single family.

8

How Juries Are Fooled by Statistics By Peter Donnelly

Professor of Statistical Science (Dept Statistics) at University of Oxford

@ 11:15-13:50 Disease Testing @ 13:50-18:30 Sally Clark

9

http://www.youtube.com/watch?v=kLmzxmRcUTo http://www.stats.ox.ac.uk/people/academic_staff/peter_donnelly

Prosecutor’s Fallacy Aside from its invalidity, figures such as the 1 in 73 million are

10

very easily misinterpreted. Some press reports at the time stated that this was the chance that the deaths of Sally Clark's two children were accidental. This (mis-)interpretation is a serious error of logic known as the Prosecutor's Fallacy. The jury needs to weigh up two competing explanations for the babies' deaths: 1) SIDS or 2) murder. Two deaths by SIDS or two murders are each quite unlikely, but one has apparently happened in this case. What matters is the relative likelihood of the deaths under each explanation, not just how unlikely they are under one explanation (in this case SIDS, according to the evidence as presented).

Independence among three events Can be checked via 23-3-1 = 4 conditions:

Independence

𝑃 𝐴∩𝐵 𝑃 𝐴∩𝐶 𝑃 𝐵∩𝐶 𝑃 𝐴∩𝐵∩𝐶

=𝑃 𝐴 𝑃 𝐵 Pairwise independence =𝑃 𝐴 𝑃 𝐶 =𝑃 𝐵 𝑃 𝐶 =𝑃 𝐴 𝑃 𝐵 𝑃 𝐶

Remarks: Pairwise independence among the three events is defined by the first three conditions 11

Independence among four events Can be checked via 24-4-1 = 11 conditions:

𝑃 𝑃 𝑃 𝑃 𝑃 𝑃

𝐴∩𝐵 𝐴∩𝐶 𝐴∩𝐷 𝐵∩𝐶 𝐵∩𝐷 𝐶∩𝐷

=𝑃 =𝑃 =𝑃 =𝑃 =𝑃 =𝑃

𝐴 𝐴 𝐴 𝐵 𝐵 𝐶

𝑃 𝑃 𝑃 𝑃 𝑃 𝑃

𝐵 𝐶 𝐷 𝐶 𝐷 𝐷

Pairwise independence requires only these six conditions

12

𝑃 𝐵∩𝐶∩𝐷 𝑃 𝐴∩𝐶∩𝐷 𝑃 𝐴∩𝐵∩𝐷 𝑃 𝐴∩𝐵∩𝐶 𝑃 𝐴∩𝐵∩𝐶∩𝐷

=𝑃 𝐵 𝑃 𝐶 𝑃 𝐷 =𝑃 𝐴 𝑃 𝐶 𝑃 𝐷 =𝑃 𝐴 𝑃 𝐵 𝑃 𝐷 =𝑃 𝐴 𝑃 𝐵 𝑃 𝐶 =𝑃 𝐴 𝑃 𝐵 𝑃 𝐶 𝑃 𝐷

Probability and Random Processes ECS 315

Dr. Prapun Suksompong [email protected]

6.3 Bernoulli Trials Office Hours: BKD 3601-7 Monday 14:40-16:00 Friday 14:00-16:00 13

n Bernoulli trials Assume success probability = 1/n 1 0.9 0.8

P #successes 1

0.7

1 1 0.6321 e

0.6

P #successes 1

0.5 0.4

P #successes 0

0.3 0.2

16

P #successes 2

1 0.1839 2e

P #successes 3

0.1 0

1 0.3679 e

0

5

10

15

20

25 n

30

35

40

45

50

Error Control Coding Repetition Code at Tx: Repeat the bit n times. Channel: Binary Symmetric Channel (BSC) with bit error

probability p. Majority Vote at Rx 0.5 0.45 0.4 0.35

P

0.3

n=1 n=5

0.25 0.2

n = 15

0.15 0.1

n = 25

0.05

14

0

0

0.05

0.1

0.15

0.2

0.25

p

0.3

0.35

0.4

0.45

0.5