# Guessing about Guessing: Practical Strategies for Card Guessing with
Feedback

Persi Diaconis  Ron Graham  Sam Spiro

###### Abstract

In simple card games, cards are dealt one at a time and the player guesses
each card sequentially. We study problems where feedback (e.g.,
correct/incorrect) is given after each guess. For decks with repeated values
(as in blackjack where suits do not matter), the optimal strategy differs from
the “greedy strategy” (of guessing a most likely card each round). Further,
both optimal and greedy strategies are far too complicated for real-time use
by human players. Our main results show that simple heuristics perform close
to optimal.

##  1 Introduction.

Consider the following game. A deck of $n$ cards labeled $1,2,\ldots,n$ is
randomly shuffled. A player then guesses each card (sequentially) as the cards
are dealt face down on the table. After each guess, the player is given some
amount of feedback. The main cases that we consider are the following:

  * •

No feedback (the player is told nothing after each guess),

  * •

Complete feedback (the player is shown the value of the card after each
guess),

  * •

Yes/No feedback (the player is only told whether their guess was correct or
not).

The final score is the total number of correct guesses made after all $n$
cards have been drawn. Suppose that the player uses some fixed strategy
$\mathcal{G}$ for guessing cards based on the level of feedback they are
given. Let $\mathbf{X}_{i}=1$ if the $i$th guess is correct (under the fixed
strategy $\mathcal{G}$) and $\mathbf{X}_{i}=0$ otherwise. Thus
$\mathbf{S}_{n}:=\mathbf{X}_{1}+\cdots+\mathbf{X}_{n}$ is the score in this
game. Then:

  * •

With No feedback, $\Pr[\mathbf{X}_{i}=1]=n^{-1}$ for all $1\leq i\leq n$, so
the expected number of correct guesses is

$\mathbb{E}[\mathbf{S}_{n}]=n\cdot n^{-1}=1.$

  * •

With Complete feedback, the maximizing strategy is to always guess a card
known to be left in the deck. Thus

$\Pr[\mathbf{X}_{1}=1]=\frac{1}{n},\
\Pr[\mathbf{X}_{2}=1]=\frac{1}{n-1},\ldots,\
\Pr[\mathbf{X}_{i}=1]=\frac{1}{n-i+1},\ldots,$

so $\mathbb{E}[\mathbf{S}_{n}]=1+\frac{1}{2}+\cdots+\frac{1}{n}=\log n+O(1)$.

  * •

With Yes/No feedback, consider the following strategy. Guess “1.” If this was
correct, then the player knows “1” is no longer in the deck. If incorrect, all
the player knows for sure is that “1” is still in the deck. Thus,
heuristically, a good strategy would be to guess “1” until the player is told
they are correct, then “2” until they are told they are correct (or until the
deck runs out), then “3,” and so on. And indeed, this strategy turns out to
maximize $\mathbb{E}[\mathbf{S}_{n}]$; see Diaconis and Graham [5].

Under this strategy, the player always gets at least 1 correct guess, that is,
$\Pr[\mathbf{S}_{n}\geq 1]=1$. There are at least 2 correct guesses if and
only if “2” appears after “1,” so $\Pr[\mathbf{S}_{n}\geq 2]=\frac{1}{2}$.
More generally, for all $1\leq k\leq n$ we have $\Pr[\mathbf{S}_{n}\geq
k]=\frac{1}{k!}$. Thus under optimal play,

$\mathbb{E}[\mathbf{S}_{n}]=\sum_{k=1}^{n}\Pr[\mathbf{S}_{n}\geq
k]=1+\frac{1}{2}+\cdots+\frac{1}{n!}=e-1+O(1/n!).$

In real card games, cards have repeated values. For example, in Blackjack or
Baccarat, suits do not matter and all of the card types “10, J, Q, K” have
value 10. The analysis for No feedback in the repeated setting is trivial, but
for Complete feedback things become more complex. Under Complete feedback, one
can easily prove that the strategy “each round guess a card type that has the
most number of copies left in the deck” is an optimal strategy. Thus computing
the expected score under optimal play reduces to analyzing the performance of
this (optimal) strategy, which was done by Diaconis and Graham [5].

The problem becomes significantly harder when we consider repeated values
under Yes/No feedback. In this setting, it is theoretically possible to
compute the probability that the next card type is a given value “$k$” given
the feedback from previous guesses; see Chung, Diaconis, Graham, and Mallows
[2] for information on how this can be done. Thus one can define the greedy
strategy: at each round, guess a card type that is most likely to appear next.

The first issue with the greedy strategy is that it is very complicated to
implement. In particular, computing the probabilities needed in the strategy
is equivalent to computing the permanents of certain matrices. Thus this
strategy is impractical for human players to use.

The second issue is that the greedy strategy is not optimal; and in general it
is not known what the optimal strategy is when one considers repeated values
with Yes/No feedback. Even if such a strategy were known, it seems likely that
it would be far too complex to implement by human players in practice. Given
this, Diaconis and Graham [5] posed the following two simple problems when the
deck has $2n$ cards with two copies of each card type labeled $1,\ldots,n$
under Yes/No feedback:

  * •

Is the optimal score of this game bounded as a function of $n$?

  * •

Are there simple strategies in this game which perform reasonably well?

The answer to this first question has recently been answered positively by
Diaconis, Graham, He, and Spiro [6]. In this article, we focus on the second
question. More precisely, we consider decks with $mn$ cards where each of the
$n$ card types appear $m$ times.111A useful mnemonic is that $m$ is the
multiplicity of each card type, while $n$ is the number of card types. We
define $\mathbf{S}_{m,n}$ to be the number of correct guesses made by the
player with this deck if they use a given strategy under some level of
feedback. Our goal is to use practical strategies to bound the maximum and
minimum possible values of $\mathbb{E}[\mathbf{S}_{m,n}]$ under Yes/No
feedback.

To this end, we say that a strategy is an optimal strategy if it achieves
$\max\mathbb{E}[\mathbf{S}_{m,n}]$, where the maximum ranges over all
strategies, and similarly we say a strategy is an optimal misère strategy if
it achieves $\min\mathbb{E}[\mathbf{S}_{m,n}]$. Our main results are the
following bounds on the score of the game under the optimal and optimal misère
strategies. Moreover, we will see that all of these bounds are achieved by
relatively simple strategies.

######  Theorem 1.

For all $m$ and $n\geq 8m$:

  * •

Under the optimal strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]\geq m+\frac{1}{40}\sqrt{m}.$

  * •

Under the optimal misère strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]\leq m-\frac{1}{40}\sqrt{m}.$

It was proved in [6] that $\mathbb{E}[\mathbf{S}_{m,n}]\leq m+O(m^{3/4}\log
m)$ uniformly in $n$ under the optimal strategy when $n$ is sufficiently large
in terms of $m$, so one cannot prove a lower bound that is much stronger than
Theorem 1 for $m$ large (though the constant $1/40$ can easily be improved).

Our second main result consists of bounds for small (fixed values) of $m$ when
$n$ is large.

######  Theorem 2.

For $n$ sufficiently large, under the optimal strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{2,n}]\geq 2.91,$ $\mathbb{E}[\mathbf{S}_{3,n}]\geq
3.97.$

Computational evidence suggests that the actual value of
$\mathbb{E}[\mathbf{S}_{2,n}]$ is close to the bound in Theorem 2; see Table
3.

Finally, we prove the following result regarding the optimal misère strategy.

######  Theorem 3.

For all $m$ and $n$ sufficiently large in terms of $n$, under the optimal
misère strategy with Yes/No feedback we have

$1-e^{-m}-o(1)\leq\mathbb{E}[\mathbf{S}_{m,n}]\leq
m-1+m^{-1}-m^{-1}e^{-m}+o(1).$

When $m=1$, Theorem 3 implies a previous result of [5], see Theorem 5. We also
note that for large $m$, the upper bound of Theorem 1 is more effective than
that of Theorem 3.

### Organization and notation.

The rest of the article is organized as follows. In Section 2, we discuss the
history of the problem in more depth. In Section 3, we state some practical
strategies that one can implement in the Yes/No feedback model and give some
computational data for how they perform. We then prove rigorous bounds on some
of these strategies (or slight technical variants thereof) in order to prove
our main results. In particular, Theorem 1 is proved in Section 4 and Theorem
2 in Section 5. Concluding remarks and further problems are given in Section
7.

We gather some notation that we use throughout the text. We use standard
asymptotic notation throughout this article. In particular, we write $O(f(n))$
to refer to a function $g(n)$ such that
$\limsup_{n\to\infty}\frac{g(n)}{f(n)}<\infty$, and similarly $o(f(n))$ refers
to a function $g(n)$ such that $\lim_{n\to\infty}\frac{g(n)}{f(n)}=0$. We
write $\Omega(f(n))$ if $\liminf_{n\to\infty}\frac{g(n)}{f(n)}>0$ and
$\Theta(f(n))$ to mean a function that is both $O(f(n))$ and $\Omega(f(n))$.
We write $f\sim g$ if $\lim_{n\to\infty}\frac{g(n)}{f(n)}=1$. For more on
asymptotic notation, see the book by Florescu and Spencer [11].

We let $\mathfrak{S}_{m,n}$ refer to the set of all words $\pi$ consisting of
$m$ copies of each element in $[n]:=\\{1,2,\ldots,n\\}$, which we think of as
a permutation of a deck of $mn$ cards with $n$ card types each occurring with
multiplicity $m$. We always write $\boldsymbol{\pi}$ to indicate an element of
$\mathfrak{S}_{m,n}$ chosen uniformly at random. If $\mathcal{G}$ is a
deterministic strategy for the player under some level of feedback, we let
$S(\mathcal{G},\pi)$ be the score of the player if they follow strategy
$\mathcal{G}$ and the deck is shuffled according to $\pi$. Thus the expected
score following strategy $\mathcal{G}$ is
$\mathbb{E}[S(\mathcal{G},\boldsymbol{\pi})]$. As much as possible we denote
random variables, such as $\mathbf{S}_{m,n}$, in bold and strategies, such as
$\mathcal{G}$, in script.

##  2 History.

### Real-world applications.

The original motivation for studying guessing problems that use sampling
without replacement and different levels of feedback comes from certain real-
world problems.

One such problem involves clinical trials, which was investigated by Blackwell
and Hodges [1] and Efron [8]. Suppose that one wishes to test the
effectiveness of two treatment options. In comparing the effectiveness of two
treatments on $2m$ patients, suppose it is decided that $m$ patients are to be
randomly selected to receive each treatment. Assume the patients arrive
sequentially and that they must be ruled either ineligible or eligible before
being assigned to one of the two treatments. The order that the treatments
will be administered is decided (randomly) in advance and is unknown to the
physician. However, a physician observing the outcome of each trial would know
which treatment was most likely used, and thus they would know roughly the
number of remaining treatments of each type at any given time. This
information might bias results if the physician ruled less healthy patients
ineligible for trials where a favored treatment was less likely. A natural
measure of selection bias is the number of times the physician correctly
guesses which treatment will be used next. Blackwell and Hodges [1] showed
that $m+\frac{1}{2}\sqrt{\pi m}-\frac{1}{2}+O(1/m)$ correct guesses are made
under optimal guessing. Note that this setting corresponds to $n=2$ in our
notation with either Complete or Yes/No feedback. (These two are the same when
$n=2$.)

Independently, the same problem is studied by Ethier and Levin [10] as part of
their work in evaluating card counting strategies in casino games such as
Blackjack, Baccarat, and Trente et Quarante. As cards are turned up during
play, the deck changes composition, so betting levels and actual strategy
changes can make some games favorable. Exactly the same formula given by
Blackwell and Hodges appears in Ethier [9, Problem 11.15]. This wonderful book
develops many further ideas tailored to these applications.

Another instance of this problem comes from testing if a subject has
extrasensory perception (ESP). A huge number of trials of the following
experiment were performed by J. B. Rhine at the Durham parapsychology lab. A
deck of 25 cards with five copies of five different symbols ($0,\ +,\ \iiint,\
\square,\ *$) is shuffled, and a guessing subject guesses them sequentially as
above. It is common practice to give various kinds of feedback in these
experiments, which is sometimes inadvertent if the guessing and sending
subject are in the same room. For extensive references, see Diaconis [3].

### Some numbers.

The main results in our article are asymptotic, giving results as $m$ and/or
$n$ tend to infinity. It is of interest to obtain exact results for decks of
small size, both to get a feel for what the correct asymptotic bounds should
be, and to make use of these results in the real-world applications mentioned
above.

For example, consider the classical ESP experiment which corresponds to
$m=n=5$. In [5], a direct recursion was used to get the exact answers recorded
in Table 1. As noted in [3], for actual ESP experiments, the highest recorded
scores essentially never exceeded 8.65, and the highest scores among long-term
subjects never exceeded 6.63; so the numbers of Table 1 help benchmark high
scoring experiments. Much more can be said about this well-studied case; see
Diaconis, Gatto, and Graham [4] and Gatto [12].

Table 1: Expected number of correct guesses under an optimal strategy with Yes/No feedback when $m=n=5$. The results are rounded to two decimal places. No feedback | Yes/No feedback | Complete feedback
---|---|---
5 | 6.65 | 8.65

Table 2 gives some numbers for $m=2$ and small $n$ under Yes/No feedback using
various strategies. This data was obtained by implementing the algorithms
detailed in Gatto [12]. The linear strategy mentioned in this table is the
following: assume at some stage one has incorrectly guessed each $i$ a total
of $g_{i}$ times and that one has correctly guessed each $i$ a total of
$n-c_{i}$ times (so there are $c_{i}$ copies of $i$ that have not been
confirmed which may or may not be among the remaining cards). Given this, we
guess the type $i^{*}$ such that $c_{i}+.51g_{i}$ is maximized (breaking ties
at random). The value .51 was found by experimenting with different choices of
parameters. Table 2 shows that, in addition to the greedy strategy being
nonoptimal, it is seemingly outperformed by this simple linear strategy.
Observe by Table 2 that the greedy and linear strategies are close to optimal
for small $n$. While we suspect that this phenomenon holds for all $n$, we do
not know how to prove this.

We find it rather surprising that the simple linear “card counting” strategy
performs so well. In the classical ESP setting of $m=n=5$, a similar strategy
can be used where one guesses the $i^{*}$ that maximizes $c_{i}+.35g_{i}$.
This simple strategy has expectation 6.6149, which is better than the greedy
strategy! Here .35 is again the result of a computer search, and in general we
expect for linear strategies of the form $c_{i}+\beta g_{i}$ that the optimal
value of $\beta$ should decrease as $n$ increases.

Table 2: Expected number of correct guesses with Yes/No feedback under various strategies when $m=2$. The results are rounded to four decimal places. | Optimal | Greedy | Linear
---|---|---|---
$\mathbb{E}[\mathbf{S}_{2,2}]$ | 2.8333 | 2.8333 | 2.8333
$\mathbb{E}[\mathbf{S}_{2,3}]$ | 3.0111 | 3.0111 | 3.0111
$\mathbb{E}[\mathbf{S}_{2,4}]$ | 3.0452 | 3.0333 | 3.0433
$\mathbb{E}[\mathbf{S}_{2,5}]$ | 3.0467 | 3.0222 | 3.0441

At a first glance of Table 2, it may appear as if
$\mathbb{E}[\mathbf{S}_{2,n}]$ under the optimal strategy is nondecreasing,
but Table 3 shows that this is not the case. Note that all of these values
seem to be very close to 3. It is unclear what the true asymptotic value
should be, though Theorem 2 shows that it is as least $2.91$.

Table 3: Expected number of correct guesses with Yes/No feedback under an optimal strategy when $m=2$. The results are rounded to four decimal places. $n$ | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---
$\mathbb{E}[\mathbf{S}_{2,n}]$ | 3.0376 | 3.0323 | 3.0260 | 3.0219 | 3.0186

### Previous research.

This article continues research in [5, 6]. In these papers, the problem of
determining $\mathbb{E}[\mathbf{S}_{m,n}]$ under both optimal and optimal
misère strategies with Complete feedback was essentially solved. The authors
were able to prove this result in large part due to the optimal and optimal
misère strategies being known when Complete feedback is given.

Despite not knowing the optimal strategy under Yes/No feedback in general, it
was proved in [6] that $\mathbb{E}[\mathbf{S}_{m,n}]$ is at most $m$ plus
lower-order terms under the optimal strategy. More precisely, the following
was proved.

######  Theorem 4 ([6], Theorem 1.3).

If $n$ is sufficiently large in terms of $m\geq 2$, then under an optimal
strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]=m+O(m^{3/4}\log m),$

where this bound holds uniformly in $n$.

This shows that the lower bound of Theorem 1 is close to best possible. It
also shows that for fixed $m$, under an optimal strategy with Yes/No feedback,
$\mathbb{E}[\mathbf{S}_{m,n}]$ is bounded as a function of $n$. This is in
sharp contrast to the Complete feedback model, where one can guarantee
$\Omega(\log n)$ correct guesses in expectation; see [6].

Theorem 4 does not given an effective bound on $\mathbb{E}[\mathbf{S}_{m,n}]$
under Yes/No feedback for any fixed $m$. For example, it does not tell us
whether $\mathbb{E}[\mathbf{S}_{2,n}]\leq 100$ for $n$ sufficiently large, and
it is natural to ask for bounds when $m$ is a fixed small integer. The case
$m=1$ was completely solved in [5].

######  Theorem 5 ([5], Theorems 5 and 6).

Under the optimal strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{1,n}]=e-1+O(1/n!)\approx 1.72,$

and under the optimal misère strategy,

$\mathbb{E}[\mathbf{S}_{1,n}]=1-e^{-1}+O(1/n!)\approx.632.$

The proof of Theorem 5 relies on an optimal strategy which is easy to analyze
when $m=1$, and without this it seems difficult to nail down asymptotic values
of $\mathbb{E}[\mathbf{S}_{m,n}]$ in general.

##  3 Practical Strategies and Computational Data.

Perhaps the simplest strategy to use in the Yes/No feedback model is the
strategy where one guesses “1” every round. This strategy always gives exactly
$m$ correct guesses. Of course, this strategy is somewhat silly. One can
always do at least as well by using the strategy: guess card “1” until the
player is told $m$ guesses were correct, then guess card “2” until the player
is told $m$ guesses were correct, and so on. We call this the safe strategy
and denote it by $\mathcal{S}$. While this does better than the trivial
strategy of guessing “1” every round, heuristic reasoning suggests that it
does not do much better when $m$ is large.

Indeed, the probability that the safe strategy gives at least $m+k$ correct
guesses for $k\leq m$ is exactly ${2m-k\choose m}/{2m\choose m}$ (since this
happens whenever the $m$ “1”s appear in the first $2m-k$ positions in the
deck). Thus the expected number of correct guesses of “1” and “2” card types
using the safe strategy is

$\displaystyle\sum_{k=0}^{2m}\Pr[\mathbf{S}_{m,n}\geq k]$
$\displaystyle=m-1+\sum_{k=0}^{m}\frac{{2m-k\choose m}}{{2m\choose m}}$
$\displaystyle=m-1+\frac{{2m+1\choose m+1}}{{2m\choose m}}$
$\displaystyle=m-1+\frac{2m+1}{m+1}=m+1-\frac{1}{m+1}.$

For $n>2$ the probability of guessing any “3” correctly is less than
${2m\choose m}^{-1}$, so for large $m$ the safe strategy will typically only
guess “1” and “2.” Thus we do not expect much more than $m+1$ correct guesses
using the safe strategy.

Another natural strategy is the shifting strategy $\mathcal{F}$ where the
player guesses “1” until they get a correct guess, then “2” until they get a
correct guess, and so on; and upon guessing an “$n$” correctly, they go back
to guessing “1”s, and then “2”s, and so on. Observe that the safe and shifting
strategies look identical until the first “1” is guessed correctly. Because of
this, the player can choose which strategy they wish to use after seeing the
first “1,” where intuitively they should use the shifting strategy if the
first “1” shows up early and the safe strategy otherwise.

To this end, we define the $\gamma$-shifting strategy $\mathcal{F}_{\gamma}$
by guessing “1” until a correct guess is made at time $t$. If $t\geq\gamma
mn$, the player proceeds as in the safe strategy, and otherwise they proceed
as in the shifting strategy. For example, $\mathcal{F}_{0}$ is the safe
strategy and $\mathcal{F}_{1}$ is the shifting strategy, so
$\mathcal{F}_{\gamma}$ serves as a sort of interpolation between these two
strategies.

We next define the halfway strategy $\mathcal{H}^{+}$ by guessing “1” for the
first $\frac{1}{2}mn$ trials. If at most $\frac{1}{2}m$ cards have been
guessed correctly, then keep guessing “1” (guaranteeing $m$ points at the end
of the game), and otherwise guess “2” for the rest of the game. The intuition
is that if there are many copies of “1” in the first half of the deck, then
there will be slightly more copies of “2” (or any other card type) in the
second half of the deck. This intuition is made rigorous in Lemma 3.

We now turn to strategies which get few correct guesses. Analogous to
$\mathcal{H}^{+}$, we define the halfway strategy $\mathcal{H}^{-}$ by
guessing “1” for the first half of the game, then to keep guessing “1”s if
more than $\frac{1}{2}m$ correct guesses were made, and otherwise guessing
“2”s the rest of the game. Finally, we define the avoiding strategy
$\mathcal{A}$ by guessing “1,” then “2,” then “3,” and so on until some “$k$”
is guessed correctly, at which point one guesses “$k$” for the rest of the
game. If the player does not guess any of the first $n$ cards correctly, then
they again guess “1,” then “2,” and so on until a card “$k$” is guessed
correctly, and then they guess “$k$” for the rest of the game.

In Table 4, we present computational data for most of these strategies. The
first two rows are the exact value of $\mathbb{E}[\mathbf{S}_{m,n}]$ using the
stated strategy with Yes/No feedback. The next two rows represent the sample
mean of $S(\mathcal{G},\boldsymbol{\pi})$ obtained after sampling $t=10^{6}$
permutations of $\mathfrak{S}_{m,n}$. The entries corresponding to
$\mathcal{F}_{\gamma}$ indicate which value of $\gamma$ was used, and these
values were chosen to roughly maximize the expectation. Each entry is rounded
after three decimal places.

Table 4: (Simulated) values of $\mathbb{E}[\mathbf{S}_{m,n}]$ under various strategies. | $\mathcal{S}$ | $\mathcal{F}$ | $\mathcal{F}_{\gamma}$ | $\mathcal{H}^{+}$ | $\mathcal{H}^{-}$
---|---|---|---|---|---
$m=2,n=6$ (exact) | 2.737 | 2.751 |  $\mathcal{F}_{.3}$: 2.941 | 2.212 | 1.682
$m=3,n=5$ (exact) | 3.772 | 3.753 |  $\mathcal{F}_{.25}$: 4.006 | 3.431 | 2.569
$m=4,n=10\ (t=10^{6})$ | 4.806 | 4.831 |  $\mathcal{F}_{.2}$: 5.100 | 4.370 | 3.585
$m=5,n=20\ (t=10^{6})$ | 5.835 | 5.856 |  $\mathcal{F}_{.15}$: 6.136 | 5.482 | 4.516

The main benefit of the strategies of this section is that we can give
rigorous bounds on their performance (or more precisely, on technical variants
of the strategies which are easier to analyze). For example, we provided no
computational data for the avoiding strategy, since it turns out that we can
determine its expectation asymptotically for all $m$.

######  Proposition 1.

For any fixed $m$, using the avoiding strategy with Yes/No feedback gives

$\mathbb{E}[\mathbf{S}_{m,n}]\sim m-1+m^{-1}-m^{-1}e^{-m}.$

##  4 Proof of Theorem 1: the Halfway Strategies $\mathcal{H}^{\pm}$.

In this section, we prove Theorem 1 using a technical variant of the halfway
strategies $\mathcal{H}^{\pm}$, which we denote by $\mathcal{H}^{\pm}_{*}$ and
define as follows. Guess “1” a total of $\left\lfloor mn/2\right\rfloor$
times. If at most most $\frac{1}{2}m+\frac{1}{2}\sqrt{m}$ correct guesses have
been made, then we continue to guess “1” for the rest of the game, otherwise
we guess “2” for the rest of the game otherwise. Similarly,
$\mathcal{H}_{*}^{-}$ is defined by guessing “1” a total of $\left\lfloor
mn/2\right\rfloor$ times, then continuing if at most
$\frac{1}{2}m-\frac{1}{2}\sqrt{m}$ correct guesses have been made, and with
“2” being guessed otherwise.

To show that $\mathcal{H}^{+}_{*}$ gives the correct lower bound, we first
show that the probability of getting at least
$\frac{1}{2}m+\frac{1}{2}\sqrt{m}$ correct guesses in the first phase is
relatively large.

######  Lemma 1.

For $\pi\in\mathfrak{S}_{m,n}$, let $K_{1}(\pi)$ denote the number of
$t\leq\left\lfloor mn/2\right\rfloor$ with $\pi_{t}=1$. Then for $m\geq 2$ and
$n\geq 8m$ and all $0\leq k\leq m$, we have

$\displaystyle\Pr[K_{1}(\boldsymbol{\pi})=k]\geq\frac{1}{2}\cdot
2^{-m}{m\choose k}.$

That is, the probability of having exactly $k$ of the $m$ “1”s appearing in
the first half of $\boldsymbol{\pi}$ is roughly the probability of having $k$
heads in a series of $m$ coin tosses.

###### Proof.

First assume $mn$ is even. Then

$\Pr[K_{1}(\boldsymbol{\pi})=k]={mn/2\choose k}{mn/2\choose m-k}/{mn\choose
m}.$ (1)

We recall the bounds ${N\choose r}\leq N^{r}/r!$ and

${N\choose
r}\geq\frac{(N-r)^{r}}{r!}=(1-r/N)^{r}\frac{N^{r}}{r!}\geq(1-r^{2}/N)\frac{N^{r}}{r!},$

where the last inequality uses $(1+x)^{r}\geq 1+rx$, which holds for $x\geq-1$
and $r\geq 1$. Using these bounds and (1), we find for $0\leq k\leq m$ and
$n\geq 8m$ that

$\displaystyle\Pr[K_{1}(\boldsymbol{\pi})=k]$
$\displaystyle\geq\frac{(mn/2)^{m}m!}{(mn)^{m}k!(m-k)!}(1-2k^{2}/mn)(1-2(m-k)^{2}/mn)$
$\displaystyle\geq 2^{-m}{m\choose k}\cdot(1-2m/n)^{2}\geq 2^{-m}{m\choose
k}\cdot\frac{1}{2}.$

This completes the proof for $mn$ even. If $mn$ is odd, then a similar
analysis as before gives

$\displaystyle\Pr[K(\boldsymbol{\pi})=k]$ $\displaystyle\geq 2^{-m}{m\choose
k}\cdot\frac{(mn-1)^{k}(mn+1)^{m-k}}{(mn)^{m}}(1-2m^{2}/(mn-1))^{2}$
$\displaystyle\geq 2^{-m}{m\choose k}\cdot(1-1/mn)^{m}(1-2m^{2}/(mn-1))^{2}.$

Using $(1+x/r)^{r}\geq 1+x$, $n\geq 8m$, as well as $mn$ odd and $m\geq 2$
implying $m\geq 3$, we find that the above quantity is at least

$2^{-m}{m\choose k}\cdot(1-1/8m)(1-2m^{2}/(8m^{2}-1))^{2}\geq 2^{-m}{m\choose
k}\cdot(23/24)(53/71)^{2},$

which is greater than $2^{-m}{m\choose k}\cdot\frac{1}{2}$ as desired. ∎

We show that the bound in Lemma 1 is large for
$k\geq\frac{1}{2}m+\frac{1}{2}\sqrt{m}$ by using the following anti-
concentration result for binomial random variables.

######  Lemma 2.

Let $\mathbf{B}_{m}$ denote a binomial random variable with $m$ trials and
probability of success $1/2$. Then for all $m$,

$\Pr\left[\mathbf{B}_{m}\geq\frac{1}{2}m+\frac{1}{2}\sqrt{m}\right]\geq\frac{7}{64}.$

We note that this bound is best possible by considering $m=6$.

###### Proof.

By the symmetry of the binomial distribution, it suffices to prove

$\Pr\left[\mathbf{B}_{m}\leq\frac{1}{2}m-\frac{1}{2}\sqrt{m}\right]\geq\frac{7}{64}.$

By [13, Corollary 1.2], for all $m$ we have

$\left|\Pr\left[\mathbf{B}_{m}\leq\frac{1}{2}m-\frac{1}{2}\sqrt{m}\right]-\Phi(-1)\right|\leq\frac{1}{\sqrt{2\pi
m}},$

where $\Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-t^{2}/2}dt$ is the
cumulative distribution function of a standard normal distribution. This
implies

$\Pr\left[\mathbf{B}_{m}\leq\frac{1}{2}m-\frac{1}{2}\sqrt{m}\right]\geq.158+\frac{1}{\sqrt{2\pi
m}},$

which gives the desired bound for $m\geq 68$, and one can verify the result
for smaller $m$ by aid of a computer. ∎

Finally, we show that conditional on getting at least
$\frac{1}{2}m+\frac{1}{2}\sqrt{m}$ correct guesses in the first phase of the
strategy, one expects to guess “2” correctly at least $\frac{1}{2}m$ times in
the second phase.

######  Lemma 3.

For $\pi\in\mathfrak{S}_{m,n}$, let $K_{2}(\pi)$ denote the number of
$t>\left\lfloor mn/2\right\rfloor$ with $\pi_{t}=2$, and define $K_{1}(\pi)$
as in Lemma 1. If $k\geq\frac{1}{2}m$, then

$\mathbb{E}[K_{2}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k]\geq\frac{1}{2}m,$

and if $k<\frac{1}{2}m$,

$\mathbb{E}[K_{2}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k]\leq\frac{1}{2}m.$

###### Proof.

For $i\geq 2$ define $K_{i}(\pi)$ to be the number of $t>\left\lfloor
mn/2\right\rfloor$ with $\pi_{t}=i$. Observe that for all $k$ and $i\geq 2$,
we have
$\mathbb{E}[K_{2}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k]=\mathbb{E}[K_{i}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k]$.
Thus

$\displaystyle(n-1)\cdot\mathbb{E}[K_{2}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k]$
$\displaystyle=\mathbb{E}\big{[}\sum_{i\geq
2}K_{i}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k\big{]}$
$\displaystyle=mn-\left\lfloor mn/2\right\rfloor-m+k,$

where this last step used that the expectation is exactly the number of cards
among the last $mn-\left\lfloor mn/2\right\rfloor$ that are not of type “1,”
which is deterministically equal to $mn-\left\lfloor mn/2\right\rfloor-m+k$.

With this, if $k\geq\frac{1}{2}m$ we find

$\mathbb{E}[K_{2}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k]\geq\frac{1}{n-1}(mn-
mn/2-m/2)=\frac{1}{2}m,$

and similarly if $k<\frac{1}{2}m$, then $k$ being an integer implies
$k\leq\frac{1}{2}m-\frac{1}{2}$, and we have

$\mathbb{E}[K_{2}(\boldsymbol{\pi})|K_{1}(\boldsymbol{\pi})=k]\leq\frac{1}{n-1}(mn-(mn-1)/2-m/2-1/2)=\frac{1}{2}m,$

proving the result.

∎

With all this we can prove Theorem 1, which for the convenience of the reader
we restate here.

######  Theorem 1.

For all $m$ and $n\geq 8m$:

  * •

Under the optimal strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]\geq m+\frac{1}{40}\sqrt{m}.$

  * •

Under the optimal misère strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]\leq m-\frac{1}{40}\sqrt{m}.$

###### Proof.

If $m=1$, then this follows from Theorem 5, so from now on we assume $m\geq
2$. We first prove our lower bound on the optimal strategy by considering the
aforementioned strategy $\mathcal{H}^{+}_{*}$ of guessing “1” a total of
$\left\lfloor mn/2\right\rfloor$ times, then guessing “1” the rest of the game
if we guessed fewer than $\frac{1}{2}m+\sqrt{m}$ cards correctly, and
otherwise guessing “2” for the rest of the game.

For ease of notation, we let $\mathbf{K}_{i}=K_{i}(\boldsymbol{\pi})$ for
$i=1,2$ as defined in Lemmas 1 and 3. With this, we see that
$S(\mathcal{H}_{*}^{+},\boldsymbol{\pi})=m$ if
$\mathbf{K}_{1}<\frac{1}{2}m+\frac{1}{2}\sqrt{m}$ and
$S(\mathcal{H}_{*}^{+},\boldsymbol{\pi})=\mathbf{K}_{1}+\mathbf{K}_{2}$
otherwise. Thus $\mathbb{E}[S(\mathcal{H}_{*}^{+},\boldsymbol{\pi})]$ is equal
to

$\displaystyle Pr\Big{[}\mathbf{K}_{1}$
$\displaystyle<\frac{1}{2}m+\frac{1}{2}\sqrt{m}\Big{]}\cdot
m+\sum_{k\geq\frac{1}{2}m+\frac{1}{2}\sqrt{m}}\Pr[\mathbf{K}_{1}=k]\cdot(k+\mathbb{E}[\mathbf{K}_{2}|\mathbf{K}_{1}=k])$
$\displaystyle\geq\hskip
5.0pt\Pr\Big{[}\mathbf{K}_{1}<\frac{1}{2}m+\frac{1}{2}\sqrt{m}\Big{]}\cdot
m+\sum_{k\geq\frac{1}{2}m+\frac{1}{2}\sqrt{m}}\Pr[\mathbf{K}_{1}=k]\cdot\left(\frac{1}{2}m+\frac{1}{2}\sqrt{m}+\frac{1}{2}m\right)$
$\displaystyle=\hskip
5.0ptm+\Pr\Big{[}\mathbf{K}_{1}\geq\frac{1}{2}m+\frac{1}{2}\sqrt{m}\Big{]}\cdot\frac{1}{2}\sqrt{m},$

where the inequality used Lemma 3. By Lemmas 1 and 2, we have

$\Pr\left[\mathbf{K}_{1}\geq\frac{1}{2}m+\frac{1}{2}\sqrt{m}\right]\geq\frac{1}{2}\Pr\left[\mathbf{B}_{m}\geq\frac{1}{2}m+\frac{1}{2}\sqrt{m}\right]\geq\frac{1}{20},$

and with this we conclude the desired lower bound for the optimal strategy.

For the optimal misère strategy, essentially the same analysis as above
applies to $\mathcal{H}_{*}^{-}$, the only significant change being that we
use the second half of Lemma 3 instead of the first half. We omit the details.
∎

##  5 Proof of Theorem 2: the $\gamma$-shifting Strategy
$\mathcal{F}_{\gamma}$.

Intuitively we use the $\gamma$-shifting strategy $\mathcal{F}_{\gamma}$ to
achieve the lower bound of Theorem 2 for $\mathbb{E}[\mathbf{S}_{2,n}]$ and
$\mathbb{E}[\mathbf{S}_{3,n}]$, though for technical reasons it will be
convenient to use a variant that never guesses card types larger than some
cutoff value $k$. To aid in our proof, we use the following lemma for
approximating sums with integrals.

######  Lemma 4 ([11], Theorem 4.2).

Let $a<b$ be integers. Let $h$ be an integrable function on $[a-1,b+1]$,
$S=\sum_{i=a}^{b}h(i)$, and $I=\int_{a}^{b}h(x)\,dx$. Let $M$ be such that
$|h(x)|\leq M$ for all $a-1\leq x\leq b+1$. Suppose $[a-1,b+1]$ can be broken
up into at most $r$ intervals such that $h$ is monotone on each. Then

$|S-I|\leq 6rM.$

We now prove Theorem 2, which for the convenience of the reader we restate
here.

######  Theorem 1.

For $n$ sufficiently large, under the optimal strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{2,n}]\geq 2.91,$ $\mathbb{E}[\mathbf{S}_{3,n}]\geq
3.97.$

###### Proof.

The argument is somewhat complex, so to start we consider $m=2$. Fix some
integer $k$ and real $\gamma$, and define the $(k,\gamma)$-shifting strategy
$\mathcal{F}_{k,\gamma}$ as follows. The player guesses “1” until they get a
correct guess. If this happens in fewer than $2\gamma n$ guesses, they use a
modified shifting strategy $\mathcal{F}_{k}$ where they guess “2” until they
get a correct guess, then “3” until they get a correct guess, all the way up
to “$k$,” after which they go back to guessing “1” until they get a correct
guess, then “2,” and so on. If they guess “$k$” correctly a second time, they
keep guessing “$k$” (effectively giving up on trying to get more points). If
the first “1” appears after $2\gamma n$ guesses, they use a modified safe
strategy $\mathcal{S}_{k}$ where they guess “1” until they guess both
correctly, then “2” until they guess both correctly, and so on until they
guess both “$k$”s correctly, after which they keep guessing “$k$” for the rest
of the game.

Given a permutation $\pi$, let $F_{k}(\pi)$ be the score the player gets using
the modified shifting strategy $\mathcal{F}_{k}$ on $\pi$, and let
$G_{k}(\pi)$ be the score they get using the modified safe strategy
$\mathcal{S}_{k}$ on $\pi$. Let $\pi_{1}^{-1}$ denote the index of the
leftmost “1” in $\pi$. For example, if $k=3$ and $\pi=41234132$, then
$\pi_{1}^{-1}=2,\ F_{3}(\pi)=5$ (coming from guessing 1, 2, 3, 1, 2 correctly)
and $G_{3}(\pi)=3$ (coming from guessing 1, 1, 2 correctly). As another set of
examples,
$\\{(\pi,\pi_{1}^{-1},F_{2}(\pi),G_{2}(\pi)):\pi\in\mathfrak{S}_{2,2}\\}$ is
equal to

$\displaystyle\\{(1122,1,2,4),\ (1212,1,4,3),\ (1221,1,3,2),\ (2112,2,2,3),\
(2121,2,3,2),\ (2211,3,1,2)\\}.$ (2)

Let $\pi^{\leq k}$ denote $\pi$ after deleting every letter larger than $k$.
By construction, $S(\mathcal{F}_{k,\gamma},\pi)=F_{k}(\pi)=F_{k}(\pi^{\leq
k})$ if $\pi_{1}^{-1}<2\gamma n$ and
$S(\mathcal{F}_{k,\gamma},\pi)=G_{k}(\pi^{\leq k})$ otherwise. That is,
$S(\mathcal{F}_{k,\gamma},\pi)$ depends entirely on $\pi^{\leq k}$ and
$\pi_{1}^{-1}$. In particular,

$\displaystyle\mathbb{E}[S(\mathcal{F}_{k,\gamma},\boldsymbol{\pi})]=$
$\displaystyle\sum_{t<2\gamma n}\
\sum_{\sigma\in\mathfrak{S}_{2,k}}F_{k}(\sigma)\Pr[\boldsymbol{\pi}_{1}^{-1}=t\
\cap\ \boldsymbol{\pi}^{\leq k}=\sigma]$ $\displaystyle+\sum_{t\geq 2\gamma
n}\
\sum_{\sigma\in\mathfrak{S}_{2,k}}G_{k}(\sigma)\Pr[\boldsymbol{\pi}_{1}^{-1}=t\
\cap\ \boldsymbol{\pi}^{\leq k}=\sigma].$ (3)

With this in mind, we wish to determine $\Pr[\boldsymbol{\pi}_{1}^{-1}=t\
\cap\ \boldsymbol{\pi}^{\leq k}=\sigma]$. Fix some
$\sigma\in\mathfrak{S}_{2,k}$ and define $q=\sigma_{1}^{-1}-1$. We claim that
the total number of $\pi\in\mathfrak{S}_{2,n}$ with $\pi_{1}^{-1}=t$ and
$\pi^{\leq k}=\sigma$ is

${t-1\choose q}{2n-t\choose 2k-1-q}\frac{(2n-2k)!}{2^{n-k}}.$ (4)

Indeed, first we choose the indices where the letters of type
$\\{1,\ldots,k\\}$ will go as follows. The leftmost “1” must go in position
$t$, and then one chooses the $q$ positions to the left of $t$ and the
$2k-1-q$ positions to the right of $t$ where the remainder of these symbols go
in ${t-1\choose q}{2n-t\choose 2k-1-q}$ ways. Once these indices are chosen,
the relative order of the symbols in $\\{2,\ldots,k\\}$ is determined by
$\sigma$. One then arranges the remaining symbols that are not in
$\\{1,\ldots,k\\}$ in $(2n-2k)!/2^{n-k}$ total ways. This proves the claim. We
note that (4) can be written as

$\displaystyle\frac{(t-1)(t-2)\cdots(t-q)\cdot(2n-t)\cdots(2n-t-2k+q+2)\cdot(2n-2k)!}{2^{n-k}q!(2k-1-q)!}$
$\displaystyle\geq\frac{(t-2k)^{q}(2n-t-2k)^{2k-1-q}(2n-2k)!}{2^{n-k}q!(2k-1-q)!}$
,

where we used that $0\leq q<2k$. By dividing this by
$|\mathfrak{S}_{2,n}|=(2n)!/2^{n}$, we conclude that

$\displaystyle\Pr[\boldsymbol{\pi}_{1}^{-1}=t\ \cap\ \boldsymbol{\pi}^{\leq
k}=\sigma]$
$\displaystyle\geq\frac{2^{k}}{q!(2k-1-q)!}\frac{(t-2k)^{q}(2n-t-2k)^{2k-1-q}}{(2n)\cdots(2n-2k+1)}$
$\displaystyle\geq\frac{2^{k}}{q!(2k-1-q)!}\frac{(t-2k)^{q}(2n-t-2k)^{2k-1-q}}{(2n)^{2k}}.$
(5)

Let

$\phi_{q,n}(t):=\frac{2^{k}}{2n\cdot
q!(2k-1-q)!}\left(\frac{t}{2n}\right)^{q}\left(1-\frac{t}{2n}\right)^{2k-1-q},$

which is simply (5) after replacing each $t-2k$ term with $t$, and intuitively
this should be close to (5) because $k$ is a fixed integer. More precisely, we
claim that (5) is equal to $\phi_{q,n}(t)+O(n^{-2})$ for $1\leq t\leq 2n$,
which implies

$\Pr[\boldsymbol{\pi}_{1}^{-1}=t\ \cap\ \boldsymbol{\pi}^{\leq
k}=\sigma]\geq\phi_{q,n}(t)+O(n^{-2}).$ (6)

Indeed, consider the numerator of the second fraction in (5) as a polynomial
in $2k$. Because $t\leq 2n$, for any integer $\alpha$ the coefficient of
$(2k)^{\alpha}$ in this polynomial will be bounded in absolute value by
$2^{2k}(2n)^{2k-1-\alpha}$, so summing over all the terms involving $2k$ in
the numerator gives, in absolute value, at most

$2^{2k}\sum_{\alpha=1}^{2k}(2k)^{\alpha}(2n)^{2k-1-\alpha}\leq
2^{2k}(2k)^{2k+1}n^{2k-2}=O(n^{2k-2}),$

where we used that $k$ is a fixed constant. Dividing this by the denominator
$(2n)^{2k}$ gives the result.

Define

$f_{k,n}(t)=\sum_{q=0}^{2k-1}\sum_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{2,k},\\\
\sigma_{1}^{-1}=q+1\end{subarray}}F_{k}(\sigma)\phi_{q,n}(t),$

and similarly define $g_{k,n}(t)$ but with $G_{k}(\sigma)$ used instead of
$F_{k}(\sigma)$. Then (3) and (6) imply

$\mathbb{E}[S(\mathcal{F}_{k,\gamma},\boldsymbol{\pi})]\geq\sum_{t<2\gamma
n}f_{k,n}(t)+\sum_{t\geq 2\gamma n}g_{k,n}(t)+O(n^{-1}).$

We wish to replace these sums with integrals using Lemma 4. Observe that
$|f_{k,n}(t)|\leq\frac{k2^{k}}{n}|\mathfrak{S}_{2,k}|$ for $0\leq t\leq 2n$
since $|\phi_{q,n}(t)|\leq\frac{2^{k-1}}{n}$ in this range and
$F_{k}(\sigma)\leq 2k$ for all $\sigma\in\mathfrak{S}_{2,k}$. Further,
$f_{k,n}(t)$ has degree at most $2k$, so we can break $\mathbb{R}$ into at
most $2k$ intervals on which $f$ is monotone. Similar analysis holds for
$g_{k,n}(t)$. By taking $r=2k=O(1)$ and
$M=\frac{2k}{n}|\mathfrak{S}_{2,k}|=O(n^{-1})$, we conclude that

$\displaystyle\mathbb{E}[S(\mathcal{F}_{k,\gamma},\boldsymbol{\pi})]$
$\displaystyle\geq\int_{1}^{\left\lfloor 2\gamma
n\right\rfloor-1}f_{k,n}(t)\,dt+\int_{\left\lceil 2\gamma
n\right\rceil}^{2n-1}g_{k,n}(t)\,dt+O(n^{-1})$
$\displaystyle=\int_{0}^{2\gamma n}f_{k,n}(t)\,dt+\int_{2\gamma
n}^{2n}g_{k,n}(t)\,dt+O(n^{-1}),$

where we used that $|g_{k,n}(t)|,|f_{k,n}(t)|=O(n^{-1})$ in this range to
tweak the limits of integration.

At this point one simply needs to choose some $k$ for which the polynomials
$f_{k,n}$ and $g_{k,n}$ are feasible to compute and then to choose $\gamma$ so
that the corresponding integral is optimized. For example, taking $k=2$ and
using (2) gives that $f_{2,n}(t)$ equals

$(2+4+3)\frac{1}{3n}(1-t/2n)^{3}+(2+3)\frac{1}{n}(t/2n)(1-t/2n)^{2}+1\cdot\frac{1}{n}(t/2n)^{2}(1-t/2n),$

and similarly $g_{2,n}(t)$ equals

$(4+3+2)\frac{1}{3n}(1-t/2n)^{3}+(3+2)\frac{1}{n}(t/2n)(1-t/2n)^{2}+2\cdot\frac{1}{n}(t/2n)^{2}(1-t/2n).$

In this case $g_{2,n}(t)\geq f_{2,n}(t)$ for all $0\leq t\leq 2n$, so the
optimal choice is $\gamma=0$, and evaluating $\int_{0}^{2n}g_{2,n}(t)\,dt$
gives the bound

$\mathbb{E}[S(\mathcal{F}_{2,0},\boldsymbol{\pi})]\geq 8/3+O(n^{-1}).$

In a similar fashion, it is feasible to compute the polynomials $f_{6,n}(t)$
and $g_{6,n}(t)$ by use of a computer. Namely, one does this by computing
$F_{6}(\pi)$ and $G_{6}(\pi)$ for each $\pi\in\mathfrak{S}_{2,6}$, which took
about a day using a laptop. After recording the functions
$f_{6,n}(t),g_{6,n}(t)$, one can choose various values of $\gamma$ to plug
into $\int_{0}^{2\gamma n}f_{6,n}(t)\,dt+\int_{2\gamma n}^{2n}g_{6,n}(t)\,dt$
in order to find a value of $\gamma$ which gives a relatively large value.
Experimentally we found that $\gamma=.35$ makes this integral fairly large,
namely at least 2.9144. In total this gives the bound

$\mathbb{E}[S(\mathcal{F}_{6,.35},\boldsymbol{\pi})]\geq 2.9143+O(n^{-1}),$

so for $n$ sufficiently large we obtain our desired bound.

For larger $m$ a similar proof works, the only significant change being that
we use

$\phi_{q,n}(x)=\frac{(m!)^{k}}{(mn)q!(mk-1-q)!}(t/mn)^{q}(1-t/mn)^{mk-1-q}.$

For $m=3$, if we take $k=5$ and $\gamma=.25$ (which again is found through
computer computation and experimentation), this method ends up giving the
desired lower bound for $\mathbb{E}[\mathbf{S}_{3,n}]$ when $n$ is
sufficiently large. ∎

In principle, many other strategies that utilize finite cutoffs could be
analyzed with this method, which could further improve our asymptotic bounds.
However, it seems impractical to extend this method to larger $m$.

##  6 Proof of Theorem 3: the Avoiding Strategy $\mathcal{A}$

This section does not appear in the journal version of this paper and has not
been peer reviewed.

We recall that the avoiding strategy $\mathcal{A}$ was defined in Section 3 as
the strategy of guessing ‘1’, then ‘2’, and so on until some ‘$k$’ is guessed
correctly, and then ‘$k$’ is guessed the rest of the game. To determine
$\mathbb{E}[S(\mathcal{A},\boldsymbol{\pi})]$, we recall the Bonferonni
inequalities, which are essentially weaker versions of the principle of
inclusion-exclusion.

######  Lemma 5 ([11]).

Let $A_{1},\ldots,A_{k-1}$ be events in a finite probability space. For all
even $L$ we have

$\Pr\left[\bigcap\overline{A_{t}}\right]\leq\sum_{\ell=0}^{L}(-1)^{\ell}\sum_{1\leq
t_{1}<\cdots<t_{\ell}<k}\Pr\left[\bigcap_{j=1}^{\ell}A_{t_{j}}\right],$

and for all odd $L$ we have

$\Pr\left[\bigcap\overline{A_{t}}\right]\geq\sum_{\ell=0}^{L}(-1)^{\ell}\sum_{1\leq
t_{1}<\cdots<t_{\ell}<k}\Pr\left[\bigcap_{j=1}^{\ell}A_{t_{j}}\right].$

We use this to prove our main technical lemma of this section.

######  Lemma 6.

For $\pi\in\mathfrak{S}_{m,n}$, let $f(\pi)$ denote the first index which is
guessed correctly using the avoiding strategy $\mathcal{A}$, with
$f(\pi):=\infty$ if no such index exists. For $m$ fixed and any $\epsilon>0$,
we have for all $k\leq mn$,

$\left|\Pr[f(\boldsymbol{\pi})=k]-e^{-k/n}n^{-1}\right|\leq\epsilon
n^{-1}+O_{\epsilon,m}(n^{-2}),$

and moreover

$\left|\Pr[f(\boldsymbol{\pi})=k]\cdot\mathbb{E}[S(\mathcal{A},\boldsymbol{\pi})|f(\boldsymbol{\pi})=k]-\left(m-\frac{(m-1)k}{mn}\right)e^{-k/n}n^{-1}\right|\leq\epsilon
n^{-1}+O_{\epsilon,m}(n^{-2}).$

###### Proof.

For simplicity we first prove these results for $k\leq n$. For $t\leq n$ let
$A_{t}$ be the event $\boldsymbol{\pi}_{t}=t$. Also define $A_{*}$ to be the
event $\boldsymbol{\pi}_{k+1}=k$. Observe that $f(\boldsymbol{\pi})=k$ if and
only if $A_{k}$ occurs and no other $A_{t}$ with $t<k$ occurs. Given
$f(\boldsymbol{\pi})=k$, the expected score is 1 plus the expected number of
$k$’s after index $k$, which by linearity of expectation is 1 plus $mn-k$
times the probability of $\boldsymbol{\pi}_{k+1}=k$. In total then we conclude

$\Pr[f(\boldsymbol{\pi})=k]=\Pr\left[\bigcap_{t<k}\overline{A_{t}}\cap
A_{k}\right],$ (7)

and similarly

$\displaystyle\Pr[f(\boldsymbol{\pi})=k]\cdot\mathbb{E}[S(\mathcal{A},\boldsymbol{\pi})]$
$\displaystyle=\Pr\left[\bigcap_{t<k}\overline{A_{t}}\cap
A_{k}\right]\cdot\left(1+(mn-k)\Pr\left[A_{*}|\bigcap_{t<k}A_{t}\cap
A_{k}\right]\right)$ $\displaystyle=\Pr\left[\bigcap_{t<k}\overline{A_{t}}\cap
A_{k}\right]+(mn-k)\Pr\left[\bigcap_{t<k}\overline{A_{t}}\cap A_{k}\cap
A_{*}\right].$ (8)

We wish to bound these quantities using the Bonferonni inequalities. We claim
for any $1\leq t_{1}<\cdots<t_{\ell}\leq k\leq n$ that

$\Pr[A_{t_{1}}\cap\cdots\cap A_{t_{\ell}}]=\frac{(mn-\ell)!m^{\ell}}{(mn)!}.$

Indeed, every $\pi\in\mathfrak{S}_{m,n}$ with the property $\pi_{t_{j}}=t_{j}$
for $1\leq j\leq\ell$ can be formed by setting $\pi_{t_{j}}=t_{j}$ (with the
$t_{j}$ values all distinct since $k\leq n$) and then the remaining positions
can be filled in $(mn-\ell)!(m!)^{-n+\ell}((m-1)!)^{-\ell}$ ways. The total
number of $\pi\in\mathfrak{S}_{m,n}$ is $(mn)!(m!)^{-n}$, so dividing these
two quantities gives the claim. Using
$(mn)^{\ell}\geq\frac{(mn)!}{(mn-\ell)!}\geq(mn-\ell+1)^{\ell}$, we in
particular find

$n^{-\ell}\leq\Pr[A_{t_{1}}\cap\cdots\cap A_{t_{\ell}}\cap A_{k}]\leq
n^{-\ell-1}+O_{\ell}(n^{-\ell-2}).$ (9)

Similarly we find

$\displaystyle\Pr\left[\bigcap A_{t_{j}}\cap A_{k}\cap A_{*}\right]$
$\displaystyle=\frac{(mn-\ell-2)!(m!)^{-n+\ell+1}((m-1)!)^{-\ell}(m-2)!^{-1}}{(mn)!(m!)^{-n}}$
$\displaystyle=\frac{m-1}{m}n^{-\ell-2}+\Theta_{\ell}(n^{-\ell-3}).$ (10)

Using the Bonferonni inequality and (9) gives for any even $L\leq k$ that

$\displaystyle\Pr\left[\bigcap_{t<k}\overline{A_{t}}\cap A_{k}\right]$
$\displaystyle\leq\sum_{\ell=0}^{L}(-1)^{\ell}\sum_{1\leq
t_{1}<\cdots<t_{\ell}<k}\Pr[\bigcap A_{t_{j}}\cap A_{k}]$
$\displaystyle=n^{-1}\sum_{\ell=0}^{L}\frac{(-k/n)^{\ell}}{\ell!}+O_{\ell}(k^{\ell}n^{-\ell-1})$
$\displaystyle=n^{-1}e^{-k/n}+O(L^{-L}n^{-1})+O_{L}(n^{-2}),$ (11)

where this last step used
$|e^{x}-\sum_{\ell=0}^{L}\frac{x^{\ell}}{\ell!}|\leq\frac{e^{x}}{(L+1)!}=O(L^{-L})$
for $x\leq 1$. Similarly one can use (10) to show

$(mn-k)\Pr\left[\bigcap_{t<k}\overline{A_{t}}\cap A_{k}\cap
A_{*}\right]=\left(1-\frac{k}{mn}\right)(m-1)n^{-1}e^{-k/n}+O(L^{-L}n^{-1})+O_{L}(n^{-2}),$
(12)

and using odd $L$ gives the reveres inequalities. We conclude the first result
for $k\leq n$ by using (7) and (11) after taking $L$ sufficiently large so
that $O(L^{-L}n^{-1})\leq\epsilon n^{-1}$. Similarly we conclude the second
result for $k\leq n$ by using (8), (11), (12), and taking $L$ to be
sufficiently large.

We now consider the general case. Given $t\leq mn$, let $1\leq t^{(1)}\leq n$
and $0\leq t^{(2)}<m$ be the unique integers such that $t=t^{(1)}+t^{(2)}n$.
Let $A_{t}$ be the event $\boldsymbol{\pi}_{t}=t^{(1)}$ and $A_{*}$ the event
$\boldsymbol{\pi}_{k+1}=k^{(1)}$. With this notation established, the exact
same argument as above will work, with the only issue being that the bounds of
(9) and (10) will be incorrect whenever we have two entries in our sequence
with the same $t^{(1)}$ value. However, the number of such sequences is
$O(k^{\ell-1})$, and one can show that the probabilities are still
$\Theta_{\ell}(n^{-\ell-1})$ for any sequence. Thus these terms get absorbed
in the error term and the bound continues to hold. ∎

With this we can determine the asymptotic value of
$\mathbb{E}[S(\mathcal{A},\boldsymbol{\pi})]$.

###### Proof of Proposition 1.

Note that

$\mathbb{E}[S(\mathcal{A},\boldsymbol{\pi})]=\sum\Pr[f(\boldsymbol{\pi})=k]\mathbb{E}[S(\mathcal{A},\boldsymbol{\pi})|f(\boldsymbol{\pi})=k],$

where this conditional expectation is 0 for $k=\infty$. Using this, Lemma 6,
and Lemma 4, we find for all $\epsilon>0$

$\displaystyle\mathbb{E}[S(\mathcal{A},\boldsymbol{\pi})]$ $\displaystyle\leq
n^{-1}\sum_{k=1}^{mn}\left(m-\frac{(m-1)k}{mn}\right)e^{-k/n}+\epsilon+O_{\epsilon,m}(n^{-1})$
$\displaystyle=\int_{0}^{m}\left(m-\frac{(m-1)x}{m}\right)e^{-x}dx+m\epsilon+O_{\epsilon,m}(n^{-1})$
$\displaystyle=m-1+m^{-1}-m^{-1}e^{-m}+m\epsilon+O_{\epsilon,m}(n^{-1}).$

A similar lower bound holds with $\epsilon$ replaced by $-\epsilon$, and by
taking $\epsilon$ arbitrarily small we conclude the desired result. ∎

The last fact we need to prove Theorem 3 is the following.

######  Lemma 7.

Given a strategy $\mathcal{G}$ with Yes/No feedback, let $X(\mathcal{G})$ be
the event that $S(\mathcal{G},\boldsymbol{\pi})=0$. Then
$\Pr[X(\mathcal{A})]\geq\Pr[X(\mathcal{G})]$ for all strategies $\mathcal{G}$.

###### Proof.

Let $\mathcal{G}$ be any strategy, and let $g_{t}$ denote the guess made for
$\boldsymbol{\pi}_{t}$ assuming no correct guesses have been made up to this
point. Let $c_{i}=|\\{t:g_{t}=i\\}|$ and let
$\mathfrak{S}_{m,n}(c_{1},\ldots,c_{n})$ denote the number of permutations
which have no 1 in the first $c_{1}$ positions, then no 2 in the next $c_{2}$
positions, and so on. It is not too difficult to see that
$\Pr[X(\mathcal{G})]=|\mathfrak{S}_{m,n}(c_{1},\ldots,c_{n})|/|\mathfrak{S}_{m,n}|$.
Intuitively the quantity $|\mathfrak{S}_{m,n}(c_{1},\ldots,c_{n})|$ is
maximized when $c_{i}=m$ for all $i$, and one can formally show this by using
Theorem 4 of [2].

In total, $\Pr[X(\mathcal{G})]$ is maximized by any strategy which guesses
each card type $m$ times whenever it guesses no cards correctly. The result
follows since $\mathcal{A}$ is such a strategy. ∎

###### Proof of Theorem 3.

The upper bound follows from Proposition 1. For the lower bound, fix some
strategy $\mathcal{G}$. Observe that
$\mathbb{E}[S(\mathcal{G},\boldsymbol{\pi})]$ is always at least the
probability that some card is guessed correctly using $\mathcal{G}$, so by
Lemma 7 this quantity is at least $1-\Pr[X(\mathcal{A})]$. In the language of
Lemma 6, this is equal to $\Pr[f(\boldsymbol{\pi})\leq mn]$. By Lemmas 6 and
4, this quantity is at least

$\int_{0}^{m}e^{-x}dx-\epsilon m-O_{\epsilon,m}(n^{-1})=1-e^{-m}-\epsilon
m-O_{\epsilon,m}(n^{-1}).$

Taking $\epsilon$ arbitrarily small gives the desired result. ∎

##  7 Concluding Remarks.

There are many questions that remain in this area. Perhaps the most
embarrassing gap in our knowledge is in understanding the score under the
optimal misère strategy with Yes/No feedback. Theorem 3 proves that this
quantity is bounded away from 0, but there is still a large gap between this
and the upper bound of Theorem 1. We conjecture the following.

######  Conjecture 1.

If $n$ is sufficiently large in terms of $m$, then under an optimal misère
strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]=m-o(m),$

where this bound holds uniformly in $n$.

Observe that Theorem 4 shows that the analogous conjecture for the optimal
strategy is true.

It would be of significant interest to determine the asymptotic value of
$\mathbb{E}[\mathbf{S}_{2,n}]$ under an optimal strategy with Yes/No feedback,
but this seems difficult. We claim that one can adapt the methods of [6] to
prove $\mathbb{E}[\mathbf{S}_{m,n}]\leq 2.7m$ for any $m$ provided $n$ is
sufficiently large in terms of $m$. In light of Theorem 4, we know that the
ratio $\mathbb{E}[\mathbf{S}_{m,n}]/m$ tends to 1 as a function of $m$
provided $n$ is sufficiently large in terms of $m$. Given this and Theorem 5,
we suspect the following holds.

######  Conjecture 2.

For all $m$ and $\epsilon>0$, if $n$ is sufficiently large in terms of $m$, we
have under an optimal strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]\leq(e-1)m+\epsilon.$

Another problem of interest would be to close the gap in the error terms of
Theorems 1 and 4 for the optimal strategy. In particular, we conjecture the
following.

######  Conjecture 3.

For all $\epsilon>0$, if $n$ is sufficiently large in terms of $m$, then under
an optimal strategy with Yes/No feedback,

$\mathbb{E}[\mathbf{S}_{m,n}]=m+O(m^{1/2+\epsilon}),$

where this bound holds uniformly in $n$.

That is, we suspect the lower bound of Theorem 1 to be essentially best
possible.

  * ACKNOWLEDGMENTS

The authors would like to thank Steve Butler, Maryanne Gatto, Xiaoyu He, and
Matthew Kwan for fruitful discussions. The authors would also like to thank
the referees and editors for their helpful comments, and in particular for
improving the statement and proof of Theorem 1. The first author was partially
supported by National Science Grant DMS 195404. The last author was partially
supported by the National Science Foundation Graduate Research Fellowship
under Grant No. DGE-1650112.

## References

  * 1. Blackwell, D., Hodges, J. (1957). Design for the control of selection bias. Ann. Math. Statist. 28(2): 449–460. doi.org/10.1214/aoms/1177706973
  * 2. Chung, F., Diaconis, P., Graham, R., Mallows, C. (1981). On the permanents of complements of the direct sum of identity matrices. Adv. Appl. Math. 2(2): 121–137. doi.org/10.1016/0196–8858(81)90001–4
  * 3. Diaconis, P. (1978). Statistical problems in ESP research. Science. 201(4351): 131–136. doi.org/10.1126/science.663642
  * 4. Diaconis, P., Gatto, M., Graham, R. (1980). Suboptimal strategies for a card guessing experiment involving feedback. Bell Laboratories Tech. Memorandum 80–1216 16.
  * 5. Diaconis, P., Graham, R. (1981) The analysis of sequential experiments with feedback to subjects. Ann. Statist. 9(1): 3–23. doi.org/10.1214/aos/1176345329
  * 6. Diaconis, P., Graham, R., He, X., Spiro, S. (2020). Card guessing with partial feedback. Available at: arxiv.org/abs/2010.05059
  * 7. Diaconis, P., Graham, R., Spiro, S. (2020). Guessing about guessing: practical strategies for card guessing with feedback. Available at: arxiv.org/abs/2012.04019
  * 8. Efron, B. (1971). Forcing a sequential experiment to be balanced. Biometrika 58(3): 403–417. doi.org/10.2307/2334377
  * 9. Ethier, S. (2010). The Doctrine of Chances: Probabilistic Aspects of Gambling. Berlin, Germany: Springer Science & Business Media.
  * 10. Ethier, S., Levin, A. (2005). On the fundamental theorem of card counting, with application to the game of trente et quarante. Adv. in Appl. Probab. 37(1): 90–107. doi.org/10.1007/BF01737563
  * 11. Florescu, L., Spencer, J. (2014). Asymptopia. Providence, RI: American Mathematical Society.
  * 12. Gatto, M. (1978). Statistical experiments involving feedback: An example. Bell Laboratories Tech. Memorandum 78-1212–7.
  * 13. Hipp, C, Mattner, K. (2008). On the normal approximation to symmetric binomial distributions. Theory Probab. its Appl. 52(3): 516–523.

  * PERSI DIACONIS

has been shuffling cards since he was five years old. He learned to perfectly
shuffle at age 13 and started proving theorems about shuffling at age 20 (he
is still at it). He is professor of mathematics and statistics at Stanford
University.

    * Department of Mathematics and Statistics, Stanford, Stanford CA 94305
<EMAIL_ADDRESS>
  * RON GRAHAM

was the Irwin and Joan Jacobs Professor in the Department of Computer Science
and Engineering at the University of California, San Diego, and the Chief
Scientist of the California Institute for Telecommunications and Information
Technology. He was a former president of the Mathematical Association of
America and the American Mathematical Society and had been awarded numerous
honors for his extensive groundbreaking work in discrete mathematics. He co-
wrote Magical Mathematics with Persi Diaconis, which was awarded the 2013
Euler Book Prize.

    * Department of Mathematics, UC San Diego, La Jolla CA 92093

  * SAM SPIRO

is a PhD student at UC San Diego studying combinatorics with Jacques
Verstraëte. In addition to playing card games, he also enjoys reading books
and making math puns.

    * Department of Mathematics, UC San Diego, La Jolla CA 92093
<EMAIL_ADDRESS>