#  No Feedback? No Worries!
The art of guessing the right card

Tipaluck Krityakierne1 Thotsaporn Aek Thanatipanonda2

(1Department of Mathematics, Faculty of Science, Mahidol University, Bangkok,
Thailand
2Science Division, Mahidol University International College, Nakhon Pathom,
Thailand
)

###### Abstract

In 1998, Ciucu published “No-feedback card guessing for dovetail shuffles”, an
article which gives the optimal guessing strategy for $n$ cards ($n$ even)
after $k$ riffle shuffles whenever $k>2\log_{2}\left(n\right)$. We discuss in
this article the optimal guessing strategy and the asymptotic (in $n$)
expected number of correct guesses for any fixed $k\geq 1$. This complements
the work achieved two decades ago by Ciucu.

Keywords: card guessing; no feedback; optimal strategy; discrete probability;
generating function.

## The $\cancelto{\bf{math}}{\bf{art}}$ of guessing it right

Over the past several decades, there have been studies and established
theories attempting to tackle many aspects of the Card Guessing Game, e.g.
finding the optimal or worst case strategies, identifying the distribution and
the expected number of correct guesses, etc. You might have seen a dealer
performing “riffle shuffles”, perhaps at the Vegas casinos or at the basement
poker nights. Before play can begin, the cards have to be shuffled multiple
times to mix the cards randomly. [Bayer and Diaconis (1992)] proved the famous
result that after giving the deck seven riffle shuffles, all the 52 cards will
be equally likely to be in one position as in another.

#### Card Guessing Game!

Start: To start, you will need: • A dealer and a player • 1 deck of $mn$ cards
ordered $\underbrace{1,...,1}_{m\text{
copies}},\dots,\underbrace{n,...,n}_{m\text{ copies}}$ How to Play? • The
dealer shuffles the deck according to some Shuffling Rule $\mathcal{R}$. •
Cards are then dealt from the top, and the player guesses each card one at a
time. • Play continues until the entire deck has been gone through. Scoring:
The player earns 1 point for each correct guess. Feedback: The player is given
Feedback $\mathcal{F}\in$ {Complete, Partial, No} after each guess. Object of
the Game: The object of the game is to earn as many points as possible.

Let us take a look at a quick guide of how the game is played. As shown above,
the player may or may not receive feedback from the dealer depending on the
rule. The complete feedback game is similar to blackjack for which the dealer
reveals the card after each play (guess). The player thus can adjust their
strategy of play, to improve his odds of guessing the next cards correctly,
according to the cards they have already seen. For the no-feedback game,
however, as no feedback is given, the player has to guess all the cards
beforehand. To increase the probability of guessing the correct number, it is
possible to guess the same card number for cards in different positions.
Summary of terminologies and definitions related to the card guessing games
are now given.

Terminologies

  * •

Level of feedback: The player in the No Feedback variant is informed nothing
about the correctness of his or her guess after each guess. In the Complete
Feedback variant, on the other hand, the value of the card will be revealed to
the player after each guess. Finally, in the Partial Feedback variant (also
known as Yes/No Feedback), the player is informed whether his or her guess was
correct after each guess, but the value of the card will not be revealed in
case of incorrect guesses.

  * •

Card shuffling: If Uniform Shuffle is applied, the shuffled deck starts in a
randomly shuffled state. Applying Top to Random Shuffle means the dealer takes
the top card and places it back into the deck at position $i$ with probability
$p_{i}$. For Riffle Shuffle (also known as GSR Shuffle or Dovetail Shuffle),
the dealer cuts the deck into two piles before interleaving the two back into
one. Beginning with an ordered set (1 increasing subsequence), a single riffle
shuffle will lead to a permutation with at most 2 increasing subsequences. The
parameter $k$ for the riffle and top to random shuffles represents the number
of times the deck has been shuffled. In particular, $k=1$ means a single
shuffle.

  * •

Optimal (Best) versus Optimal Misère Strategy: A given strategy is said to be
Optimal (or Best) Strategy if the strategy achieves the maximum expected
number of correct guesses, where the maximum is taken over all strategies.
Optimal Misère (or Worst-case) Strategy, which achieves the minimum expected
number, is defined analogously [Diaconis et al. (2020)].

We summarize the game variants in the literature, characterized by the
shuffling rules, the level of feedback, and the number of copies of each card
type in Table 1.

Table 1: Variants of the Card Guessing Game Authors | Shuffling ${\cal R}$ | #Copies | Feedback ${\cal F}$ | Contribution
---|---|---|---|---
[Diaconis and Graham (1981)] | uniform | 1, $m$ | complete ($m>1$), | distribution of the number
|  |  | partial ($m=1$) | of correct guesses,
|  |  |  | optimal and misère strategies
[Diaconis et al. (2020)] | uniform | $m$ | partial | expected number of
and [Diaconis et al. (2022)] |  |  |  | correct guesses
[Bayer and Diaconis (1992)] |  $k$\- riffle | 1 | complete | a sharp bound on the number
|  |  |  | of shuffles to random deck
[Ciucu (1998)] |  $k$\- riffle | 1 | no | best strategy for $k=1$
|  |  |  | and $k>2\log_{2}\left(n\right)$, $n$ even,
|  |  |  | expected number of correct guesses
▶ Present work |  $k$\- riffle | 1 | no | best strategy for any fixed $k\geq 1$,
|  |  |  | expected number of correct guesses
[Pehlivan (2010)] |  $k$\- top to | 1 | no | best strategy for $k>4n\log(n)+cn$,
| random |  |  |  $n$ even
[Liu (2021)] |  $1$\- riffle | 1 | complete | expected number of
|  |  |  | correct guesses
[Krityakierne et al. (2021)] |  $1$\- riffle | 1 | complete | (refined) expected number
|  |  |  | of correct guesses, higher moments

Our contribution

As specified in the table, our contribution in this paper builds on and fills
gaps of the no-feedback card guessing game with riffle shuffles in the
literature. Specifically, [Ciucu (1998)] proved that, given a deck of $n$
cards ($n$ even), the best no-feedback guessing strategy after $k$ riffle
shuffles when $k>2\log_{2}\left(n\right)$ is to guess card number 1 for the
first half and card number $n$ for the second half of the deck. The expected
number of correct guesses in this case is therefore at most 2. By using this
strategy, Ciucu showed that after shuffling the cards the number of order
$\log_{2}\left(n\right)$ times, the deck is well mixed, i.e. close to randomly
distributed deck. In addition, Ciucu also gave the strategy for the other
extreme case, $k=1$. In this work, we focus exclusively on the analysis of
games for a general but finite value of $k\geq 1$, which complements work by
[Ciucu (1998)] in the no-feedback card guessing game with riffle shuffle
variant.

### Time to play

Let us consider now a strategy of guessing the cards after the deck is riffle-
shuffled $k$-times, for $k\geq 1$, following these rules:

  * •

At the beginning, a deck of $n$ cards is ordered $1,2,3,\dots,n$.

  * •

The dealer riffle shuffles the deck $k$ times.

  * •

No feedback is given after each guess.

Let’s start with $k=1$, a single riffle shuffle

Take out a deck of $n$ cards, cut it into two piles (possible to have 0 cards
in one of the piles), and interleave the cards from two piles in any possible
way. What are all possible permutations you can generate?

Figure 1: Examples of all possible permutations after 1-time riffle shuffling
for $n=1,2,3,4$. For each card position, the color indicates the most likely
number.

For instance, when $n=1$, $\\{1\\}$ is the only possible permutation, but with
multiplicity 2, generated from the piles $\left(\\{1\\},\\{\\}\right)$ or
$\left(\\{\\},\\{1\\}\right)$. In general, there are $2^{n}$ possibilities,
among which $n+1$ are the identity permutation (having one increasing
subsequence), and the others are of two increasing subsequences (with
multiplicity 1). We give a few examples in Figure 1. For each card position,
the color indicates the most likely number to show up in that position.

What number is most likely to show up in position $i$?

We record the frequency of a card in position $i$ being number $j$ in the
matrix $M=\left(m_{i,j}\right).$ Then, the row $i$ of the matrix corresponds
to position $i$ of the card. The column $j$ of the matrix corresponds to card
number $j$. For example $m_{1,3}$ gives the number of times the top card is 3.

When $n=4$, the matrix $M$ is given by

$M=\left[\begin{array}[]{cccc}\framebox{\bf 9}&3&3&1\\\ 4&\framebox{\bf
6}&4&2\\\ 2&4&\framebox{\bf 6}&4\\\ 1&3&3&\framebox{\bf 9}\\\
\end{array}\right].$

Probability matrix for $k=1$ shuffle, $P^{(1)}$

For a fixed $n$, we define a probability matrix for $k=1$ shuffle,
$P^{(1)}:=M/2^{n}$. Let $a(i,j,n):=\dfrac{m_{i,j}}{2^{n}}$ be the $(i,j)$
element of $P^{(1)}$. Then, $a(i,j,n)$ represents the probability of a card in
position $i$ being number $j$. It turns out that $a(i,j,n)$ has an exact
formula:

$a(i,j,n)=\dfrac{1}{2^{i}}\binom{i-1}{j-1}+\dfrac{1}{2^{n-i+1}}\binom{n-i}{j-i}.$
(1)

This formula was mentioned and proved earlier in [Ciucu (1998)]. We notice
that the first term is non-zero when $i\geq j$ and the second term is non-zero
when $j\geq i.$ The row sum and column sum are both equal to $1,$ i.e.
$P^{(1)}$ is a doubly stochastic matrix. This is easy to show in one
direction, but not so easy to show in the other direction:

$\sum_{j=1}^{n}a(i,j,n)=\dfrac{1}{2^{i}}\sum_{j=1}^{i}\binom{i-1}{j-1}+\dfrac{1}{2^{n-i+1}}\sum_{j=i}^{n}\binom{n-i}{j-i}=\dfrac{1}{2}+\dfrac{1}{2}=1,$

and

$\sum_{i=1}^{n}a(i,j,n)=\sum_{i=j}^{n}\dfrac{1}{2^{i}}\binom{i-1}{j-1}+\sum_{i=1}^{j}\dfrac{1}{2^{n-i+1}}\binom{n-i}{j-i}=1.$

Also, the symmetic property is easily observed through the matrix $P^{(1)}$:

$a(i,j,n)=a(n+1-i,n+1-j,n).$ (2)

Guessing strategy exists. Do not blind guessing!

As we now have a formula for the probability that each number $j$ shows up in
the position $i$ stored in the matrix $P^{(1)}$, it is possible to find the
optimal guessing strategy that gives the maximum expected number of correct
guesses. Since the first row of $P^{(1)}$ corresponds to the top card, the
second row the second card, and so on, it is easily shown that one should pick
the index of the largest value from each row $i$ as a best guess for the card
in the position $i$, for $i=1,\dots,n$.

The expected number of correct guesses

Let $X^{\cal{G}}$ be a random variable representing the number of correct
guesses of an $n$-card deck if the player uses strategy $\cal{G}$. To find the
expectation $E\left[X^{\cal{G}}\right]$, we consider

$X^{\cal{G}}_{i}=\begin{cases}\begin{array}[]{c}1\\\
0\end{array}&\begin{array}[]{c}\text{if the player guesses the }i\text{th
position correctly}\\\ \text{otherwise.}\end{array}\end{cases}$

Since

$\displaystyle E\left[X^{\cal{G}}\right]$
$\displaystyle=\sum_{i=1}^{n}E\left[X^{\cal{G}}_{i}\right]=\sum_{i=1}^{n}P\left(X^{\cal{G}}_{i}=1\right)\leq\sum_{i=1}^{n}\max_{1\leq
j_{i}\leq n}a(i,j_{i},n),$

the optimal strategy can be defined as follows.

Optimal guessing strategy $\cal{G}^{*}$
For a fixed row $i$ ($1\leq i\leq n$) of the matrix $P^{(1)}$, let
$j_{i}^{*}:=\operatorname*{arg\,max}_{j}a(i,j,n)$. Under the optimal guessing
strategy $\cal{G}^{*}$, the player guesses number $j_{i}^{*}$ for the card
position $i$, and in this case,
$E\left[X^{\cal{G}^{*}}\right]=\sum_{i=1}^{n}a\left(i,j^{*}_{i},n\right).$

For example, when $n=4$, the largest number from each row $i$ of the matrix
$M$ (those numbers having a small square around) tells us that $j_{1}^{*}=1$,
$j_{2}^{*}=2$, $j_{3}^{*}=3$, and $j_{4}^{*}=4$. Thus, the optimal strategy is
to guess number 1, 2, 3, 4, respectively.

In general, as we shall see later in our main theorem (Theorem 9, in its
simplest case) that for a 1-time shuffled deck, the optimal strategy is to
guess the top half of the deck with sequence

$1,2,2,3,3,4,4,\dots$

and guess the bottom half in the reverse manner, i.e.

$\dots,n-3,n-3,n-2,n-2,n-1,n-1,n.$

To end the section, we restate a result from [Ciucu (1998)] regarding the
value of $E\left[X^{\cal{G}^{*}}\right]$ for $k=1$. The main result of our
paper is to obtain similar results, but for any $k\geq 1$ times riffle
shuffles.

######  Theorem 1 (Ciucu, 1998).

For a deck of $n$ cards, given that the no-feedback guessing of the whole deck
after 1-time shuffle goes according to the best strategy, the average number
of correct guesses is $\dfrac{2\sqrt{n}}{\sqrt{\pi}}+\mathcal{O}(1).$

##  1 Preview: the $k$-time riffle shuffles

0%

We now turn to a general case in which a deck of $n$ cards is given $k>1$
times riffle shuffles. Our goal is to obtain a similar statement to Theorem 1
for asymptotic $n$.

Probability matrix for general $k$ shuffles, $P^{(k)}$

Analogous to $a(i,j,n)$ for the case $k=1$, we let $a_{i,j}^{(k)}$ denote the
probability that the card number $j$ will show up at position $i$ after giving
the deck $k$ riffle shuffles (where we now make $i,j$ subscripts, and suppress
$n$ from $a_{i,j}^{(k)}$ for simplicity). The probabilty matrix $P^{(k)}$ for
$k$ shuffles is subsequently defined by
$\left(P^{(k)}\right)_{i,j}=a_{i,j}^{(k)}$.

Since the transpose matrix $\left(P^{(1)}\right)^{T}$ is a probability
transition matrix, it follows that $P^{(k)}=\left(P^{(1)}\right)^{k}$, the
$k$-th power of the matrix, and so

$a_{i,j}^{(k)}=\sum_{s_{1}=1}^{n}\dots\sum_{s_{k-1}=1}^{n}a_{i,s_{1}}^{(1)}a_{s_{1},s_{2}}^{(1)}\dots
a_{s_{k-1},j}^{(1)}.$ (3)

Similar to the case $k=1$, the expected number of correct guesses under the
optimal strategy $\cal{G}^{*}$ is

$E\left[X^{\cal{G}^{*}}\right]=\sum_{i=1}^{n}a_{i,j_{i}^{*}}^{(k)}.$ (4)

Thus, finding the optimal guessing strategy boils down to determining the
optimal strategy $j_{i}^{*}$ which maximizes $a_{i,j}^{(k)}$ for each
$i=1,\dots,n$.

Caution! Even though we have a closed-form expression for $a_{i,j}^{(1)}$ as
given in Equation 1, simply plugging the closed-form formula in Equation 3 in
attempt to solving for the maximizer of $a_{i,j}^{(k)}$ directly is
unfortunately not tractable.

Before we dive into the details of the proof, we give an overview of the proof
procedure, together with the accompanying Figure 2 depicting the p.m.f.
$a_{60,j}^{(3)}$ (i.e. $i=60,k=3$) for $n=200$ cards. Here, we want to find
the maximizer index $j_{60}^{*}$ of the p.m.f. In practice, the expression of
the p.m.f. (the red line) is not tractable. We show later that the p.m.f. is
indeed a mixture model with $2^{k}$ components, whose expressions are
tractable via the generating functions.

Proof procedure

Setup: We fix row $i$ of matrix $P^{(k)}$, and let $J_{i}$ be a random
variable whose probability mass function (p.m.f.) is given by
$P(J_{i}=j)=a_{i,j}^{(k)},\;\;\;{\text{ for }}j=1,\dots,n.$ Goal: Find the
index $j_{i}^{*}$ that maximizes $P(J_{i}=j)$.
Procedure: The main steps in the proof proceed as follows: 1. Decompose the
p.m.f. of $J_{i}$ into a mixture model with $2^{k}$ components:
$P(J_{i}=j)=\frac{1}{2^{k}}\sum_{t=1}^{2^{k}}p_{L_{t}}(j).$ 2. Define, for
each $p_{L_{t}}$, the probability generating function (p.g.f.):
$F_{L_{t}}(x)=\sum_{j=1}^{n}p_{L_{t}}(j)\cdot x^{j}.$ 3. Recover the
distribution $p_{L_{t}}$ through the p.g.f. $F_{L_{t}}(x)$. 4. Find, for $n$
large, the location and the height of the peak of $p_{L_{t}}$. 5. Show, for
$n$ large, that the components $p_{L_{1}},\dots,p_{L_{2^{k}}}$ of the mixture
model are (almost) non-overlapping. Maximizer: The location of the highest
peak among the $2^{k}$ components is the solution $j_{i}^{*}$.

Figure 2:  Example ($k=3$, $n=200$, $i=60$): (a) the p.m.f. of the mixture
model $J_{60}$;
(b) the decomposed components of the mixture model,
$P(J_{60}=j)=\frac{1}{8}\sum_{t=1}^{8}p_{L_{t}}(j)$

##  2 Game start: the generating function of $p_{L}$

13%

As outlined in the proof procedure, we let $i=1,\dots,n$ be fixed, and focus
exclusively on the $i$th row of the matrix $P^{(k)}$ whose p.m.f. is given by

$P(J_{i}=j)=a_{i,j}^{(k)},\,\,\,j=1,\dots,n.$

We start by decomposing $a_{i,j}$ ($k=1$):

$a_{i,j}=\dfrac{1}{2}[b^{(1)}_{i,j}+b^{(2)}_{i,j}],$ (5)

where

$b^{(1)}_{i,j}:=\dfrac{1}{2^{i-1}}\binom{i-1}{j-1},\qquad\qquad
b^{(2)}_{i,j}:=\dfrac{1}{2^{n-i}}\binom{n-i}{j-i}.$

In general, for $k\geq 1$, we decompose $a_{i,j}^{(k)}$ into the sum of
$2^{k}$ possible products of $b_{i,j}^{(l)}$. That is, we write

$a_{i,j}^{(k)}=\dfrac{1}{2^{k}}\sum_{L}p_{L}(j),$ (6)

where $L$ is the list of length $k$ whose entries are either 1 or 2,

$p_{L}(j):=\sum_{s_{1}=1}^{n}\dots\sum_{s_{k-1}=1}^{n}b^{(L[1])}_{i,s_{1}}b^{(L[2])}_{s_{1},s_{2}}\dots
b^{(L[k])}_{s_{k-1},j},$ (7)

and $L[l]$ refers to the $l$th element of $L$.

For example, for $k=2,$

$a_{i,j}^{(2)}=\dfrac{1}{4}\left[p_{[1,1]}(j)+p_{[2,1]}(j)+p_{[1,2]}(j)+p_{[2,2]}(j)\right],$

where

$\displaystyle p_{[1,1]}(j)$
$\displaystyle=\sum_{s=1}^{n}b^{(1)}_{i,s}b^{(1)}_{s,j}=\sum_{s=1}^{n}\dfrac{1}{2^{i-1}}\binom{i-1}{s-1}\dfrac{1}{2^{s-1}}\binom{s-1}{j-1},$
$\displaystyle p_{[2,1]}(j)$
$\displaystyle=\sum_{s=1}^{n}b^{(2)}_{i,s}b^{(1)}_{s,j}=\sum_{s=1}^{n}\dfrac{1}{2^{n-i}}\binom{n-i}{s-i}\dfrac{1}{2^{s-1}}\binom{s-1}{j-1},$
$\displaystyle p_{[1,2]}(j)$
$\displaystyle=\sum_{s=1}^{n}b^{(1)}_{i,s}b^{(2)}_{s,j}=\sum_{s=1}^{n}\dfrac{1}{2^{i-1}}\binom{i-1}{s-1}\dfrac{1}{2^{n-s}}\binom{n-s}{j-s},$
$\displaystyle p_{[2,2]}(j)$
$\displaystyle=\sum_{s=1}^{n}b^{(2)}_{i,s}b^{(2)}_{s,j}=\sum_{s=1}^{n}\dfrac{1}{2^{n-i}}\binom{n-i}{s-i}\dfrac{1}{2^{n-s}}\binom{n-s}{j-s}.$

Another example for $k=3$, $L=[1,1,2]$ leads to

$p_{L}(j)=\sum_{s_{1}=1}^{n}\sum_{s_{2}=1}^{n}b^{(1)}_{i,s_{1}}b^{(1)}_{s_{1},s_{2}}b^{(2)}_{s_{2},j}=\sum_{s_{1}=1}^{n}\sum_{s_{2}=1}^{n}\dfrac{1}{2^{i-1}}\binom{i-1}{s_{1}-1}\dfrac{1}{2^{s_{1}-1}}\binom{s_{1}-1}{s_{2}-1}\dfrac{1}{2^{n-s_{2}}}\binom{n-s_{2}}{j-s_{2}}.$

Generating function of $p_{L}$

The expression of $p_{L}$ in Equation 7 initially involves $(k-1)$-nested
binomial sum, for which we have no means of simplifying. The crux of our
proposed approach is to find the generating function of $p_{L}$, giving rise
to $k$-nested sum. After reordering the summation by moving the outermost sum
(the summation over index $j$) to innermost, and evaluating the summations
from the inside (that of the index $j$) to the outside (those of
$s_{k-1},\dots,s_{1}$), fortunately, we obtain a very simple generating
function for all $k\geq 1$.

We define the generating function by

$F_{L}(x)=\sum_{j=1}^{n}p_{L}(j)\cdot x^{j}.$ (8)

######  Remark 1.

$F_{L}(x)$ is a valid probability generating function as $F_{L}(1)=1.$ This
also ensures that each $p_{L}$ in Equation 6 is a valid probability mass
function.

Let us look at some examples of $F_{L}(x)$:

  * •

for $k=0$,

$F_{[\,\,]}(x)=x^{i}.$

This is a trivial case. When cards are not shuffled, the probability that the
card in position $i$ is $i$ is 1.

  * •

for $k=1$,

$F_{[1]}(x)=(0x+1)^{n-i}\left(\dfrac{x}{2}+\dfrac{1}{2}\right)^{i-1}x,\qquad
F_{[2]}(x)=\left(\dfrac{x}{2}+\dfrac{1}{2}\right)^{n-i}\cdot\left(x+0\right)^{i-1}x.$

  * •

for $k=2$,

$F_{[1,1]}(x)=(0x+1)^{n-i}\left(\dfrac{x}{4}+\dfrac{3}{4}\right)^{i-1}x,\qquad
F_{[2,1]}(x)=\left(\dfrac{x}{4}+\dfrac{3}{4}\right)^{n-i}\left(\dfrac{x}{2}+\dfrac{1}{2}\right)^{i-1}x,$
$F_{[1,2]}(x)=\left(\dfrac{x}{2}+\dfrac{1}{2}\right)^{n-i}\left(\dfrac{3x}{4}+\dfrac{1}{4}\right)^{i-1}x,\qquad
F_{[2,2]}(x)=\left(\dfrac{3x}{4}+\dfrac{1}{4}\right)^{n-i}\left(x+0\right)^{i-1}x.$

Hooray! $F_{L}(x)$ has a nice simple pattern

It is utterly important that $F_{L}(x)$ has a simple pattern from which the
underlying structure of the problem can be uncovered. To keep track of the
pattern, we define a functional notation:

$g(a,b)=[ax+(1-a)]^{n-i}\cdot[bx+(1-b)]^{i-1}\cdot x.$ (9)

With this notation, the function $F_{L}(x)$ for $k=0,1$ can be expressed as

  * •

for $k=0$,

$F_{[\,\,]}(x)=g(0,1).$

  * •

for $k=1$,

$F_{[1]}(x)=g\left(0,\dfrac{1}{2}\right),\;\
F_{[2]}(x)=g\left(\dfrac{1}{2},1\right).$

Figure 3:  A bisection tree structure. Each node of depth $k$ represents
$F_{L_{t}}(x)$ for $t=1,2,\dots,2^{k}$.

For general $k\geq 1$, a bisection tree in Figure 3 illustrates the
connections between the expressions $F_{L}(x)$ of the $k$ and $k+1$ shuffles.
At any subtree, the argument $(a,b)$ for the function $g(\cdot)$ of the parent
node is bisected, yielding the arguments for the left $(a,\frac{a+b}{2})$ and
the right $(\frac{a+b}{2},b)$ child nodes. It is important to note that the
parent’s index $L_{t}$ is expanded by adding the first entry (either 1 or 2)
to create the child’s indices, i.e. the list indices $\left[1,L_{t}\right]$
and $\left[2,L_{t}\right]$ for the first and second child nodes, respectively.

Let us state and prove this observation.

######  Theorem 2 (Generating functions).

Let $g(a,b)=[ax+(1-a)]^{n-i}\cdot[bx+(1-b)]^{i-1}\cdot x.$ For any given
$k\geq 1$, and the list indices $L_{1},L_{2},\dots,L_{2^{k}}$,

$F_{L_{t}}(x)=g\left(\dfrac{t-1}{2^{k}},\dfrac{t}{2^{k}}\right),$

for $t=1,2,\dots,2^{k}$

We use the following lemma to find the sum of the terms in $F_{L}(x)$
recursively.

######  Lemma 3.

Assume $f(i)=A^{n-i}B^{i-1}x$ where $A=ax+(1-a)$ and $B=bx+(1-b)$. Then,

$T_{1}(f):=\sum_{s=1}^{i}\dfrac{1}{2^{i-1}}\binom{i-1}{s-1}f(s)=A^{n-i}\left(\dfrac{A+B}{2}\right)^{i-1}x;$
$T_{2}(f):=\sum_{s=i}^{n}\dfrac{1}{2^{n-i}}\binom{n-i}{s-i}f(s)=\left(\dfrac{A+B}{2}\right)^{n-i}B^{i-1}x.$

###### Proof.

First, it is easy to show that

$\sum_{s=1}^{i}\dfrac{1}{2^{i-1}}\binom{i-1}{s-1}x^{s-1}=\left(\dfrac{x}{2}+\dfrac{1}{2}\right)^{i-1}$

and

$\sum_{s=i}^{n}\dfrac{1}{2^{n-i}}\binom{n-i}{s-i}x^{s-1}=\left(\dfrac{x}{2}+\dfrac{1}{2}\right)^{n-i}\cdot\left(x+0\right)^{i-1}.$

For the general case,

$\displaystyle\sum_{s=1}^{i}\dfrac{1}{2^{i-1}}\binom{i-1}{s-1}f(s)$
$\displaystyle=\sum_{s=1}^{i}\dfrac{1}{2^{i-1}}\binom{i-1}{s-1}A^{n-1}\left(\dfrac{B}{A}\right)^{s-1}x$
$\displaystyle=A^{n-1}x\left(\dfrac{A+B}{2A}\right)^{i-1},\;\ \;\ \text{from
the above identity}$
$\displaystyle=A^{n-i}\left(\dfrac{A+B}{2}\right)^{i-1}x.$

This proves the first claim regarding $T_{1}(f)$. The second claim can be done
similarly. ∎

We now return to the proof of Theorem 2.

###### Proof of Theorem 2.

We prove by induction on $k=|L|$. For the base case, we verify that
$F_{[\,\,]}(x)=x^{i}$, is indeed $g(0,1)$. For the induction step, let
$L^{\prime}=[l_{k-1},..,l_{2},l_{1}]$ and
$L=[l_{k},l_{k-1},...,l_{2},l_{1}]=[l_{k},L^{\prime}]$ . Assume
$f:=F_{L^{\prime}}(x)=g\left(\dfrac{t-1}{2^{k-1}},\dfrac{t}{2^{k-1}}\right)$.
Then it follows from Lemma 3 that
$F_{L}(x)=T_{1}(f)=g\left(\dfrac{2t-2}{2^{k}},\dfrac{2t-1}{2^{k}}\right)$ if
$l_{k}=1$ and
$F_{L}(x)=T_{2}(f)=g\left(\dfrac{2t-1}{2^{k}},\dfrac{2t}{2^{k}}\right)$ if
$l_{k}=2.$ ∎

Open Problem 1: Find a combinatorial interpretation for the generating
function $F_{L}(x)$ of this card guessing problem.

##  3 Distribution of $p_{L}$ when $n$ is large

47%

Exact distribution of $p_{L}$

Through the formula of $g(a,b)$ in Theorem 2, it is easy to see that $p_{L}$
is the sum of two independent binomial random variables and a constant. The
following corollary formally states the distribution of $p_{L}$, and
eventually the exact distribution of $a_{i,j}^{(k)}$.

######  Corollary 4.

For any given $k\geq 1$ and $L_{1},L_{2},\dots,L_{2^{k}}$, let $S_{L_{t}}$ be
a random variable whose probability generating function is given by
$F_{L_{t}}(x)$ defined in Theorem 2. Then,

$S_{L_{t}}\sim B_{1}+B_{2}+1,$

where $B_{1}\sim\text{Binomial}\left(n-i,\dfrac{t-1}{2^{k}}\right)$ and
$B_{2}\sim\text{Binomial$\left(i-1,\dfrac{t}{2^{k}}\right)$}$ are independent.
In other words, $p_{L_{t}}$ follows a Poisson Binomial distribution with
success probabilities equal to

$\underbrace{\dfrac{t-1}{2^{k}},...,\dfrac{t-1}{2^{k}}}_{n-i\text{
times}},\underbrace{\dfrac{t}{2^{k}},...,\dfrac{t}{2^{k}}}_{i-1\text{
times}},1.$

Hence, for fixed values of $n,i,k$, the distribution
$\\{a_{i,j}^{(k)}:j=1,\dots,n\\}$ is a mixture of $2^{k}$ components of
Poisson Binomials.

######  Example.

To better visualize the distribution, Figure 4 illustrates the p.m.f. for the
case $k=2$ shuffles when $i=15$ and $n=40$.

Figure 4: Probability mass functions $p_{[1,1]}$, $p_{[2,1]}$, $p_{[1,2]}$,
$p_{[2,2]}$ for $i=15$ and $n=40$

In this case, the distribution of each random variable is

$S_{[1,1]}\sim\text{Binomial$\left(14,\dfrac{1}{4}\right)$}+1,\;\;\;\;\;S_{[2,1]}\sim\text{Binomial}\left(25,\dfrac{1}{4}\right)+\text{Binomial$\left(14,\dfrac{2}{4}\right)$}+1,$
$S_{[1,2]}\sim\text{Binomial}\left(25,\dfrac{2}{4}\right)+\text{Binomial$\left(14,\dfrac{3}{4}\right)$}+1,\;\;\;\;S_{[2,2]}\sim\text{Binomial}\left(25,\dfrac{3}{4}\right)+15.$

Lyapunov Central Limit Theorem

The Lyapunov CLT generalizes the classical Lindeberg-Feller CLT. The theorem
provides a sufficient condition under which the sum of independent (but not
necessarily identical) random variables converges in distribution to the
standard normal distribution [Durrett (2019)].

######  Theorem 5 (Lyapunov CLT).

Let $X_{1},X_{2},\dots,$ be a sequence of independent random variables such
that $E\left(X_{n}\right)=\mu_{n}$ and
$\text{Var}\left(X_{n}\right)=\sigma_{n}^{2}$ are both finite. Define

$\displaystyle s_{n}^{2}$ $\displaystyle=\sum_{i=1}^{n}\sigma_{i}^{2}.$

If there exists $\delta>0$ such that

$\lim_{n\rightarrow\infty}\frac{1}{s_{n}^{2+\delta}}\sum_{i=1}^{n}E\left(\left|X_{i}-\mu_{i}\right|^{2+\delta}\right)=0,\qquad\text{{(Lyapunov's\,condition)}}$

then

$\frac{1}{s_{n}}\sum_{i=1}^{n}E\left(X_{i}-\mu_{i}\right)\stackrel{{\scriptstyle
d}}{{\rightarrow}}N\left(0,1\right).$

The following example gives a sufficient condition for the sum of non-
identical Bernoulli random variables to converge to a normal distribution.

######  Example (Lyapunov’s condition for Bernoulli random variables).

Let $X_{n}\sim\text{Bernoulli}\left(p_{n}\right)$ be a sequence of independent
Bernoulli random variables. Then, $\mu_{n}=p_{n}$ and
$\sigma_{n}^{2}=p_{n}\left(1-p_{n}\right)$. Since

$E\left(\left|X_{n}-\mu_{n}\right|^{3}\right)=p_{n}\left(1-p_{n}\right)^{3}+\left(1-p_{n}\right)p_{n}^{3}=\sigma_{n}^{2}\left(1-2p_{n}\left(1-p_{n}\right)\right)\leq\sigma_{n}^{2},$

it follows that (for $\delta=1$),

$\frac{1}{s_{n}^{3}}\sum_{i=1}^{n}E\left(\left|X_{i}-\mu_{i}\right|^{3}\right)\leq\frac{1}{s_{n}^{3}}\sum_{i=1}^{n}\sigma_{n}^{2}=\frac{1}{s_{n}}.$

Thus, if $\lim_{n\rightarrow\infty}s_{n}=\infty$, or equivalently, whenever

$\sum_{i=1}^{n}p_{i}\left(1-p_{i}\right)\rightarrow\infty,$

the Lyapunov’s condition holds for Bernoulli random variables.

######  Corollary 6.

Let $0<p,q<1$ be fixed, and $T_{1}\sim\text{Binomial}\left(m,p\right)$ and
$T_{2}\sim\text{Binomial$\left(n,q\right)$}$ be two independent binomial
random variables. Then,

$\frac{\left(T_{1}+T_{2}\right)-\left(mp+nq\right)}{\sqrt{mp\left(1-p\right)+nq\left(1-q\right)}}\stackrel{{\scriptstyle
d}}{{\rightarrow}}N\left(0,1\right)$

whenever $m\rightarrow\infty$ or $n\rightarrow\infty$ or both hold.

###### Proof.

First note that $T_{1}+T_{2}$ has mean $mp+nq$ and variance
$mp\left(1-p\right)+nq\left(1-q\right)$. The result is immediate as we can
write

$T_{1}+T_{2}\stackrel{{\scriptstyle
d}}{{=}}\underbrace{X_{1}+\dots+X_{m}}_{X_{i}\sim\text{Bernoulli}(p)}+\underbrace{X_{m+1}+\dots+X_{m+n}}_{X_{i}\sim\text{Bernoulli}(q)},$

and the Lyapunov’s condition for Bernoulli random variables,

$\sum_{i=1}^{m+n}p_{i}\left(1-p_{i}\right)=mp+nq\rightarrow\infty,$

is satisfied whenever $m\rightarrow\infty$ or $n\rightarrow\infty$ or both
hold. ∎

The trivial cases of $p_{[1,1,\dots,1]}$ and $p_{[2,2,\dots,2]}$
Corollaries 4 and 6 tell us that as $n$ is sufficiently large, $p_{L_{t}}$
will approach a normal distribution, except for the trivial cases that might
occur with $p_{[1,1,\dots,1]}$ and $p_{[2,2,\dots,2]}$. In particular,
regardless of the magnitude of $n$, $p_{[1,1,\dots,1]}$ will remain a shifted
binomial random variable,
$\text{Binomial$\left(i-1,\dfrac{1}{2^{k}}\right)$}+1$, for small $i$, whereas
$p_{[2,2,\dots,2]}$ remains
$\text{Binomial}\left(n-i,1-\dfrac{1}{2^{k}}\right)+i$, for small $n-i$.

For the future reference, the modes of $p_{[1,1,\dots,1]}$ and
$p_{[2,2,\dots,2]}$ are located at

$j_{i}=\left\lfloor\dfrac{i}{2^{k}}\right\rfloor+1$ (10)

and

$j_{i}=\left\lfloor(n-i+1)\left(1-\dfrac{1}{2^{k}}\right)\right\rfloor+i,$
(11)

respectively, for $i=1,\dots,n$.

We shall hereafter call these two cases “the trivial cases”. In order not to
interrupt the flow of the presentation, we will consider only the non-trivial
cases of $p_{[1,1,\dots,1]}$ and $p_{[2,2,\dots,2]}$ (when the CLT applies) in
detail, and defer the discussion of the trivial cases to the end of the
section.

We immediately obtain the following corollary (for the non-trivial cases).

######  Corollary 7.

Let $k\geq 1$ be fixed, and $t=1,2,3,\dots,2^{k}$. As $n\rightarrow\infty$,

$p_{L_{t}}\stackrel{{\scriptstyle
d}}{{\rightarrow}}N\left(\mu_{t},\sigma^{2}_{t}\right),$

where

$\mu_{t}=(n-i)\left(\dfrac{t-1}{2^{k}}\right)+(i-1)\left(\dfrac{t}{2^{k}}\right)+1$

and

$\sigma^{2}_{t}=(n-i)\left(\dfrac{t-1}{2^{k}}\right)\left(1-\dfrac{t-1}{2^{k}}\right)+(i-1)\left(\dfrac{t}{2^{k}}\right)\left(1-\dfrac{t}{2^{k}}\right).$

Figure 5:  (Figure accompanying Remark 2.) Probability mass functions
$p_{[1,1]}$, $p_{[2,1]}$, $p_{[1,2]}$, $p_{[2,2]}$ for $i=15$, and $n$ varies
from 30 (top row), 50 (middle row), and 100 (bottom row). Observe that
regardless of the value of $n$, the distribution $p_{[1,1]}$ remains the same.

######  Remark 2.

As a practical note, whenever we come across the statement “as
$n\rightarrow\infty$’’ or “large enough $n$”, the condition such as $n\geq
N(k)$ can be used for the CLT to be applicable. This can be seen from Figure
5: $k=2$ shuffles where we fix $i=15$, and vary $n$ from 30, 50, and 100.
Here, $n=30$ seems pretty large already for the middle two distributions
$p_{[2,1]}$ and $p_{[1,2]}$ to converge to a normal distribution. For the case
when $t=1$, since $i=15$ is small, we have the trivial case here. The
distribution $p_{[1,1]}$ which is independent of $n$ remains the same shifted
Binomial regardless of the values of $n$ (see the first column of the figure).
On the other hand, for the case when $t=2^{k}$, $n-i=n-15$ increases from
$15,35,85$ as $n$ increases from $30,50,100$, and so the distribution of
$p_{[2,2]}$ converges to a normal distribution in this case (see the last
column of the figure).

##  4 Which peak is highest when $n$ is large?

61%

Our goal now is to compare the heights of the peak of each component
$p_{L_{t}}$, $t=1,\dots,2^{k}$ (for the non-trivial cases). To clearly
visualize this, we overlay the plots of $p_{[1,1]}$, $p_{[2,1]}$, $p_{[1,2]}$,
$p_{[2,2]}$ on the same axis in Figure 6. Here, we fix $n=100$ and vary $i$
from 10, 20, 50, and 91. We give an example of $i=91$ in order to emphasize
the fact that the cases $i=10$ and $i=100-10+1=91$ are mirror images of each
other along the vertical direction. The cases when $i=10$ and $20$ lead to the
trivial case of $p_{[1,1]}$.

Figure 6: Probability mass functions $p_{[1,1]}$, $p_{[2,1]}$, $p_{[1,2]}$,
$p_{[2,2]}$ for $n=100$, and $i$ varies from 10, 20, 50, and 91. Notice that
$i=10$ and $i=91$ are mirror images along the vertical direction.

The smaller the standard deviation, the higher the peak

Recall the standard deviation $\sigma_{t}$ of each $p_{L_{t}}$ given in
Corollary 7, and the fact that the component $p_{L_{t}}$ with smallest
standard deviation will have the highest peak. By comparing the values of
$\sigma_{t}$, we obtain the following proposition which can be used to
identify the component $p_{L^{*}}$ which achieves the highest peak among
components $p_{L_{t}}$, $t=1,\dots,2^{k}$.

######  Proposition 8.

Let $n,i,k$ be fixed. For $t=1,\dots,2^{k}$, the height of the peak of
$p_{L_{t}}$ (when $n$ is large) is approximately equal to
$\dfrac{1}{\sigma_{t}\sqrt{2\pi}}$, where

$\sigma_{t}=\sqrt{(n-i)\left(\dfrac{t-1}{2^{k}}\right)\left(1-\dfrac{t-1}{2^{k}}\right)+(i-1)\left(\dfrac{t}{2^{k}}\right)\left(1-\dfrac{t}{2^{k}}\right)}.$
(12)

Denote by $p_{L^{*}}$ the component whose peak is highest among $p_{L_{t}}$,
$t=1,\dots,2^{k}$. Then,

$p_{L^{*}}=\begin{cases}\begin{array}[]{c}p_{[1,1,\dots,1]}\\\
p_{[2,2,\dots,2]}\end{array}&\begin{array}[]{c}\text{if i
$\leq\left\lfloor\dfrac{(n+1)}{2}\right\rfloor$}\\\
\text{otherwise.}\end{array}\end{cases}$ (13)

###### Proof.

The height $\dfrac{1}{\sigma_{t}\sqrt{2\pi}}$ of the peak is due to the bell-
shaped curve normal distribution. Using the fact that $f(p):=p(1-p)$ is
unimodal and attains a minimum value at the boundary points, it is clear that
if $i\leq\left\lfloor\dfrac{(n+1)}{2}\right\rfloor$, $\sigma_{t}$ is smallest
when $t=1$. Hence, $p_{L^{*}}=p_{[1,1,\dots,1]}$ in this case. The result of
the other case is justified in the same way. ∎

##  5 Almost non-overlapping $p_{L_{1}},p_{L_{2}},\dots,p_{L_{2^{k}}}$

79%

Recall that our ultimate goal is to determine for each $i$, the index
$j^{*}_{i}$ that maximizes the mixture distribution

$a_{i,j}^{(k)}=\dfrac{1}{2^{k}}\sum_{t=1}^{2^{k}}p_{L_{t}}(j).$

Thus far, we were able to show that, as $n$ is large, the mixture components
$p_{L_{t}}$ are each normal distribution, and hence $a_{i,j}^{(k)}$ has the
Gaussian mixture distribution. We have also identified the component
$p_{L_{t}^{*}}$ whose peak is highest. Now, since the peaks of any two
consecutive components $p_{L_{t}}$ and $p_{L_{t+1}}$ are $\dfrac{n-1}{2^{k}}$
apart (easily verified by taking $\mu_{t+1}-\mu_{t}$), while the standard
deviation of each $p_{L_{t}}$ is of order $\mathcal{O}(\sqrt{n})$, we can be
sure that, as $n\to\infty$, the Gaussian components
$p_{L_{1}},\dots,p_{L_{2^{k}}}$ are hardly overlapping.

Maximum probablity $a_{i,j^{*}}^{(k)}$ is found!

The fact that the components $p_{L_{1}},p_{L_{2}},\dots,p_{L_{2^{k}}}$ are
(almost) non-overlapping (i.e. well-separated) when $n$ is large is very
crucial and tremendously simplifies the problem of locating the maximizer
$j^{*}_{i}$ of $a_{i,j}^{(k)}$. In particular, the location of the highest
peak $p_{L^{*}}$, identified previously in Proposition 8, is the maximizer we
are seeking.

To see this, Figure 7 ($k=3$, $i=15$) illustrates the p.m.f of components
$p_{L_{1}},p_{L_{2}},\dots,p_{L_{8}}$, and the superposition of the mixture
distribution (the red line). We do not assign the weight of 1/8 to each
component for the sake of clear visualization of the mixture. The location of
the peak of the red line is the maximizer $j_{i}^{*}$. As can be seen from the
figure, when $n$ is small (top), the location of $j^{*}_{i}=3$ (red asterisk)
does not coincide with the location of the highest peak of $p_{L_{1}}$ (blue
asterisk, at $j=2$). On the other hand, as $n$ becomes larger (bottom), the
almost non-overlapping phenomenon occurs: while the peak of $p_{L_{1}}$
remains at the same height, the peaks of other components $p_{L_{t}},t>1$, get
lower and further apart (remember the standard deviation is of order
$\mathcal{O}(\sqrt{n})$). Thus, the location of the maximizer $j^{*}_{i}$
coincides with the location of the peak of the component $p_{L_{1}}$ whenever
$n$ is sufficiently large.

######  Remark 3.

We actually do not require $n$ to be that close to infinity. The components
$p_{L_{t}}$ can still be overlapping, as long as there is no shift in the
location of the maximum peak in the mixture model, and that is all we need.
For example, we can see from the middle plot of Figure 7 that we already get
the desired outcome when $n$ is as small as 50.

Figure 7:  Overlay probability mass functions $p_{L_{1}}$-$p_{L_{8}}$ for
$k=3$ shuffles and $i=15$. The red line is the superposition of the mixture
distribution (without the weight 1/8.) Top: when $n$ is small, the location of
$j^{*}_{i}$ does not necessary coincide with the location of the peak of
$p_{L_{1}}$. Middle and Bottom: when $n$ is large enough, the location of
$j^{*}_{i}$ coincides with the location of the peak of $p_{L_{1}}$.

Revisit and settle the trivial cases

Before we end this section, let us now settle the trivial cases. In fact,
everything we have discussed so far applies to the trivial cases. In
particular the result regarding $p_{L^{*}}$ in Proposition 8 still holds true.
Consider for example the trivial case of $p_{[1,1,\dots,1]}$ when $i$ is
small. Being a shifted Binomial with small and constant standard deviation
$\sigma_{1}$, the peak of $p_{[1,1,\dots,1]}$ will indeed be highest. Figure 7
(when $i=15$) also highlights the fact that $p_{[1,1,\dots,1]}$ does not
depend on $n$. In particular, while the peaks of the other $p_{L_{t}},t>1$ get
lower as $n$ increases from $30,50,400$, the peak of $p_{[1,1,\dots,1]}$
remains at the same height (and same location of course). Proceeding in the
same manner, the trivial case of $p_{[2,2,\dots,2]}$ when $n-i$ is small will
achieve the highest peak, the result consistent with the second case of
Proposition 8.

##  6 Game solved!

100%

Now that we have done all the hard work, we are ready to wrap things up. The
maximum probablity of $a_{i,j}^{(k)}$ is contributed solely from the peak of
$p_{[1,1,...,1]}$ if $i\leq\left\lfloor\dfrac{(n+1)}{2}\right\rfloor$ or
$p_{[2,2,...,2]}$ otherwise. Following immediately from the location of the
mode of the shifted Binomial, $p_{[1,1,...,1]}$ and $p_{[2,2,...,2]}$ as given
in Equations 10-11 and Proposition 8, the optimal strategy $\cal{G}^{*}$ can
now be determined.

Optimal guessing strategy $\cal{G}^{*}$ for the $i$th position
• If $i\leq\left\lfloor\dfrac{(n+1)}{2}\right\rfloor$, the best guess is the
number $j^{*}_{i}=\left\lfloor\dfrac{i}{2^{k}}\right\rfloor+1$; • If
$i\geq\left\lceil\dfrac{(n+1)}{2}\right\rceil$, the best guess is the number
$j^{*}_{i}=\left\lfloor(n-i+1)\left(1-\dfrac{1}{2^{k}}\right)\right\rfloor+i.$

That is, for a $k$-time shuffled deck of $n$ cards, one should guess the top
half of the deck with sequence

$\underbrace{1,\dots,1}_{2^{k}-1\text{
times}},\;\underbrace{2,\dots,2}_{2^{k}\text{
times}},\;\underbrace{3,\dots,3}_{2^{k}\text{
times}},\;\underbrace{4,\dots,4}_{2^{k}\text{ times}},\dots$

and guess the bottom half in the reverse manner, i.e.

$\dots,\underbrace{n-3,\dots,n-3}_{2^{k}\text{
times}},\;\underbrace{n-2,\dots,n-2}_{2^{k}\text{
times}},\;\underbrace{n-1,\dots,n-1}_{2^{k}\text{
times}},\;\underbrace{n,\dots,n}_{2^{k}-1\text{ times}}.$

Using this strategy, we can calculate the expected number of correct guesses
for the whole deck leading to the main result of this paper. It is worth
noting that the expected value relies only on the standard deviation of the
component $p_{[1,1,...,1]}$ of the first half of the deck, as we shall now
see.

######  Theorem 9.

For an $n$-card deck, let $X^{\cal{G}^{*}}$ be the number of correct guesses
(according to the optimal strategy $\cal{G}^{*}$) after $k$-riffle shuffles.
Then,
$E\left[X^{\cal{G}^{*}}\right]=\dfrac{2\sqrt{n}}{\sqrt{(2^{k}-1)\pi}}+\mathcal{O}(1).$

###### Proof.

Recall Equation 4:
$E\left[X^{\cal{G}^{*}}\right]=\sum_{i=1}^{n}a_{i,j^{*}}^{(k)}=\dfrac{1}{2^{k}}\sum_{i=1}^{n}p_{L}(j^{*}_{i}),$
and the standard deviation of $p_{[1,1,...,1]}$:
$\sigma_{1}=\sqrt{(i-1)\left(\dfrac{1}{2^{k}}\right)\left(1-\dfrac{1}{2^{k}}\right)}$.
By the symmetric property of the probability matrix $P^{(k)}$, we will
consider only half of the deck and double the value of the summation. For an
asymptotic value $n$, we have (from Proposition 8):

$\displaystyle E\left[X^{\cal{G}^{*}}\right]$
$\displaystyle=2\sum_{i=2}^{\left\lfloor\frac{(n+1)}{2}\right\rfloor}\frac{1}{\sqrt{(i-1)(2^{k}-1)}\sqrt{2\pi}}+\mathcal{O}(1)$
$\displaystyle=\dfrac{2}{\sqrt{(2^{k}-1)2\pi}}2\sqrt{\dfrac{n}{2}}+\mathcal{O}(1)$
$\displaystyle=\dfrac{2\sqrt{n}}{\sqrt{(2^{k}-1)\pi}}+\mathcal{O}(1).$

Let us clarify the approximation error terms absorbed in $\mathcal{O}(1)$.
Specifically, this includes (i) the error in normal approximations, when $i$
is small. The normal distribution gives a less accurate approximation, say,
for the first $N(k)$ terms (finite number of terms for a given $k$) of the
sum, after which the approximation becomes more and more accurate. The total
error in this case is of order $\mathcal{O}(1)$; (ii) the approximation errors
due to the CLT (i.e. the normal approximation to the shifted Binomial). These
approximation errors are asymptotically negligible compared to that in (i);
and finally (iii) the errors of order $\mathcal{O}(1)$ due to approximation of
a summation by an integral (in the second equality). ∎

From the theorem, notice that for each additional shuffle, the expected number
of correct guesses will go down by roughly a factor of $\sqrt{2}$ (in a huge
deck of $n$ cards, of course). We also remark that for $k=1$, the result boils
down to that of [Ciucu (1998)].

Game Complete!

## References

  * [Bayer and Diaconis (1992)] Dave Bayer, Persi Diaconis. Trailing the dovetail shuffle to its lair, Ann. Appl. Probab. 2 (1992), 294-313.
  * [Ciucu (1998)] Mihai Ciucu. No-feedback card guessing for dovetail shuffles. Ann. Appl. Probab. 8(4) (1998), 1251-1269.
  * [Diaconis and Graham (1981)] Persi Diaconis, Ronald Graham. The analysis of sequential experiments with feedback to subjects. The Annals of Statistics 9.1 (1981), 3-23.
  * [Diaconis et al. (2020)] Diaconis, Persi, Ron Graham, and Sam Spiro. Guessing about guessing: Practical strategies for card guessing with feedback. arXiv preprint arXiv:2012.04019 (2020).
  * [Diaconis et al. (2022)] Persi Diaconis, Ronald Graham, Xiaoyu He, Sam Spiro. Card guessing with partial feedback. Combinatorics, Probability and Computing 31.1 (2022), 1-20.
  * [Durrett (2019)] Rick Durrett. Probability: theory and examples. Vol. 49. Cambridge university press, 2019.
  * [Krityakierne et al. (2021)] Tipaluck Krityakierne, Thotsaporn Aek Thanatipanonda. The Card Guessing Game: A generating function approach. arXiv preprint arXiv:2107.11142 (2021).
  * [Liu (2021)] Pengda Liu. On card guessing game with one time riffle shuffle and complete feedback. Discrete Applied Mathematics, 288 (2021), 270-278.
  * [Pehlivan (2010)] Lerna Pehlivan. No Feedback Card Guessing for Top to Random Shuffles. arXiv preprint arXiv:1006.1321 (2010).