# On Card guessing games: limit law for no feedback one-time riffle shuffle

Markus Kuba  Markus Kuba
Department Applied Mathematics and Physics
University of Applied Sciences - Technikum Wien
Höchstädtplatz 5, 1200 Wien<EMAIL_ADDRESS>and  Alois Panholzer
Alois Panholzer
Institut für Diskrete Mathematik und Geometrie
Technische Universität Wien
Wiedner Hauptstr. 8-10/104
1040 Wien, Austria<EMAIL_ADDRESS>
###### Abstract.

We consider the following card guessing game with no feedback. An ordered deck
of $n$ cards labeled $1$ up to $n$ is riffle-shuffled exactly one time. Then,
the goal of the game is to maximize the number of correct guesses of the
cards. One after another a single card is drawn from the top, the guesser
makes a guess without seeing the card and gets no response if the guess was
correct or not. Building upon and improving earlier results, we provide a
limit law for the number of correct guesses and also show convergence of the
integer moments.

###### Key words and phrases:

Card guessing, riffle shuffle, no feedback, limit law, moments

###### 2000 Mathematics Subject Classification:

05A15, 05A16, 60F05, 60C05

##  1\. Introduction

The analysis of card shuffling and card guessing games has a long history.
Starting from a mathematical model of shuffling developed in 1956 at Bell Labs
by E. Gilbert and C. Shannon, the subject has extended in various directions
in a great many articles, amongst others [1, 8, 9, 10, 16, 17, 21, 22, 23, 25,
26, 28, 29]. The mathematical analysis of questions related to card shuffling
and card guessing are not only of purely theoretical interest. There are
applications to the analysis of clinical trials [5, 11], fraud detection
related to extra-sensory perceptions [8], guessing so-called Zener Cards [25],
as well as relations to tea tasting and the design of statistical experiments
[12, 26].

In this work we consider the following problem. A deck of $n$ cards labeled
consecutively from 1 on top to $n$ on bottom is face down on the table. The
deck is riffle shuffled once and placed back on the table, face down. A
guesser tries to guess at the cards one at a time, starting from the top. The
goal is to maximize the number of correct guesses with the caveat, that the
identities of the card guessed are not revealed, nor is the guesser told
whether a particular guess was correct or not. Such card guessing games are
usually called no feedback games, as no information at all is delivered to the
person guessing. In contrast, there are complete feedback games, where the
guesser is shown the drawn card and thus knows, whether the guess was correct
or not. For a similar card guessing game with complete feedback we refer the
reader to [20, 24].

The optimal strategy for the no feedback game, as well as extensions to
$k$-time riffle shuffles, has been given by Ciucu [7]. Therein, he also
derived the expected value ${\mathbb{E}}(X_{n})$ of the number of correct
guesses $X_{n}$, when the deck is riffle shuffled once; see also Krityakierne
and Thanatipanonda [19] for related results. The first few higher moments of
$X_{n}$ were derived by Krityakierne et al. [18]. We build on the earlier work
[7, 18] and derive in this article the limit law of the number of correct
guesses $X_{n}$ in the no feedback game and also give asymptotic results for
all integer moments, extending the results of [18].

Finally, we also comment on a different kind of card guessing games under the
uniform distribution. A deck of a total of $M$ cards is shuffled, and then the
guesser is provided with the total number of cards $M$, as well as the
individual numbers of say hearts, diamonds, clubs and spades. After each
guess, the person guessing the cards is shown the drawn card, which is then
removed from the deck. This process is continued until no more cards are left.
Assuming the guesser tries to maximize the number of correct guesses, one is
again interested in the total number of correct guesses. The card guessing
procedure can be generalized to an arbitrary number $N\geq 2$ of different
types of cards. In the simplest setting there are two colors, red (hearts and
diamonds) and black (clubs or spades), and their numbers are given by non-
negative integers $m_{1}$, $m_{2}$, with $M=m_{1}+m_{2}$. One is then
interested in the random variable $C_{m_{1},m_{2}}$ counting the number of
correct guesses. Interestingly, it turned out that the random variable
$C_{m_{1},m_{2}}$ is closely related to card guessing with complete feedback
after a single riffle shuffle. For this complete feedback card guessing game,
not only the expected value and the distribution of the number of correct
guesses is known [9, 17, 23, 28, 29], but also multivariate limit laws and
interesting relations to combinatorial objects such as Dyck paths and Pólya-
Eggenberger urn models have been established [9, 21, 22].

###  1.1. Notation

As a remark concerning notation used throughout this work, we always write
$X\operatorname{\overset{\mathcal{L}}{=}}Y$ to express equality in
distribution of two random variables (r.v.) $X$ and $Y$, and
$X_{n}\operatorname{\overset{\mathcal{L}}{\rightarrow}}X$ for the weak
convergence (i.e., convergence in distribution) of a sequence of random
variables $X_{n}$ to a r.v. $X$. Furthermore, throughout this work we let
$h:=h(n)=\lceil\frac{n}{2}\rceil$. Moreover, we denote for $s\in\mathbb{N}$
with $x^{\underline{s}}=x(x-1)\cdots(x-(s-1))$ the falling factorials.

##  2\. Riffle shuffle model and optimal strategy

###  2.1. Gilbert-Shannon-Reeds model

The riffle shuffle, sometimes also called dovetail shuffle, is a card
shuffling technique. In the mathematical modeling of card shuffling, the
_Gilbert–Shannon–Reeds_ model [9, 15] is a probability distribution serving as
a model of a riffle shuffle. One considers a sorted deck of $n$ cards labeled
consecutively from 1 up to $n$. The deck of cards is cut into two packets,
assuming that the probability of selecting $k$ cards in the first packet,
which we call a cut at position $k$, and $n-k$ in the second packet is defined
as a binomial distribution with parameters $n$ and $1/2$:

${\mathbb{P}}\\{\mathsf{Cut}=k\\}=\frac{\binom{n}{k}}{2^{n}},\quad 0\leq k\leq
n.$

Afterward, the two packets are interleaved back into a single pile: one card
at a time is moved from the bottom of one of the packets to the top of the
shuffled deck, such that if $m_{1}$ cards remain in the first and $m_{2}$
cards remain in the second packet, then the probability of choosing a card
from the first packet is $m_{1}/(m_{1}+m_{2})$ and the probability of choosing
a card from the second packet is $m_{2}/(m_{1}+m_{2})$.

Figure 1. Example of a one-time riffle shuffle: a deck of five cards is split
after 2 with probability $\binom{5}{2}/2^{5}=5/16$ and then interleaved.

For a one-time shuffle, the operation of interleaving described above gives
rise to an ordered deck (corresponding to the identity permutation) with
multiplicity $n+1$. Each other shuffled deck corresponds to a permutation with
exactly two increasing subsequences and has multiplicity 1. In total number
there are $2^{n}-n-1$ different permutations of two increasing subsequences
from the interleaving.

###  2.2. Optimal strategy

The optimal strategy $\mathcal{G}^{\ast}$ for maximizing the number $X_{n}$ of
correctly guessed cards, starting with a deck of $n$ ordered cards, after a
one-time riffle shuffle stems from the following proposition based on work of
Ciucu [7] and Krityakierne and Thanatipanonda [19].

######  Proposition 1 ([7, 19]).

In order to maximize the number of correct guesses in a one-time riffle
shuffle no feedback card guessing game, for large $n$, the guesser should
follow the optimal strategy $\mathcal{G}^{\ast}$: guess the top half of the
deck with sequence

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

and guess the bottom half of the deck with sequence

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

###### Proof.

For the sake of completeness and to make this work more self-contained, we add
the nice and short argument justifying this strategy. From the Gilbert-
Shannon-Reeds model one can readily determine the probability
$m_{i,j}=m_{i,j}(n)$ that the card labeled $i$ ends up at position $j$ after a
riffle shuffle, starting with a deck of $n$ ordered cards:

$\begin{split}m_{i,i}&=\frac{1}{2^{n}}\big{(}2^{i-1}+2^{n-i}\big{)},\\\
m_{i,j}&=\frac{1}{2^{n-j+1}}\binom{n-j}{i-j},\quad j<i,\end{split}$ (1)

and the symmetry

$m_{i,j}=m_{n-i+1,n-j+1}.$

This follows directly by considering the different cutting positions $k$,
$0\leq k\leq n$, and the number of different interleavings, such that card
labeled $i$ ends up at position $j$. Let $j<i$. Then, cuts at positions $k\geq
i$ cannot contribute, as all cards labeled $1$ up to $i-1$ are still before
$i$ after interleaving and the final position is at least $i$. Thus, we are
left with cuts at $1\leq k<i$. As the cards $k+1$ up to $i-1$, a total of
$i-k-1$, of the second packet are always before $i$, we require exactly
$j-i+k$ of the first packet out of the cards labeled $\\{1,\dots,k\\}$ to be
interleaved before $j$. There are $\binom{j-1}{j-i+k}$ ways to do so. The
remaining $i-j$ cards of the first packet have to be interleaved above $j$,
leading to $\binom{n-j}{i-j}$ different ways. In total,

$m_{i,j}=\frac{1}{2^{n}}\sum_{k=i-j}^{i-1}\binom{j-1}{j-i+k}\binom{n-j}{i-j}=\frac{1}{2^{n-j+1}}\binom{n-j}{i-j}.$

In the case $i=j$ there are additional contributions from the cuts at $k\geq
i$, leading to

$m_{i,i}=\frac{1}{2^{n-i+1}}+\sum_{k=i}^{n}\frac{\binom{n-i}{k-i}}{2^{n}}=\frac{1}{2^{n-i+1}}+\frac{1}{2^{i}}.$

The case $j>i$ can be treated similarly; we opt to recall a nice symmetry
argument of [7]: We imagine having a second set of numbers on our cards, in
which the cards are labeled consecutively from 1 on bottom through $n$ on top.
We call this the ”upward labeling”, compared to the original ”downward
labeling”. It is clear that, after a riffle shuffle, card $i$ ends up in
position $j$ in downward labeling if and only if card $n-i+1$ goes to position
$n-j+1$ in the upward labeling. Since the probability distributions involved
in the riffle shuffle have a vertical symmetry axis, we obtain the stated
symmetry. Finally, the best guess $g_{j}$ at the card in position $j$ of the
optimal strategy $\mathcal{G}^{\ast}=g_{1}g_{2}\dots g_{n}$ is determined by
guessing the asymptotically largest probability,

$g_{j}=\max_{i}\\{m_{i,j}\\},\quad 1\leq j\leq n,$

which can be obtained by a close inspection of the binomial coefficients. ∎

######  Remark 1.

As already pointed out in [19], the optimal strategy is not unique for a one-
time riffle shuffle. In particular, for the card position $j$, the player can
optimally choose to guess any number from the set $\mathcal{S}_{j}$, where
$\mathcal{S}=(\mathcal{S}_{j})$:

$\mathcal{S}=\\{1\\},\\{2\\},\\{2\\},\\{2,3\\},\\{3\\},\\{3,4\\},\\{4\\},\\{4,5\\},\dots\quad\text{top
half}$

and

$\dots,\\{n-3,n-2\\},\\{n-2\\},\\{n-2,n-1\\},\\{n-1\\},\\{n-1\\},\\{n\\}\quad\text{bottom
half}.$

However, in our analysis we follow exclusively the strategy
$\mathcal{G}^{\ast}$, which is the one that can be extended naturally to
multiple-time riffle shuffle [19].

######  Example 1.

We consider the case $n=3$ and the $2^{3}$ possible permutations $\sigma$. In
Table 1 we highlight all $2^{3}-3=5$ different permutations, colored cyan, as
well as the cut positions and number of correct guesses.

$\sigma$ | $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\end{matrix}$ |  $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\end{matrix}$ | $\begin{matrix}2\\\ 1\\\ \boldsymbol{3}\end{matrix}$ | $\begin{matrix}2\\\ 3\\\ 1\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ 3\\\ 2\end{matrix}$ | $\begin{matrix}3\\\ 1\\\ 2\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\end{matrix}$
---|---|---|---|---|---|---|---|---
$\mathsf{Cut}$ | 0 |  1 | 1 | 1 | 2 | 2 | 2 | 3
$X$ | 3 |  3 | 1 | 0 | 3 | 1 | 0 | 3
Table 1. Case $n=3$: optimal strategy $\mathcal{G}^{\ast}=(1,2,3)$ and the
number of correct guesses.

We observe that under the optimal strategy we have

${\mathbb{P}}\\{X_{3}=3\\}=\frac{1}{2},\quad{\mathbb{P}}\\{X_{3}=2\\}=0,\quad{\mathbb{P}}\\{X_{3}=1\\}={\mathbb{P}}\\{X_{3}=0\\}=\frac{1}{4}.$

######  Example 2.

We consider the case $n=4$ and the $2^{4}$ possible permutations $\sigma$.
Again, in Table 2 we highlight all $2^{4}-4=12$ different permutations,
colored cyan, as well as the cut positions and number of correct guesses.

$\sigma$ | $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\\\ \boldsymbol{4}\end{matrix}$ |  $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\\\ \boldsymbol{4}\end{matrix}$ |  $\begin{matrix}2\\\ 1\\\ \boldsymbol{3}\\\ \boldsymbol{4}\end{matrix}$ | $\begin{matrix}2\\\ 3\\\ 1\\\ \boldsymbol{4}\end{matrix}$ | $\begin{matrix}2\\\ 3\\\ 4\\\ 1\end{matrix}$ |  $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\\\ \boldsymbol{4}\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ 3\\\ 2\\\ \boldsymbol{4}\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ 3\\\ 4\\\ 2\end{matrix}$ | $\begin{matrix}3\\\ 1\\\ 2\\\ \boldsymbol{4}\end{matrix}$ | $\begin{matrix}3\\\ 1\\\ 4\\\ 2\end{matrix}$ | $\begin{matrix}3\\\ 4\\\ 1\\\ 2\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\\\ \boldsymbol{4}\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ 4\\\ 3\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ 4\\\ 2\\\ 3\end{matrix}$ | $\begin{matrix}4\\\ 1\\\ 2\\\ 3\end{matrix}$ | $\begin{matrix}\boldsymbol{1}\\\ \boldsymbol{2}\\\ \boldsymbol{3}\\\ \boldsymbol{4}\end{matrix}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\mathsf{Cut}$ | 0 |  1 |  1 | 1 | 1 |  2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4
$X$ | 4 |  4 |  2 | 1 | 0 |  4 | 2 | 1 | 1 | 0 | 0 | 4 | 2 | 1 | 0 | 4
Table 2. Case $n=4$: optimal strategy $\mathcal{G}^{\ast}=(1,2,3,4)$ and the
number of correct guesses.

Under the optimal strategy we obtain

${\mathbb{P}}\\{X_{4}=4\\}=\frac{5}{16},\,{\mathbb{P}}\\{X_{4}=3\\}=0,\,{\mathbb{P}}\\{X_{4}=2\\}=\frac{3}{16},\,{\mathbb{P}}\\{X_{4}=1\\}={\mathbb{P}}\\{X_{4}=0\\}=\frac{1}{4}.$

We further simulated the probability mass function by looking at the empirical
probabilities $h_{k}$ for $n=200$, $1000$ and $5000$ with samples of size
$N=50000$ for $n=200$, $1000$ and sample size $N=100000$ for $n=5000$.

$0$$20$$40$$0$$2$$4$$\cdot 10^{-2}$$0$$50$$100$$0$$1$$2$$\cdot
10^{-2}$$0$$100$$200$$0$$0.5$$1$$\cdot 10^{-2}$

##  3\. Distributional analysis and generating functions

Let $X_{n}$ denote the random variable counting the number of correct guesses
under the optimal strategy $\mathcal{G}^{\ast}$ in the no-feedback model after
a single riffle shuffle, starting with $n$ ordered cards. In [18], the
distribution of $X_{n}$ has been determined using the generating function
$f_{n}(q)$:

${\mathbb{E}}(q^{X_{n}})=\frac{f_{n}(q)}{2^{n}}.$

Our starting point is the following nice result, giving a formula for
$f_{n}(q)$ in terms of an auxiliary generating function $g_{m_{1},m_{2}}(q)$,
which is described itself in a recursive way.

######  Lemma 1 (Krityakierne et al. [18]).

Let $h:=\lceil\frac{n}{2}\rceil$. The generating function $f_{n}(q)$ satisfies

$f_{n}(q)=4q^{4}-2(q^{2}+q^{3})+\sum_{a=0}^{h}\sum_{b=0}^{n-h}g_{a,h-a}(q)\cdot
g_{b,n-h-b}(q).$

Here, the generating function $g_{m_{1},m_{2}}(q)$ is determined by the
recurrence relation

$g_{m_{1},m_{2}}(q)=q^{\delta(c,m_{1})}g_{m_{1}-1,m_{2}}(q)+g_{m_{1},m_{2}-1}(q),\quad
m_{1},m_{2}\geq 0\;\text{and}\;(m_{1},m_{2})\neq(0,0),$ (2)

where $c=\lfloor\frac{m_{1}+m_{2}}{2}\rfloor+1$ and $\delta(x,y)$ denotes the
Kronecker delta function, with initial values $g_{0,0}(q)=1$ and
$g_{m_{1},m_{2}}(q)=0$, for $m_{1}<0$ or $m_{2}<0$.

In order to study the limit law of $X_{n}$, we interpret the results of Lemma
1 in a probabilistic way. Let $Y_{m_{1},m_{2}}$ denote the random variable
defined in terms of recurrence relation (2),

${\mathbb{E}}(q^{Y_{m_{1},m_{2}}})=\frac{g_{m_{1},m_{2}}(q)}{g_{m_{1},m_{2}}(1)}=\frac{g_{m_{1},m_{2}}(q)}{\binom{m_{1}+m_{2}}{m_{1}}},$
(3)

where the latter equality holds, since for $q=1$ recurrence (2) is equivalent
to Pascal’s rule for the binomial coefficients. Next we translate above
recurrence relations into a distributional equation for $X_{n}$.

######  Proposition 2 (Distributional equation for $X_{n}$).

The random variable $X_{n}$ satisfies for $n\to\infty$:

$X_{n}\sim Y_{h-J_{h},J_{h}}+Y^{\ast}_{n-h-J^{\ast}_{n-h},J^{\ast}_{n-h}},$

where $Y$, $Y^{\ast}$ are distributed according to (3), $J$, $J^{\ast}$ are
binomially distributed with parameter $p=1/2$ and parameters
$h:=\lceil\frac{n}{2}\rceil$ and $n-h$, respectively. Moreover, all random
variables are independent.

###### Proof.

By Lemma 1 we have

$\displaystyle{\mathbb{E}}(q^{X_{n}})$
$\displaystyle=\frac{4q^{4}-2(q^{2}+q^{3})}{2^{n}}+\frac{1}{2^{n}}\sum_{a=0}^{h}\sum_{b=0}^{n-h}g_{a,h-a}(q)\cdot
g_{b,n-h-b}(q)$
$\displaystyle=\frac{4q^{4}-2(q^{2}+q^{3})}{2^{n}}+\sum_{a=0}^{h}\frac{g_{a,h-a}(q)}{\binom{h}{a}}\cdot\frac{\binom{h}{a}}{2^{h}}\sum_{b=0}^{n-h}\frac{g_{b,n-h-b}(q)}{\binom{n-h}{b}}\cdot\frac{\binom{n-h}{b}}{2^{n-h}}$
$\displaystyle=\frac{4q^{4}-2(q^{2}+q^{3})}{2^{n}}$
$\displaystyle\qquad\mbox{}+\sum_{a=0}^{h}{\mathbb{E}}(q^{Y_{a,h-a}})\cdot{\mathbb{P}}\\{J_{h}=a\\}\sum_{b=0}^{n-h}{\mathbb{E}}(q^{Y^{\ast}_{b,n-h-b}}){\mathbb{P}}\\{J^{\ast}_{n-h}=b\\}.$

Using that the product of probability generating functions corresponds to a
sum of independent random variables, we obtain the distributional equation

$X_{n}\operatorname{\overset{\mathcal{L}}{=}}\hat{Y}_{h-J_{h},J_{h}}+\hat{Y}^{\ast}_{n-h-J^{\ast}_{n-h},J^{\ast}_{n-h}},$

where the ”hat” versions differ from their ordinary versions only on the
values $\\{2,3,4\\}$, with the difference tending to zero exponentially fast
for $n\to\infty$. Thus, we can safely neglect this difference when
characterizing the limiting behaviour. ∎

###  3.1. Limit law

From the properties of the binomial distribution we know that
$J_{h}=\operatorname{B}(h,\frac{1}{2})$ satisfies

$J_{h}\sim\mu_{J}+\sigma_{J}\cdot\mathcal{N},$ (4)

with $\mu_{J}=\frac{h}{2}\sim\frac{n}{4}$,
$\sigma_{J}=\frac{\sqrt{h}}{2}\sim\frac{\sqrt{n}}{2\sqrt{2}}$ and
$\mathcal{N}=\mathcal{N}(0,1)$ the standard normal distribution. In view of
Proposition 2 this implies that we need to know the distribution of
$Y_{m_{1},m_{2}}$ with parameters

$m_{1}\sim h-\mu_{j}-\sigma_{J}\cdot t,\quad m_{2}\sim\mu_{j}+\sigma_{J}\cdot
t,\quad t\in\mathbb{R}.$

Thus we require the limit law of $Y_{m_{1},m_{2}}$, for $m_{1},m_{2}\to\infty$
and satisfying the assumptions above. In order to analyze recurrence relation
(2) and thus $Y_{m_{1},m_{2}}$, we proceed similar to the two-color card
guessing game [21], setting up a suitable bijection. This bijection allows to
analyze $Y_{m_{1},m_{2}}$ in terms of certain Dyck paths by using tools from
Analytic Combinatorics [13].

First, according to recurrence (2) we consider the sample paths from
$(m_{1},m_{2})$ to $(0,0)$, $m_{1},m_{2}\geq 0$, with steps $(-1,0)$, “left”,
and $(0,-1)$, “down”, where the leftward steps carry a weight $q$ if
$c=\lfloor\frac{m_{1}+m_{2}}{2}\rfloor+1$. Next we reverse the direction of
the walks, thus going from $(0,0)$ to $(m_{1},m_{2})$, and then rotate the
coordinate system clockwise by 45 degrees. After scaling, the resulting walks
are directed walks of length $m_{1}+m_{2}$ with Dyck steps $(1,1)$, “upward”,
and $(1,-1)$, “downward”, starting at the origin and ending at
$(m_{1}+m_{2},m_{2}-m_{1})$, see Figure 2.

Figure 2. Mapping of a sample path of $Y_{6,3}$ to a directed lattice path
from the origin to $(9,-3)$.

It remains to translate the weight $q^{\delta(c,m_{1})}$, with
$c=\lfloor\frac{m_{1}+m_{2}}{2}\rfloor+1$, to the directed paths. We consider
all four different cases resulting from the parity of $m_{1},m_{2}$, where we
obtain the following.

  * •

Both $m_{1},m_{2}$ are even or both $m_{1},m_{2}$ are odd:

$\Big{\lfloor}\frac{m_{1}+m_{2}}{2}\Big{\rfloor}+1=\frac{m_{1}+m_{2}}{2}+1=m_{1},\quad\text{which
yields}\quad m_{1}=m_{2}+2.$

  * •

$m_{1}$ is even and $m_{2}$ odd or vice versa:

$\Big{\lfloor}\frac{m_{1}+m_{2}}{2}\Big{\rfloor}+1=\frac{m_{1}+m_{2}-1}{2}+1=m_{1},\quad\text{which
yields}\quad m_{1}=m_{2}+1.$

This implies that $q$ counts the number of contacts with the two lines

$g_{1}\colon\ y=x-1,\quad g_{2}\colon\ y=x-2.$

After rotation, i.e., for Dyck paths, this implies that we count contacts with
the lines $y=-1$, corresponding to $g_{1}$, as well as $y=-2$, corresponding
to $g_{2}$. However, as only left steps from $(m_{1},m_{2})\to(m_{1}-1,m_{2})$
can carry a weight in the original sample paths, in the Dyck path setting a
contact with these two lines is only counted when occurring after a downward
step, see Figure 3. Above findings are summarized as follows.

Figure 3. Mapping of a directed lattice path from the origin to $(9,-3)$ to
its corresponding sample path of $Y_{6,3}$.

######  Proposition 3 (Sample paths of the card guessing game and Dyck paths).

Let $\mathcal{S}_{m_{1},m_{2}}$ denote the set of weighted sample paths from
$(m_{1},m_{2})$ to $(0,0)$, $m_{1},m_{2}\geq 0$, with steps $(-1,0)$, carrying
a weight $q$ if $c=\lfloor\frac{m_{1}+m_{2}}{2}\rfloor+1$, and $(0,-1)$. Then,
$\mathcal{S}_{m_{1},m_{2}}$ is in bijection with the set
$\mathcal{D}_{m_{1}+m_{2}}$ of Dyck paths with step sets $(1,1)$ and $(1,-1)$
of length $m_{1}+m_{2}$, starting at the origin and ending at
$(m_{1}+m_{2},m_{2}-m_{1})$, where the contacts with $y=-1$ and $y=-2$ are
counted after a downward step.

######  Proposition 4.

Assume that the numbers $m_{1}$, $m_{2}$ satisfy $m_{1}-m_{2}\sim
t\cdot\sqrt{m_{1}}$, as $m_{1}\to\infty$, with $t>0$. Then, the random
variable $Y_{m_{1},m_{2}}$ is asymptotically linear exponentially distributed,

$\frac{Y_{m_{1},m_{2}}}{\sqrt{m_{1}}}\operatorname{\overset{\mathcal{L}}{\rightarrow}}\operatorname{LinExp}(\textstyle{\frac{t}{2}},\textstyle{\frac{1}{2}}),$

or equivalently by stating the cumulative distribution function,

${\mathbb{P}}\\{Y_{m_{1},m_{2}}\leq z\sqrt{m_{1}}\\}\to
1-e^{-\frac{z(2t+z)}{4}},\quad z\geq 0.$

An analogous result holds for $m_{2}-m_{1}\sim t\cdot\sqrt{m_{1}}$, as
$m_{2}\to\infty$, with $t>0$.

Before we prove this result, we discuss a motivation or, in other words, a
back of the envelope explanation for it. Asymptotically, the number of down-
contacts at levels $-1$ and $-2$ should be indistinguishable from the number
of $W_{m_{1},m_{2}}$ of returns to zero of Dyck paths of length $m_{1}+m_{2}$,
starting at zero and ending at $m_{2}-m_{1}$. This latter quantity has been
already analyzed in the context of two-color card guessing games, leading
exactly to the same limit law.

######  Lemma 2 ([21]).

For $m_{2}\sim m_{1}$, where the difference $d=m_{1}-m_{2}$ satisfies $d\sim
t\sqrt{m_{1}}$, with $t>0$: suitably scaled, $W_{m_{1},m_{2}}$ weakly
converges to a linear exponential distribution, which is characterized via the
distribution function

$F(x)=1-e^{-\frac{x(2t+x)}{4}},\quad x>0.$

Thus, $W_{m_{1},m_{2}}$ is asymptotically linear exponentially distributed:

$\frac{W_{m_{1},m_{2}}}{\sqrt{m_{1}}}\operatorname{\overset{\mathcal{L}}{\rightarrow}}\operatorname{LinExp}\big{(}\textstyle{\frac{t}{2}},\textstyle{\frac{1}{2}}\big{)}.$

Next we show that the random variables $W_{m_{1},m_{2}}$ and $Y_{m_{1},m_{2}}$
are asymptotically indistinguishable. We show that both generating functions
are almost identical and lead to the same asymptotic behavior. We derive the
generating function of the weighted Dyck paths of interest, counting the
number of down-contacts at levels $-1$ and $-2$ . We follow the classical
analysis of Banderier and Flajolet [2], see also [13]. Assume that $m_{1}\geq
m_{2}+2$, such that the endpoint has a negative $y$-coordinate:
$m_{2}-m_{1}\leq-2<0$. We can decompose these Dyck paths into three parts (see
Figure 4):

  * •

Part one. An excursion $\mathcal{E}$ of arbitrary length, starting at the
origin and never going below the $x$-axis and eventually returning to $y=0$,
then followed by a downward step with additional weight $q$ leading to the
first contact with $y=-1$.

  * •

Part two. The middle part $\mathcal{M}$ consists itself of two different
subparts. The first part consists of excursions $\mathcal{E}_{\text{up}}(q)$
initially going upwards from $y=-1$ to the same level. Here, the last step is
always a downward step to $y=-1$ and is weighted with $q$. Second, we consider
excursions $\mathcal{E}_{\text{down}}(q)$ going downwards, with an additional
weight $q$ at the first step at height $y=-2$. The middle part finishes with a
final contact at $y=-1$, followed by a downward step to $y=-2$ with additional
weight $q$, yielding the formal description (see [13] for basic combinatorial
constructions and the symbolic method):

$\mathcal{M}=\text{{Seq}}(\mathcal{E}_{\text{up}}(q)\cup\mathcal{E}_{\text{down}}(q))\times\\{q\\}.$

  * •

Part three. An excursion starting at $y=-2$ and ending at
$y=m_{2}-m_{1}\leq-2$, never reaching $y=-1$.

Figure 4. Visualization of the decomposition for $m_{1}\gg m_{2}$: the first
part is the excursion (blue), the center part starts at $y=-1$ and ends at the
same level (green), the final part departs from $y=-2$ to the ending position
at level $y=m_{2}-m_{1}\leq-2$ (orange).

By the classical arch decomposition, the generating function of excursions
$E(z)$, obtained by using the sequence construction from the symbolic method
in combinatorics [13], satisfies

$E(z)=\frac{1}{1-z^{2}E(z)},\quad\text{which implies}\quad
E(z)=\frac{1-\sqrt{1-4z^{2}}}{2z^{2}}.$

Thus, our searched function for part one equals $G_{1}(z):=E(z)\cdot zq$.
Furthermore, the generating function of excursions
$\mathcal{E}_{\text{up}}(q)$ and $\mathcal{E}_{\text{down}}(q)$, both with
generating functions

$\frac{1}{1-z^{2}qE(z)}=1+\sum_{k\geq 1}\big{(}z^{2}qE(z)\big{)}^{k},$

are grouped together using the decomposition by arches corresponding to
contacts with $y=-1$, and taking into account the last additional downward
step reaching $y=-2$ yields for part two:

$G_{2}(z):=M(z)=\frac{1}{1-2z^{2}qE(z)}\cdot zq.$

Finally, the generating function of the last excursion from $y=-2$ to
$y=m_{2}-m_{1}$ is obtained using the classical generating function
$F(z,u)=\sum_{\text{$p$ meander}}z^{\text{length of $p$}}u^{\text{final
altitude of $p$}}$ of the final altitude of meanders, see Banderier and
Flajolet [2]. It is known that for Dyck paths it holds:

$F(z,u)=\frac{u-zE(z)}{u\big{(}1-z\big{(}u+\frac{1}{u}\big{)}\big{)}},$

where it is here assumed that the paths are starting at the origin and are
never going below the $x$-axis. In our case, the paths go from $y=-2$ to
$y=m_{2}-m_{1}$, so by symmetry we need to extract the coefficient of
$u^{m_{1}-m_{2}-2}$, thus we get for the third part
$G_{3}(z)=[u^{m_{1}-m_{2}-2}]F(z,u)$.

Collecting all parts $G_{1}(z)$, $G_{2}(z)$ and $G_{3}(z)$, we obtain for the
generating function

$G(z,q)=\sum_{\text{$p$ Dyck path}}z^{\text{length of $p$}}q^{\text{$\\#$
downward visits at $y\in\\{-1,-2\\}$ of $p$}},$

where the sum is running over all Dyck paths $p$ starting at the origin and
ending at $y=m_{2}-m_{1}\leq-2$,

$G(z,q)=[u^{m_{1}-m_{2}-2}]\frac{z^{2}q^{2}E(z)}{1-2z^{2}qE(z)}\cdot\frac{u-zE(z)}{u\big{(}1-z\big{(}u+\frac{1}{u}\big{)}\big{)}}.$
(5)

The extraction of coefficients can actually be carried out in an explicit
manner, as the denominators factors nicely [2],

$u\big{(}1-z\big{(}u+\frac{1}{u}\big{)}\big{)}=u-zu^{2}-z=-z(u-u_{1}(z))(u-u_{2}(z)),$

where

$u_{1}(z)=\frac{1-\sqrt{1-4z^{2}}}{2z}=zE(z),\quad
u_{2}(z)=\frac{1+\sqrt{1-4z^{2}}}{2z},$ (6)

such that

$\frac{u-zE(z)}{u\big{(}1-z\big{(}u+\frac{1}{u}\big{)}\big{)}}=\frac{1}{-z(u-u_{2}(z))}=\frac{1}{zu_{2}(z)\big{(}1-\frac{u}{u_{2}(z)}\big{)}}=\frac{u_{1}(z)}{z\big{(}1-u\cdot
u_{1}(z)\big{)}},$

where we used that $u_{1}(z)u_{2}(z)=1$. This leads to the following result.

######  Proposition 5.

Assume that $m_{1}\geq m_{2}+2$. The generating function $G(z,q)$ of the
number of Dyck paths of length $n=m_{1}+m_{2}$, starting at level $0$ and
ending at level $m_{2}-m_{1}$, weighted according to downward visits at levels
$y=-1$ and $y=-2$, is given by

$G(z,q)=q^{2}\frac{1}{1-2z^{2}qE(z)}\cdot\big{(}zE(z)\big{)}^{m_{1}-m_{2}}.$
(7)

######  Remark 2 (Generalized composition schemes).

The structure of the generating function is similar to (extended) composition
schemes

$F(z,q)=\Psi\big{(}qH(z)\big{)}\cdot M(z),$

considered in [4, 3, 13]. The main novelty here is the dependance on the
additional parameter $u$ in (5), or equivalently, the power
$\big{(}zE(z)\big{)}^{m_{1}-m_{2}-1}$, where $m_{1}-m_{2}$ is allowed to
depend on $n$, when analyzing $[z^{n}]F(z,q)$. This leads to new asymptotic
regimes. A general study of such augmented schemes is forthcoming, together
with the authors of [4].

Next, we compare this generating function to the generating function of the
number of zero-contacts starting at $y=0$ and ending at $y=m_{2}-m_{1}\neq 0$,
where the walks have the length $n=m_{1}+m_{2}$. We can decompose this
generating function into two parts: the first part is a bridge, where the
weight $q$ encodes the zero-contacts. Then, after a single step, we leave the
$x$-axis and start our approach to the final position at $d=|m_{2}-m_{1}|$:

$\begin{split}&[u^{|m_{1}-m_{2}|-1}]\frac{1}{1-2z^{2}qE(z)}\cdot
z\cdot\frac{u-zE(z)}{u\big{(}1-z\big{(}u+\frac{1}{u}\big{)}\big{)}}\\\
&\quad=\frac{1}{z}\cdot\frac{1}{1-2z^{2}qE(z)}\big{(}zE(z)\big{)}^{|m_{1}-m_{2}|+1}.\end{split}$
(8)

We observe that both generating functions (5) and (8) are nearly identical,
except a shift of length one in the length and in the difference
$d=|m_{1}-m_{2}|$. Symbolically,

$Y_{m_{1},m_{2}}\sim W_{m_{1}-1,m_{2}}+2,$

which readily leads to the stated limit law for $Y_{m_{1},m_{2}}$. Note that
one can give a more detailed analysis by extraction of coefficients, very
similar to [21]; we leave the details to the interested reader.

Now are are ready to state the main result, namely the limit law for $X_{n}$.

######  Theorem 3.

The random variable $X_{n}/\sqrt{n}$, counting the normalized number of
correct guesses in a one-time riffle shuffle with no feedback card guessing
game, tends for $n\to\infty$ to a sum of two independent identically
distributed half-normal distributed random variables $H_{1}$, $H_{2}$, each
one with density function $f_{H}(x)=\frac{2}{\sqrt{\pi}}e^{-x^{2}}$, $x\geq
0$,

$\frac{X_{n}}{\sqrt{n}}\operatorname{\overset{\mathcal{L}}{\rightarrow}}H_{1}+H_{2}.$

Equivalently, the density $f(x):=f_{H_{1}+H_{2}}(x)$ of the limit law
$H_{1}+H_{2}$, supported on $[0,\infty)$, is given in terms of the density
function $\varphi(x)=\frac{1}{\sqrt{2\pi}}e^{-x^{2}/2}$ and the cumulative
distribution function $\Phi(x)=\int_{-\infty}^{x}\varphi(t)dt$ of the standard
normal distribution as follows:

$f(x)=4\varphi(x)\cdot\big{(}2\Phi(x)-1\big{)}.$

$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$x$$f(x)$
Figure 5. Plot of the density function $f(x)$ of the limit law. The red
vertical line marks the expected value $\frac{2}{\sqrt{\pi}}\approx 1.12838$
and the corresponding value of the density $f(\frac{2}{\sqrt{\pi}})\approx
0.62548$.

The shape of the density matches very well the simulations in [18, Figure 3],
as well as our own simulations shown before.

###### Proof.

Our starting point is the distributional equation of $X_{n}$ stated in
Proposition 2. In the following we give a derivation of the limit law for the
first summand $Y_{h-J_{h},J_{h}}$, the second one is analyzed in a similar
way. Let $x>0$. We use the de Moivre-Laplace asymptotics of the binomial
distribution and get, with $\mu_{J}=h/2$ and $\sigma_{J}=\sqrt{h}/2$ as
denoted in (4),

$\displaystyle F_{h}(x)$
$\displaystyle:={\mathbb{P}}\big{\\{}Y_{h-J_{h},J_{h}}\leq
x\sqrt{h/2}\big{\\}}$
$\displaystyle\sim\int_{0}^{h}{\mathbb{P}}\big{\\{}Y_{h-j,j}\leq
x\sqrt{h/2}\big{\\}}\exp\Big{(}-\frac{(j-\mu_{J})^{2}}{2\sigma_{J}^{2}}\Big{)}\frac{1}{\sigma_{J}\sqrt{2\pi}}dj.$

By the asymptotics of the binomial random variable we further get by
substituting $j=\mu_{J}+\sigma_{J}t$:

$\displaystyle F_{h}(x)\sim
2\int_{0}^{\infty}{\mathbb{P}}\big{\\{}Y_{h/2-t\sqrt{h}/2,h/2+t\sqrt{h}/2}\leq
x\sqrt{h/2}\big{\\}}\exp\Big{(}-\frac{t^{2}}{2}\Big{)}\frac{1}{\sqrt{2\pi}}dt.$

Furthermore, by our previous result in Proposition 4 we obtain

${\mathbb{P}}\\{Y_{h/2-t\sqrt{h}/2,h/2+t\sqrt{h}/2}\leq x\sqrt{h/2}\\}\to
1-e^{-\frac{x(2\sqrt{2}t+x)}{4}},$

as

$t\sqrt{h}\sim t\sqrt{2}\cdot\sqrt{h/2}.$

This implies that

$F_{h}(x)\sim
1-\frac{2}{\sqrt{2\pi}}\int_{0}^{\infty}e^{-\frac{x(2\sqrt{2}t+x)}{4}-t^{2}/2}dt=1-\frac{2}{\sqrt{2\pi}}\int_{0}^{\infty}e^{-\big{(}\frac{\sqrt{2}t+x}{2}\big{)}^{2}}dt.$

The integral is readily evaluated by substituting $\tau=(\sqrt{2}t+x)/2$ and
we get

$F_{h}(x)\sim 1-\frac{2}{\sqrt{\pi}}\int_{x/2}^{\infty}e^{-\tau^{2}}d\tau.$

This implies that the arising density of the limit law of
$Y_{h-J_{h},J_{h}}/\sqrt{h/2}$ is obtained by taking the derivative w.r.t. $x$
yielding

$\frac{e^{-x^{2}/4}}{\sqrt{\pi}},\quad x\geq 0.$

Actually, this is the density of a half-normal distributed random variable
$\text{HN}(c)$ with parameter $c=\sqrt{2}$. Finally, we note that

$\sqrt{n}\sim\sqrt{4\cdot\frac{h}{2}}=2\sqrt{\frac{h}{2}},$

which implies that the limit law of $Y_{h-J_{h},J_{h}}/\sqrt{n}$ has, due to
scaling, the density

$f_{H}(x)=\frac{2}{\sqrt{\pi}}e^{-x^{2}},\quad x\geq 0.$

Finally, the density of the limit law $H_{1}+H_{2}$ of $X_{n}/\sqrt{n}$ can be
obtained using standard methods, where
$\operatorname{erf}(x)=\frac{2}{\sqrt{\pi}}\int_{0}^{x}e^{-t^{2}}dt$ denotes
the error function:

$\displaystyle f_{H_{1}+H_{2}}(x)$
$\displaystyle=\int_{0}^{x}f_{H_{1}}(t)f_{H_{2}}(x-t)dt=\frac{4}{\pi}\int_{0}^{x}e^{-t^{2}-(x-t)^{2}}dt=\frac{4}{\pi}e^{-x^{2}}\int_{0}^{x}e^{-2t(t-x)}dt$
$\displaystyle=\frac{4}{\pi}e^{-x^{2}/2}\int_{0}^{x}e^{-2(t-\frac{x}{2})^{2}}dt=\frac{2\sqrt{2}}{\sqrt{\pi}}e^{-x^{2}/2}\operatorname{erf}\big{(}\frac{x}{\sqrt{2}}\big{)}=4\varphi(x)\cdot\big{(}2\Phi(x)-1\big{)}.$

∎

##  4\. Convergence of moments

We start by collecting the moment sequence of the limit law. Then, we perform
a sanity check by comparing the moments of the limit law $H_{1}+H_{2}$ of
$X_{n}/\sqrt{n}$ with the precise results for the first five moments with
$n=4L$ tending to infinity, computed in [18]. Afterwards, we extend the
results of [18] obtaining moment convergence for arbitrary high integer
moments (for arbitrary $n\to\infty$).

######  Lemma 4 (Moments of the limit law).

The sum $H_{1}+H_{2}$ of two independent identically distributed half-normal
distributed random variables $H_{1}$, $H_{2}$, each one with density function
$f_{H}(x)=\frac{2}{\sqrt{\pi}}e^{-x^{2}}$, $x\geq 0$, has moment sequence

$\tilde{\mu}_{s}=\sum_{k=0}^{s}\binom{s}{k}\frac{\Gamma(\frac{k+1}{2})\Gamma(\frac{s-k+1}{2})}{\Gamma^{2}(\frac{1}{2})},$

for integer $s\geq 1$.

###### Proof.

We recall basic properties of the half-normal distribution $H$ with density
$f_{H}(x)=\frac{2}{\sqrt{\pi}}e^{-x^{2}}$. Its integer moments are given by

$\mu_{s}={\mathbb{E}}(H^{s})=\frac{\Gamma(\frac{s+1}{2})}{\Gamma(\frac{1}{2})}=\frac{\Gamma(\frac{s+1}{2})}{\sqrt{\pi}},$

with $s\geq 0$. Consequently, the $s$-th integer moments $\tilde{\mu}_{s}$ of
$H_{1}+H_{2}$ are given by

$\tilde{\mu}_{s}={\mathbb{E}}\Big{(}\big{(}H_{1}+H_{2}\big{)}^{s}\Big{)}=\sum_{k=0}^{s}\binom{s}{k}\mu_{k}\mu_{s-k}=\sum_{k=0}^{s}\binom{s}{k}\frac{\Gamma(\frac{k+1}{2})\Gamma(\frac{s-k+1}{2})}{\Gamma^{2}(\frac{1}{2})}.$
(9)

∎

######  Example 3 (Asymptotics of the first five moments [18]).

The first five moments of the half normal distributed random variable are
given by

$\mu_{1}=\mu_{3}=\frac{1}{\sqrt{\pi}},\ \mu_{2}=\frac{1}{2},\
\mu_{4}=\frac{3}{4},\ \mu_{5}=\frac{2}{\sqrt{\pi}}.$

This implies that the first five moments of the limit law are given by

$\tilde{\mu}_{1}=\frac{2}{\sqrt{\pi}},\
\tilde{\mu}_{2}=\frac{2}{\sqrt{\pi}}+1,\
\tilde{\mu}_{3}=\frac{5}{\sqrt{\pi}},\ \tilde{\mu}_{4}=\frac{8}{\pi}+3,\
\tilde{\mu}_{5}=\frac{43}{2\sqrt{\pi}}.$ (10)

We check with the asymptotic expansions of the moments
${\mathbb{E}}(X_{n}^{s})$, $1\leq s\leq 5$ for $n=4L$, and summarize here for
the reader’s convenience the dominant terms of the first five integer moments
of $X_{n}$, with $n=4L$, as stated in [18]:

$\displaystyle{\mathbb{E}}(X_{n})$
$\displaystyle\sim\frac{4L}{4^{L}}\binom{2L}{L},$
$\displaystyle{\mathbb{E}}(X_{n}^{2})$
$\displaystyle\sim\frac{(4L)^{2}}{2\cdot 4^{2L}}\binom{2L}{L}^{2}+4L,$
$\displaystyle{\mathbb{E}}(X_{n}^{3})$
$\displaystyle\sim\frac{40L^{2}}{4^{L}}\binom{2L}{L},$
$\displaystyle{\mathbb{E}}(X_{n}^{4})$
$\displaystyle\sim\frac{256L^{3}}{2\cdot 4^{2L}}\binom{2L}{L}^{2}+48L^{2},$
$\displaystyle{\mathbb{E}}(X_{n}^{5})$
$\displaystyle\sim\frac{688L^{3}}{4^{L}}\binom{2L}{L}.$

By the standard asymptotics

$\frac{2L}{4^{L}}\binom{2L}{L}\sim\frac{\sqrt{n}}{\sqrt{\pi}}$ (11)

and our results for the first five moments (10), we observe that indeed, for
$n=4L$, it holds

${\mathbb{E}}\big{(}\big{(}X_{n}/\sqrt{n}\big{)}^{s}\big{)}\to\tilde{\mu}_{s},\quad
1\leq s\leq 5.$

The remaining part of the section is devoted to prove that actually all
integer moments of $X_{n}/\sqrt{n}$ converge to the moments of $H_{1}+H_{2}$.
Again we deal with the generating functions description given in Lemma 1, but
we proceed in treating the occurring recurrence for $g_{m_{1},m_{2}}(q)$ in a
direct way by using the so-called kernel method, see [2, 27]. To this aim we
first rewrite (2) by setting $M:=m_{1}+m_{2}$ and $d:=m_{2}-m_{1}$, and
introducing

$\tilde{g}_{M,d}(q)=g_{m_{1},m_{2}}(q)=g_{(M-d)/2,(M+d)/2}(q).$

This yields the recurrence

$\displaystyle\tilde{g}_{M,d}(q)=q^{\delta(d,-1)+\delta(d,-2)}\cdot\tilde{g}_{M-1,d+1}+\tilde{g}_{M-1,d-1},\quad\text{for
$M\geq 1$ and $|d|\leq M$},$
$\displaystyle\tilde{g}_{0,0}(q)=1,\qquad\text{with}\quad\tilde{g}_{M,d}=0,\quad\text{for
$M<0$ or $|d|>M$}.$ (12)

Let us introduce the trivariate generating function

$\tilde{G}(z,u,q)=\sum_{M\geq
0}\sum_{d=-M}^{M}\tilde{g}_{M,d}(q)z^{M}u^{d}=\sum_{m_{1},m_{2}\geq
0}g_{m_{1},m_{2}}(q)z^{m_{1}+m_{2}}u^{m_{2}-m_{1}},$ (13)

for which we get an explicit solution.

######  Proposition 6.

The generating function $\tilde{G}(z,u,q)$ of the sequence
$\tilde{g}_{M,d}(q)$ (and thus also $g_{m_{1},m_{2}}(q)$, resp.) satisfying
recurrence (12) (and (2), resp.) is given by

$\tilde{G}(z,u,q)=\frac{\big{(}2qu^{2}z+(q-1)^{2}u-q(q-1)z\big{)}P(z^{2})-zu(u+q(q-1)z)}{zu(zu^{2}-u+z)(1-2qP(z^{2}))},$
(14)

where $P(t)=\frac{1-\sqrt{1-4t}}{2}=\sum_{n\geq
1}\frac{1}{n}\binom{2n-2}{n-1}t^{n}$ denotes the generating function of
shifted Catalan-numbers.

###### Proof.

Introducing the auxiliary functions $\tilde{G}_{d}(z,q)=\sum_{M\geq
0}\tilde{g}_{M,d}(q)z^{M}$, for $d\in\mathbb{Z}$, we immediately obtain from
(12) the system of equations

$\displaystyle\tilde{G}_{d}(z,q)$
$\displaystyle=z\tilde{G}_{d+1}(z,q)+z\tilde{G}_{d-1}(z,q),\quad\text{$d\geq
1$ or $d\leq-3$},$ $\displaystyle\tilde{G}_{0}(z,q)$
$\displaystyle=z\tilde{G}_{1}(z,q)+z\tilde{G}_{-1}(z,q)+1,$ (15)
$\displaystyle\tilde{G}_{d}(z,q)$
$\displaystyle=qz\tilde{G}_{d+1}(z,q)+z\tilde{G}_{d-1}(z,q),\quad\text{$d=-1$
or $d=-2$}.$

In order to treat (15) by means of the kernel method, we introduce the pair of
functions

$A(z,u,q)=\sum_{d\geq 0}\tilde{G}_{-d}(z,q)u^{d},\qquad B(z,u,q)=\sum_{d\geq
0}\tilde{G}_{d}(z,q)u^{d}.$

It is straightforward to get from (15) the following pair of equations for
$A(z,u,q)$ and $B(z,u,q)$, which involve the unknown functions
$\tilde{G}_{0}(z,q)$ and $\tilde{G}_{-1}(z,q)$:

$\begin{split}&(zu^{2}-u+z)A(z,u,q)\\\
&\qquad\qquad\mbox{}+((q-1)zu^{2}+u-z)\tilde{G}_{0}(z,q)+((q-1)zu^{2}-zu)\tilde{G}_{-1}(z,q)=0,\\\
&(zu^{2}-u+z)B(z,u,q)-z\tilde{G}_{0}(z,q)+zu\tilde{G}_{-1}(z,q)+u=0.\end{split}$
(16)

The roots $u_{1}=u_{1}(z)$, $u_{2}=u_{2}(z)$ satisfying
$K(z,u):=zu^{2}-u+z=z(u-u_{1})(u-u_{2})=0$, i.e., vanishing the kernel
$K(z,u)$, are the ones stated in (6). Plugging the root $u_{1}$, which admits
a power series expansion around $z=0$, for $u$ into (16), the kernel is
annihilated leading to a linear system of equations for $\tilde{G}_{0}(z,q)$
and $\tilde{G}_{-1}(z,q)$, whose solution can be written in the following way
(note that $P(z^{2})=zu_{1}(z)$):

$\tilde{G}_{0}(z,q)=\frac{(1-q)P(z^{2})+qz^{2}}{z^{2}(1-2qP(z^{2}))},\qquad\tilde{G}_{-1}(z)=\frac{qP(z^{2})}{z(1-2qP(z^{2}))}.$
(17)

According to (16) and (17), we thus also get explicit solutions for the
auxiliary trivariate g.f.:

$\displaystyle A(z,u,q)$
$\displaystyle=\frac{(z-u-(q-1)zu^{2})\tilde{G}_{0}(z,q)+(zu-(q-1)zu^{3})\tilde{G}_{-1}(z,q)}{zu^{2}-u+z},$
$\displaystyle B(z,u,q)$
$\displaystyle=\frac{z\tilde{G}_{0}(z,q)-zu\tilde{G}_{-1}(z,q)-u}{zu^{2}-u+z}.$

Finally, according to the definition, we have

$\tilde{G}(z,u,q)=A(z,u^{-1},q)+B(z,u,q)-\tilde{G}_{0}(z,q),$

which, after simple manipulations, yields the stated result. ∎

Bearing in mind the representation of $f_{n}(q)$ given in Lemma 1, we will set
$u=1$, i.e., considering

$\tilde{G}(z,q):=\tilde{G}(z,1,q)=\sum_{M\geq
0}\sum_{d=-M}^{M}\tilde{g}_{M,d}(q)z^{M}=\sum_{M\geq
0}\sum_{m=0}^{M}g_{m,M-m}(q)z^{M}.$ (18)

Namely, when setting $R(q)=4q^{4}-2(q^{2}+q^{3})$, this yields

$f_{n}(q)=R(q)+[z^{h}]\tilde{G}(z,q)\cdot[z^{n-h}]\tilde{G}(z,q).$ (19)

As we are interested in the moments of $X_{n}$, we will set $q=1+w$ in (19)
and carry out a series expansion around $w=0$. According to the definition of
$f_{n}(q)$, the coefficients in the corresponding expansion involve the
factorial moments of $X_{n}$,

$f_{n}(1+w)=\sum_{s\geq
0}\frac{2^{n}\mathbb{E}(X_{n}^{\underline{s}})}{s!}w^{s}.$

When denoting the respective expansions of the remaining functions via

$R(1+w)=\sum_{0\leq s\leq 4}r_{s}w^{s},\qquad\tilde{G}(z,1+w)=\sum_{s\geq
0}\tilde{g}_{s}(z)w^{s},$

we thus get from (19), by extracting the coefficient of $w^{s}$, the useful
representation:

$\mathbb{E}(X_{n}^{\underline{s}})=\frac{s!\,r_{s}}{2^{n}}+\sum_{k=0}^{s}\frac{s!}{2^{n}}\sum_{k=0}^{s}\big{(}[z^{h}]\tilde{g}_{k}(z)\big{)}\cdot\big{(}[z^{n-h}]\tilde{g}_{s-k}(z)\big{)}.$
(20)

Of course, to make use of it, we require suitable expansions of
$\tilde{G}(z,1+w)$. First we use Proposition 6 and set $u=1$ to get the
explicit formula (with $P(t)$ defined above):

$\tilde{G}(z,q)=\frac{1}{1-2z}+\frac{(q-1)\big{(}qz^{2}+(1-q+qz)P(z^{2})\big{)}}{z(1-2z)(1-2qP(z^{2}))}.$
(21)

Next we consider the coefficients in the series expansion of
$\tilde{G}(z,1+w)$ around $w=0$, i.e., the functions
$\tilde{g}_{s}(z)=[w^{s}]\tilde{G}(z,1+w)$, determine the dominant
singularities and provide local expansions around the singularity yielding the
main asymptotic contributions.

######  Lemma 5.

Let $\tilde{G}(z,q)$ as defined in (18). The functions
$\tilde{g}_{s}(z)=[w^{s}]\tilde{G}(z,1+w)$ obtained as coefficients in a
series expansion of $\tilde{G}(z,1+w)$ around $w=0$ have radius of convergence
$\frac{1}{2}$ and, for $s\geq 1$, have the two dominant singularities
$\rho_{1,2}=\pm\frac{1}{2}$. Moreover, the local behaviour of
$\tilde{g}_{s}(z)$ around $\rho:=\rho_{1}=\frac{1}{2}$ is given as follows,

$\tilde{g}_{s}(z)=\frac{1}{2^{\frac{s}{2}}\,(1-2z)^{\frac{s}{2}+1}}\cdot\big{(}1+\mathcal{O}(\sqrt{1-2z})\big{)},\quad
s\geq 0.$

######  Remark 3.

It is not difficult to show that the second dominant singularity
$\rho_{2}=-\frac{1}{2}$ occurring in the functions $\tilde{g}_{s}(z)$ of Lemma
5 leads to contributions that do not affect the main terms stemming from the
contributions of the singularity $\rho=\rho_{1}=\frac{1}{2}$. Since we are
here only interested in the main term contribution, we will restrict ourselves
to elaborate the expansion around $\rho$.

###### Proof.

The explicit formula for $\tilde{G}(z,q)$ given in (21) can be rewritten as

$\tilde{G}(z,q)=\frac{1}{1-2z}+\frac{(q-1)\big{(}z^{2}+zP(z^{2})+(q-1)(z^{2}+(z-1)P(z^{2}))\big{)}}{z(1-2z)(1-2P(z^{2}))\big{(}1-\frac{2(q-1)P(z^{2})}{1-2P(z^{2})}\big{)}}.$

Setting $q=1+w$, we obtain the series expansion

$\displaystyle\tilde{G}(z,1+w)=\frac{1}{1-2z}+\frac{w\big{(}z^{2}+zP(z^{2})+w(z^{2}+(z-1)P(z^{2}))\big{)}}{z(1-2z)(1-2P(z^{2}))\big{(}1-\frac{2wP(z^{2})}{1-2P(z^{2})}\big{)}}$
$\displaystyle\quad=\frac{1}{1-2z}+w\frac{P(z^{2})+z}{(1-2z)(1-2P(z^{2}))}$
$\displaystyle\qquad\mbox{}+\sum_{s\geq
2}w^{s}\frac{(z+P(z^{2}))(2P(z^{2}))^{s-1}}{(1-2z)(1-2P(z^{2}))^{s}}+\sum_{s\geq
2}w^{s}\frac{(z^{2}+(z-1)P(z^{2}))(2P(z^{2}))^{s-2}}{z(1-2z)(1-2P(z^{2}))^{s-1}}$
$\displaystyle=\frac{1}{1-2z}+w\frac{P(z^{2})+z}{(1-2z)(1-2P(z^{2}))}+\sum_{s\geq
2}w^{s}\frac{(2P(z^{2}))^{s-2}((z+1)P(z^{2})-z^{2})}{z(1-2z)(1-2P(z^{2}))^{s}},$

where we used in the last step the relation $(P(z^{2}))^{2}=P(z^{2})-z^{2}$.
Thus, the functions $\tilde{g}_{s}(z)$ are given as follows:

$\displaystyle\tilde{g}_{0}(z)=\frac{1}{1-2z},\qquad\tilde{g}_{1}(z)=\frac{P(z^{2})+z}{(1-2z)(1-2P(z^{2}))},$
$\displaystyle\tilde{g}_{s}(z)=\frac{\big{(}(z+1)P(z^{2})-z^{2}\big{)}(2P(z^{2}))^{s-2}}{z(1-2z)(1-2P(z^{2}))^{s}},\quad
s\geq 2.$ (22)

Since $1-2P(z^{2})=\sqrt{1-4z^{2}}=\sqrt{1-2z}\cdot\sqrt{1+2z}$, it is
immediate from the explicit formulæ, that the functions $\tilde{g}_{s}(z)$
have radius of convergence $\frac{1}{2}$ with dominant singularities
$\rho_{1}=\frac{1}{2}$ and, for $s\geq 1$, $\rho_{2}=-\frac{1}{2}$. To
describe the local behaviour of $\tilde{g}_{s}(z)$ around $\rho:=\rho_{1}$ we
use the notation $\mathcal{Z}=\frac{1}{1-2z}$ and
$\tilde{\mathcal{Z}}=\frac{1}{1-4z^{2}}=\frac{1}{(1-2z)(1+2z)}$. We collect a
few local expansions around $\rho$ used thereafter:

$\displaystyle
z=\frac{1}{2}\cdot\big{(}1+\mathcal{O}(\mathcal{Z}^{-1})\big{)},\qquad\tilde{Z}=\frac{\mathcal{Z}}{2}\cdot\big{(}1+\mathcal{O}(\mathcal{Z}^{-1})\big{)},$
$\displaystyle
P(z^{2})=\frac{1}{2}\cdot\big{(}1+\mathcal{O}(\mathcal{Z}^{-\frac{1}{2}})\big{)},\qquad\frac{1}{1-2P(z^{2})}=\frac{\mathcal{Z}^{\frac{1}{2}}}{2^{\frac{1}{2}}}\cdot\big{(}1+\mathcal{O}(\mathcal{Z}^{-1})\big{)}.$

We then immediately get from (22):

$\tilde{g}_{0}(z)=\mathcal{Z},\qquad\tilde{g}_{1}(z)=\frac{\mathcal{Z}^{\frac{3}{2}}}{2^{\frac{1}{2}}}\cdot\big{(}1+\mathcal{O}(\mathcal{Z}^{-\frac{1}{2}})\big{)}.$

Furthermore, with these expansions we easily obtain, for $s\geq 2$ arbitrary
but fixed,

$\displaystyle\tilde{g}_{s}(z)$
$\displaystyle=\big{(}1+\mathcal{O}(\mathcal{Z}^{-\frac{1}{2}})\big{)}\cdot\big{(}\frac{1}{2}+\mathcal{O}(\mathcal{Z}^{-\frac{1}{2}})\big{)}\cdot
2\big{(}1+\mathcal{O}(\mathcal{Z}^{-1})\big{)}\cdot\mathcal{Z}\cdot\frac{\mathcal{Z}^{\frac{s}{2}}}{2^{\frac{s}{2}}}\cdot\big{(}1+\mathcal{O}(\mathcal{Z}^{-1})\big{)}$
$\displaystyle=\frac{\mathcal{Z}^{\frac{s}{2}+1}}{2^{\frac{s}{2}}}\cdot\big{(}1+\mathcal{O}(\mathcal{Z}^{-\frac{1}{2}})\big{)},$

which completes the proof. ∎

Now we have all ingredients at hand to show convergence of the moments of
$X_{n}$.

######  Theorem 6.

The $s$-th integer moments
${\mathbb{E}}\big{(}\big{(}\frac{X_{n}}{\sqrt{n}}\big{)}^{s}\big{)}$ of the
suitably scaled r.v. $X_{n}$ converge, for arbitrary but fixed $s\geq 0$ and
$n\to\infty$, to the moments of the limit law $H_{1}+H_{2}$:

${\mathbb{E}}\Big{(}\big{(}\frac{X_{n}}{\sqrt{n}}\big{)}^{s}\Big{)}\to\tilde{\mu}_{s}={\mathbb{E}}\big{(}\big{(}H_{1}+H_{2}\big{)}^{s}\big{)}=\sum_{k=0}^{s}\binom{s}{k}\cdot\frac{\Gamma\big{(}\frac{k+1}{2}\big{)}\Gamma\big{(}\frac{s-k+1}{2}\big{)}}{\pi}.$

###### Proof of Theorem 6.

We consider the representation (20) of the $s$-th factorial moments of $X_{n}$
and first observe that $r_{s}$, the contributions of $R(q)$, are bounded,
$|r_{s}|\leq 24$, thus turn out to be exponentially small compared to the
remaining contributions. Consequently, they can be neglected, yielding

$\mathbb{E}(X_{n}^{\underline{s}})\sim\sum_{k=0}^{s}\frac{s!}{2^{n}}\sum_{k=0}^{s}\big{(}[z^{h}]\tilde{g}_{k}(z)\big{)}\cdot\big{(}[z^{n-h}]\tilde{g}_{s-k}(z)\big{)}.$
(23)

In order to extract coefficients from the functions $\tilde{g}_{s}(z)$
asymptotically, we use Lemma 5 and apply transfer lemmata [13] that
“translate” the local behaviour of the generating function near the dominant
singularity to the asymptotic behaviour of their coefficients. The local
expansion around $\rho=\frac{1}{2}$ given there (see also Remark 3)
immediately leads to the following asymptotic behaviour, for $n\to\infty$ and
arbitrary but fixed $s\geq 0$:

$[z^{n}]\tilde{g}_{s}(z)=\frac{2^{n}n^{\frac{s}{2}}}{2^{\frac{s}{2}}\Gamma(\frac{s}{2}+1)}\cdot\big{(}1+\mathcal{O}(n^{-\frac{1}{2}})\big{)}=\frac{2^{n}2^{\frac{s}{2}}\Gamma(\frac{s+1}{2})}{s!\sqrt{\pi}}\cdot\big{(}1+\mathcal{O}(n^{-\frac{1}{2}})\big{)},$

where we used for the latter equation the duplication formula of the Gamma
function,
$\Gamma(\frac{s}{2}+1)\Gamma(\frac{s+3}{2})=\sqrt{\pi}\,2^{-s-1}\Gamma(s+2)$,
and $\Gamma(\frac{1}{2})=\sqrt{\pi}$.

Plugging this asymptotic result into (23) and using
$h=\frac{n}{2}\cdot\big{(}1+\mathcal{O}(n^{-1})\big{)}$, we get

$\begin{split}\mathbb{E}(X_{n}^{\underline{s}})&=\sum_{k=0}^{s}\frac{s!}{2^{n}}\cdot\frac{2^{h}2^{\frac{k}{2}}\Gamma(\frac{k+1}{2})h^{\frac{k}{2}}}{\sqrt{\pi}\,k!}\cdot\big{(}1+\mathcal{O}(h^{-\frac{1}{2}})\big{)}\\\
&\qquad\cdot\frac{2^{n-h}2^{\frac{s-k}{2}}\Gamma(\frac{s-k+1}{2})(n-h)^{\frac{s-k}{2}}}{\sqrt{\pi}\,(s-k)!}\cdot\big{(}1+\mathcal{O}((n-h)^{-\frac{1}{2}})\big{)}\\\
&=\sum_{k=0}^{s}\binom{s}{k}\cdot\frac{\Gamma(\frac{k+1}{2})\Gamma(\frac{s-k+1}{2})}{\pi}\cdot
n^{\frac{s}{2}}\cdot\big{(}1+\mathcal{O}(n^{-\frac{1}{2}})\big{)}.\end{split}$
(24)

The raw moments can be expressed in terms of the factorial moments by

${\mathbb{E}}(X_{n}^{s})=\sum_{k=0}^{s}\genfrac{\left\\{}{\right\\}}{0.0pt}{}{s}{k}{\mathbb{E}}(X_{n}^{\underline{k}}),$

where $\genfrac{\left\\{}{\right\\}}{0.0pt}{}{s}{k}$ denote the Stirling
numbers of the second kind, counting the number of ways to partition a set of
$s$ objects into $k$ non-empty subsets. From (24) we thus obtain

${\mathbb{E}}(X_{n}^{s})={\mathbb{E}}(X_{n}^{\underline{s}})+\mathcal{O}\big{(}{\mathbb{E}}(X_{n}^{\underline{s-1}})\big{)}$

for $n\to\infty$ and arbitrary but fixed $s\geq 1$. This leads to the
expansion

$\mathbb{E}(X_{n}^{s})=\sum_{k=0}^{s}\binom{s}{k}\cdot\frac{\Gamma(\frac{k+1}{2})\Gamma(\frac{s-k+1}{2})}{\pi}\cdot
n^{\frac{s}{2}}\cdot\big{(}1+\mathcal{O}(n^{-\frac{1}{2}})\big{)}=\tilde{\mu}_{s}\cdot
n^{\frac{s}{2}}\cdot\big{(}1+\mathcal{O}(n^{-\frac{1}{2}})\big{)}.$

Scaling of $X_{n}$ by $\sqrt{n}$ immediately yields the stated result. ∎

######  Remark 4 (Proof of Theorem 3 by the method of moments).

Finally, we note that Theorem 6 also strengthens Theorem 3. Carleman’s
criterion [6, pp. 189–220] for the Stieltjes moment problem, support
$[0,\infty)$, states that if

$\sum_{s=0}^{\infty}\mu_{s}^{-1/(2s)}=+\infty,$ (25)

then the moment sequence $(\mu_{s})_{s\geq 1}$ determines a unique
distribution. Furthermore, this implies that if there exists a constant $C>0$
such that

$\mu_{s}\leq C^{s}(2s)!\quad\text{for }s\in\mathbb{N},$

then Carleman’s criterion is satisfied. We note that for the sum of
independent half-normals $H_{1}+H_{2}$ with moment sequence
$(\tilde{\mu}_{s})_{s\in\mathbb{N}}$ it holds

$\begin{split}\tilde{\mu}_{s}&=\sum_{k=0}^{s}\binom{s}{k}\frac{\Gamma(\frac{k+1}{2})\Gamma(\frac{s-k+1}{2})}{\Gamma^{2}(\frac{1}{2})}\leq\frac{1}{\pi}\sum_{k=0}^{s}\binom{s}{k}\Gamma(k+1)\Gamma(s-k+1)=\frac{s}{\pi}s!\leq(2s)!,\end{split}$

such that the divergence in Carleman’s criterion is satisfied. Thus, by the
Fréchet–Shohat theorem [14], we obtain the weak convergence of the normalized
random variable $\frac{X_{n}}{\sqrt{n}}$ to $H_{1}+H_{2}$ with moment sequence
$(\tilde{\mu}_{s})_{s\in\mathbb{N}}$.

##  5\. Conclusion

We studied the number of correct guesses when starting with an ordered deck of
$n$ cards labeled $1$ up to $n$ is riffle-shuffled exactly one time. Assuming
that no feedback is given to the person guessing, the limit law was
determined. Additionally, we have shown convergence of all positive integer
moments, providing a second proof of the limit law. We note that the approach
of this work also allows to analyze different questions, like waiting times
for correct guesses, etc.

## Declarations of interest

The authors declare that they have no competing financial or personal
interests that influenced the work reported in this paper.

## References

  * [1] D. Aldous and P. Diaconis.  Shuffling cards and stopping times.  Amer. Math. Monthly, 93:333–348, 1986.
  * [2] C. Banderier and P. Flajolet.  Basic analytic combinatorics of directed lattice paths.  Theoretical Computer Science, 281(1–2):37–80, 2002.
  * [3] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria.  Random maps, coalescing saddles, singularity analysis, and Airy phenomena.  Random Struct. Algorithms, 19(3-4):194–246, 2001.
  * [4] C. Banderier, M. Kuba, and M. Wallner.  Phase transitions of composition schemes: Mittag-leffler and mixed poisson distributions.  Accepted for publication in Annals of Applied Probability.
  * [5] D. Blackwell and J. L. Hodges Jr.  Design for the control of selection bias.  The Annals of Mathematical Statistics, 28(2):449–460, 1957\.
  * [6] T. Carleman.  Sur les équations intégrales singulières à noyau réel et symétrique.  Uppsala Universitets Årsskrift, 1923.
  * [7] M. Ciucu.  No-feedback card guessing for dovetail shuffles.  Ann. Appl. Probab., 8(4):1251–1269, 1998.
  * [8] P. Diaconis.  Statistical problems in esp research.  Science, 201(4351):131–136, 1978.
  * [9] P. Diaconis and R. Graham.  The analysis of sequential experiments with feedback to subjects.  Annals of Statistics, 9(1):3–23, 1981.
  * [10] P. Diaconis, M. McGrath, and J. Pitman.  Riffle shuffles, cycles, and descents.  Combinatorica, 15:11–29, 1995.
  * [11] B. Efron.  Forcing a sequential experiment to be balanced.  Biometrika, 58(3):403–417, 1971.
  * [12] R. A. Fisher.  Design of experiments.  British Medical Journal, 1(3923):554, 1936.
  * [13] P. Flajolet and R. Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [14] M. Fréchet and J. Shohat.  A proof of the generalized second limit theorem in the theory of probability.  Trans. Amer. Math. Soc., 33(2):533–543, 1931.
  * [15] E. Gilbert.  Theory of shuffling.  Technical memorandum, Bell Labs, 1955.
  * [16] J. He and A. Ottolini.  Card guessing and the birthday problem for sampling without replacement.  Accepted for publication in Annals of Applied Probability., 2021.
  * [17] A. Knopfmacher and H. Prodinger.  A simple card guessing game revisited.  Electronic Journal of Combinatorics, 8, R13:9 pages, 2001.
  * [18] T. Krityakierne, P. Siriputcharoen, T. A. Thanatipanonda, and C. Yapolha.  No-feedback card guessing game: Moments and distributions under the optimal strategy.  Manuscript (Arxiv), 2022.
  * [19] T. Krityakierne and T. A. Thanatipanonda.  No feedback? No worries! The art of guessing the right card.  Manuscript (Arxiv), 2022.
  * [20] T. Krityakierne and T. A. Thanatipanonda.  The card guessing game: A generating function approach.  Journal of Symbolic Computation, 115:1–17, 2023.
  * [21] M. Kuba and A. Panholzer.  On card guessing with two types of cards.  Manuscript (Arxiv), 2023.
  * [22] M. Kuba, A. Panholzer, and H. Prodinger.  Lattice paths, sampling without replacement, and limiting distributions.  Electronic Journal of Combinatorics, 16 (1), R67:12 pages, 2009\.
  * [23] K. Levasseur.  How to beat your kids at their own game.  Mathematical Magazine, 61:301–305, 1988.
  * [24] P. Liu.  On card guessing game with one time riffle shuffle and complete feedback.  Discrete Applied Mathematics, 288:270–278, 2021.
  * [25] A. Ottolini and S. Steinerberger.  Guessing cards with complete feedback.  Manuscript (Arxiv), 2022.
  * [26] A. Ottolini and R. Tripathi.  Central limit theorem in complete feedback games.  Manuscript (Arxiv), 2023.
  * [27] H. Prodinger.  The kernel method: a collection of examples.  Séminaire Lotharingien de Combinatoire, 50, B50f:19 pages, 2001.
  * [28] R. C. Read.  Card-guessing with information. a problem in probability.  American Mathematical Monthly, 69:506–511, 1962.
  * [29] D. Zagier.  How often should you beat your kids?  Mathematical Magazine, 63:89–92, 1990.


* [14] Everett Howe, Franck Leprévost, and Bjorn Poonen.  Large torsion subgroups of split Jacobians of curves of genus two or three.  Forum. Math, 12(3):315–364, 2000.
  * [15] Tomoyoshi Ibukiyama.  On rational points of curves of genus 3 over finite fields.  Tohoku Mathematical Journal, 45(3):311–329, 1993.
  * [16] Jun-ichi Igusa.  Arithmetic variety of moduli for genus two.  Annals of Mathematics, pages 612–649, 1960.
  * [17] Ernst Kani and Michael Rosen.  Idempotent relations and factors of Jacobians.  Mathematische Annalen, 284:307–327, 1989.
  * [18] Toshiyuki Katsura.  Decomposed Richelot isogenies of Jacobian varieties of curves of genus 3.  Journal of Algebra, 588:129–147, 2021.
  * [19] Toshiyuki Katsura and Katsuyuki Takashima.  Counting Richelot isogenies between superspecial abelian surfaces.  In Proceedings of Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), MSP, 2020.
  * [20] Toshiyuki. Katsura and Katsuyuki Takashima.  Decomposed Richelot isogenies of Jacobian varieties of hyperelliptic curves and generalized Howe curves.  arXiv: 2108.06936, 2021.
  * [21] Momoanri. Kudo and Shushi Harashita.  Algorithmic study of superspecial hyperelliptic curves over finite fields.  arXiv:1907.00894 [math.AG] (the full version of [23]), 2019.
  * [22] Momonari Kudo.  Constructing superspecial curves in higher genus.  in preparation, 2022.
  * [23] Momonari Kudo and Shushi Harashita.  Superspecial hyperelliptic curves of genus 4 over small finite fields.  In International Workshop on the Arithmetic of Finite Fields–WAIFI 2018, pages 58–73. Springer, 2018.
  * [24] Momonari Kudo and Shushi Harashita.  Algorithm to enumerate superspecial Howe curves of genus 4.  preprint, arXiv:2003.04153, 2020.
  * [25] Momonari Kudo, Shushi Harashita, and Everett Howe.  Algorithms to enumerate superspecial Howe curves of genus four.  In Proceedings of Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), MSP, 2020.
  * [26] Momonari Kudo, Shushi Harashita, and Hayato Senda.  The existence of supersingular curves of genus 4 in arbitrary characteristic.  Research in Number Theory, 6(4):1–17, 2020.
  * [27] Yagati Lakshman.  A single exponential bound on the complexity of computing Gröbner bases of zero dimensional ideals.  In Effective methods in algebraic geometry, pages 227–234. Springer, 1991.
  * [28] Reynald Lercier and Christophe Ritzenthaler.  Hyperelliptic curves and their invariants: geometric, arithmetic and algorithmic aspects.  Journal of Algebra, 372:595–636, 2012.
  * [29] Reynald Lercier, Christophe Ritzenthaler, Florent Rovetta, and Jeroen Sijsling.  Parametrizing the moduli space of curves and applications to smooth plane quartics over finite fields.  LMS Journal of Computation and Mathematics, 17(A):128–147, 2014\.
  * [30] Reynald Lercier, Christophe Ritzenthaler, and Jeroen Sijsling.  Fast computation of isomorphisms of hyperelliptic curves and explicit Galois descent.  The Open Book Series, 1(1):463–486, 2013.
  * [31] James Milne.  Jacobian varieties.  In Arithmetic geometry, pages 167–212. Springer, 1986.
  * [32] David Mumford, Chidambaran Padmanabhan Ramanujam, and Jurij Ivanovič Manin.  Abelian varieties, volume 3.  Oxford university press Oxford, 1974.
  * [33] Ryo Ohashi.  Maximality of Ciani curves over finite fields.  Finite Fields and Their Applications, 83:102089, 2022.
  * [34] Ryo Ohashi.  On the maximality of hyperelliptic Howe curves of genus 3.  Kodai Mathematical Journal, 45(2):282–294, 2022.
  * [35] Ryo. Ohashi, Momonari. Kudo, and Shushi Harashita.  Fast enumeration of superspecial hyperelliptic curves of genus 4 with automorphism group $V_{4}$.  to appear in Proceedings of WAIFI2022, 2022.
  * [36] Toshiaki Ohno.  The graded ring of invariants of ternary quartics I, 2005.
  * [37] Frans Oort.  Hyperelliptic supersingular curves.  In Arithmetic Algebraic Geometry, pages 247–284. Springer, 1991\.
  * [38] Jennifer Paulhus.  Decomposing Jacobians of curves with extra automorphisms.  Acta Arithmetica, 132(3):231–244, 2008.
  * [39] Jennifer Paulhus and M. Rojas Anita.  Completely decomposable Jacobian varieties in new genera.  Experimental Mathematics, 26:430–445, 2017.
  * [40] Christophe Ritzenthaler Reynald Lercier, Jeroen Sijsling.  Functionalities for genus 2 and 3 curves.  arXiv:2102.04372 [math.AG], 2021.
  * [41] Sander Rijnswou, van.  Testing the equivalence of planar curves.  PhD thesis, Mathematics and Computer Science, 2001.
  * [42] Tetsuji Shioda.  On the graded ring of invariants of binary octavics.  American Journal of Mathematics, 89(4):1022–1046, 1967.
  * [43] Tetsuji Shioda.  Supersingular K3 surfaces.  In Algebraic geometry, pages 564–591. Springer, 1979.
  * [44] Henning Stichtenoth.  Über die automorphismengruppe eines algebraischen funktionenkörpers von primzahlcharakteristik.  Archiv der Mathematik, 24:527–544, 1973.