11
$\begingroup$

Assume is shuffle is quite good that it randomizes the card order.

We know that E = $ \sum_{X=1}^n X*P(X) $

We are already know that n=52 and that there are 52! ways to arrange the cards.

So probability that exactly 1 card is in correct position is $\frac{1}{52!} {52 \choose 1}*$(derangements of remaining cards)

This will be summed over all the 52 cases. This seems a bit complicated. Is there a simpler way?

$\endgroup$
3
  • 1
    $\begingroup$ It would be interesting to find the probability that $n$ cards return to the same position. This seems harder to me. It would probably be approximately Poisson. $\endgroup$
    – user13618
    Jul 5, 2020 at 18:39
  • $\begingroup$ @BenCrowell Interesting question. Note special cases such as P(n=51)=0, since you can't have a single card out of place. $\endgroup$ Jul 5, 2020 at 23:04
  • $\begingroup$ @BenCrowell that would be a great separate question $\endgroup$
    – qwr
    Jul 5, 2020 at 23:07

3 Answers 3

21
$\begingroup$

Let $X_i$ be an indicator random variable that is $1$ if card $i$ being shuffled back to its original position, otherwise $0$.

We see $E[X_i] = 1/52$ since card $i$ has an equal chance of each of 52 positions where it could be permuted to. Another way to see this: there are 51! permutations of the cards with card $i$ shuffled to its original position and the rest may be permuted however, out of a total of 52! possible permutations.

The magic step: the quantity we are looking for is $E[X_1 + \cdots + X_{52}] = E[X_1] + \cdots + E[X_{52}] = 52 \times 1/52 = 1$ by linearity of expectation!

(This is effectively the same answer as by Gribouillis, just in the language of expectation instead of computing all cases explicitly)

$\endgroup$
12
$\begingroup$

Examine the $6$ permutations of $123$:

$$\color{red}1\color{red}2\color{red}3$$ $$\color{red}1\color{black}3\color{black}2$$ $$\color{black}2\color{black}1\color{red}3$$ $$\color{black}2\color{black}3\color{black}1$$ $$\color{black}3\color{black}1\color{black}2$$ $$\color{black}3\color{red}2\color{black}1$$

with red indicating a correct position.

Then each number is in its correct position exactly twice, and there are three numbers, hence six red numbers, which gives the expected number of correct positions as $\frac66=1$.

In general there are $n$ numbers, and each is correct $(n-1)!$ times, hence $n!$ correct positions, and so the expected number of correct positions is $\frac{n!}{n!}=1$.

$\endgroup$
0
8
$\begingroup$

For $i\in {1,..,n}$ and $\sigma$ a random permutation, let $\chi_{i=\sigma(i)}$ have value $1$ if $i=\sigma(i)$ and zero otherwise. The expected number of cards returning in their initial position is \begin{equation} m = \frac{1}{n!}\sum_{\sigma}\sum_{i=1}^n \chi_{i = \sigma(i)} = \frac{1}{n!}\sum_{i=1}^n \sum_\sigma \chi_{i=\sigma(i)} = \frac{1}{n!}\sum_{i=1}^n (n-1)! = 1 \end{equation} because $(n-1)!$ permutations leave the $i$-th element invariant.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .