| hard | probability |
There are 26 black(B) and 26 red(R) cards in a standard deck. A run is number of blocks 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.
Linearity of expectation
27
We form the answer for general deck of 2n cards, with n red cards and n black cards. Consider any sequence X1,X2..X2n (of R & B). Now define Y1 = 1; Yi = 1 if Xi and X(i-1) are of different colors Yi = 0 otherwise.
We want to find E[Y1 + ..+ Y2n], using linearity of expectation, = E(Y1) +...+E(Yn). Now note that, E[Y1] = 1 and E[Yi] = E[Yj] for the rest (by symmetry)
Also E[Yi] = E(Y2) = P(X2 is diff from X1) = (number of ways first two are RB or BR) / (Total number of orientations) = 2 * [ (2n-2)choose(n-1) ] / [ 2n choose n ] = n/(2n-1)
Ans = 1+(2n-1) * E[Y_i] = n+1
This is 27 for deck of 52 cards.