# On card guessing game with one time riffle shuffle and complete feedback

Pengda Liu  Department of Mathematics, Stanford University, Stanford, CA 94305
<EMAIL_ADDRESS>
(Date: March 2020)

###### Abstract.

This paper studies the game of guessing riffle-shuffled cards with complete
feedback. A deck of $n$ cards labelled 1 to $n$ is riffle-shuffled once and
placed on a table. A player tries to guess the cards from top and is given
complete feedback after each guess. The goal is to find the guessing strategy
with maximum reward (expected number of correct guesses). We give the optimal
strategy for this game and prove that the maximum expected reward is
$n/2+\sqrt{2/\pi}\cdot\sqrt{n}+O(1)$, partially solving an open problem of
Bayer and Diaconis [2].

###### Key words and phrases:

card guessing, dovetail shuffle, asymptotic analysis

###### 2010 Mathematics Subject Classification:

60C05, 65C50

##  1\. Introduction

Consider the following game in which a deck of $n$ cards is shuffled according
to some method. A player is then asked to guess the shuffled deck from top
down. Each round, the player only guesses the card at the top of the deck and
receives certain feedback after the guess. Then the top card is removed and
the player continues to guess the next card until the deck is empty. The
reward of the game is the total number of correct guesses. The goal is to find
the optimal guessing strategy so that the expected reward is maximized. The
best strategy would then depend on the {shuffling method, feedback}
combination. This problem is studied in [3] in the framework of sequential
experiments and is shown to have great applications in statistical testings
like taste testing and partially randomized clinical trials. Three common
feedbacks that they consider are

  1. .

zero feedback
In this scenario, no feedback of any kind is given.

  2. .

correctness feedback
In this scenario, after each guess, the player is told whether the guess is
correct or not.

  3. .

complete feedback
In this scenario, after each guess, the correct card is revealed to the
player.

They mostly focus on the uniform shuffling setting. In this paper, we consider
the game of dovetail shuffle (also called riffle shuffle and we will use the
two names interchangeably) with complete feedback. In [2] Bayer and Diaconis
raised the open problem of deciding the optimal guessing strategy with
complete feedback when a deck has been riffle shuffled an arbitrary number of
times and calculating the expected reward. We make the first known progress
towards this problem by completely solving the case where the cards are riffle
shuffled once. This already requires new techniques and the asymptotic formula
for the expected reward appears to be highly non-trivial. We present our main
results next.

###  1.1. Main Results

Consider the following algorithm for playing the game.

######  Algorithm 1.1.

  1. 1.

(guessing consecutive stage) Guess 1 at the first step. After that, if the
previously revealed card sequence $[1,2,...,m]$ is still consecutive, then we
guess the next to be card $m+1$.

  2. 2.

(separating pile stage) Suppose that when card $k$ is shown, the revealed
sequence $1,2...m,k$ becomes non-consecutive, separate the remaining cards
into two sequences $A=\\{m+1,...,k-1\\}$ and $B=\\{k+1,...,n\\}$.

  3. 3.

(guess interleave stage) Each time guess the first card in the longer sequence
and cross the revealed card from its sequence.

######  Remark 1.2.

When $m+1>k-1$, we let $A$ to be empty and if $k+1>n$, we let $B$ to be empty.

We show that the algorithm is optimal and give its expected return as the next
theorem.

######  Theorem 1.3.

Algorithm 1.1 is the optimal strategy for guessing a deck of $n$ cards riffle
shuffled once with complete feedback and has expected reward $\frac{1}{2}\cdot
n+\sqrt{2/\pi}\cdot\sqrt{n}+O(1)$.

This will be proved in section 3 and next we introduce some notations to be
used in the paper.

###  1.2. Notations

For an event or statement $A$, we use $\delta(A)$ to denote the indicator
function. For two functions $f(n)$ and $g(n)$ of non-negative integers, $f\sim
g$ means $\lim_{n\rightarrow\infty}f/g=1$, $f=O(g)$ means $|f|\leq C|g|$ for
some universal constant $C$ and $f=o(g)$ means
$\lim_{n\rightarrow\infty}f/g=0$. For two probability distributions $P_{1}$
and $P_{2}$ on a finite set $\Omega$, the total variation distance
$TV(P_{1},P_{2})$ is defined to be

$TV(P_{1},P_{2})=\frac{1}{2}\sum_{\omega\in\Omega}|P_{1}(\omega)-P_{2}(\omega)|.$

An equivalent definition is

$TV(P_{1},P_{2})=\frac{1}{2}\sup_{f:\Omega\rightarrow[-1,1]}\\{\sum_{\omega\in\Omega}P_{1}(\omega)f(\omega)-\sum_{\omega\in\Omega}P_{2}(\omega)f(\omega)\\}.$

We let $[n]$ denote the sequence $1,2,...,n$ and use $S_{n}$ for the
permutation group of $[n]$. For a sequence $a=a_{1},...,a_{n}$ that are
distinct numbers in $[n]$, its rising sequence is a maximal increasing
consecutive subsequence. Let $rs(a)$ denote the number of rising sequences of
$a$. For example, for $a=[1,4,2,5,3,6]$, its rising sequences are $[1,2,3]$
and $[4,5,6]$, thus $rs(a)=2$. For any $\pi\in S_{n}$, let
$rs(\pi)=rs(\pi([n]))$ to be the number of rising sequences of the permutation
$\pi$. We will particularly care about the permutations with 2 rising
sequences and let $R_{n}=|\\{\pi\in S_{n}:rs(\pi)=2\\}|$.

###  1.3. Formulation of shuffling

Throughout this paper we assume that initially a deck of $n$ cards are laid
and labeled as $1,2,...,n$ from top to bottom. A given shuffling method is an
algorithm $f$ that upon query outputs a shuffled sequence $(c_{1},...,c_{n})$
representing that from top to bottom, the shuffled cards are
$c_{1},...,c_{n}$. We formulate such algorithm $f$ as follows. First $f$ is a
random permutation and thus defines a probability distribution $Q_{f}$ over
the symmetry group $S_{n}$. Each time when we query the algorithm $f$, it
samples a permutation $\pi$ from the symmetry group $S_{n}$ with respect to
$Q_{f}$ and applies $\pi([n])$ to get the shuffled deck. When there is an
need, we use $f_{n}$ to denote that this algorithm is for $n$ cards. With such
formulation, $f$ also induces an $n$ by $n$ transition matrix $P^{f}$ where
$P^{f}_{ij}$ is the probability that card $i$ ends up at position $j$ after
the shuffle. When the shuffling method $f$ used in context is unambiguous, we
just use $Q$ and $P$.

###  1.4. High level proof idea

If the player guesses with complete feedback, let $\mathcal{U}$ be the set of
all sequences of length no more than $n$, then the optimal strategy is a map
$\lambda:\mathcal{U}\rightarrow[n]$ such that

$\lambda(x_{1}...x_{m-1})=\arg\max_{a}\Pr(x_{m}=a|x_{1}...x_{m-1})\hskip
14.22636pt\forall x_{1}....x_{m-1}\in\mathcal{U}.$

Let $R^{*}(\pi,f)$ be the reward with this optimal strategy when the sampled
permutation is $\pi$, then we have the maximum expected reward satisfies

(1.1) $R^{*}(f)=\sum_{\pi\in S_{n}}R^{*}(\pi,f)Q_{f}(\pi).$

Directly computing these conditional probabilities and summing over all
$S_{n}$ may be applicable to some cases like uniform shuffle. For other cases,
it may be hard to compute all the conditional probabilities to arrive at an
operational description of the optimal strategy and we sometimes we need to
adopt the following recursive approach. The best guess for the first card is
always $\max_{j}\\{P^{f}_{j1}\\}$. After the first card is revealed to be $i$,
we can think of the remaining $n-1$ cards as being shuffled according to a
conditional shuffle $f^{(i)}$ and

(1.2)
$R^{*}(f)=\max_{j}\\{P^{f}_{j1}\\}+\sum_{i=1}^{n}P^{f}_{i1}R^{*}(f^{(i)}).$

This is exactly the main idea behind the proof—the riffle shuffle can be
approximated by another shuffling method with recursive structure.

##  2\. Related Work

###  2.1. The mathematical model for riffle shuffle

Dovetail shuffle is a common shuffling method used in real life. The shuffler
first divides the deck into two piles and then drops the cards from the two
piles to make a new shuffled pile. We will use the following GSR model
introduced by Gilbert and Shannon (see Gilbert (1955)) and Reeds (1981) to
mathematically describe the dovetail shuffling algorithm.

GSR(Gilbert-Shannon-Reeds) Model

  1. (1)

The deck of $n$ cards is cut at a position into two piles randomly according
to the binomial distribution such that the probability of cutting it at
position $k$ (where $0\leq k\leq n$) is $\frac{\binom{n}{k}}{2^{n}}$. After
this step, we end up with two piles of cards $A,B$ of size $k$ and $n-k$.

  2. (2)

Start with the shuffled pile $C$ being empty and drop the cards from the
bottom of $A$ and $B$ onto $C$ one at a time in the following way. At each
time, let $x$ be the number of remaining cards in pile $A$ and $y$ be the
number of remaining cards in pile $B$, drop a card from pile $A$ with
probability $\frac{x}{x+y}$ and a card from pile $B$ with probability
$\frac{y}{x+y}$.

Diaconis [5] gives an analysis showing that the GSR model is a good model for
riffle shuffle in real life. Diaconis [4] briefly mentioned another way to
interpret step (2) without proof, we prove it here for completeness as the
following lemma.

######  Lemma 2.1.

Step (2) is equivalent to interleaving the two piles uniform randomly.

###### Proof.

Suppose initially pile $A$ has $a$ cards and pile $B$ has $b$ cards. For a
sequence $x_{1}...x_{m}$, let $P_{1}(.)$ be the probability that, with step
(2), this sequence ends up being the first $m$ cards in the shuffled pile from
bottom to top and let $P_{2}$ be defined similarly if we interleave the two
piles uniformly. Define $P_{1}$ and $P_{2}$ both be 1 when $m=0$. We prove by
induction on $m$ that $P_{1}(x_{1}....x_{m})=P_{2}(x_{1}....x_{m})$.
The base case $m=0$ holds by definition. Now suppose the result holds for all
sequences of length $m$, consider any sequence $x_{1},...,x_{m+1}$ that could
be the layout of the first $m+1$ cards of the shuffled deck, that is,
$rs(x_{1},...,x_{m+1})\leq 2$. Let

$a^{\prime}=|A\setminus\\{x_{1},...,x_{m}\\}|,b^{\prime}=|B\setminus\\{x_{1},...,x_{m}\\}|.$

Let $P_{1}(x_{m+1}|x_{1},...,x_{m})$ denote the probability that the
$m+1^{th}$ card being $x_{m+1}$ conditioning on the first $m$ cards being
$x_{1},...,x_{m}$. Note that conditioning on step 1, $x_{m+1}$ can assume only
two values, either the first card from pile $A$ or the first card from pile
$B$. WLOG, suppose $x_{m+1}$ is from pile $A$, then we have

$P_{1}(x_{1}...x_{m+1})=P_{1}(x_{m+1}|x_{1},...,x_{m})P_{1}(x_{1},...,x_{m})=\frac{a^{\prime}}{a^{\prime}+b^{\prime}}P_{1}(x_{1},...,x_{m}).$

Now consider the case where we interleave the two piles uniformly, given that
the first $m$ cards are $x_{1},...,x_{m}$, there are
$\binom{a^{\prime}+b^{\prime}}{a^{\prime}}$ ways to interleave the remaining
cards and $\binom{a^{\prime}+b^{\prime}-1}{a^{\prime}-1}$ ways to interleave
if the next card is $x_{m+1}$, thus

$\displaystyle
P_{2}(x_{m+1}|x_{1},...,x_{m})=\frac{\binom{a^{\prime}+b^{\prime}-1}{a^{\prime}-1}}{\binom{a^{\prime}+b^{\prime}}{a^{\prime}}}=\frac{a^{\prime}}{a^{\prime}+b^{\prime}}$
$\displaystyle\Rightarrow$ $\displaystyle
P_{2}(x_{1},...,x_{m+1})=P_{2}(x_{m+1}|x_{1},...,x_{m})P_{2}(x_{1},...,x_{m})=\frac{a^{\prime}}{a^{\prime}+b^{\prime}}P_{2}(x_{1},...,x_{m}).$

By induction, we have $P_{1}(x_{1},...,x_{m+1})=P_{2}(x_{1},...,x_{m+1})$ thus
step (2) is equivalent to interleave the two piles uniformly. ∎

Given a deck already cut, the probability of each of the configuration is
given by the following corollary.

######  Corollary 2.2.

If the deck is cut at position $k$ , the resulting deck’s configuration is one
of the possible interleavings each with probability $\frac{1}{\binom{n}{k}}$.

The GSR model gives an operational description of riffle shuffle, now we
provide its distribution $Q$ and transition matrix $P$. First from the
operational description we note that every permutation $\pi$ in the support of
$Q$ satisfies $rs(\pi)=1$ or 2, that is, it is either the identity or has
exactly 2 rising sequences. Bayer and Diaconis [2] proves a more general
result about $a$-shuffle where the original deck is separated into $a$ packs
instead of 2. Here we use the version of $a=2$ and a simpler proof is provided
for completeness.

######  Theorem 2.3.

For dovetail shuffle, the distribution $Q$ on $S_{n}$ satisfies

$Q(\pi)=\begin{cases}\frac{n+1}{2^{n}}&\text{if }\pi=id\\\
\frac{1}{2^{n}}&\text{if }rs(\pi)=2\\\ 0&\text{otherwise}.\\\ \end{cases}$

###### Proof.

Let $\Pr(\text{cut}_{k})$ be the probability of cutting at position $k$ and
$\Pr(\pi|\text{cut}_{k})$ be the probability of $\pi$ conditioning on that it
is cut at $k$. By Lemma 2.1 and Corollary 2.2 we have

$\displaystyle Q(\pi)$
$\displaystyle=\sum_{k=0}^{n}\Pr(\text{cut}_{k})\Pr(\pi|\text{cut}_{k})$
$\displaystyle=\sum_{k=0}^{n}\frac{\binom{n}{k}}{2^{n}}\frac{1}{\binom{n}{k}}\delta(\text{there
is an interleaving to generate }\pi([n])\text{ when cut at }k)$
$\displaystyle=\frac{M(\pi)}{2^{n}}$

where $M(\pi)$ is the number of cuts that can generate $\pi([n])$.
Every cut could generate the identity, so $M(id)=n+1$. For the other $\pi$
such that $rs(\pi)=2$, exactly one cut could generate it (which is to cut it
at the minimum of the ends of the two rising sequences), thus $M(\pi)=1$, so
the theorem is proved. ∎

######  Remark 2.4.

This theorem shows that the number of rising sequences is a sufficient
statistics and this is true in general for $a$-shuffle as well. We also have
that the entropy of $Q$ is $n\log 2-\frac{n+1}{2^{n}}\log(n+1).$

######  Corollary 2.5.

Recall that in section 1.2 we let $R_{n}$ denote the number of permutations
with 2 rising sequences. From this theorem we have that
$R_{n}=(1-Q(id))2^{n}=2^{n}-n-1$.

In [1] Ciucu has made great contributions to guessing riffle shuffled deck
with zero feedback in which he proves the following theorem

######  Theorem 2.6.

The optimal strategy for guessing a deck of $n$ cards riffle shuffled once
without feedback has expected reward $\frac{2}{\sqrt{\pi}}\cdot\sqrt{n}+O(1)$.

In his proof, the transition matrix $P$ for riffle shuffle is calculated and
this plays a major role in our proof.

######  Theorem 2.7.

For dovetail shuffle, the transition matrix $P$ satisfies

$P_{ij}=\begin{cases}\frac{1}{2^{j}}\binom{j-1}{j-i}&\text{if }i<j\\\
\frac{1}{2^{n}}(2^{j-1}+2^{n-j})&\text{if }i=j\\\
\frac{1}{2^{n-j+1}}\binom{n-j}{i-j}&\text{if }i>j.\\\ \end{cases}$

##  3\. Proof of Theorem 1.3

The proof consists of two parts. We first show that the algorithm is optimal
in Proposition 3.1 and prove its expected reward in Proposition 3.3.

######  Proposition 3.1.

Algorithm 1.1 is the optimal strategy.

In showing the optimality, we first prove a lemma explaining the guessing
consecutive stage.

######  Lemma 3.2.

Given a deck of $n$ cards riffle shuffled once, let the true cards be
$a_{1},....,a_{n}$ from top down, then we have

$\arg\max_{l}\Pr(a_{m}=l|a_{i}=i\text{ for }1\leq i<m)=m.$

###### Proof.

Let the true underlying permutation be $\pi$ and

$I_{m}=\\{\pi|\pi([m])=id([m])\text{ and }rs(\pi)=2\\}$

then by Corollary 2.5 we have

$|I_{m}|=|\\{\pi|rs(\pi[m+1,...,n])=2\\}|=R_{n-m}=2^{n-m}-n+m-1.$

By Theorem 2.3

$\Pr(\pi([m])=id([m]))=\Pr(\pi=id)+\sum_{\pi\in
I_{m}}\Pr(\pi)=\frac{n+1}{2^{n}}+|I_{m}|\frac{1}{2^{n}}=\frac{2^{n-m}+m}{2^{n}}.$

Thus

$\displaystyle\Pr(\pi(m)=m|\pi([m-1])=id([m-1]))$
$\displaystyle=\frac{\Pr(\pi([m])=id([m]))}{\Pr(\pi([m-1])=id([m-1]))}$
$\displaystyle=\frac{2^{n-m}+m}{2^{n-m+1}+m-1}>\frac{1}{2}$

which gives $\arg\max_{l}P(a_{m}=l|a_{i}=i\text{ for }1\leq i<m)=m$. ∎

With the above lemma, it’s easy to prove that our algorithm is optimal.

###### Proof of Proposition 3.1.

By Theorem 2.7, we have $P_{11}=\frac{1+2^{n-1}}{2^{n}}>\frac{1}{2}$, thus at
the first step, the best guess should be 1. By Lemma 3.2 and induction, if the
previous revealed sequence is consecutive, the best guess should be the next
card in the consecutive sequence. Finally, if the revealed sequence
$[1,2,....,m,k]$ became non-consecutive when $k$ is flipped, by step 2 of GSR
model and Lemma 2.1, we know that the remaining deck is formed by interleaving
$A=\\{m+1,...,k-1\\}$ and $B=\\{k+1,...,n\\}$ uniformly. Then we have

$\Pr(\text{next
card=}m+1)=\frac{\binom{|A|+|B|-1}{|A|-1}}{\binom{|A|+|B|}{|A|}}=\frac{|A|}{|A|+|B|}.$

Thus in this stage the best guess is the beginning of the longer sequence. ∎

The next proposition gives the expected reward.

######  Proposition 3.3.

Algorithm 1.1 has expected reward $n/2+\sqrt{2/\pi}\cdot\sqrt{n}+O(1).$

In proving this proposition, we first introduce the following sequence which
was also appears in Ciucu [1].

######  Definition 3.4.

Let the sequence $\\{a_{i}\\}_{i=0}^{\infty}$ be such that
$a_{i}=\frac{1}{2^{i}}\binom{i}{\lfloor i/2\rfloor}$.

[1] proves a lemma about $\sum_{i=0}^{\infty}a_{i}$ and we prove something
similar with a more refined asymptotic bound.

######  Lemma 3.5.

Let $A_{n}=\sum_{i=0}^{n}a_{i}$, then $A_{n}=c\sqrt{n}+O(1)$ where the
constant $c=\sqrt{\frac{8}{\pi}}\approx 1.60$.

###### Proof.

By Sterling’s formula of the form $n!=\sqrt{2\pi
n}(\frac{n}{e})^{n}e^{\lambda_{n}}$ where
$\frac{1}{12n+1}<\lambda_{n}<\frac{1}{12n}$, we have

$\displaystyle a_{2i}$
$\displaystyle=\frac{(2i)!}{2^{2i}i!i!}=\frac{\sqrt{4\pi
i}(\frac{2i}{e})^{2i}e^{\lambda_{2i}}}{2^{2i}\Big{(}\sqrt{2\pi
i}(\frac{i}{e})^{i}e^{\lambda_{i}}\Big{)}^{2}}$
$\displaystyle=\frac{e^{\lambda_{2i}}}{\sqrt{\pi
i}e^{2\lambda_{i}}}=\frac{1}{\sqrt{\pi i}}e^{\lambda_{2i}-2\lambda_{i}}.$

By the bound on $\lambda_{n}$, we have

$\displaystyle\frac{1}{24i+1}-\frac{2}{12i}<\lambda_{2i}-2\lambda_{i}<\frac{1}{24i}-\frac{2}{12i+1}$
$\displaystyle\Rightarrow\lambda_{2i}-2\lambda_{i}=\Theta(\frac{1}{i})\Rightarrow
e^{\lambda_{2i}-2\lambda_{i}}=1+O(\frac{1}{i})$ $\displaystyle\Rightarrow
a_{2i}=\frac{1}{\sqrt{\pi i}}+O(\frac{1}{i^{\frac{3}{2}}}).$

where the second last equality is by the expansion of
$e^{x}=\sum_{i=0}^{\infty}\frac{x^{i}}{i!}$.
We have $a_{2i}=a_{2i-1}$ and since the series
$\sum_{i=0}^{n}\frac{1}{i^{\frac{3}{2}}}$ converges,

$A_{2n}=\sum_{i=1}^{2n}a_{i}+O(1)=2\sum_{i=1}^{n}a_{2i}+O(1)=\frac{2}{\sqrt{\pi}}\sum_{i=1}^{n}\frac{1}{\sqrt{i}}+O(1).$

To estimate the series $\sum_{i=1}^{\infty}\frac{1}{\sqrt{i}}$, we have

$\displaystyle
2\sqrt{n+1}-2=\int_{1}^{n+1}\frac{1}{\sqrt{x}}dx\leq\sum_{i=1}^{n}\frac{1}{\sqrt{i}}\leq
1+\int_{1}^{n}\frac{1}{\sqrt{x}}dx=2\sqrt{n}-1$ $\displaystyle\Rightarrow
A_{2n}=\sqrt{\frac{8}{\pi}}\sqrt{2n}+O(1).$

Since $A_{2n}\leq A_{2n+1}\leq A_{2n+2}$, we have
$A_{n}=\sqrt{\frac{8}{\pi}}\cdot\sqrt{n}+O(1)$. ∎

Let $f_{n}$ denote the riffle shuffle algorithm for $n$ cards, now we attempt
to compute the maximal expected reward $R^{*}(f_{n})$. It’s hard to directly
compute this using Equation (1.1). Instead, we use the recursive Equation
(1.2). For $k\geq 2$, the conditional shuffling $f^{(k)}_{n}$ is just
interleaving uniformly which is an easy object to deal with (recall that in
section 1.4 we define $f^{(k)}_{n}$ to the random permutation on the remaining
$n-1$ cards given that the first card is $k$). If $k=1$, then we note that the
strategy on the remaining cards is a relabelling of Algorithm 1.1 on $n-1$
cards. Define $g_{n}=f^{(1)}_{n+1}$ to be the shuffling(a random permutation)
on the remaining $n$ cards when the first card is revealed to be 1 after the
riffle shuffle. Then $g_{n-1}=f^{(1)}_{n}$ shares the same optimal strategy
with $f_{n-1}$ after reducing every card number by 1. Thus we conjecture that
$g_{n}$ and $f_{n}$ may be very similar and indeed this conjecture is true in
the following sense.

######  Lemma 3.6.

  1. (a)

The optimal guessing algorithm for $g_{n}$ is the same as $f_{n}$.

  2. (b)

$R^{*}(g_{n})=R^{*}(f_{n})+o(1)$.

###### Proof.

For (a), since Algorithm 1.1 is optimal by Proposition 3.1, the optimal
strategy for $g_{n}$ is that algorithm applied when the first card is 1. Thus
it is isomorphic to the optimal strategy for $f_{n}$ after reducing every card
number by 1.
For (b), given any permutation $\pi$ on $[n]$, we denote $\pi^{\prime}$ to be
a permutation on $[n+1]$ such that $\pi^{\prime}(1)=1$ and
$\pi^{\prime}(i)=\pi(i-1)+1$. Basically $\pi^{\prime}$ acts on $[2,...,n+1]$
the same as $\pi$ acts on $[1,...,n]$.
First, we compute the distribution $Q_{g_{n}}$ on $S_{n}$. By Theorem 2.3 and
Theorem 2.7, we have

$\displaystyle Q_{g_{n}}(id_{[n]})$
$\displaystyle=\text{Pr}_{f_{n+1}}(id_{[n+1]}|\text{ the first card is 1})$
$\displaystyle=\frac{Q_{f_{n+1}}(id_{[n+1]})}{P^{f_{n+1}}_{11}}=\frac{n+2}{2^{n}+1}.$

For any $\pi$ with two rising sequences, $\pi^{\prime}$ also satisfies
$rs(\pi^{\prime})=2$, thus we have

$Q_{g_{n}}(\pi)=\text{Pr}(\pi^{\prime}|\pi^{\prime}(1)=1)=\frac{Q_{f_{n+1}}(\pi^{\prime})}{P^{f_{n+1}}_{11}}=\frac{1}{2^{n}+1}.$

Thus the total variation distance of their distributions satisfies

$\displaystyle TV(Q_{f_{n}},Q_{g_{n}})$ $\displaystyle=\frac{1}{2}\sum_{\pi\in
S_{n}}|Q_{f_{n}}(\pi)-Q_{g_{n}}(\pi)|=\frac{1}{2}|Q_{f_{n}}(id)-Q_{g_{n}}(id)|+\frac{1}{2}\sum_{\pi\in
I_{n}}|Q_{f_{n}}(\pi)-Q_{g_{n}}(\pi)|$
$\displaystyle=\frac{1}{2}|Q_{f_{n}}(id)-Q_{g_{n}}(id)|+\frac{1}{2}|I_{n}|\cdot|\frac{1}{2^{n}}-\frac{1}{2^{n}+1}|=\frac{2^{n}-n-1}{(2^{n}+1)2^{n}}.$

Recall that in section 1.4 we defined $R^{*}(\pi,f_{n})$ as the reward of the
optimal strategy for $f_{n}$ when the underlying permutation is $\pi$. Part
$(a)$ tells us that $R^{*}(\cdot,f_{n})=R^{*}(\cdot,g_{n})$ as functions on
$S_{n}$. Since $R^{*}(\cdot,f_{n})\leq n$, by the equivalent definition of
total variation distance we have

$\displaystyle|R^{*}(f_{n})-R^{*}(g_{n})|$ $\displaystyle=|\sum_{\pi\in
S_{n}}R^{*}(\pi,f_{n})Q_{f_{n}}(\pi)-\sum_{\pi\in
S_{n}}R^{*}(\pi,f_{n})Q_{g_{n}}(\pi)|$ $\displaystyle\leq 2n\cdot
TV(Q_{f_{n}},Q_{g_{n}})=\frac{2n(2^{n}-n-1)}{2^{n}(2^{n}+1)}\leq\frac{n}{2^{n-1}}=o(1).$

Thus we have $R^{*}(g_{n})=R^{*}(f_{n})+o(1)$. ∎

With the above lemma and Equation (1.2) , we can establish a recursive
relationship for the sequence $\\{R^{*}(f_{n})\\}$ and prove our proposition.

###### Proof of Proposition 3.3.

For two piles $A$ and $B$ with size $a$ and $b$ interleaved uniformly, let
$f(a,b)$ denote the maximum expected reward. Then by Equation (1.2),

(3.1)
$R^{*}(f_{n})=P_{11}+P_{11}R^{*}(g_{n-1})+\sum_{k=2}^{n}P_{k1}f(k-1,n-k).$

Let $G(n)=R^{*}(f_{n})$, by Theorem 2.7 and Lemma 3.6 we have

$G(n)=\frac{1+2^{n-1}}{2^{n}}\big{(}1+G(n-1)+o(1)\big{)}+\sum_{k=2}^{n}\frac{\binom{n-1}{k-1}}{2^{n}}f(k-1,n-k).$

Define

$S(n)=\sum_{k=1}^{n}\binom{n}{k}f(k,n-k)\text{ and
}F(n)=\frac{S(n)}{2^{n+1}}.$

Since $G(n)\leq n$ and $\lim_{n\rightarrow\infty}G_{n}/2^{n}=0$, we have

(3.2) $G(n)=\frac{1}{2}G(n-1)+F(n-1)+\frac{1}{2}+o(1)$

with condition $G(1)=1$.
For $f(a,b)$, by considering where the next card comes from, we have

(3.3)
$f(a,b)=\max\\{\frac{a}{a+b},\frac{b}{a+b}\\}+\frac{b}{a+b}f(a,b-1)+\frac{a}{a+b}f(a-1,b)$

with conditions $f(a,b)=f(b,a)$ and $f(a,0)=f(0,a)=a$.
Next, we attempt to solve the above recursive formulas, by Equation (3.3) we
have

$\displaystyle S(n)$
$\displaystyle=n+\sum_{k=1}^{n-1}\binom{n}{k}(\max\\{\frac{k}{n},1-\frac{k}{n}\\}+\frac{k}{n}f(k-1,n-k)+\frac{n-k}{n}f(k,n-k-1))$
$\displaystyle=n+\sum_{k=1}^{n-1}\binom{n}{k}\max\\{\frac{k}{n},1-\frac{k}{n}\\}+\sum_{k=1}^{n-1}\binom{n}{k}\frac{k}{n}f(k-1,n-k)+\sum_{k=1}^{n-1}\binom{n}{k}\frac{n-k}{n}f(k,n-k-1)$
$\displaystyle=n+\sum_{k=1}^{n-1}\binom{n}{k}\max\\{\frac{k}{n},1-\frac{k}{n}\\}+\sum_{k=1}^{n-1}\binom{n-1}{k-1}f(k-1,n-1-(k-1))$
$\displaystyle+\sum_{k=1}^{n-1}\binom{n-1}{k}f(k,n-1-k)$
$\displaystyle=n+\sum_{k=1}^{n-1}\binom{n}{k}\max\\{\frac{k}{n},1-\frac{k}{n}\\}+2S(n-1)$
$\displaystyle=n+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{k}\frac{n-k}{n}+\sum_{k=\lfloor\frac{n}{2}\rfloor+1}^{n-1}\binom{n}{k}\frac{k}{n}+2S(n-1)$
$\displaystyle=n+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{n-1}{k}+\sum_{k=\lfloor\frac{n}{2}\rfloor+1}^{n-1}\binom{n-1}{k-1}+2S(n-1)$
$\displaystyle=n+\sum_{k=1}^{n-2}\binom{n-1}{k}+\binom{n-1}{\lfloor\frac{n}{2}\rfloor}+2S(n-1)$
$\displaystyle=2^{n-1}+\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}+n-2+2S(n-1).$

Thus we end up with the following recursive formula for $S(n)$

$S(n)=2^{n-1}+\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}+n-2+2S(n-1)$

which gives

$\displaystyle F(n)$
$\displaystyle=\frac{1}{4}+\frac{\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}+n-2}{2^{n+1}}+F(n-1)$
$\displaystyle=\frac{1}{4}+\frac{n-2}{2^{n+1}}+\frac{a_{n-1}}{4}+F(n-1)$
$\displaystyle\Rightarrow
F(n)=\frac{n}{4}+\frac{\sum_{k=1}^{n-1}a_{k}}{4}+O(1).$

By Lemma 3.5 we have

(3.4) $F(n)=\frac{n}{4}+\sqrt{\frac{n}{2\pi}}+O(1).$

Recall that from earlier we have

(3.5) $G(n)=\frac{1}{2}G(n-1)+F(n-1)+\frac{1}{2}+o(1).$

Next, we prove that $G(n)=\frac{1}{2}\cdot
n+\sqrt{\frac{2}{\pi}}\cdot\sqrt{n}+O(1)$.
By Equation (3.4), there is a constant $c_{0}$ such that
$F(n)=\frac{n}{4}+\sqrt{\frac{n}{2\pi}}+x_{n}$ and $|x_{n}|\leq c_{0}$ for all
$n$. By Equation (3.5), there is a constant $c_{1}$ such that
$G(n)=\frac{1}{2}G(n-1)+F(n-1)+y_{n}$ and $|y_{n}|\leq c_{1}$ for all $n$.
Suppose $G(n)=\frac{1}{2}\cdot n+\sqrt{\frac{2}{\pi}}\cdot\sqrt{n}+z_{n}$ let
$C=\max\\{2c_{0}+2c_{1}+2,|z_{1}|\\}$, we prove by induction that $|z_{n}|\leq
C$.
By our choice of $C$, the base case of $n=1$ is true. Now suppose the
statement holds for $n$, consider $n+1$. Then we have

$\displaystyle G(n+1)$
$\displaystyle=\frac{1}{2}G(n)+F(n)+y_{n+1}=\frac{1}{2}(\frac{1}{2}\cdot
n+\sqrt{\frac{2}{\pi}}\cdot\sqrt{n}+z_{n})+\frac{n}{4}+\sqrt{\frac{n}{2\pi}}+x_{n}+y_{n+1}$
$\displaystyle=\frac{n}{2}+\sqrt{\frac{2}{\pi}}\cdot\sqrt{n}+\frac{z_{n}}{2}+x_{n}+y_{n+1}$
$\displaystyle=\frac{n+1}{2}+\sqrt{\frac{2}{\pi}}\cdot\sqrt{n+1}-\frac{1}{2}-\sqrt{\frac{2}{\pi}}(\sqrt{n+1}-\sqrt{n})+\frac{z_{n}}{2}+x_{n}+y_{n+1}$
$\displaystyle\Rightarrow
z_{n+1}=\frac{z_{n}}{2}+x_{n}+y_{n+1}-\frac{1}{2}-\sqrt{\frac{2}{\pi}}(\sqrt{n+1}-\sqrt{n})$
$\displaystyle\Rightarrow|z_{n+1}|\leq|\frac{z_{n}}{2}|+|x_{n}|+|y_{n+1}|+\frac{1}{2}+\sqrt{\frac{2}{\pi}}\frac{1}{\sqrt{n}+\sqrt{n+1}}$
$\displaystyle\leq\frac{C}{2}+c_{0}+c_{1}+1\leq C.$

Thus the statement holds for $n+1$, which means $|z_{n}|\leq C$ for all $n$,
thus we have the expected reward is

$G(n)=n/2+\sqrt{2/\pi}\cdot\sqrt{n}+O(1).$

∎

######  Remark 3.7.

Currently our approximation technique is not refined enough to find a constant
$c$ to replace the $O(1)$ term by $c+o(1)$. By doing numerical calculation for
$1\leq n\leq 10000$, the error term is below 0.5.

##  4\. Open problems

The notation in this section is the same as in section 3.

  1. 1.

Calculating the variance of the number of correct guesses under optimal
strategy. Since we already have a formula for the expected value
$R^{*}(f_{n})$, it suffices to compute the following expected square sum

(4.1) $T^{*}(f_{n}):=\sum_{\pi\in S_{n}}R^{*}(\pi,f_{n})^{2}Q_{f}(\pi).$

It satisfies

$T^{*}(f_{n})=P_{11}(1+R^{*}(g_{n-1}))^{2}+\sum_{k=2}^{n}P_{k1}f(k-1,n-k)^{2}$
$=\frac{1+2^{n-1}}{2^{n}}(1+R^{*}(f_{n-1}))^{2}+\sum_{k=2}^{n}\frac{\binom{n-1}{k-1}}{2^{n}}f(k-1,n-k)^{2}+o(1).$

Thus it remains to estimate

$F^{\prime}(n):=\sum_{k=2}^{n}\binom{n-1}{k-1}f(k-1,n-k)^{2}.$

Currently we are not able to get a good estimate of $F^{\prime}$ since an
expansion using Equation (3.3) would involve cross terms and be very
complicated to solve.

  2. 2.

Generalize to $k$ riffle shuffles $f^{(k)}_{n}$. A natural next step is to
prove an optimal guessing strategy and find its expected number of correct
guesses for a deck of cards riffle shuffled for $k\geq 2$ times. A conjectured
optimal strategy is given in [2]. The main difficulty in extending the current
method to the general setting is the following. With $k=1$, the two piles of
cards before interleaving would be fully determined once the first non-
consecutive card appears. For larger $k$, the natural generalization of this
would be based on the sequential description of $a$-shuffle formulated in [2]
on page 299. However, the original card piles before interleaving are much
harder to be determined by the revealed cards if $k$ is large.

  3. 3.

Generalize to yes or no feedback. For the case of uniform shuffle, it is
solved in [3]. However, this question remains wide open for riffle shuffle,
primarily because the conditional shuffle of receiving negative feedback is
less understood.

##  5\. Acknowledgements

We would like to thank Pr.Diaconis for teaching a class at Stanford University
through which I get to know this interesting topic and providing some
references. We thank Anita for proofreading and providing valuable feedback.
We also thank the anonymous reviewer for helpful comments and suggestions.

## References

  * [1] M. Ciucu. (1998) No-feedback card guessing for dovetail shuffles. Ann. Appl. Probab. Vol. 8, No. 4, 1251-1269
  * [2] Dave Bayer, Persi Diaconis. (1992) Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2. 294-313.
  * [3] Persi Diaconis, Ronald Graham. (1981). The analysis of sequential experiments with feedback to subjects. The Ann. Stats. 9 3-23.
  * [4] Persi Diaconis. (2003) Mathematical developments from the analysis of riffle shuffling. Groups, Combinatorics and Geometry A. Ivanov, M. Liebeck and J. Saxl, eds, World Scientific, New Jersey, 73-97.
  * [5] Persi Diaconis. (1988). Group Representations in Probability and Statistics. IMS, Hayward, CA.