Placing Balls in Urns and Expected values
Taria
placing balls in urns :p) and I usually like these types of problems.
But this problem is different from what I've ever experienced.
Suppose that n balls are randomly placed in n urns in such a way that
each ball is equally to go into each urn. What are the expected number
of empty urns.
I thought I'd try using the expectation formula, so note to myself...
E(X) = summation of nPx(X)
Thus: n=number of balls and urns (n = 1,2,3,...n)
p = 1/n
So I get: E(X) = (1*1/n) + ((2*(1/n)) + ((3*(1/n)) + ((n-1)*(1/n)) +
(n*(1/n))
= n!/n = (n-1)!
I peek into the back of my book for the answer to this question and
it's not THAT answer.
The answer is: n(1-(1/n))^n
I try to backwards derive how they came to this step since I know the
answer, I start from there. I substitute known values making
k = 0 urns are filled
p=1/n:
B(n,0)=C(n,0) * p^0 * (1-1/n)^(n-0) = 1*1*(1-(1/n)^n)
Eureka, there's some of my answer ..once I simplify it some, it
condenses to the book's answer partially. I'm not sure where that
extra n came from. So I scratch that part out.
So I rethink this again and came up with E(X) = n(1-(1/n))
Agggh. I'm realizing the expection formula has no power to it. I'm
going in circles in my head. :(
Any insight to this is helpful,
Thanks in advance,
Taria the Weary
Rob Johnson
"Taria" <mch...@hotmail.com> wrote:
>Suppose that n balls are randomly placed in n urns in such a way that
>each ball is equally to go into each urn. What are the expected number
>of empty urns.
The probability that a particular ball will not be in urn 1 is 1-1/n.
So the probability that no balls are in urn 1 is (1-1/n)^n. That is
the expectancy of urn 1 being empty is (1-1/n)^n. This means that the
expected number of empty urns is n (1-1/n)^n.
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
The Last Danish Pastry
there were lines ruled across the bottoms of the urns, and we dropped
in needles instead of balls... we could experimentally determine pi
and e at the same time!
Dan Dima
I'll write a detailed, rigorous proof:
"Probability for a urn to be empty is x=(1-1/n)^n since a ball is not placed in that urn with a probability (1-1/n) and we supposed the balls are placed independently.
0 empty urns -> P(0) = (1-x)^n
1 empty urns -> P(1) = C(n,1)*x*(1-x)^{n-1}
..
k empty urns -> P(k) = C(n,k)*x^k*(1-x)^{n-k}
..
n empty urns -> P(n) = x^n
by the binomial expansion:
P(1) + P(2) + ... + P(k) + ... + P(n) = 1
You want:
E(X) = 0*P(0) + 1*P(1) + ... + k*P(k) + ... + n*P(n)
E(X) = 1*C(n,1)*x*(1-x)^{n-1} + ... + k*C(n,k)*x^k*(1-x)^{n-k} + ... + n*x^n
E(X) = x * (1*C(n,1)*(1-x)^{n-1} + ... + k*C(n,k)*x^{k-1}*(1-x)^{n-k} + ... + n*x^{n-1})
But k*C(n,k) = n*C(n-1,k-1) hence:
E(X) = n * x * ( C(n-1,0)*(1-x)^{n-1} + ... + C(n-1,k-1)*x^{k-1}*(1-x)^{n-k} + ... + C(n-1,n-1)*x^{n-1} )
and again use the binomial expansion to conclude:
E(X) = n * x
E(X) = n * (1-1/n)^n"
I don't like that proof of ""
I hope it helped...
Regards,
Dan
Taria
>
the linearity of the the way it looks in text form online, it becomes
almost impossible for me to follow without taking a significant amt of
time to decipher.
I think the problem I'm having here is the inconsistency of the 2
stated equations above and I think I have it worked out now.
The probablilies should be stated like this:
Probability for 1 urn to be empty is (1- 1/n)^1
Probability for n urns to be empty is (1- 1/n)^n
One statement is a statement for all n urns while the other is a
specific instance. Ok, I'm fine. Next, we apply it to the expectancy
formula. E(X)=npx(X)
E(X)= 0*(1 - 1/n)^0 + 1*(1 - 1/n)^1 + 2*(1 - 1/n)^2 + ... + (n-1)*(1 -
1/n)^(n-1) + n*(1 - 1/n)^n
Assuming the answer n*(1 - 1/n)^n given by my textbook is correct, all
the terms of the above equation except for the last one must add to 0.
How can that be?
Taria
instances and test what you stated.
The expectation value formula I'm familiar with is this:
For E(X=2) = 1*(1 - 1/n)^1 + 2*(1 - 1/n)^2
For E(X=3) = 1*(1 - 1/n)^1 + 2*(1 - 1/n)^2 + 3*(1 - 1/n)^3
I feel like sometihng's wrong. The probablity of each ball to enter
each urn is equally likely as stated in the original problem. Just by
looking at the above expanded equations, I see that the probabiliities
of as X increases, the probability decreases. This doesn't make sense
to me, because let's say you take a simple example like a die. The
probablity for each roll is 1/6th regardless of what X is. So I would
expect p to remain constant when figuring out the expectation for the
urns.
On Dec 14, 12:55 am, r...@trash.whim.org (Rob Johnson) wrote:
> In article <1166092677.142803.243...@j72g2000cwa.googlegroups.com>,
>
> "Taria" <mche...@hotmail.com> wrote:
> >Suppose that n balls are randomly placed in n urns in such a way that
> >each ball is equally to go into each urn. What are the expected number
> >of empty urns.The probability that a particular ball will not be in urn 1 is 1-1/n.
C6...@shaw.ca
> I see what you mean. But I'm not fully convinced. Let's try it for 3
> instances and test what you stated.
Let I_i = 1 if urn i is empty, I_i = 0 otherwise. The total number of
empty urns is N = sum[I_i, i=1,...,n]. The expected number empty is
E(N). But, by linearity of expectation, E(N) = sum [E(I_i),i=1..n].
Each E(I_i) = (1 - 1/n)^n, so E(N) = n (1-1/n)^n.
>
> The expectation value formula I'm familiar with is this:
Are you also familiar with the elementary property E(U+V) = E(U) + E(V)
for any two random variables (whether or not they are independent)?
That's all you need. (Of course, it goes by induction from a two-term
sum to an n-term sum.)
R.G. Vickson
Taria
apply E(X) + E(Y) since this involves add 2 values and I don't see
where the 2nd value would come from.
In any case, I've gotten hints from my professor about this problem and
his reply was: "Are you mixing up the variable X which is the total
number of empty urns with the indicator variable, which we could call
X_i which tells us if the urn is empty or not? You can find the
variance of X in terms of X-I's by looking at examples xxx thru xxx in
the book."
My reaction: !!! He has not shown how to solve those examples he has
shown me which is identical to this one and there are no examples in
the book.
Fine. I'll try working on it out.
The indicator random variable of E is 1-P(E) if x = 0, P(E) if x=1.
So P(E)=1/n for x=1 and
since x=0 then P(E)= 1 - 1/n follows. We're fine so far but this
isn't something new.
To figure the probability of empty urns, is this the usual counting
method? Kinda like the way you count # of ways you don't get the value
1 in 3 tosses when you toss a die. then the P(no 1's in 3 tries) =
C(5,3)(1/6)^0 * (5/6)^3 so, equating this to our current problem P(no
empty urns) = C(N,n) (1/n)^0 * (1 - 1/n)^n. Agh that's wrong! Now
this equation has another variable in it and I don't think that's the
way I want to go. :(
Any insightful thoughts on this?
The only thing I can say for certain is, being in this class is
certainly a humbling one.
Dan Dima
> since a ball is not placed in that urn with a
> probability (1-1/n) and we supposed the balls are
> placed independently.
> >
> Proofs are probably my weakest link in mathematics.
> Couple that with
> the linearity of the the way it looks in text form
> online, it becomes
> almost impossible for me to follow without taking a
> significant amt of
> time to decipher.
>
> I think the problem I'm having here is the
> inconsistency of the 2
> stated equations above and I think I have it worked
> out now.
>
> The probablilies should be stated like this:
> Probability for 1 urn to be empty is (1- 1/n)^1
> Probability for n urns to be empty is (1- 1/n)^n
A ball is placed randomly in one of the n urns with an equal probability.
Hence the probability to be in the 1st urn is 1/n, to be in the 2nd urn is 1/n, .. so on in the k-th urn is 1/n ... in the n-th urn is 1/n.
Then a ball is not in the k-th urn with a probability of 1-1/n. (1 <= k <= n)
Since the balls are placed independently then:
Probability for 1 urn to be empty is (1- 1/n)^n
Taria
from? What type of reasoning are you using so that n is included in
the answer?
C6...@shaw.ca
> This problem seems so easy but I dunno! I'm not clear how I would
> apply E(X) + E(Y) since this involves add 2 values and I don't see
> where the 2nd value would come from.
Suppose n = 4.
I1 = 1 if urn #1 is empty, I1 = 0 if urn #1 is not empty
I2 = 1 if urn # 2 is empty, I2 = 0 if it is not empty,
I3 = 1 if urn #3 is empty, I3 = 0 if it is not empty,
I4 = 1 if urn #4 is empty, I4 = 0 if it is not empty.
Number of empty urns is N = I1 + I2 + I3 + I4. The expected number of
empty urns is
E(N) = E(I1) +E(I2) + E(I3) + E(I4) . Now E(I1) = E(I2) = E(I3) = E(I4)
= P{urn #1 is empty} = (1 - 1/4)^4, so E(N) = 4 (1 - 1/4)^4. It works
the same way for any n.
R.G. Vickson
Taria
I get it now!
Thank you so much Professor Vickson!
Taria
On Dec 14, 2:45 pm, "C...@shaw.ca" <C...@shaw.ca> wrote:
> Taria wrote:
> > This problem seems so easy but I dunno! I'm not clear how I would
> > apply E(X) + E(Y) since this involves add 2 values and I don't see
> > where the 2nd value would come from.Suppose n = 4.
> > certainly a humbling one.- Hide quoted text -- Show quoted text -
Rob Johnson
"Taria" <mch...@hotmail.com> wrote:
>On Dec 14, 12:55 am, r...@trash.whim.org (Rob Johnson) wrote:
>> In article <1166092677.142803.243...@j72g2000cwa.googlegroups.com>,
>> "Taria" <mche...@hotmail.com> wrote:
>> >Suppose that n balls are randomly placed in n urns in such a way that
>> >each ball is equally to go into each urn. What are the expected number
>> >of empty urns.The probability that a particular ball will not be in urn 1 is 1-1/n.
>> So the probability that no balls are in urn 1 is (1-1/n)^n. That is
>> the expectancy of urn 1 being empty is (1-1/n)^n. This means that the
>> expected number of empty urns is n (1-1/n)^n.
>I see what you mean. But I'm not fully convinced. Let's try it for 3
>instances and test what you stated.
>
>The expectation value formula I'm familiar with is this:
>
>For E(X=2) = 1*(1 - 1/n)^1 + 2*(1 - 1/n)^2
>For E(X=3) = 1*(1 - 1/n)^1 + 2*(1 - 1/n)^2 + 3*(1 - 1/n)^3
>
>I feel like sometihng's wrong. The probablity of each ball to enter
>each urn is equally likely as stated in the original problem. Just by
>looking at the above expanded equations, I see that the probabiliities
>of as X increases, the probability decreases. This doesn't make sense
>to me, because let's say you take a simple example like a die. The
>probablity for each roll is 1/6th regardless of what X is. So I would
>expect p to remain constant when figuring out the expectation for the
>urns.
I believe that the Principle of Inclusion-Exclusion is helpful here.
Look at <http://www.whim.org/nebula/math/counting.html>. We will use
the same notation here.
Let S(i) be the collection of scenarios with urn i empty. An element
of the intersection of j of the S(i) is a scenario with j of the urns
empty. For a given set of j empty urns, the balls can be arranged in
(n-j)^n ways in the remaining n-j remaining urns. Since there are
C(n,j) ways to pick the j empty urns, the size of the intersection of
j of the S(i) is N(j) = C(n,j)(n-j)^n. Note that we have specified j
of the empty urns, but (n-j)^n includes scenarios where some of the
other n-j urns may be empty. The Inclusion-Exclusion Principle sorts
these cases out. The Generalized Inclusion-Exclusion Principle says
that the number of scenarios with exactly k of the urns empty is
--- j-k
> (-1) C(j,k) N(j)
---
j
--- j-k n
= > (-1) C(j,k) C(n,j) (n-j) [1]
---
j
To simplify the computations, we will use the following identity:
--- j-k
> (-1) C(j,k) C(k,m) = d(j,m) [2]
---
k
where d(j,m) = 1 if j = m, and 0 otherwise.
Obviously, the total number of scenarios is n^n (n balls into n urns)
which agrees with [1]:
--- --- j-k n
> > (-1) C(j,k) C(n,j) (n-j)
--- ---
k j
--- --- j-k n
= > > (-1) C(j,k) C(k,0) C(n,j) (n-j)
--- ---
k j
--- n
= > d(j,0) C(n,j) (n-j)
---
j
n
= C(n,0) (n-0)
n
= n
Thus, the probability of having exactly k urns empty is
1 --- j-k n
--- > (-1) C(j,k) C(n,j) (n-j)
n^n ---
j
The expected number of empty urns is
1 --- --- j-k n
--- > k > (-1) C(j,k) C(n,j) (n-j)
n^n --- ---
k j
1 --- --- j-k n
= --- > > (-1) C(j,k) C(k,1) C(n,j) (n-j)
n^n --- ---
k j
1 --- n
= --- > d(j,1) C(n,j) (n-j)
n^n ---
j
1 n
= --- C(n,1) (n-1)
n^n
n
= n (1-1/n)
as I had said before. You can use this method to compute the
variance of the number of empty urns as well.
The expected value of the square of the number of urns is
1 --- 2 --- j-k n
--- > k > (-1) C(j,k) C(n,j) (n-j)
n^n --- ---
k j
1 --- --- j-k n
= --- > > (-1) C(j,k) (2 C(k,2) + C(k,1)) C(n,j) (n-j)
n^n --- ---
k j
1 --- n
= --- > (2 d(j,2) + d(j,1)) C(n,j) (n-j)
n^n ---
j
1 n n
= --- ( 2 C(n,2) (n-2) + C(n,1) (n-1) )
n^n
n n
= n(n-1)(1-2/n) + n(1-1/n)
The variance of the number of empty urns is therefore
n n 2 2n
n(n-1)(1-2/n) + n(1-1/n) - n (1-1/n)
As n -> oo, this is approximately n ( 1/e - 2/e^2 ) ~ .0972 n
kunzmilan
urns, if balls are indexed, too.
>From this number, there are n possibilities how to place all balls into
only one urn.
We have n!/(n-2)!1!1! how to chose two urn to place odd number of balls
in them, and eventually n!/(n-2)!2! , if the number of balls in both
urns is the same. These counts do not count with indexing of balls and
leave (n-2) urns empty.
If only urns are indexed, the sum of all such coefficients for all
partitions reduces to
(2m -1)!/m!(m-1).
The sum of both coefficients divided by this coefficient gives the
probability of (n-2) urns to be empty.
kunzmilan
Rob Johnson
"kunzmilan" <kunz...@atlas.cz> wrote:
>There are n^n possibilities how to place n indexed balls into n indexed
>urns, if balls are indexed, too.
>From this number, there are n possibilities how to place all balls into
>only one urn.
This agrees with [1] from my previous post; since k = n-1, only the
term with j = n-1 is non-zero:
--- j-k n
> (-1) C(j,n-1) C(n,j) (n-j)
---
j
0 n
= (-1) C(n-1,n-1) C(n,n-1) 1
= n
>We have n!/(n-2)!1!1! how to chose two urn to place odd number of balls
>in them, and eventually n!/(n-2)!2! , if the number of balls in both
>urns is the same. These counts do not count with indexing of balls and
>leave (n-2) urns empty.
>If only urns are indexed, the sum of all such coefficients for all
>partitions reduces to
>(2m -1)!/m!(m-1).
>The sum of both coefficients divided by this coefficient gives the
>probability of (n-2) urns to be empty.
To compute probability, we must index the balls. Consider the case
where n = 2; 2 balls and 2 urns. If we do not index the balls, there
are 3 arrangements:
|o| | | | | | | | | |o|
|o| | | |o| |o| | | |o|
- - - - - -
but they are not equally likely. Coloring the balls (b for blue, r
for red) does not change the probabilities, however, it does show
the proper probabilities; each ball can be in each urn with equal
probability:
|b| | | | | | | | | | | | | |b|
|r| | | |b| |r| |r| |b| | | |r|
- - - - - - - -
That is, each ball will be in the left urn 50% and the right urn
50%, as shown above.
So labelling the balls determines the proper probabilities.
C6...@shaw.ca
Very nice little demonstration. Of course, that only holds for
"classical" balls; for indistinguishable quantum-mechanical balls, the
first (unlabelled) version holds for bosonic balls, and only the middle
configuration of the unlabelled version is possible at all for
fermionic balls.
R.G. Vickson
kunzmilan
fermionic, but on the way, how we count. For example, 3 balls (i index)
and 3 urns (j index):
(1,0,0)
(0,1,0)
(0,1,0)
The column sums (eventually diagonal elements in the quadratic form)
are (1,2,0). Any distinction vanishes.
Ones in the matrix are distinguished only by their position.
It is necessary to use the second polynomial coefficient to take
account on the position of ones in columns (m-permutations).
If ones have their index (are distinguishable), the third index must be
used
(1_a,0,0)
(0,1_b,0)
(0,1_c,0).
Instead of n^m possibilities, the solution of this problem leads to the
growing factorial function.
kunzmilan
C6...@shaw.ca
Exactly! Classical balls are counted one way. Fermionic and bosonic
balls are counted differently from classical balls and differently from
each other. (Indeed, for fermions, some configurations are just plain
not allowed at all.) If you don't believe it, get a book on Quantum
Mechanics, or modern Statistical Mechanics and start reading.
R.G. Vickson
kunzmilan
> Exactly! Classical balls are counted one way. Fermionic and bosonic
> balls are counted differently from classical balls and differently from
> each other. (Indeed, for fermions, some configurations are just plain
> not allowed at all.) If you don't believe it, get a book on Quantum
> Mechanics, or modern Statistical Mechanics and start reading.
>
> R.G. Vickson
only existing possibilities of distribution are counted, given by the
number of occupied (nonzero) urns. Number of urns (atoms) is 5, number
of balls (quanta of energy) is 5:
URNS 1 2 3 4
5
5
4,1;1,4
3,2;2,3 3,1,1;1,3,1;3,11;
2,2,1;2,1,2;1,2,2;*
2,1,1,1;1,2,1,1;1,1,2,11;1,1,1,2
1,1,1,1,1.
Sum = 16. Microparticle have no special properties. Mathematics does
not depend on the size of its objects.
kunzmilan
C6...@shaw.ca
> > Exactly! Classical balls are counted one way. Fermionic and bosonic
> > balls are counted differently from classical balls and differently from
> > each other. (Indeed, for fermions, some configurations are just plain
> > not allowed at all.) If you don't believe it, get a book on Quantum
> > Mechanics, or modern Statistical Mechanics and start reading.
> >
> > R.G. Vickson
> The bosonic counting is just a difference of the previous one, where
> only existing possibilities of distribution are counted, given by the
> number of occupied (nonzero) urns. Number of urns (atoms) is 5, number
> of balls (quanta of energy) is 5:
> URNS 1 2 3 4
> 5
> 5
> 4,1;1,4
> 3,2;2,3 3,1,1;1,3,1;3,11;
> 2,2,1;2,1,2;1,2,2;*
> 2,1,1,1;1,2,1,1;1,1,2,11;1,1,1,2
>
> 1,1,1,1,1.
I cannot understand your English, and I cannot follow your development
(partly because the columns do not line up well, etc.)
> Sum = 16. Microparticle have no special properties.
Wrong: they have some very special properties.
> Mathematics does
> not depend on the size of its objects.
No, but I was talking about the properties of *physical* objects. Those
properties are determined by experimentation and observation, not by
"logic". Look at the simpler case of n = 2 urns and n = 2 balls. Let B
= {both urns contain a ball}. For indistinguishablel classical balls,
we would have P{B} = 1/2, while for indistinguishable
quantum-mechanical balls we would have P{B} = 1/3 for bosons and P{B} =
1 for fermions. Accounting for these types of differences is important
when we want to model nature. Classical counting gives incorrect
results for specific heats, for example, and the strange behaviour of
liquid Helium stems more-or-less directly from Bose-Einstein
statistics. Now, you might say: how is this possible? Counting is
counting, and the particles cannot know anything about how they are
being counted. It is all nonsense! Well, nature does not care about our
opinion of its rightness or wrongness; things behave in a certain way,
and we just have to accept that. Quantum mechanics IS weird and
mysterious; it is also one of the most carefully and rigorously-studied
bodies of knowledge in all history. Again, I say: don't take my word
for it; do some reading.
R.G. Vickson
> kunzmilan
Rob Johnson
"R.G. Vickson" <C6...@shaw.ca> wrote:
>Rob Johnson wrote:
>> In article <1166352415.9...@n67g2000cwd.googlegroups.com>,
>> "kunzmilan" <kunz...@atlas.cz> wrote:
>> >There are n^n possibilities how to place n indexed balls into n indexed
>> >urns, if balls are indexed, too.
>> >From this number, there are n possibilities how to place all balls into
>> >only one urn.
Since the original problem was stated as
Suppose that n balls are randomly placed in n urns in such a
way that each ball is equally [likely] to go into each urn.
What are the expected number of empty urns.
The part about "each ball is equally [likely] to go into each urn"
indicates a labelled ball approach. Your description of "bosonic
balls" counts partitions, where only the number of balls in each
container matters. This requires a different model. Do each of
the partitions of the "bosonic balls" have equal probability?
C6...@shaw.ca
That was the assumption, yes. In a physical sysstem, though, the answer
may be different, depending on energy levels, etc.
R.G. Vickson
kunzmilan
Microparticle have no special properties.
> Wrong: they have some very special properties.
> > Mathematics does
> > not depend on the size of its objects.
> No, but I was talking about the properties of *physical* objects.
One from the most important properties of physical objects is their
existence.
it is nor possible to observe non-existing objects. Mathematics can
count with them.
I apologize for the bad table. I checked it before posting, but it
distorted after. If you can not understand, it is fault your teachers
of combinatorics.
Please, forget urns and balls and speak about vectors and units.
We have n vectorss and m units, say n = m = 5. 5^5 = 3125.
The terms of this product are too many for microparticles, since we are
not able to distinguish, how quanta are placed in space, the string
abbab is not distinguishable from the string aaabb. For us, all 5!/3!2!
such strings have the form a^2b^3. Particles c, d, e do not appear
here, but we can write a^2b^3c^0d^0e^0.
When we derive the original product according to the zero terms, we get
consecutively
(aaaaa), which means 5 in the table, only one observable vector.
(4,1); (1,4)
(3,2); (2,3).
Two observable vectors, 4 possible partitions of 5 units between them.
(3,1,1); (1,3,1); (3,11)
(2,2,1); (2,1,2); (1,2,2).
Three observable vectors, 6 possible partitions of 5 units between
them.
(2,1,1,1); (1,2,1,1); (1,1,2,1,1); (1,1,1,2).
Four observable vectors, 4 possible partitions of 5 units between them.
(1,1,1,1,1).
Five observable vectors, 1 possible partition of 5 units between them.
Is there some specific for microparticles? Units can be any
quantifiable properties.
There is another possibility to differentiate the product n^m, the
difference according to the one variable. This gives another
statistical distribution.
kunzmilan