Re: Placing Balls in Urns and Expected values

In article <1166107484.644894.86080@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Taria" <mchew02@xxxxxxxxxxx> wrote:
On Dec 14, 12:55 am, rob@xxxxxxxxxxxxxx (Rob Johnson) wrote:
In article <1166092677.142803.243...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Taria" <mche...@xxxxxxxxxxx> 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

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
.

Relevant Pages

  • Re: Placing Balls in Urns and Expected values
    ... stated equations above and I think I have it worked out now. ... Probability for n urns to be empty is ^n ...
    (sci.math)
  • Re: Help with Urn Problem
    ... number of SINGLY occuppied urns when M balls are randomly placed into N ... exactly one ball, and find the probability that exactly K, ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.stat.math)
  • Re: Placing Balls in Urns and Expected values
    ... urns, if balls are indexed, too. ... the sum of all such coefficients for all ... To compute probability, ...
    (sci.math)
  • Urns and balls
    ... A number of elementary problems in Probability have the equivalent model consisting in to draw balls randomly among urns. ...
    (sci.stat.math)