# An extrasensory perception strategy :-)

I asked this question at MSE some months ago but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a professional mathematician, although I am not a specialist in the domain of the problem. Therefore my question is: are the following results new, good and worthy to be published somewhere? Thanks.

So, here is the shortened story. 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 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$. I expect that I can easily prove by induction that

$$c_{m,i}=(-1)^{i-1}2^{m-i}{m-1 \choose i-1}.$$

Henry pointed that $c_{m,i}$ looks very like OEIS A013609.

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.$$

I was interested mainly in asymptotics for the case $m=n$, and Antonio Vargas using the Laplace method showed that

$$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.$$

• MO is not usually a place to ask people to review your results. Instead, you might want to ask for references where this has been studied before. By the way, your first conjecture that the obvious strategy is optimal follows from linearity of expectation. – Douglas Zare Mar 9 '14 at 17:00
• @DouglasZare I do not need a review. I expect that it suffices to specialist to cast a glance at the results and to say a couple of words about them. I think that it is more “scientific” way to ask opinions at MO than (or before) I write an article and submit it to a journal. – Alex Ravsky Mar 9 '14 at 18:52
• @DouglasZare Thanks for pointing me on the first conjecture. – Alex Ravsky Mar 9 '14 at 19:05
• The problem definitely isn't new. Some of the results are standard. I think the final result follows from properties of Catalan numbers. mathoverflow.net/questions/88314/… Please separate out what you think is new after reviewing Catalan numbers. – Douglas Zare Mar 9 '14 at 21:31