You are not logged in.
We have n balls. Suppose that balls are tossed into b bins. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses before at least one of the bins contains two balls?
=============
My answer is: Expected number of ball tosses before at least one of the bins contains two balls
=1[(n-i)/b] = (b-n+i)/b
is that correct?
thank so much
Offline
I don't see how n is relevant. Surely it doesn't matter how many balls you have, once a bin has 2 balls in it then you stop throwing them.
So, whatever the formula is, it will most probably only have b in it.
Edit: I get it as (b+3)/2.
Why did the vector cross the road?
It wanted to be normal.
Offline
Are you looking for the expected number where expected means 100% chance (absolutely will happen), in which case the answer is (b+1) bin deposits.
Or are you looking for expected meaning 50% chance of happening, in which case, I haven't done the math yet.
igloo myrtilles fourmis
Offline
Expected meaning that if you did an infinite number of trials, it would be the average.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
My solution :
Suppose n = number of balls
b = number of bins
The ith stage is the stage when the first bin contains 2 balls.
So in ith stage there are (n-i) balls remain
We have the expected number of balls (n) in a given bin (b) = n/b
So expected number of ball tosses after at least one of the bins contains two balls = (n-i)/b
So expected number of ball tosses before at least one of the bins contains two balls
=1[(n-i)/b] = (b-n+i)/b
Offline
At 1st toss, the expected number of a ball in a bin = 1/b
At 2nd toss, the expected number of another ball in the same bin = 1/b
The expected number of 2 balls (non-resersal order) in a given bin = 1/b x 1/b = 1/b^2
The expected number of 2 balls in 1 bin of b bin = b x 1/b^2 = 1/b
It seems there are n(n-1) combinations of 2 balls out of n balls but I can't see how it affects outcome.
Maybe I was wrong.
You're all making it more complicated than it needs to be.
Let's say you have just one bin. The first ball will go in Bin1, because that's the only bin there is, and the second will also go in, so your answer is always 2.
Now we add another bin. We can assume that the first ball goes into Bin1. If it goes into Bin2, we just switch the labels on the bins. So now the second ball has a 1/2 chance of going into Bin1 and a 1/2 chance of going into Bin2. If it goes into Bin2, then the third ball will always make a bin have 2 balls in it. So the expected value is (1/2 * 2) + (1/2 * 3) = 2 1/2.
Generalising to b bins, we can use the above reasoning to see that the number of balls needed could be any integer between 2 and (b+1).
That means that the expected value is [{b+1th triangular number} -1]/b, which is (b+3)/2.
Why did the vector cross the road?
It wanted to be normal.
Offline
Dear,
I was trying to find the solution to the same problem. Thanks very much for such beautiful solution.
But, should it not be (b+1)/2 as the question asks for number of throw before any bin gets two balls( such could be 1st to the bth throw).
Anyway, I am very pleased to find this forum and will come time to time.
Thanks
Krishna
"Or are you looking for expected meaning 50% chance of happening, in which case, I haven't done the math yet."
- this meaning more or less, though the chance probabilities are more complex. Too complex for this question!
Last edited by George,Y (2006-10-09 15:36:41)
X'(y-Xβ)=0
Offline
Dear,
I was trying to find the solution to the same problem. Thanks very much for such beautiful solution.
But, should it not be (b+1)/2 as the question asks for number of throw before any bin gets two balls( such could be 1st to the bth throw).
Anyway, I am very pleased to find this forum and will come time to time.
Thanks
Krishna
Hmm. It could be like that. There's a bit of ambiguity in the question. I'd still interpret it the way I did, but it probably wouldn't matter which way you did it as long as you put reasoning with your answer.
Why did the vector cross the road?
It wanted to be normal.
Offline
Dear,
When I saw your solution i thought it was right. But now I doubt it. The probability of getting two balls in a bin starts with the second ball up to the b+1th ball but are all they equally probable? Of course not. in the seond ball the probability is 1/b but in the third ball it is 2/b and it goes to (b-1)/b for bth ball and b/b to the (b+1) th ball. I mean, they are not equally probable, the probablity increses when more and more balls are thrown. So, sipmly taking average of the 2 and b+1 may not be correct.
This problem is chasing me for two months. I relaxed for a week but again I am am in trouble.
Please, give your thoght on it.
Krishna
Ah, you're right. This is a harder problem than it looks then. Let's see...
If you have b bins, the chance that you'll finish with the 2nd ball is 1/b.
The chance of the 3rd ball finishing is 2/b*(b-1)/b, because you need to consider that there is a chance that you would never get to throw a 3rd ball.
So then the 4th ball has a chance of 3/b*(b-1)/b*(b-2)/b, using similar reasoning to above and it just gets more and more complicated as you go along.
I have no idea how to get all that into a nice simple formula though. Sorry.
Why did the vector cross the road?
It wanted to be normal.
Offline
Empirical evaluations shows on average after 50,000 trials each:
1 bin, 2 balls
2 bins, 2.50114 balls
3 bins, 2.88792 balls
4 bins, 3.2159 balls
5 bins, 3.51112 balls
6 bins, 3.77518 balls
7 bins, 4.01582 balls
8 bins, 4.23194 balls
9 bins, 4.45494 balls
10 bins, 4.65486 balls
11 bins, 4.84902 balls
12 bins, 5.03418 balls
13 bins, 5.22098 balls
14 bins, 5.38594 balls
15 bins, 5.5387 balls
16 bins, 5.63002 balls
17 bins, 5.86984 balls
18 bins, 5.99712 balls
19 bins, 6.14244 balls
With an margin of error which appears to be less than 0.01.
My arm is a bit tired now.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Ah, you're right. This is a harder problem than it looks then. Let's see...
If you have b bins, the chance that you'll finish with the 2nd ball is 1/b.
The chance of the 3rd ball finishing is 2/b*(b-1)/b, because you need to consider that there is a chance that you would never get to throw a 3rd ball.
So then the 4th ball has a chance of 3/b*(b-1)/b*(b-2)/b, using similar reasoning to above and it just gets more and more complicated as you go along.
I have no idea how to get all that into a nice simple formula though. Sorry.
Yes, I dwelled into this probiblities once, but I thought you'd got a simple solution. It's a pitty to see the simple formula fail.
X'(y-Xβ)=0
Offline
Hard question!
But I got it!
After reviewing the Classic Probability Model, anyone could solve this problem!
Hint: First consider all the possiblities to throw all balls one by one. The number of combinations is
binnumber^ballnumber. Apparently each possiblity have the SAME chance. Then all you have to do is to count how many ways to arrange k different bins+the bin repeating the kth+ the rest random bins.
Anyone like to solve it thorough??:P:P
Last edited by George,Y (2006-12-14 18:31:28)
X'(y-Xβ)=0
Offline
Since no one seems interested, I have to solve it myself:
n balls;
b bins;
k times independent and different toss and one repeated toss before game over.
Now the issue important is the probability of the event that the initial k times of toss are into one-by-one different bins, among which is the destination of the k+1th ball.
The method to solve this probability, now defined as P(k), where 1≤k≤b-1,(n≤b is defaulted) is rather macro, more specifically, the Classical Probability Model. First, toss all the n balls, observe each ball's destination, so number of all the possible exclusive sequences of the destinations of 1st to nth balls is b^[sup]n[/sup]. For each ball has b destinations. Moreover, these sequences not only share the same probability, they altogether are all the possibility as well. Hence, the probability of each sequences is 1/b^[sup]n[/sup].
Now we need to count how many ways there are to satisfy the out come of k different destinations, then one repeated destination, and then, if any, n-k-1 arbitary destinations. Apparently the number of ways is:
So the expected number of all k's is
Then who can simplify the formula above out??????????????????
Last edited by George,Y (2006-12-17 16:10:27)
X'(y-Xβ)=0
Offline
Or to be lazy, let's just resort to computer to "compute" every situation needed.
X'(y-Xβ)=0
Offline
A program:
#include<iostream>
#include<math.h>
using namespace std;
int main(){
const int MAXBINS=100;
long bins, tests, btmp[MAXBINS], current, counter, res, i, j, rnd;
START:
cout<<"Please enter the number of bins:";
cin>>bins;
cout<<"Please enter the number of tests:";
cin>>tests;
res=0;
for(i=0;i<tests;i++){
counter=0;
for(j=0;j<bins;j++)
btmp[j]=0;
while(1){
rnd = floor((double)rand()*bins/RAND_MAX);
btmp[rnd]++;
counter++;
if(btmp[rnd]==2) break;
}
res+=counter;
}
cout<<"The result is:"<<(double)res/tests<<endl;
cout<<"Press 1 for new test, 0 for exit:";
cin>>i;
if(i!=0) goto START;
return 0;
}
IPBLE: Increasing Performance By Lowering Expectations.
Offline
Hard question!
But I got it!
After reviewing the Classic Probability Model, anyone could solve this problem!Hint: First consider all the possiblities to throw all balls one by one. The number of combinations is
binnumber^ballnumber. Apparently each possiblity have the SAME chance. Then all you have to do is to count how many ways to arrange k different bins+the bin repeating the kth+ the rest random bins.Anyone like to solve it thorough??:P:P
We don't need to examine all combinations. We only need those, in which there's EXACTLY 1 bin with 2 balls AND every other bin contains 0 or 1 balls.
From the above definition, we have
IPBLE: Increasing Performance By Lowering Expectations.
Offline
And, going to the classical way:
We have 0 combinations with 1 balls.
b combinations with 2 balls (each box filled with 2 balls and the others - empty)
b(b-1) combinations with 3 balls (filling some box with 2 balls and other with one)
b(b-1)(b-2) combinations with 4 balls (filling as 3 balls and another ball)
...
b(b-1)(b-2)...(b-k+2) = b!/(b-k+1)! combinations with k balls
By Pigenhole principe, we should stop at k=b+1.
Now, just finding AM:
Last edited by krassi_holmz (2006-12-27 12:07:52)
IPBLE: Increasing Performance By Lowering Expectations.
Offline
Rereading the posts trying to understand what's wrong with the formula, something crossed my mind:
Hard question!
But I got it!
After reviewing the Classic Probability Model, anyone could solve this problem!Hint: First consider all the possiblities to throw all balls one by one. The number of combinations is
binnumber^ballnumber. Apparently each possiblity have the SAME chance. Then all you have to do is to count how many ways to arrange k different bins+the bin repeating the kth+ the rest random bins.Anyone like to solve it thorough??:P:P
George, are you APPARENTLY SURE?
My formula is build assuming the same. But it's FALSE!
Yes! The probability for possibilities with much balls is LESS than the probability for possibilities with less balls, simply because you may end many times before obtainig a position with much balls.
I want to say that the probability to obtain the following:
2 0 0 ... ->b times
is much greater than this:
2 1 1 ... ->b times
IPBLE: Increasing Performance By Lowering Expectations.
Offline
So my formula may work by adding some error correction function:
- the probability to end in a stage with k balls in n bins, such that:Last edited by krassi_holmz (2006-12-28 01:01:32)
IPBLE: Increasing Performance By Lowering Expectations.
Offline
Back to work.
For better understanding of the Omega function, I'll try to find its values for small number of bins using brute-force
IPBLE: Increasing Performance By Lowering Expectations.
Offline
I founded it at least!
I had to leave my original function, because the omega function became so complicated.
I used another approach, which is hard to explain, and now I have a formula, which agrees with the experimental results:
First, I defined a function, S:
IPBLE: Increasing Performance By Lowering Expectations.
Offline
Now, I cannot find closed form for this sum. Mathematica gave me:
That I call cool!
GOOD QUESTION!
I'll post pictures soon.
[EDIT] Plot posted.
Last edited by krassi_holmz (2006-12-28 07:51:13)
IPBLE: Increasing Performance By Lowering Expectations.
Offline