Question

A deck of n cards numbered 1 through n, initially in any arbitrary order, is shuffled in the following manner: At each stage, we randomly choose one of the cards and move it to the front of the deck, leaving the relative positions of the other cards unchanged. This procedure is continued until all but one of the cards has been chosen. At this point, it follows by symmetry that all n! possible orderings are equally likely. Find the expected number of stages that are required.

Short answer

The expected value will be$E\left[X\right]=1+\frac{n}{n-1}+\dots +\frac{n}{2}$.

Step-by-step solution

Given information

A deck of n cards numbered 1 through n, initially in any arbitrary order, is shuffled in the following manner: At each stage, we randomly choose one of the cards and move it to the front of the deck, leaving the relative positions of the other cards unchanged.

Solution

Let X_i be the digit of cards that must be picked before one collects a distinct type after collecting i distinct types of cards.

So,

$X=X_0+X_1+\dots +X_{N-2}$

$E\left[X\right]=E\left[X_0\right]+E\left[X_1\right]+\dots +E\left[X_{N-2}\right]$

If one collects i distinct types of coupons,

The probability of obtaining a new distinct card after k pick will be,

$P\left\{X_i=k\right\}=\frac{n-i}{n}{\left(\frac{i}{n}\right)}^{k-1},k\ge 1$

Solution

$X_i=$geometric random variable

So the expectation value will be,

$E\left[X_i\right]=\frac{n}{n-i}$

The expectation value of X is given by.

$E\left[X\right]=E\left[X_0\right]+E\left[X_1\right]+\dots +E\left[X_{N-2}\right]$

$=\frac{n}{n-0}+\frac{n}{n-1}+\dots +\frac{n}{n-n+2}$

$=1+\frac{n}{n-1}+\dots +\frac{n}{2}$

Final answer

The expected value is$E\left[X\right]=1+\frac{n}{n-1}+\dots +\frac{n}{2}$.