Top-to-random shuffles and generalized Stirling numbers

In a top-to-random shuffle one takes the top card of a deck of n cards and inserts it into a position chosen uniformly at random. This is not a practical way to shuffle: as in the coupon collector problem, it takes about n \log n shuffles to have a good chance of having moved every card, so one expects at least this number to be necessary to get good mixing. In fact, a careful analysis shows that it takes n \log n + cn shuffles for the probability distribution on arrangements of the n cards to be exponentially close by \mathrm{e}^{-c} (up to a small error term) to the uniform distribution. So for 52 cards we need about 200 shuffles. By contrast, a famous result, also due to Diaconis, says that 7 riffle shuffles suffice to get good mixing on a deck of 52 cards. However, there is at least one sense in which top-to-random still wins: if we count each top-to-random shuffle as moving one card (i.e. thinking physically, and ignoring that, mathematically, an insertion into position k induces a k-cycle on the top k cards) then the snail-paced top-to-random shuffle achieves its mixing by moving only 200 cards, whereas each riffle shuffle moves (in the same physical sense) 52 cards each time.

The top-to-random shuffle is also related to the optimal Knuth shuffle: at time t do a card-in-position-t-from-top-to-any-position-weakly-below shuffle. After n-1 steps the deck is uniformly mixed. Convincing anyone closely watching proceedings that this is true is left as an exercise for the shuffler.

In this paper with John Britnell we defined several generalized Stirling and Bell numbers related to the top-to-random shuffle. They’ve now been submitted to OEIS. The purpose of this post is to make a record of the numbers and record one curious observation.

The first batch of sequences, including the two already present, are, in the notation of the paper:

  • A048993 \genfrac\{\}{0pt}{}{t}{n}: number of set partitions of \{1,\ldots,t\} into exactly n parts. (A Stirling number of the second kind.)
  • A102661 B_t(n): number of set partitions of \{1,\ldots,t\} into at most n parts. (A generalized Bell number.)
  • A261139 \genfrac\{\}{0pt}{}{t}{n}': number of set partitions of \{1,\ldots,t\} into exactly n parts such that no part contains two consecutive numbers, or both 1 and t.
  • A261137 B'_t(n): number of set partitions of \{1,\ldots,t\} into at most n parts with the same conditions as A261139.

The connection with shuffling is most easily explained by using the inverse random-to-top shuffles. Take a deck of n cards, with card 1 at the top and card n at the bottom, and a set partition of \{1, \ldots, t\} into exactly n parts, say A_1, \ldots, A_n. There is a unique way to assign a card number c_j to each part A_j such that A_j is the set of times when card c_j is lifted to the top by a sequence of t random-to-top shuffles that overall leave the deck invariant. To see this, observe that the final card lifted must be card 1. Hence the part containing t must get label 1. Now continue inductively, assigning label k to the part containing the greatest number not already labelled by 1 up to k-1. It is not hard to see that \genfrac\{\}{0pt}{}{t}{n}' counts the analogous sequences where the identity permutation is forbidden.

The second batch of sequences deals with top-to-random (or random-to-top) shuffles that may flip the card moved. The corresponding sequences were all new to OEIS.

  • 2^{t-n}\genfrac\{\}{0pt}{}{t}{n}^\dagger: number of set partitions of \{1,\ldots,t\} into exactly n parts with an even number of elements in each part distinguished by marks. (Not submitted, since its just a scaling of the usual Stirling number.)
  • A261275 B^\dagger_t(n): number of set partitions of \{1,\ldots,t\} into at most n parts with an even number of elements in each part distinguished by marks.
  • A261318 \genfrac\{\}{0pt}{}{t}{n}^{\dagger\prime}: number of set partitions of \{1,\ldots,t\} into exactly n parts, with an even number of elements in each part distinguished by marks, and such that no part contains two consecutive numbers (each unmarked), or both 1 and t (each unmarked).
  • A261319 B^{\dagger\prime}_t(n): number of set partitions of \{1,\ldots,t\} into at most n parts with the same conditions as A261318.

Now for the curious observation. By Equation (5) in Section 6 of the paper, we have

\genfrac\{\}{0pt}{}{t}{n}' = \frac{(-1)^{t+n}}{n!} + \frac{1}{n!}\sum_{k=0}^{n-1} (-1)^k \binom{n}{k} (n-k-1)^t.

It easily follows by summing two series that the exponential generating function for the primed Stirling numbers is

\sum_{t=0}^\infty \sum_{n=0}^\infty \genfrac\{\}{0pt}{}{t}{n}' \frac{x^t}{t!} y^n = \mathrm{e}^{-x} \exp \bigl( y(\mathrm{e}^x-1)\bigr).

Let \genfrac\{\}{0pt}{}{t}{n}^{\ge 2} be the number of set partitions of \{1,\ldots,t\} into exactly n parts, each of size at least two. The exponential generating function for these numbers is

\sum_{t=0}^\infty \sum_{n=0}^\infty \genfrac\{\}{0pt}{}{t}{n}^{\ge 2} \frac{x^t}{t!} y^n =  \exp \bigl( y(\mathrm{e}^x-x-1)\bigr).

(The only way I can recommend to prove this is to read Chapter 3 of Wilf’s wonderful book generatingfunctionology until it becomes obvious.)

Observe that on setting y=1, the two e.g.f.s become equal to \exp (\mathrm{e}^x -x-1). Hence

B'_t(t) = B^{\ge 2}_t(t),

where B^{\ge 2}_t(n) = \sum_{m=0}^n \genfrac\{\}{0pt}{}{t}{m}^{\ge 2} is the generalized Bell number corresponding to \genfrac\{\}{0pt}{}{t}{n}^{\ge 2}. So, in some asymptotic sense, set partitions satisfying the `no-cyclically-consecutive numbers’ restriction behave like set partitions into parts of size at least two.

This can be made more precise as follows. The e.g.f. for the primed Stirling numbers may be written as

\sum_{t=0}^\infty \sum_{n=0}^\infty \genfrac\{\}{0pt}{}{t}{n}' \frac{x^t}{t!} y^n = \sum_{n=0}^\infty y^n G_n(x)

where G_n(x) = \mathrm{e}^{-x} (\mathrm{e}^x-1)^n/n!. Similarly the e.g.f. for the Stirling numbers for parts of size at least two may be written as

\sum_{t=0}^\infty \sum_{n=0}^\infty \genfrac\{\}{0pt}{}{t}{n}^{\ge 2} \frac{x^t}{t!} y^n = \sum_{n=0}^\infty y^n H_n(x)

where H_n(x) = (\mathrm{e}^x-x-1)^n/n!. Now, since

B'_t(n) = B'_t(t) = B^{\ge 2}_t(t) = B^{\ge 2}_t(n)

whenever t \le n, we have

\sum_{m=0}^n G_m(x) = \sum_{m=0}^n H_m(x) + O(x^{n+1}).

for all n \in \mathbb{N}. Letting n \rightarrow \infty we recover the equality \sum_{m=0}^\infty G_m(x) = \sum_{m=0}^\infty H_m(x) = \exp(\mathrm{e}^x-x-1) already seen. The identity above seems surprisingly unobvious analytically, but maybe I’m missing an easy argument.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: