A card grouping game: find the expected number of groups

Question

Suppose that I have a deck of $n$ cards numbered $1$ to $n$. I randomly draw the cards from the deck one by one and put them in piles according to the following rule:

1. The first drawn card forms the first pile.

2. For each subsequent card drawn, if the number on it is just smaller than the smallest number on cards in an existing pile by one, or just larger than the largest number on cards in an existing pile by one, then I will put this card on that pile.

3. If a newly drawn card cannot be put in any existing piles according to rule 2, then start a new pile with this card.

For example, if $n=6$ and the order of the cards drawn is $(2,5,1,3,6,4)$, then the piles of cards will be (step by step)

$(2)$

$(2), (5)$

$(12), (5)$

$(123), (5)$

$(123), (56)$

$(123), (456)$ or $(1234), (56)$

and I will have 2 piles.

My question is how to find the expected number of piles, $k$, I will get. My guess is $E[k] = (n+1)/3$.

Answer 1

We can calculate the expected number of new piles formed, starting with the available run $1\ldots n$, with three slightly different initial conditions:

• No initial piles (call the expected number of piles $A_n$);
• An initial pile at $0$ (call the expected number of new piles $B_n$);
• Initial piles at $0$ and $n+1$ (call the expected number of new piles $C_n$).

Clearly $A_1=A_2=1$ and $B_1=C_1=C_2=0$ and $B_2=1/2$. Beyond this, we can calculate each sequence recursively by considering how the first card can be drawn and what available runs are formed thereby. Newly formed available runs will evolve independently. With no initial piles, the result is a newly created pile and either a shortened run with one neighboring pile (if the drawn card is $1$ or $n$) or two runs with one neighboring pile:

$$ A_n=1 + \frac{2}{n}B_{n-1}+\sum_{k=1}^{n-2}\frac{1}{n}\left(B_{k}+B_{n-1-k}\right)=1+\frac{2}{n}\sum_{k=1}^{n-1}B_k. $$ With an initial pile at $0$, the result is either a shortened run with one neighboring pile (if the drawn card is $1$), or a new pile and a shortened run with two neighboring piles (if the drawn card is $n$), or a new pile and a run with two neighboring piles and a run with one neighboring pile: $$ B_n=\frac{1}{n}B_{n-1}+\sum_{k=1}^{n-2}\frac{1}{n}\left(1+C_{k}+B_{n-1}\right)+\frac{1}{n}\left(1+C_{n-1}\right)=1-\frac{1}{n}+\frac{1}{n}\sum_{k=1}^{n-1}B_k+\frac{1}{n}\sum_{k=1}^{n-1}C_k. $$ Finally, with initial piles at $0$ and $n+1$, the result is either a shortened run with two neighboring piles (if the drawn card is $1$ or $n$), or a new pile and two runs with two neighboring piles: $$ C_n=\frac{2}{n}C_{n-1}+\sum_{k=1}^{n-2}\frac{1}{n}\left(1+C_{k}+C_{n-1-k}\right)=1-\frac{2}{n}+\frac{2}{n}\sum_{k=1}^{n-1}C_k. $$ We know that $C_2=0$; let's assume, as an inductive hypothesis, that $C_k=a(k-2)$ for $2 \le k < n$ (for some fixed $n > 2$, and with the value of $a$ to be chosen later). Then $$ C_n=1-\frac{2}{n}+\frac{2}{n}\sum_{k=3}^{n-1}a(k-2)=1-\frac{2}{n}+\frac{2}{n}\left(\frac{1}{2}a(n-2)(n-3)\right)=\frac{(a(n-3)+1)(n-2)}{n}. $$ The choice $a=1/3$ gives the self-consistent result $C_n=\frac{1}{3}(n-2)$. We conclude by induction that $C_n=\frac{1}{3}(n-2)$ for all $n\ge 2$. In an exactly analogous way, we can prove by induction that $B_n=\frac{1}{2}+\frac{1}{3}(n-2)$ and (OP's result) that $$A_n=1+\frac{1}{3}(n-2)=\frac{1}{3}(n+1) \qquad {\text{for }} n\ge 2.$$

Answer 2

This is not (yet) a solution, so please don't grade this, but I need more space than is available in a comment to provide some insights:

A simple lemma: The smallest number of possible final piles is $k=1$--reached many ways, but for instance by $(1,2,3,4,\ldots,n)$. The largest number of piles is $k=n/2$--reached many ways, but for instance by ($1,3,5,7,\ldots)$.

Given a deck of $n$ cards (where $n$ is large), the number of ways to get a single final pile is bounded by $\approx n 2^{n-1}$. There are $n$ places for the first card, thereby defining the pile. Given a pile, there are only two "available" numbers that can ensure a new pile is not formed: the maximum in the pile +1 and the minimum in the pile -1. Note that this is in the large-$n$ limit, where end effects (temporary piles having a card value $1$ or having card value $n$ mean that only one slot is available). After all, once either the $1$ card or the $n$ card is drawn in this scenario, there is but a single sequence (leading sequentially from the current "open" boundary of the pile to either $1$ or $n$) that will preserve a single pile.

The number of ways to get the maximum $n/2$ piles is bounded by $\approx n (n/2-1)(n/2-2)\ldots 1 \cdot (n/2)!$. There are $n$ slots for the first card. Suppose the first card happens to be odd valued. Then the only slots available (in this case) are the remaining odd values. There are approximately $n/2-1$ of them. Once the next card is chosen (and must be odd), there are are $(n/2-2)$ available slots. And so on until all the odd slots are filled. Then there are the remaining $n/2$ even cards which can be placed in the remaining unused $n/2$ even places in $(n/2)!$ ways.

Of course, the total number of ways in which to draw cards is $n!$.