Source: http://www.quantnet.com/forum/threads/colored-runs-of-cards.6508/
Problem:
There are 26 black(B) and 26 red(R) cards in a standard deck. A run is a maximum block of consecutive cards of the same color. For example, a sequence RRRRBBBRBRB of only 11 cards has
6 runs; namely, RRRR, BBB, R, B, R, B.
Find the expected number of runs in a shuffled deck of cards.
Update (29-05-2011):
Solution:
Posted by Siddhant Agarwal (EE IITB 2011 Alumnus) in comments!
Select the text between * to see the solution.
* Let us have n red cards and n black cards. Consider any sequence X_1,X_2..X_2n. Now define
Y_1 = 1,
Y_i = 1 if X_i and X_(i-1) are of diff colours
Y_i = 0 otherwise.
Clearly we have to find E[Y_1 + ..+Y_2n]
E[Y_1] = 1 by def.
E[Y_i] = E[Y_j] for all i,j>=2
by symmetry.
Also E[Y_i] = $2*(\binom{2n-2}{n-1})/($\binom{2n}{n})
so ans = 1+(2n-1)*E[Y_i] = n+1 *
Problem:
There are 26 black(B) and 26 red(R) cards in a standard deck. A run is a maximum block of consecutive cards of the same color. For example, a sequence RRRRBBBRBRB of only 11 cards has
6 runs; namely, RRRR, BBB, R, B, R, B.
Find the expected number of runs in a shuffled deck of cards.
Update (29-05-2011):
Solution:
Posted by Siddhant Agarwal (EE IITB 2011 Alumnus) in comments!
Select the text between * to see the solution.
* Let us have n red cards and n black cards. Consider any sequence X_1,X_2..X_2n. Now define
Y_1 = 1,
Y_i = 1 if X_i and X_(i-1) are of diff colours
Y_i = 0 otherwise.
Clearly we have to find E[Y_1 + ..+Y_2n]
E[Y_1] = 1 by def.
E[Y_i] = E[Y_j] for all i,j>=2
by symmetry.
Also E[Y_i] = $2*(\binom{2n-2}{n-1})/($\binom{2n}{n})
so ans = 1+(2n-1)*E[Y_i] = n+1 *