Expert: Josh - 11/4/2003

Question
Fifty ping-pong balls, each marked with a different counting number from 1 to 50, are placed in a bag.  One by one, fifteen students remove a ball from the bag, announce its number, then return the ball to the bag, at which time the next student takes his or her turn.  What is the probability that at least two students will pick the same ball?  Round the answer to the nearest tenth of a percent.

Answer
regarding your comments -"You totally confused me.. is the answer 3.5 percent.. because i did it a different way that i think makes more sense.. but im not sure if its correct (gina on 11/5/03 4:26:26 PM)"

I am sorry that you got frustrated. I think you probably got lost in the notations, because you are not used to writing mathematics with such rigor. But I can assure you that this is a good way of setting up and understanding the problem. You are right, this stuff can probably be explained more easily verbally. In writing, it is sometimes difficult to follow.

What you should remember is not a numerical recipe for getting the right answer, you should instead take pride in KNOWING HOW to get the right answer and learn the techniques that you could use to solve future problems. If you already know a good way of solving the problem, share it with us. If you do not require lengthy explanation, please say so and explain what you are looking for. It would save me so much typing.

The key point that I tried to emphasize (and you will see this over and over again) is that IN GENERAL,

The total probability of seeing "a" lots of "x" and "N-a" lots of "non-x"

EQUALS

C(N,a), the number of ways of seeing an occurrence of "a" lots of "x" and "N-a" lots of "non-x"

WEIGHTED BY

P(a "x" & N-a "notX"), the probability of seeing a single occurrence of "a" lots of "x" and "N-a" lots of "non-x".

SOLUTION:
SUM C(N,a)* P(a "x" & N-a "notX") over all possible a values
=SUM N!/[a!(N-a)!]} * {(p^a)*(1-p)^(N-a)}

Bear in mind, in this example, a={2,3,...15}, "x" represents any number between 1 & 50 and N=15.

I have computed the solution using the following script.
==============================
ans=0; N=15; p=1/50;
for a=2:N
 %we compute the factorials f1=N!, f2=a!, f3=(N-a)!
 f1=1;f2=1;f3=1;
 for i=1:N
  f1=f1*i;
 end
 for i=1:a
  f2=f2*i;
 end
 for i=1:N-a
  f3=f3*i;
 end
 %accumulate P(a "x" & (N-a) "notX") for various "a" value
 ans=ans+(f1/(f2*f3))*((p^a)*(1-p)^(N-a))
end
==============================
I can confirm that the answer is 3.533831491213%. The dominant terms involve a=2,3,4. For larger values of "a", the additional terms make very little difference to the answer, because they are very improbable (i.e., (1/50) raised to high powers is negligible). Nonetheless, they should be included for correctness.

You don't have to do it my way, but other methods that you consider are based on the same principle. As long as it makes sense to you, it's all good!


Hello Gina,

Since each ball is replaced in the bag after it has been drawn and each event (a number in the range 1-50 being selected) is equally probable, the problem at hand involves nothing more than a binomial expansion.

To see this, observe that the probability of a certain number "x" being drawn, by student number "n" remains constant throughout. We write P(X[n]=x) to represent this.
In fact, P(X[n]=x)=1/50 for n={1,2,3,...N}, where N=15.

Since the order of appearance does not matter, we are only interested in the number of combinations with
- "a" lots of "x" and "N-a" lots of "non-x".

In this problem, we are interested in two or more occurrences of "x" amongst N=15 ping-pongs. So, "a">=2.

PART ONE
========
Start by considering number of combinations, C(N,a) , with "a" lots of "x" and "N-a" lots of "non-x". Here, "a" can be any integer in the range [2,15] inclusive.

In general, we have C(N,a)=N!/[a!*(N-a)!] ways of selecting such combinations. ...[#Result1]

Where factorial N!=N*(N-1)*(N-2)*(N-3)*...*2*1. For instance, 8!=8*7*6*5*4*3*2*1.

------------------------------------------------------
ASIDE: As motivation, to convince you of this fact, we shall do a little experiment. Pick some smaller numbers for illustrative purpose. Let's say, that we had N=6 and a=2.
We seek all possible arrangements of {"x","x","-","-","-","-"}, where "-" denotes "non-x".
Writing this out, we have
----xx
---x-x
---xx-
--x--x
--x-x-
--xx--
-x---x
-x--x-
-x-x--
-xx---
x----x
x---x-
x--x--
x-x---
xx----
counting these, you'll find that it matches N!/[a!*(N-a)!]=6!/[2!*(6-2)!]=6!/[2!4!]=6*5/[2*1]=15 exactly.
------------------------------------------------------
PART TWO
========
Now, consider the chances of seeing any combination of "a" lots of "x" and "N-a" lots of "non-x".
Let P(X[n]=x) be the probability of student "n" picking a "x". In fact we can simplify the notation and use P(X=x) to denote the probability that any of the 15 students pick up an "x". We can do this because the probability remains the same throughout, it is said to be "time-invariant". It is 1/50 regardless of who picks it.

As usual, we assume that the selection process is independent. Loosely speaking, seeing the outcome of a selection has no bearing on the outcome of the next person's pick. Consequently, we can multiply the individual probabilities together to determine the probability of joint (or composite) events.

All that matters is that we have "a" lots of x's and "N-a" lots of non-x's. To keep the algebra simple, let P(X=x)=p.
Then, we have probability of seeing "a" lots of "x" and "N-a" lots of "non-x",
P("a"*"x" & "N-a"*"non-x")=(p^a)*(1-p)^(N-a) ...[#Result2]
==========================================================

Putting together result 1 & 2 (from above), for each value of "a" in {2,3,4,5,6,7,8,9,10,11,12,13,14,15}
The total probability of seeing "a" lots of "x" and "N-a" lots of "non-x" EQUALS the number of ways of seeing an occurrence of "a" lots of "x" and "N-a" lots of "non-x" WEIGHTED BY the probability of seeing a single occurrence of "a" lots of "x" and "N-a" lots of "non-x".

Mathematically, this is equivalent to

C(N,a)*P("a"*"x" & "N-a"*"non-x")
={N!/[a!(N-a)!]} * {(p^a)*(1-p)^(N-a)} ...[Result3]

Don't forget, this is valid for a particular "a" value.

We want to sum this over all "a" from 2 to 15.

So the answer to your question is
SUM C(N,a)*P("a"*"x" & "N-a"*"non-x"); a=2,3,..,15

You can use your calculator to work this out yourself.
You should realize that C(N,a) are exactly the same as the
binomial coefficients in the binomial expansion of (y+z)^N=
C(N,0)*z^N+C(N,1)*y*z^(N-1)+C(N,2)*(y^2)*z^(N-2)+C(N,3)*(y^3)*z^(N-3)+...+C(N,N-1)*y^(N-1)*z+C(N,N)*(y^N)
And for N odd, there are N+1 terms.
The coefficients are symmetrical, i.e., C(N,0)=C(N,N), C(N,1)=C(N,N-1) etc.