TAOCP 5.1.3 Exercise 13
Let $X_1 X_2 \cdots X_{52}$ be the sequence of suits obtained from a uniformly random permutation of a multiset containing $13$ clubs, $13$ diamonds, $13$ hearts, and $13$ spades, ordered $C<D<H<S$.
Exercise 13. [05] [05] If Simon Newcomb’s solitaire game is played with a standard bridge deck, ignoring face value but treating clubs < diamonds < hearts < spades, what is the average number of piles?
Verified: no
Solve time: 1m48s
Let $X_1 X_2 \cdots X_{52}$ be the sequence of suits obtained from a uniformly random permutation of a multiset containing $13$ clubs, $13$ diamonds, $13$ hearts, and $13$ spades, ordered $C<D<H<S$. A pile starts at position $1$ and at every position $i>1$ a new pile starts exactly when $X_i < X_{i-1}$, so the number of piles equals $1 + D$, where $D$ is the number of descents $X_{i-1} > X_i$ for $1 \le i \le 51$.
For each adjacent pair, the probability of a descent is computed by sampling two distinct cards without replacement. For suits $s>t$, the contribution is
$\mathbb{P}(X_{i-1}=s, X_i=t) = \frac{13}{52}\cdot \frac{13}{51},$
since after choosing a card of suit $s$, there remain $13$ cards of suit $t$. There are $\binom{4}{2}=6$ ordered suit pairs with $s>t$, namely $(D,C),(H,C),(H,D),(S,C),(S,D),(S,H)$, so
$\mathbb{P}(X_{i-1} > X_i) = 6 \cdot \frac{13}{52}\cdot \frac{13}{51} = 6 \cdot \frac{1}{4}\cdot \frac{13}{51} = \frac{13}{34}.$
Hence
$\mathbb{E}[D] = 51 \cdot \frac{13}{34} = \frac{51}{34}\cdot 13 = \frac{3}{2}\cdot 13 = \frac{39}{2}.$
The expected number of piles equals $1 + \mathbb{E}[D]$, hence
$\mathbb{E}[\text{piles}] = 1 + \frac{39}{2} = \frac{41}{2}.$
$\boxed{\frac{41}{2}}$