An extrasensory perception strategy :-)

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

Solution 2:

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