Expected value of lowest card
Divide a pack of cards into two piles, what is the expected value of the lowest card value on the left pile.
Here is the question
Divide a pack of cards into two piles, what is the expected value of the lowest card value on the left pile.
To solve this problem, we first solve a simpler form (assuming we have cards with value $n=1, \cdots, 52$), and then in the next section we solve for pack of cards where the values are $n=1,\cdots,13$ repeated four times. So to answer this question, I’ll first assume:
- We have $n$ distinct cards labeled $1,2,\dots,n$ (for a standard deck, $n=52$; you can map ranks however you like).
- The deck is shuffled uniformly at random.
- Then we cut the deck at a random position $K\in{1,\dots,n-1}$, all cuts equally likely.
- The left pile is the first $K$ cards; the right pile is the rest.
- We want $\mathbb{E}[\min(\text{left pile})]$.
If you meant a different model of “divide into two piles” (like dealing alternately, or independent coin flips), the method is very similar; only the distribution of the pile size changes. The core ideas stay the same.
Step 1: Condition on the size of the left pile
Let:
- $K$ = number of cards in the left pile (the cut position).
- $L$ = the lowest card value (minimum) in the left pile.
We want $\mathbb{E}[L]$.
We’ll use the law of total expectation:
\[\mathbb{E}[L] = \mathbb{E}\bigl[\mathbb{E}[L \mid K]\bigr].\]So we need:
- The distribution of $K$.
- The expectation of the minimum given $K=k$: $\mathbb{E}[L \mid K=k]$.
Distribution of $K$
We choose the cut uniformly among positions $1,\dots,n-1$, so:
\[\mathbb{P}(K = k) = \frac{1}{n-1}, \quad k=1,2,\dots,n-1.\]Step 2: What does the left pile look like, given its size?
Given that the left pile size is $K=k$:
- The set of cards in the left pile is just a random subset of size $k$ from ${1,2,\dots,n}$ (because of the shuffle).
- The order inside the left pile doesn’t matter for the minimum, only which values are there.
So conditioned on $K=k$, the left pile is a uniformly random $k$-subset of ${1,\dots,n}$.
Let $M_k$ be the minimum of a uniformly random $k$-subset of ${1,\dots,n}$. Then:
\[\mathbb{E}[L \mid K = k] = \mathbb{E}[M_k].\]So we need $\mathbb{E}[M_k]$ for a random $k$-subset. That’s a standard order-statistics fact, and it’s nice to derive it once.
Step 3: Expected minimum of a random $k$-subset of (${1,\dots,n}$)
Let $X_{(1)} < X_{(2)} < \dots < X_{(k)}$ be the sorted values when you pick a random $k$-subset of ${1,\dots,n}$. Then:
\[\mathbb{E}[X_{(m)}] = \frac{m (n+1)}{k+1}, \quad m=1,\dots,k.\]In particular, for the minimum $(m=1)$:
\[\mathbb{E}[M_k] = \mathbb{E}[X_{(1)}] = \frac{n+1}{k+1}.\]If you want a quick derivation:
- For a random $k$-subset, the distribution of order statistics is the same as for i.i.d. sample from (${1,\dots,n}$) with replacement conditioned on being distinct; the same “Beta–Binomial” structure appears.
- Or you can do it directly: $\Pr(M_k > m) = \frac{\binom{n-m}{k}}{\binom{n}{k}}$ (all $k$ cards chosen from ${m+1,\dots,n})$, then use
\(\mathbb{E}[M_k] = \sum_{j\ge1} \Pr(M_k \ge j) = \sum_{j=1}^{n-k+1} \frac{\binom{n-j+1}{k}}{\binom{n}{k}}\) and simplify. That sum evaluates to $\frac{n+1}{k+1}$.
We’ll happily take this result:
\[\boxed{\mathbb{E}[L \mid K = k] = \frac{n+1}{k+1}}.\]Step 4: Average over all possible cut sizes
Recall:
$K$ is uniform on ${1,\dots,n-1}$.
So
\(\mathbb{E}[L] = \mathbb{E}\bigl[\mathbb{E}[L \mid K]\bigr] = \sum_{k=1}^{n-1} \mathbb{E}[L \mid K=k] \cdot \mathbb{P}(K=k).\)
Plug in:
\[\mathbb{E}[L] = \sum_{k=1}^{n-1} \frac{n+1}{k+1} \cdot \frac{1}{n-1}.\]Factor out constants:
\[\mathbb{E}[L] = \frac{n+1}{n-1} \sum_{k=1}^{n-1} \frac{1}{k+1}.\]Change index $j = k+1$, so $j$ runs from $2$ to $n$:
\[\mathbb{E}[L] = \frac{n+1}{n-1} \sum_{j=2}^{n} \frac{1}{j}.\]The sum $\sum_{j=1}^{n} \frac{1}{j}$ is the harmonic number $H_n$, so:
\[\sum_{j=2}^{n} \frac{1}{j} = H_n - 1.\]So the final general formula is:
\[\boxed{\mathbb{E}[L] = \frac{n+1}{n-1}\bigl(H_n - 1\bigr)}.\]This is the expected value of the smallest card in the left pile when you randomly cut a shuffled deck of (n) distinct cards into two nonempty piles.
Tail Sum Derivation
Let: $p_k = \Pr(X = k)$
Write the expectation in the usual way:
\[\mathbb{E}[X] = \sum_{k=0}^{\infty} k\,p_k.\]But each $k$ can be written as:
\[k = \underbrace{1 + 1 + \dots + 1}_{k\text{ times}}.\]So:
\[kp_k = p_k + p_k + \dots + p_k\quad (k\text{ terms}).\]Now rearrange the infinite double sum:
\[\mathbb{E}[X] = \sum_{k=1}^{\infty} p_k + \sum_{k=2}^{\infty} p_k + \sum_{k=3}^{\infty} p_k + \dots\] \[\mathbb{E}[X] = \sum_{j=1}^{\infty} \sum_{k=j}^{\infty} p_k.\]But:
\[\sum_{k=j}^{\infty} p_k = \Pr(X \ge j).\]Thus:
\[\boxed{ \mathbb{E}[X] = \sum_{j=1}^{\infty} \Pr(X \ge j) }\]Let’s now repeat this question with 52 Card Deck
I’ll assume a standard 52-card deck with ranks
$1,2,\dots,13$ (e.g. Ace=1, …, King=13), each rank appearing 4 times.
(At the end I’ll generalize so you can plug in 14 ranks if you really want.)
We use the same splitting procedure as before:
- Shuffle the deck uniformly at random.
- Choose a cut position $K$ uniformly from ${1,\dots,51}$.
- Left pile = first $K$ cards, right pile = rest.
- Let $L$ = minimum rank in the left pile.
- We want $\mathbb{E}[L]$.
Step 1 – Condition on the left pile size
Exactly like before, let:
- $K$ = number of cards in the left pile.
- $L$ = minimum rank in that pile.
We again use the law of total expectation:
\[\mathbb{E}[L] = \mathbb{E}\bigl[\mathbb{E}[L \mid K]\bigr].\]Distribution of $K$:
- The cut position is uniform on ${1,\dots,51}$, so:
\(\Pr(K = k) = \frac{1}{51},\quad k=1,\dots,51.\)
So:
\[\mathbb{E}[L] = \frac{1}{51}\sum_{k=1}^{51} \mathbb{E}[L \mid K=k].\]Now the real work is finding $\mathbb{E}[L \mid K=k]$.
Step 2 – What does the left pile look like, given $K = k$?
Given the left pile has size $K=k$:
- Before the cut, the deck is perfectly shuffled.
- The first $k$ positions are just $k$ cards chosen uniformly at random without replacement from the deck.
So, conditioned on $K=k$, the left pile is like:
“Take a sample of size $k$ without replacement from the multiset with
4 cards of rank 1, 4 of rank 2, …, 4 of rank 13.”
We want the minimum rank in that sample.
Let $Y_k$ = minimum rank in a sample of size $k$ from that multiset. Then:
\[\mathbb{E}[L \mid K = k] = \mathbb{E}[Y_k].\]Step 3 – Compute the distribution of the minimum rank in a multiset sample
This is the key combinatorial step.
We’ll work with ranks $1,\dots,13$, 4 copies each:
- Total cards: $N = 52 = 13 \cdot 4$.
- For each rank $r$, there are 4 cards.
3.1 Tail-sum formula for expectation
A very useful identity:
\[\mathbb{E}[Y_k] = \sum_{r=1}^{13} \Pr(Y_k \ge r).\]Why? Because for a positive integer-valued random variable $Y$,
\[\mathbb{E}[Y] = \sum_{r \ge 1} \Pr(Y \ge r).\]So if we can get $\Pr(Y_k \ge r)$, we’re done.
3.2 Probability that the minimum is at least (r)
Event ${Y_k \ge r}$ means:
“All cards in the sample have rank $\ge r$”
i.e. no card of rank $1,\dots,r-1$ is drawn.
Ranks $r,r+1,\dots,13$ are allowed there.
How many cards of ranks $\ge r$?
Ranks from $r$ to $13$: that’s $13 - r + 1 = 14 - r$ ranks.
Each has 4 cards →
\(\text{available cards} = 4(14 - r).\)Total cards in the deck: $52$.
To have $Y_k \ge r$, we must choose all $k$ cards from those $4(14 - r)$ cards.
So:
\(\Pr(Y_k \ge r) = \frac{\binom{4(14 - r)}{k}}{\binom{52}{k}}, \quad \text{provided } k \le 4(14 - r);\) otherwise this is 0 (you can’t choose $k$ cards out of a smaller pool).
Thus:
\[\mathbb{E}[Y_k] = \sum_{r=1}^{13} \Pr(Y_k \ge r) = \sum_{r=1}^{13} \frac{\binom{4(14 - r)}{k}}{\binom{52}{k}} \quad (\text{with the understanding terms are 0 if } 4(14-r) < k).\]This is already a perfectly valid closed form for $\mathbb{E}[L \mid K=k]$.
Step 4 – Average over all possible cut sizes $K$
Now use:
\[\mathbb{E}[L] = \frac{1}{51}\sum_{k=1}^{51} \mathbb{E}[L \mid K=k].\]Plug in the expression from above:
\[\mathbb{E}[L] = \frac{1}{51}\sum_{k=1}^{51} \sum_{r=1}^{13} \frac{\binom{4(14 - r)}{k}}{\binom{52}{k}}.\]You can write this as:
\[\boxed{ \mathbb{E}[L] = \frac{1}{51} \sum_{k=1}^{51} \sum_{r=1}^{13} \frac{\binom{4(14 - r)}{k}}{\binom{52}{k}} }\]That double sum doesn’t collapse into a neat harmonic-number expression like the “all labels distinct” case, because the repeated ranks destroy the simple ((n+1)/(k+1)) structure.
But it’s very straightforward to compute numerically.