Thread: find expectation of this r.v.

toss balls one at a time into n bins, each ball will always land in one of the n bins.
stop tossing once some bin end up with 2 balls. and the tosses are independent of each other

X be the number of tosses needed.
(so X is between 2 and n+1)
find E(X)

i find linearity hard to apply here.
and the naive definition resulted in a messy sum, that i cannot reduce to simple form.
is this a well know distribution somewhere?

thanks for any insights

Originally Posted by pv3633

toss balls one at a time into n bins, each ball will always land in one of the n bins.
stop tossing once some bin end up with 2 balls. and the tosses are independent of each other

X be the number of tosses needed.
(so X is between 2 and n+1)
find E(X)

i find linearity hard to apply here.
and the naive definition resulted in a messy sum, that i cannot reduce to simple form.
is this a well know distribution somewhere?

thanks for any insights

Hi pv3633!

This is not a well known distribution as far as I know.

The formula for EX is:

$\displaystyle EX=\sum_{k=2}^{n+1} k \cdot \frac {n!(k-1)!} {(n-k+1)!n^k}$

Wolfram|Alpha could not solve this (within its timeout).
But I found that a close numerical approximation is:

$\displaystyle EX \approx \frac 5 4 \sqrt n + \frac 3 4$

thank you.
that's the sum i got also.

how to get the approximation btw?

Originally Posted by pv3633

thank you.
that's the sum i got also.

how to get the approximation btw?

I calculated a couple of values with Wolfram|Alpha:

Code:

n	EX
1	2
10	4.6
100	13.2
1000	40.3
10000	125.66

Then I made a log-log-plot in excel which showed a straight line.
I used excel's solver to find the coefficients.

The resulting approximation is:

Code:

n	EX	Approx
1	2	2
10	4.6	4.702847075
100	13.2	13.25
1000	40.3	40.27847075
10000	125.66	125.75

thank you