9
$\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$
  • 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$ – Ben Crowell Jul 5 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$ – Ken Shirriff Jul 5 at 23:04
  • $\begingroup$ @BenCrowell that would be a great separate question $\endgroup$ – qwr Jul 5 at 23:07
19
$\begingroup$

Let $X_i$ be a binary 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 a card has an equal chance of each of 52 positions where it could be permuted to.

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)

| cite | improve this answer | |
$\endgroup$
11
$\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$.

| cite | improve this answer | |
$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.