probability/expectation question please help?

Question

With a balls and b bins what is the expected number of balls tossed until all bins contain a ball? (Define a random variable Xi equal to the number of tosses required to have a ball land in an i’th bin once i − 1 bins contain a ball, and consider E(Xi).)

Answer 1

Let's suppose that a balls were required for b bins to be filled up. That means that the last bin was finally filled on the last throw. I also assume that every throw lands in a bin and that none misses.
Thus the probability of any throw landing in a particular bin is 1/b.

There are b ways of choosing the last bin.
The number ofo ways of arranging with first a-1 balls into the b-1 bins can be shown to be the summation of
C[(a-1) , i] from i = 1 to i = a-2

So let X = number of throws required to fill the last bin

P(X = a) = 1/b^(a-1) * SUM(i)
where SUM(i) = summation from i = 1 to a-2 of C[(a-1) , i].

The expectation E(X) = Sum of a*P(X = a).

Good luck simplifying that.

EG. For a simple case of b = 2, you'll see that the prob follows a geometric distribution.
P(X = 2) = 1/2
P(X = 3) = 1/4
P(X = n) = 1/2^(n-1)
E(X) = sum of n / 2^(n-1)

Consider
f(x) = 1/(1-x) = x + x^2 + x^3 + ...
f(1/2) is the probability distributiton above
f'(x) = 1/(1-x)^2 = 1 + 2x + 3x^2 + ....
f'(1/2) = 1 + E(X) = 4
E(X) = 3 for this simple case.

Answer 2

ok wow this was tough. so we want to find E(Xi), which is the expected number of tosses it'll take to hit an i'th bin once i-1 bins are already occupied. let's look at what happens when you're throwing the balls:

when you throw a ball, the prob of hitting an unoccupied bin are (b - (i - 1))/b, and the prob of hitting an occupied bin are (i-1)/b. you'll keep throwing balls until you hit an unoccupied bin, so you can make a table with the prob of it taking different numbers of throws:
# | prob.
1 | (b - (i - 1))/b
2 | (i-1)/b * (b - i + 1)/b
3 | ((i-1)/b)^2 * (b - i + 1)/b,
and in general you'll have a geometric sequence where the first term is c = (b - (i - 1))/b, and the ratio of consecutive terms is r = (i-1)/b. I'm just using the letters c and r to make the equations look simpler. in this notation, P(n tosses) = c*r^(n-1).

since we're computing expected value, we want to sum n*P(n tosses) = nc*r^(n-1). there's a formula for sums like this; it's
sum(nc*r^n) = c/(1-r)^2. so plug the expressions for r and c into this formula, and after a lot of simplifying, you'll get b/(b-i+1). so that's what E(Xi) is.

to get the expected number of tosses to fill all the bins, you just sum E(Xi) as i goes from 1 to n. I'm not there's a nice formula for expressing this sum, so you can probably just leave your answer in sigma notation.

Answer 3

Suppose there are i-1 bins with balls. On the next toss the probality of getting in an unoppupied bin is (b-i+1)/b. Now you should know that the Expected value of the number of attempts it takes to produce an event with probability p is simply 1/p. Thus our E(Xi) is simply b/(b-i+1). You are going to have to sum this from 1 to b to get the expected number of balls to fill all b bins. You can rework the indicies of the sum to get Sum from i=1 to b of b/i as your answer.

Answer 4

p(b,n)=P(b bins are all occupied beginning after the nth toss)
=b*P(b bins are all occupied beginning after the nth toss and the nth toss goes into bin b)
=b*P(b bins are all occupied beginning after the nth toss|the nth toss goes into bin i)P(the nth toss goes into bin b)
=b*P(b bins are all occupied beginning after the nth toss|the nth toss goes into bin b)*1/b
=P(b bins are all occupied beginning after the nth toss|the nth toss goes into bin b)
=P(bins 1 through b-1 are all occupied on or before the n-1 st toss|the nth toss goes into bin b)
=P(bins 1 through b-1 are all occupied on or before the n-1 st toss)
=sum{i=b-1 to n-1}P(bins 1 through b-1 are all occupied beginning after the i th toss)
=sum{i=b-1 to n-1}p(b-1,i)
So
p(b,n)=sum{i=b-1 to n-1}p(b-1,i) if b p(b,b)=b!/(b^b)
p(b,n)=0 if n p(b,0)=0
p(1,n)=1 if n>0
This recursion will provide all required evaluations of p(b,n) to compute the expectation sum{i=b to infinity}i*p(b,i).