CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "The revenge of the Birthday Paradox"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #649
Reading Topic #649
Akash Kumar
Member since Aug-24-07
Sep-21-07, 08:50 AM (EST)
Click to EMail Akash%20Kumar Click to send private message to Akash%20Kumar Click to view user profileClick to add this user to your buddy list  
"The revenge of the Birthday Paradox"
 
   I dont know whether the title i chose for this subject sounds right to you or not but i am absolutely convinced that it'sounds right to me.

The birthday paradox has returned. And that too with vengeance. Please keep up with me for this time my question is somewhat "lengthier" this time

In a recent book by keith ball, i read some beautifully wonderful demonstrations of many mathematical truths which i believe were never earlier published at a popular level. The book is called

"Strange Curves, Counting Rabbits, & Other Mathematical Explorations".


Now back to the problem.

The author discusses at length the strange feeling you feel after your first encounter. He proceeds by telling us to find the expectation of getting a match with k ppl when we assume that there are n days in an year.

(A match is simply a pair of persons sharing the same b'day)....

Let us assume that there are 100 persons for the time being i.e k=100
A paraphrase of what Ball says is given below

"There are several ways to calculate expected number of matches; the avg num of matches we would get if we kept taking groups of 100 & running the experiment.

One way is to calculate the chance of getting exactly one match P1, the chance of getting 2 matches P2, & so on and form tne sum

P1 + 2.P2 + 3.P3 + ---- + m.Pm <======== NOTE THIS

But obviously this process is going to earn lots of hate-mails.

An easier way is to notice that the chance that a particular pair of people share their b'day is 1/n..

Also num of possible pairs is K.(K-1)/2...So, expected number of matches is simply X = K.(K-1)/2n..

So far so good...Now the trouble starts.

For Ball writes

"Suppose n events occur with probabilities P1, P2, P3...Pn respectively and that these probabilities are rather small. Show that if the events are independent, then the chance that none of them happen is roughly e^(-k).. where k is expected number of happenings given by

K = (SUM i:= 1 to n) Pi" <========= NOTE THIS

...This is what i find troubling, for earlier Ball write that the expectation, X = P1 + 2.P2 + 3.P3 + ------ + m.Pm

And now he assetes that X = P1 + P2 + P3 + ---- + Pn..


Well, i understand that in the first equation we are interested in number of matches, m and in the next we talk of number of persons, n..

Also, i notice the Pi's in 2 equation stand for different things, but what i question is - how come these two seemingly different expressions point at the same value for expectation... (that the first one does is clear too...but i can't say the same for the second one..and certainly not for them both taken together)..


Thank You and Have a nice Day
-Akash Kumar

Einstein - You know, earlier my preference mathematics. Later on i changed it to physics

Pincare: And why is that?

Einstein: I could not tell important facts from non-important ones.

Poincare: Starne that you say so. But now that you mention it, earlier i cherished physics..Now i cherish mathematics.

Einstein: And why is that

Poincare: I could not tell what is true from what is not.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexbadmin
Charter Member
2080 posts
Sep-23-07, 09:26 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: The revenge of the Birthday Paradox"
In response to message #0
 
   >I dont know whether the title i chose for this subject
>sounds right to you or not but i am absolutely convinced
>that it'sounds right to me.
>
>The birthday paradox has returned. And that too with
>vengeance. Please keep up with me for this time my question
>is somewhat "lengthier" this time
>
>In a recent book by keith ball, i read some beautifully
>wonderful demonstrations of many mathematical truths which i
>believe were never earlier published at a popular level. The
>book is called
>
>"Strange Curves, Counting Rabbits, & Other Mathematical
>Explorations".
>
>
>Now back to the problem.
>
>The author discusses at length the strange feeling you feel
>after your first encounter. He proceeds by telling us to
>find the expectation of getting a match with k ppl when we
>assume that there are n days in an year.
>
>(A match is simply a pair of persons sharing the same
>b'day)....
>
>Let us assume that there are 100 persons for the time being
>i.e k=100
>A paraphrase of what Ball says is given below
>
>"There are several ways to calculate expected number of
>matches; the avg num of matches we would get if we kept
>taking groups of 100 & running the experiment.
>
>One way is to calculate the chance of getting exactly one
>match P1, the chance of getting 2 matches P2, & so on and
>form tne sum
>
>P1 + 2.P2 + 3.P3 + ---- + m.Pm <======== NOTE THIS
>
>But obviously this process is going to earn lots of
>hate-mails.
>
>An easier way is to notice that the chance that a particular
>pair of people share their b'day is 1/n..
>
>Also num of possible pairs is K.(K-1)/2...So, expected
>number of matches is simply X = K.(K-1)/2n..
>
>So far so good...Now the trouble starts.
>
>For Ball writes
>
>"Suppose n events occur with probabilities P1, P2, P3...Pn
>respectively and that these probabilities are rather small.
>Show that if the events are independent, then the chance
>that none of them happen is roughly e^(-k)..
>where k is expected number of happenings given by
>
>K = (SUM i:= 1 to n) Pi" <========= NOTE THIS
>
>...This is what i find troubling, for earlier Ball write
>that the expectation, X = P1 + 2.P2 + 3.P3 +
>------ + m.Pm
>
>And now he assetes that X = P1 + P2 + P3 + ---- + Pn..
>
>
>Well, i understand that in the first
>equation we are interested in number of matches, m and in
>the next we talk of number of persons, n..
>
>Also, i notice the Pi's in 2 equation stand for different
>things, but what i question is - how come these two
>seemingly different expressions point at the same value for
>expectation... (that the first one does is clear too...but i
>can't say the same for the second one..and certainly not for
>them both taken together)..

>
>

You appear to ask to contradictory questions: the first is

">...This is what i find troubling, for earlier Ball write
>that the expectation, X = P1 + 2.P2 + 3.P3 +
>------ + m.Pm
>
>And now he assetes that X = P1 + P2 + P3 + ---- + Pn.. "

to which you yourself give an answer

>Well, i understand that in the first
>equation we are interested in number of matches, m and in
>the next we talk of number of persons, n..

and the second is

>Also, i notice the Pi's in 2 equation stand for >different things, but what i question is - how come these two
>seemingly different expressions point at the same value for
>expectation... (that the first one does is clear too...but i
>can't say the same for the second one..and certainly not for
>them both taken together)..


which, at the beginning, provides in passing an answer to the first question.

I am sure you can find many instances where two different expressions have the same value: any non-trivial pair of expressions with the sign of equality in-between will do. Provided, of course, that the equality is valid. All I can add is that in the second derivation, viz.

">"Suppose n events occur with probabilities P1, P2, P3...Pn
>respectively and that these probabilities are rather small.
>Show that if the events are independent, then the chance
>that none of them happen is roughly e^(-k)..
>where k is expected number of happenings given by
>
>K = (SUM i:= 1 to n) Pi" <========= NOTE THIS "

the fellow looks for the product

(1 - P1)(1 - P2)...(1- Pn)

which is approximately

1 - (P1 + P2 ... + Pn) ≈ 1 - k ≈ e-k,

assuming of course k is still reasonably small.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK