Math Is Fun Forum

samuel12

Guest

probability

Hi just need help with this probability question, pretty stuck at the moment.

Suppose there are k people each of whom randomly chooses one object from a set of n objects. We assume that the choices are independent of each other.

a(i) show that if

k>= (1+sqrt(1+8*n*ln2))/2

then the probability that at least two people choose the same object is at least 1/2.

Thanks in advance for the help=)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi samuel12;

That formula is only an approximation. It is similar to:

If you plug in n = 365 into your top formula you will get an answer that will give you a clue as to what type of problem you are dealing with. In any case it is an asymptotic form and will not be simple to derive and prove.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Guest

Re: probability

Hi Bobbym thanks for the response. So in your opinion do you think it will be acceptable to derive this result from the birthday attack, this is after all a cryptography course. Or is there a more general way of getting the approximation?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi samuel12;

That derivation is for the Birthday problem. The method Halmos uses is the simplest way. See the Wiki page for more explanation. They are probably interested in the hash collisions aspect of the Birthday problem but it doesn't matter. The derivation is the same.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Guest

Re: probability

cheers bobby, got it now . No doubt there will be more challenging parts of this question to come, if i get stuck i will post on this forum.

thanks for your help.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi samuel12;

Glad to help. Bring the problems here.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Guest

Re: probability

Hi again, this is the next part of the question (for the 400 level students btw)

*(ii) deduce that if n>= 500 and k>=1.2*sqrt(n) then the probability that at least two people choose the same object is at least 1/2.

I'll go off now and see what i can find, but if you have anything intelligent to say about this, then please feel free to share!!

cheers in advance=)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi samuel12;

Derive that from this:

Recall the asymptotic formula which gives the number of people n for k days with a probability >= 1/2 that 2 or more choose the same object or share the same birthday.

Solve for k days:

Substitute for k days = 1.2 √n

Solve for n people, you get 2 answers:

n = 0, n = 2.13777 Disregard n = 0.

The number of people n so that the probability  that 2 or more choose the same object or share the same birthday.when k = 1.2 √n is 2.13 people. Round down to 2 which is what you wanted to derive.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Guest

Re: probability

Wow very nice bobby. It seems so simple and logcial when you are given the solution.... I was going around in circles.

thanks once again bobby=)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi samuel12;

Don't mention it. Welcome to the forum!

It seems so simple and logcial when you are given the solution.... I was going around in circles.

Why not become a member?

I am glad that you appreciate the fact that their are forums like this today. When I was learning we only had a beach and some pebbles to do math with. When you got stuck or ran out of pebbles it took decades to figure it out. Some of us were eaten by sharks, which was particularly unfair.

Anyway, it was fun to work on your problem, especially without the sharks!

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Guest

Re: probability

Hi again, this is the last part to the question,

(b)(i) show that if k=70 and n=10000 then the probability that at least two people choose the same object is at least 1/5

(ii) Now suppose that 70 people each choose a 4-digit PIN (so that there are 10000 possible choices). Do you think that in real life the choice of PINs is truly random? Does this make the probability that at least two people choose the same PIN higher or lower than your answer from (b)

thanks in advance and its good you enjoy these types of questions bobbym, I'm sure there will be a few more to come=)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi samuel12;

Now suppose that 70 people each choose a 4-digit PIN (so that there are 10000 possible choices). Do you think that in real life the choice of PINs is truly random? Does this make the probability that at least two people choose the same PIN higher or lower than your answer from

This question is nonsensical. Whether or not the choice of pins is random depends on the method that you use to choose the pins, it has nothing to do with the magnitudes of n and k. Of course the probabilty of a collision when stuffing 10000 people into 70 days is higher than when stuffing 70 people into 10000 days.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Guest

Re: probability

Better is to notice that you are trying to stuff 10000 people into 70 days. The probability of a collision by the Dirichlet drawer principle of that happening is 1, which is at least 1/5.

Umm isnt it the other way around, in the original question is says '' k people '' and '' n objects '' sorry if i misunderstood what you were trying to say

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi samuel12;

The formulas, we have been looking at are: n people in k days. Or n objects being stuffed into k bins. That's how the formulas word it. This is the standard that I have followed from the books and wikipedia. It doesn't change the derivations as long as you put the right things into n and k.

The answer for ii in post# 11 remains the same but (b)(i) in post # 11 does change, do you want me to recompute?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Member

Registered: 2010-07-17

Posts: 19

Re: probability

Umm yes please that would be great if you dont mind

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi;

I have changed post #12!

(b)(i) show that if k=70 and n=10000 then the probability that at least two people choose the same object is at least 1/5

I will cast the problem in terms of p people and d days or objects.

For (b)(i) of post #11

You can use the exact formula with p for people and d days:

Putting in 70 people in 10000 days you get P(collision) = .21499 which is greater than 1/5

Or the approximate one:

p = 70 and d =10000 you get .21455 again greater than 1/5

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

samuel12

Member

Registered: 2010-07-17

Posts: 19

Re: probability

ok thanks so much bobbym that helped lots

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: probability

Hi Samuel12;

Just remember the notational differences in the formulas, k is n and n is k. It is like someone calling the x axis y and the y axis x. He would get an equation like x = 2y^2 + 3y + 5. A little bit confusing.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.