[Ghoser777]

So here's a homework problem I can't seem to get a "nice" answer to. I need to calculate the expected (average) number of balls needed to be thrown into b bins so as to get a bin with 2 balls. The formulation I got (which matches my brute force evaluation of the average) looks like this:

H(i) is the probability of getting the 2-ball condition on the ith throw - no 2-ball condition can have occurred on the previous i-1 throws.

M(i) is the probability of not getting the 2-ball condition on the ith throw.

_____H(i)_________________M(i)
1____0___________________1
i_____(i-1)xM(i-1)/b______M(i-1) - H(i)

And so my expectancy function is:

E[X] = sum from i=1 to b+1 of i*H(i)

This works, but it doesn't have a nice, easy form that I can develop. Another technique I wanted to try (but isn't giving me the right answer) looks like this:

The probability that the first i-1 throws do not result in a double balled bin is b/b * (b-1)/b * (b-2)/b * ... * (b-(i-2)) / b = 1/(b-i+1)!

The probability that the ith throw will land in one of the i-1 bins that already have a ball is (i-1)/b. Therefore, my expectancy function would be:

E[X] = sum from i=1 to b of i*(i-1) / (b*(b-1+i)!)


Any suggestions?

[Hugi]

It will require a lot of balls to answer that question.

[rickey939]

Ummmm....

[Eriamjh]

I remember doing this in college, but now, 13 years later, I have yet to come up with a reason to use such formulas in real life.

I wish i could help you, but I also forgot how to.

[Dork.]

My expectancy equation of being able to help you is:

E[x] = 0 (for all real values of x).

I can picture the problem in my head, but the math just ain't coming.

I might be able to give you an imaginary answer, if you like!

[Ghoser777]

I actually know the output values of the function (by brute force solving the recurrence), but I don't know of a non-recursive way to state the solution function.

Bins: 1 Avg: 2.0 Formula : 2.0
Bins: 2 Avg: 2.499 Formula : 2.5
Bins: 3 Avg: 2.894 Formula : 2.888888888888889
Bins: 4 Avg: 3.194 Formula : 3.21875
Bins: 5 Avg: 3.523 Formula : 3.5104
Bins: 6 Avg: 3.744 Formula : 3.774691358024691
Bins: 7 Avg: 3.975 Formula : 4.018138700711439
Bins: 8 Avg: 4.245 Formula : 4.245018005371094
Bins: 9 Avg: 4.456 Formula : 4.458315744885656
Bins: 10 Avg: 4.605 Formula : 4.660215680000001
Bins: 11 Avg: 4.869 Formula : 4.852372050737358
Bins: 12 Avg: 5.058 Formula : 5.036073675098951
Bins: 13 Avg: 5.187 Formula : 5.212347912952521
Bins: 14 Avg: 5.301 Formula : 5.382029424383519
Bins: 15 Avg: 5.445 Formula : 5.545807285147228
Bins: 16 Avg: 5.712 Formula : 5.704258247072678
Bins: 17 Avg: 5.918 Formula : 5.857870820801627
Bins: 18 Avg: 5.985 Formula : 6.007063098992892
Bins: 19 Avg: 6.073 Formula : 6.15219620095745
Bins: 20 Avg: 6.186 Formula : 6.293584586000901

Avg is my brute force calculation, while formula is the output of the recursive model (seems close enough for me). Maybe there's a math program that can take input values and create a pretty good guess for the function? (unfortunately, there are infinitely many functions with match outputs, so I'm not holding my breath).

[wdlove]

Your title through me all off, I took the expectancy literally. As I thought it was referring to pregnancy.

[Ghoser777]

I hope I'm not pregnant!

[bstone]

Or how often you have to urinate.

[tavilach]

5.6

[Randman]

0. It's rigged like at state fairs.

[RAILhead]

..dp..

[RAILhead]

I didn't expect this, either.

/still got nothin'
//maybe I should just go home

[malvolio]

The answer is 42.

[nredman]

true...no false...true...false false FALSE

[JoshuaZ]

The answer is 5! 5 Balls Ha ha ha!

[dav]

what do you mean - an african or a european swallow?

[Cubeoid]

I was expecting a baby. Nuts.. Still my anwser is "7h to the Nth root of the Gamma corn"

[teknopimp]

Originally Posted by wdlove

Your title through me all off, I took the expectancy literally. As I thought it was referring to pregnancy.

there's women in here?