An extrasensory perception strategy :-)

Question

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of Consciousness”), I consider the following experiment. A deck of cards is given to a magician John. Then John consecutively takes the cards from the deck, trying to guess suit of the taken card. He looks at the card after the guess for a feedback. The magician wishes to maximize the expected number $E$ of right guesses. For this purpose he devised the following Strategy: at each turn to guess a suit which has a maximal number of card left in the deck. As an easy exercise we can prove that for any sequence of cards in the deck Strategy ensures at least $n$ right guesses, where $n$ is the maximal number of cards with one suit in the deck. But we can consider a more interesting and complicated problem to calculate the expectation $E$ for Strategy (here we are assuming that the deck is so well shuffled such that all sequences of cards have equal probability). By the way, I conjecture that Strategy is the best for maximizing the expectation $E$, that is any other strategy yields not greater value of $E$. Now I wish to evaluate the expectation $E$ for Strategy. For the simplicity we shall consider only a case when there are only two suits ($m\ge 0$ cards of the first suit and $n\ge m$ cards of the second suit). Then $E(0,n)=n$ for each $n$ and we have the following recurrence $$E(m,n)=\frac{n}{m+n}(E(m,n-1)+1)+ \frac{m}{m+n}E(m-1,n)$$

for each $n\ge m\ge 1$.

The rest is true provided I did not a stupid arithmetic mistake.

I was interested mainly in asymptotics for the case $m=n$ and computer calculations suggested that $E(n,n)\sim n+c\sqrt{n}+o(\sqrt{n})$ for $c\approx 0.88\dots$.

Evaluating formulas for $E(m,n)$ for small values of $m\le 6$, I conjectured that there is a general formula

$$E(m,n)=n+m\sum_{i=1}^m\frac {c_{m,i}}{n+i}$$

for each $n\ge m\ge 1$, where $c_{m,i}$ are some integers satisfying the recurrence

$$(m-i)c_{m,i}+ic_{m,i+1}=(m-1)c_{m-1,i}$$

for every $1\le i\le m-1$.

Here are my values for $c_{m,i}$

i\m|  1   2   3   4   5   6 
---+------------------------
 1 |  1   2   4   8  16  32 
 2 |     -1  -4 -12 -32 -80 
 3 |          1   6  24  80 
 4 |             -1  -8 -40 
 5 |                  1  10 
 6 |                     -1

Then I discovered that for my data $c_{m,i}$ is divisible by $2^{m-i}$. After I did the division, I surprisingly obtained that $$c_{m,i}=(-1)^{i-1}2^{m-i}{m-1 \choose i-1}.$$ I expect that I can easily prove this equality by induction.

But I did not stop at this point because I observed that now the general formula for $E(m,n)$ can be compressed to the form

$$E(m,n)=n+m\int_0^1 x^n(2-x)^{m-1} dx.$$

All of above sounds nice for me and I spent a good time investigating the problem, but I am a professional mathematician, although I am not a specialist in the domain of the above problem. Therefore I care about the following questions. Are the above results new, good and worthy to be published somewhere? What another related problems are worthy to be investigated?

Thanks and merry Holidays.

Answer 1

This is to address your question about the asymptotics when $m=n$.

We only need to study the integral

$$ I(n) = \int_0^1 x^n (2-x)^{n-1}\,dx $$

or, after we've made the change of variables $x = 1-y$,

$$ \begin{align} I(n) &= \int_0^1 (1-y)^n (1+y)^{n-1}\,dy \\ &= \int_0^1 (1+y)^{-1} \exp\left[n \log\left(1-y^2\right)\right]\,dy. \end{align} $$

We'll proceed using the Laplace method. The quantity $\log(1-y^2)$ achieves its maximum at $y=0$, and near there we have

$$ \log\left(1-y^2\right) \sim -y^2. $$

This motivates us to make the change of variables $\log(1-y^2) = -z^2$, so that

$$ I(n) = \int_0^\infty \frac{z e^{-z^2}}{(1+\sqrt{1-e^{-z^2}})\sqrt{1-e^{-z^2}}} e^{-nz^2}\,dz. $$

Near $z=0$ we have

$$ \frac{z e^{-z^2}}{(1 + \sqrt{1-e^{-z^2}})\sqrt{1-e^{-z^2}}} = 1 - z + \frac{z^2}{4} + \frac{z^4}{96} - \frac{z^6}{384} + \cdots, $$

and integrating term-by-term we obtain the asymptotic series

$$ I(n) \approx \frac{\sqrt{\pi}}{2n^{1/2}} - \frac{1}{2n} + \frac{\sqrt{\pi}}{16n^{3/2}} + \frac{\sqrt{\pi}}{256n^{5/2}} - \frac{5 \sqrt{\pi}}{2048n^{7/2}} + \cdots. $$

Thus

$$ E(n,n) \approx n + \frac{\sqrt{\pi}}{2} n^{1/2} - \frac{1}{2} + \frac{\sqrt{\pi}}{16} n^{-1/2} + \frac{\sqrt{\pi}}{256} n^{-3/2} - \frac{5 \sqrt{\pi}}{2048} n^{-5/2} + \cdots. $$

Answer 2

You ask "What (...) related problems are worthy (of investigation)?"

There is the question of what the expected score is if we use that strategy (which is the best strategy) with a Zener pack of 25 cards, namely which contains 5 cards of each of 5 different shapes. I asked that question here: the answer is 8.65.

Then there are misère problems where we try to mimimise the score. I have asked the misère version of the Zener card question here.

Answer 3

If I understand right the game, and picturing the evolution as a path in a discrete grid -from $(0,0)$ to ($n,n$)- it's seen that each segment that goes towards the diagonal is a "win"; the other are misses, except for the ones that start from the diagonal itself, half of which are wins. Then, if the path of length $2n$ have $c$ diagonal-touchings (including the start, excluding the end), the total of wins is $n+c/2$.

Hence, the problem is converted to the (probably simpler and already studied) problem of computing the expected numbers of diagonal touchings on a lattice path - or, in a fair ballot counting problem, compute the expected number of ties (or lead changes).