Register to reply

Simple, yet tough urn problem

by JolleJ
Tags: simple, tough
Share this thread:
JolleJ
#1
Mar5-12, 05:22 AM
P: 35
You have k urns and M (M>k) balls.

Each ball is placed in a random urn (w/ uniform distrubution).

What is the probability that every urn has at least one ball in it after the M balls are placed?
Phys.Org News Partner Science news on Phys.org
'Office life' of bacteria may be their weak spot
Lunar explorers will walk at higher speeds than thought
Philips introduces BlueTouch, PulseRelief control for pain relief
M Quack
#2
Mar5-12, 05:50 AM
P: 673
What is the probability that a given urn will receive no balls?
kai_sikorski
#3
Mar5-12, 06:07 AM
PF Gold
kai_sikorski's Avatar
P: 162
Quote Quote by M Quack View Post
What is the probability that a given urn will receive no balls?
That's not really the right approach because the urns are not independent and the OP is asking a question not about a given urn but about ALL the urns.

kai_sikorski
#4
Mar5-12, 06:19 AM
PF Gold
kai_sikorski's Avatar
P: 162
Simple, yet tough urn problem

Let pi(n) be the probability to have i empty urns at time n.

pi(n+1) = pi(n)(k-i)/k + pi+1(n)(i+1)/k

The initial condition is

pi(1) = δk-1

Seems like you have to solve this recurrence.
kai_sikorski
#5
Mar5-12, 06:27 AM
PF Gold
kai_sikorski's Avatar
P: 162
EDIT: Err this was wrong
kai_sikorski
#6
Mar5-12, 07:05 AM
PF Gold
kai_sikorski's Avatar
P: 162
Maybe this will work better

p0(M) = 1 - p1(M) - p2(M) - ... - pk-1(M)
= 1 - (k-M)((k choose 1) * (k-1)M + ( k choose 2) * (k-2)M + ... +(k choose k-1)1M)
M Quack
#7
Mar5-12, 07:38 AM
P: 673
I know, I know, that was not supposed to be the complete answer. But you can build up from there. Following my route I get

[itex] \sum\limits_{n=1}^{k-1} (-1)^{n+1} \left(1-\frac{n}{k}\right)^M \left(\begin{array}{c}k\\n\end{array}\right)[/itex]

Kai, what do you get?
kai_sikorski
#8
Mar5-12, 07:49 AM
PF Gold
kai_sikorski's Avatar
P: 162
I got

[tex] 1 - \sum_{i=1}^{k-1} \left(
\begin{array}{c}
k \\
i \\
\end{array}
\right) \left(\frac{k-i}{k}\right)^M[/tex]
kai_sikorski
#9
Mar5-12, 08:05 AM
PF Gold
kai_sikorski's Avatar
P: 162
Quote Quote by M Quack View Post
I know, I know, that was not supposed to be the complete answer. But you can build up from there. Following my route I get

[itex] \sum\limits_{n=1}^{k-1} (-1)^{n+1} \left(1-\frac{n}{k}\right)^M \left(\begin{array}{c}k\\n\end{array}\right)[/itex]

Kai, what do you get?
Applying your formula to just the case k = 3 , we get

3(2/3)M - 3(1/3)M ≈ 3 (2 M )/(3 M )

But above doesn't go to 1. The probability that every urn has a ball must clearly go to 1 if you keep adding more and more balls.
JolleJ
#10
Mar5-12, 11:05 AM
P: 35
I been thinking sort of down the roads of what you're doing...
@Kai: Your suggestion gives negative results for m=100, k=50...
kai_sikorski
#11
Mar5-12, 11:14 AM
PF Gold
kai_sikorski's Avatar
P: 162
Hmm, yeah I see my problem. I'm trying to condition on there being a specific number of empty urns, but I'm calculating the probability to have more than or equal to that many.
Dickfore
#12
Mar5-12, 11:38 AM
P: 3,014
The event whose probability is required is opposite to the event:
After M independent, equally probable fillings of k urns, there is at least one (meaning either one, or two, ... , or k) being empty.

What is the probability [itex]p_l[/itex] of exactly l urns remaining empty? (How many M letter words can be made with k distimct letters, and how many with k-l letters if you could repeat the letters and their order matters?)
JolleJ
#13
Mar5-12, 02:16 PM
P: 35
Quote Quote by Dickfore View Post
The event whose probability is required is opposite to the event:
After M independent, equally probable fillings of k urns, there is at least one (meaning either one, or two, ... , or k) being empty.
Yes, but I am not having an easier time calculating this.

Quote Quote by Dickfore View Post
What is the probability [itex]p_l[/itex] of exactly l urns remaining empty? (How many M letter words can be made with k distimct letters, and how many with k-l letters if you could repeat the letters and their order matters?)
Knowing this would obviously solve my problem; but this is an even harder question. Harder in the sense that my need (l = 0) is a subproblem.
awkward
#14
Mar5-12, 05:01 PM
P: 327
This is the Coupon Collector's Problem.

http://en.wikipedia.org/wiki/Coupon_...or%27s_problem

Oddly enough, the Wikipedia article doesn't give the formula for the probability you asked for-- just expected values etc. But you can find it in many probability texts.
Dickfore
#15
Mar5-12, 08:33 PM
P: 3,014
Label the urns from 1 to k. Then, each placement of the balls is equivalent to an M-letter word with the "letters" 1, 2, ..., k. Each of these [itex]k^M[/itex] words is equally probable.

Let [itex]x(k, M)[/itex] be the number of M letter words in which each of the k letters of the alphabet occurs at least once.

We can divide this set into two disjoint subsets: A set in which 1 enters exactly once and in which it occurs more than once. The first subset has x(k - 1, M - 1) elements. The second x(k, M - 1). Therefore, we have the recursion:
[tex]
x(k, M) = x(k - 1, M - 1) + x(k, M - 1)
[/tex]

Obviously, [itex]x(k, M) = 0, \ k > M[/itex].

From here, we deduce that:
[tex]
x(k, k) = x(k - 1, k - 1) = \mathrm{const}.
[/tex]
This constant is obviously equal to 1, since there is only one way of filling k urns with k balls (by placing exactly one ball in each urn).

Then, we have:
[tex]
x(k, k + 1) = x(k - 1, k) + 1 \Rightarrow x(k, k + 1) = x(1, 2) + k - 1, \ k \ge 1
[/tex]
Obviously, [itex]x(1, M) = 1, M \ge 1[/itex]. This boundaty condition is consistent with the above recursion relation if and only if [itex]x(0, M) = 0, M \ge 0[/itex].

To reduce the recursion w.r.t. k, we perform a discrete Laplace transform w.r.t. k:
[tex]
X_M(s) \equiv = \sum_{k = 0}^{\infty}{x(k, M) e^{-k \, s}}
[/tex]
Multiply the recursion by [itex]e^{-(k - 1)s}[/itex] and sum w.r.t. k from 1 to ∞, to get:
[tex]
e^{s} \, \left[ X_M(s) - x(0, M) \right] = X_{M - 1}(s) + e^{s} \, \left[ X_{M - 1}(s) - x(0, M - 1) \right], \ M > 1
[/tex]

[tex]
X_{M + 1}(s) = (1 + e^{-s}) X_{M}(s), \ M \ge 1
[/tex]
This recursion w.r.t. M is a geometric sequence with an easy solution:
[tex]
X_M(s) = X_1(s) \, (1 + e^{-s})^{M - 1}, \ M \ge 1
[/tex]

[tex]
X_1(s) = \sum_{k = 0}^{\infty}{x(k, 1) \, e^{-k s}} = x(0, 1) + x(1, 1) e^{-s} = e^{-s}
[/tex]

Then, take [itex]z \equiv e^{s}[/itex], and we have:
[tex]
\tilde{X}_M(z) = X_M(s) = \frac{1}{z} \, \left(1 + \frac{1}{z} \right)^{M - 1}, \ M \ge 1
[/tex]

Then, if you expand this binomial into a Laurent series near [itex]z = 0[/itex], you can identify the coefficients as [itex]x(k, M)[/itex]. We have:
[tex]
\tilde{X}_M(z) = \frac{1}{z} \, \sum_{k = 0}^{M - 1}{\left( \begin{array}{c} M - 1 \\ k \end{array}\right) \, \frac{1}{z^k}} = \sum_{k = 1}^{M}{\left( \begin{array}{c} M - 1 \\ k - 1 \end{array}\right) \, \frac{1}{z^k}} \Rightarrow x(0, M) = 0, x(k, M) = \left( \begin{array}{c} M - 1 \\ k - 1 \end{array}\right), 1 \le k \le M, x(k, M) = 0, k > M
[/tex]

So, I think the answer is:
[tex]
P(k, M) = \left( \begin{array}{c} M - 1 \\ k - 1 \end{array}\right) \, \frac{1}{k^M}
[/tex]
SW VandeCarr
#16
Mar5-12, 09:36 PM
P: 2,504
Quote Quote by Dickfore View Post
Obviously, [itex]x(k, M) = 0, \ k > M[/itex].
The OP defined M>k, but I prefer n=M, n>k as more standard notation for the binomial distribution.

Then we have n events with 1/k probability. The binomial distribution will have a non zero probability for zero events for any value of n given P=1/k. An event is a ball in an urn. The mean (expected) value would be n/k assuming all balls go into an urn.

EDIT: The probability that every urn has at least one ball should be 1-P(x=0). So for 20 balls and 10 urns P(x=0) = 0.1216 and 1-0.1216= 0.8784
JCVD
#17
Mar6-12, 12:59 AM
P: 73
This is just a standard exercise from enumerative combinatorics.

Label the urns 1 through k. How many ways can we place the M balls in the k urns so that each urn gets a ball? Line up the balls and urns in a straight line, with lower-labeled urns to the left of higher-labeled urns and with the leftmost object being a ball, the rightmost object being an urn, and no two urns adjacent. Put all balls to the left of urn 1 into urn 1, then put all remaining balls to the left of the urn 2 into urn 2, and repeat until each ball is in an urn. There are M-1 choose k-1 ways to place the urns, since k-1 of the M-1 distinct spots between balls must be chosen for urns 1 through k-1, with urn k going on the very end.

Now how many total ways are there to put the balls in the urns? We repeat the process above, except we take away the requirements that the leftmost object be a ball (so that urn 1 can be empty) and that urns cannot be adjacent (so that for j>1 urn j can be made empty by putting it directly after urn j-1). We still need urn k to go last since otherwise we would not have placed every ball into an urn. There are M+k-1 choose k-1 ways to place the urns now, since urn k must be placed last, and before it are M+k-1 spots on which to place objects, exactly k-1 of which must be occupied by urns.

Thus the probability each urn contains a ball is (M-1 choose k-1)/(M+k-1 choose k-1).
M Quack
#18
Mar6-12, 03:15 AM
P: 673
Thanks JCVD, that explanation is very clear.

Quote Quote by kai_sikorski View Post
Applying your formula to just the case k = 3 , we get

3(2/3)M - 3(1/3)M ≈ 3 (2 M )/(3 M )

But above doesn't go to 1. The probability that every urn has a ball must clearly go to 1 if you keep adding more and more balls.
Well spotted. I was trying to calculate the opposite probability, that there is at least one empty urn. But even that I got wrong.


Register to reply

Related Discussions
Kinematics Equation - Simple yet tough Introductory Physics Homework 3
Simple Pendulum Problem...this one's kinda tough Introductory Physics Homework 4
Tough tough question: Calculating magnetic Flux in water Classical Physics 0
Tough problem Calculus & Beyond Homework 12
Tough problem (for me at least...) Introductory Physics Homework 3