Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2006-09-15 03:37:33

Fire
Member
Registered: 2006-09-15
Posts: 2

expected number??

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 smile

Offline

#2 2006-09-15 07:09:57

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: expected number??

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

#3 2006-09-15 14:04:25

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: expected number??

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

#4 2006-09-15 15:33:41

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: expected number??

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

#5 2006-09-16 03:59:02

Fire
Member
Registered: 2006-09-15
Posts: 2

Re: expected number??

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

#6 2006-09-16 23:50:43

mikey
Guest

Re: expected number??

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.

#7 2006-09-17 05:37:03

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: expected number??

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

#8 2006-10-07 21:59:54

Krishna
Guest

Re: expected number??

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

#9 2006-10-09 15:33:17

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: expected number??

"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

#10 2006-10-09 22:31:31

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: expected number??

Krishna wrote:

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

#11 2006-10-12 06:43:53

Krishna
Guest

Re: expected number??

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

#12 2006-10-12 07:37:38

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: expected number??

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

#13 2006-10-12 07:56:07

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: expected number??

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

#14 2006-10-12 23:23:43

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: expected number??

mathsyperson wrote:

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. yikes


X'(y-Xβ)=0

Offline

#15 2006-12-14 18:21:47

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: expected number??

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:Pdizzy

Last edited by George,Y (2006-12-14 18:31:28)


X'(y-Xβ)=0

Offline

#16 2006-12-17 14:54:39

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: expected number??

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:


All the ways together has the probability:

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

#17 2006-12-17 15:00:06

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: expected number??

Or to be lazy, let's just resort to computer to "compute" every situation needed. dunno


X'(y-Xβ)=0

Offline

#18 2006-12-27 11:07:15

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

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

#19 2006-12-27 11:10:05

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

George,Y wrote:

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:Pdizzy

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

  combinations.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#20 2006-12-27 11:17:51

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

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:


//NOT!
This question is harded indeed.
I thougth I've solved it.
BUT...
The theoretical results doesn't match with the tests!
I was thinking REALLY long, and then,...
I GOT IT (the error, not the solution)!

Last edited by krassi_holmz (2006-12-27 12:07:52)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#21 2006-12-27 11:52:27

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

Rereading the posts trying to understand what's wrong with the formula, something crossed my mind:

George,Y wrote:

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:Pdizzy

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

#22 2006-12-27 11:59:52

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

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:

[EDIT] GoOd LoKINGQ big_smile
[EDIT] It's too late now. I'll be back tommorow.
[EDIT]Sorry for the multiple posts sad .

Last edited by krassi_holmz (2006-12-28 01:01:32)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#23 2006-12-28 00:59:52

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

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

#24 2006-12-28 07:08:11

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

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:


And now, using this helpful function, define:

That's it!


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#25 2006-12-28 07:17:02

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: expected number??

Now, I cannot find closed form for this sum. Mathematica gave me:

,
where
is the base of the natural logaritm, and

is something called Exponention integral:

That I call cool! smile
GOOD QUESTION!
I'll post pictures soon.
[EDIT] Plot posted.
lxandempiricalresultslb1.gif

Last edited by krassi_holmz (2006-12-28 07:51:13)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

Board footer

Powered by FluxBB