Problem: Given a standard deck of 52 cards, extract 26 of the cards at random in one of the $(52 C 26)$ possible ways and place them on the top of the deck is the same relative order as they were before being selected. What is the expected number of cards that now occupy the same position in the deck as before?
The solution of this problem exists on Stackexchange and also in Paul Zeitz, Art and Craft of Problem Solving, 3.1.28, pg number 69.
https://math.stackexchange.com/questions/224975/expected-number-of-cards-fixed-in-a-deck-after-a-certain-operation[enter link description here]1
But what I don't understand is this:
Number the cards as A_1, A_2...A_52.
Now, to calculate the probability that, say A_12, is in place, is equal to 40C26/50C26. But this also counts the selections where A_13, A_14, A_15 COULD be in place.
So, when we get around to calculating the probability that A_13 is in place, do we subtract some selections in order to not double/triple/"excess" count?
If this be the case, then the solution outlined in stack exchange and in the solutions manual does not make sense to me. Could someone please tell where am I going wrong?
According to me expectation = 1(1/52)(50C25)/50C26 + 2(1/52)(1/51)(49C24)/50C26 + ...
Basically, I only consider x=1 or 2 above, since we need to multiply the number of cards that are in place with their respective probabilities to calculate expectations. The first summand of the above equation is the expectation case where the first card is in place, and the second summand of the above equation is the expectation where the first two cards are in place, followed by an ellipsis.
To elucidate further, in the equation above: 1/52 is the probability of choosing A_1, 50C25 is the number of ways of choosing 25 cards from 50 cards (where we are not choosing card A_2 in the first summand, hence 50 cards and not 51 cards), and 50C26 is basically the number of all possible 26-selections from 52 cards. Likewise, the second summand, and the third and so on...
Of course. But does does not matter, because of linearity of expectation.
Let $X_i$ be the indicator variable of the event "$A_i$ is in place" (that is, $X_i = 1$ if $A_i$ is in place, $X_i=0$ otherwise). Let $p_i = P(X_i=1)$.
Granted, the variables $X_i$ are not independent. But to compute the expected number of cards in place, we just need
$$E[Y]= E \left[ \sum X_i \right] = \sum E(X_i) = \sum p_i$$
Once you agree on the probability of $p_{i}$, the result follows.
It seems that you instead are trying to compute the expectation as
$$E[Y] = \sum j \, P(Y=j) $$
That is, of course, also valid. But much more difficult.