A random variable is a variable whose value results from a measurement on some type of random process. Expectation E(X) of a random variable X is given by :
Suppose that n balls are tossed into n bins. Each toss is independent and each ball is equally likely to end up in any bin.
Using (or maybe not) the fact that E(X+Y) = E(X) + E(Y) even if X&Y are dependent variables, give the expected value of:
- Number of balls in a bin?
- Number of tosses till a given bin contains a ball?
- Number of tosses till every bin has a ball?
- Number of tosses till a given bin contains two balls?
- Number of tosses till at least a bin contains two balls?
- Number of empty bins?
- Number of bins with exactly one ball?
really? none of the parts?
ReplyDeleteI cant sum the series in most cases :-(
ReplyDelete(i) 1
ReplyDelete(ii)n
ReplyDelete(iii)n^2
(iv)2n -1 -n/e
ReplyDeletedon't know why i am geting so awkward answers!
coz' they are wrong.. :P
ReplyDeleteI'll be posting the solutions by 2moro..
learn to use the info u are given.. wisely.. :)
oh crap! i spot a typo! its b bins! not n! sorry guys! :-|
Delete1. Number of balls in a bin
ReplyDeleteLet X be the random variable denoting the number of balls in a given bin..
P(X=i) = nCi * (1/b)^i * ((b-1)/b)^(n-i)
=> E(X) = summation of i*P(i) from i=0 to n
= sum n * (n-1)C(i-i) * (1/b)^(i-1+1) * ((b-1)/b)^(n-1-i+1)
= n/b * sum (n-1)C(i-i) * (1/b)^(i-1) * ((b-1)/b)^(n-1-i+1)
= n/b * (1/b + (b-1)/b)^(n-1)
= n/b
Alternatively, let X_i be the random variable denoting whether ball i fell into the given bin or not. If yes, X_i = 1 else 0
=> E(X_i) = 1/b * 1 + (b-1)/b * 0 = 1/b
And, E(X) = E(X_1) + E(X_2) + .. + E(X_n) because X = X_1 + X_2 + .. + X_n
=> E(X) = n * (1/b) = n/b without calculating any fancy sums!
2. Number of tosses till a given bin contains a ball
ReplyDeleteLet X be the random variable denoting the no. of tosses reqd. for a given bin to contain a ball. Note that this means the given bin does not contain any ball till X-1 throws, and the Xth throw goes into the bin.
=> P(X=i) = ((b-1)/b)^(i-1) * 1/b
=> E(X) = sum i*P(i) from i=1 to n
This is an AGP which u can easily evaluate (I assume).
http://bit.ly/x9Vqbi
Since n is large, the first 2 terms go to 0 and the answer is b.
3. Number of tosses till every bin has a ball
Let X be the random variable denoting the no. of tosses till every bin has a ball.
P(X=i) = a very bad expression such that i-1 balls distribute over b-1 bins leaving none among these b-1 empty
=> E(X) = sum i*P(i) from i = b to n
This is difficult to compute. Or maybe we can't even compute this w/o the values!
What really needs to be done is difficult to be thought of. I should not have given you this. Still, the answer comes by taking the random variable as equal to the number of tosses required to have a ball land in a j + 1th bin once j bins contain a ball for j = 0, 1, ... , b - 1.
The answer to the question comes out to be b*(1/b + 1/(b-1) + 1/(b-2) +..+ 1).
And yes, here large n == infinite n.
4. Number of tosses till a given bin contains 2 balls
This should be simple..
E(X) = sum i*1/b*(i-1)*(1-1/b)^(i-2) from i = 2 to infinity
Compute the sum as in the derivation of the AGP formula.. Just do that twice..
The answer comes out to be 2b.
Alternatively, an easier solution..
Once the given bin contains a ball (thats expectedly b tosses), we need one more ball in it.. hence its 2*(expected no. of tosses reqd. for the given bin to have a ball) = 2*b.
6. Number of empty bins
ReplyDeleteProper way, it gives a bad expression.
Greedily, its just n*(expected value of a random variable which is 1 if bin 1 is empty, else 0).
7. Number of bins with exactly 1 ball
Again, a greedy solution.. Take a random variable Xi which is 1 only if the ith bin contains exactly 1 ball. Then X = summation Xi. => E(X) = n*(b-1)^(n-1)/b^n