A Game in Probability

Let the referee's number be $Y$, and your choice $X$. Then you win if nobody's choice is in the interval from $X$ to $2Y-X$. If $0 \le 2Y-X \le 1$, that interval has length $2|Y-X|$. But if $2Y-X < 0$, its intersection with $[0,1]$ has length $X$, and if $2Y-X > 1$ it has length $1-X$. The probability that none of the other players make a choice in an interval of length $L$ contained in $[0,1]$ is $(1-L)^n$. Thus the conditional probability that you win, given $X=x$ and $Y=y$, is $$ \cases{(1-2|y-x|)^n & if $x/2 \le y \le (1+x)/2$\cr (1-x)^n & if $y \le x/2$\cr x^n & if $y \ge (1+x)/2$\cr}$$ Integrating over $y$, I find that the probability that you win if you choose $x$ is $$ f(x) = {\frac { \left( x\,n+2\,x-1 \right) \left( 1-x \right) ^{n}+ \left( - n-2 \right) {x}^{n+1}+2+ \left( n+1 \right) {x}^{n}}{2\,n+2}} $$ An optimal strategy would be to choose $x$ that maximizes this.

One critical point is $x=1/2$, but $f''(1/2) = (n-4) n 2^{1-n}$, so if $n > 4$ this is a local minimum. For example, if $n=5$ we have $$f(x) = {\frac { \left( 7\,x-1 \right) \left( 1-x \right) ^{5}}{12}}-{\frac {7\,{x}^{6}}{12}}+{\frac{1}{6}}+{\frac {{x}^{5}}{2}}$$ whose maximum on $[0,1]$ is at the real roots of $7\,{x}^{4}-14\,{x}^{3}+18\,{x}^{2}-11\,x+2$, approximately $0.2995972362$ and $0.7004027638$.

On the other hand, for $n \le 4$ the optimal solution is $x = 1/2$.

Here is an intuitive, non-rigorous, calculus-free :) explanation for what is going on. Much credit goes to Robert Israel whose excellent answer provided formulas for me to simulate, which inspired the claims & subsequent arguments below.

Following his notation, let $x$ be your pick of location, $y$ be the referee's location, and $f(x) $ be your win prob.

This answer attempts to intuitively argue for the following:

Claim 1: In the large $n$ limit, $f(\frac12) = {1\over n+1}$.

Claim 2: In the large $n$ limit, the optimal occurs at $x = {c\over n}$ (and by symmetry $x= 1 - {c \over n}$) for some small constant $c \approx \frac32$. (In fact, my simulations show the max occurring at exactly $c=2$.)

Imagine this game is not played on the $[0,1]$ interval but rather on a circle. Then clearly, your choice doesn't matter - you might as well pick $0$ - and since there are $n$ other players, your win prob is ${1 \over n+1}$ by symmetry (among players).

The key idea is this: When the game is played on the interval, and you get to pick $x$, this is equivalent to playing on the circle (and you picking location $0$) and then you get to cut open the circle / draw a divider at a distance $x$ from your location.

So $x$ affects your win prob to exactly the extent that the cut (divider) affects your win prob. Well, you start with a win prob of ${1 \over n+1}$ and the cut only affects your win prob in precisely these two scenarios:

• Scenario A: Turning a loss (in the circle game) into a win (in the interval game): In the circle game, starting from your position $0$ and looking in one direction, the immediately next few points are: $0, y, x, z$ where $z$ is some other player and $|0-y| > |y -z|$. I.e. without the cut $x$, you would have lost the circle game, but with the cut $x$, that cuts off the original winner $z$ and you are the new winner in the interval game.

• Scenario B: Turning a win (in the circle game) into a loss (in the interval game): In the circle game, starting from your position $0$ and looking in one direction, the immediately next few points are: $0, x, y, z$ where $|0-y| < |y-z|$. I.e. without the cut $x$, you would have won the circle game, but with the cut $x$, that cuts you off and $z$ becomes the new winner.

In other words, we have:

$$f(x) = {1 \over n+1} + Prob(A) - Prob(B)$$

(Rigorous?) Proof of Claim 1: Scenario A requires that only the referee was between your $0$ and $x$, and scenario B requires that nobody was between your $0$ and $x$. In the large $n$ limit, for $x=\frac12$, each event is exponentially unlikely. Therefore $f(\frac12) = {1 \over n+1}$, same value as in the circle game. In short, cut $x=\frac12$ is so far away in the large $n$ limit that it doesn't matter (so the two games are equivalent). $\square$

Non-rigorous argument for Claim 2:

In both scenarios A and B, before the cut the ordering was $0, y, z$. (If $y$ was not next to you in the circle game, you will lose both the circle game and the interval game no matter where you cut.) Obviously, you want to place the cut between $y$ and $z$, i.e. on the other side of $y$ away from you. Cutting too close and the cut might be on your side of $y$ (cutting you off), while cutting too far and it might not cut off $z$ at all.

The hand-waving comes from an intuitive guess at "aiming" the cut between $y$ and $z$.

In the circle, there will be $n+2$ points - one from the referee, one from you, and $n$ from the other players. So the average length of any interval is ${1 \over n+2}$. In particular, even when conditioned on $y$ being next to you, and $z$ being the other neighbor of $y$, we have $E[|0-y|] = E[|y-z|] = {1 \over n+2}$, because the conditioning only affects relative ordering / who's neighbor to whom. From this alone, I would have guessed that a good strategy is to cut at $x = \frac32 {1 \over n+2}\approx {c \over n}$ where $c = \frac32$, i.e. one-and-a-half expected interval lengths away. $\square$

Further thoughts: Based on my simulations, for large $n$ the optimal happens at $x = {c \over n}$ where $c=2$. In retrospect, this bias (over $c = \frac32$) can probably be explained thus:

• In scenario A, you were on the longer / losing side of $y$, i.e. $E[|0-y|] \gtrapprox {1 \over n+2}$, so it makes sense to cut slightly further away than $c=\frac32$, just to overcome your slightly longer distance to $y$.

• In scenario B, you were on the shorter / winning side of $y$, i.e. $E[|0-y|] \lessapprox {1 \over n+2}$, so it makes sense to cut further away than $c=\frac32$, just to be extra safe that you don't accidentally cut yourself off from an already-winning position.

Building on the very nice solution by antkam, we can calculate the asymptotics for the optimal choice and the corresponding winning probability.

So let $x$, $y$, $z$ be as defined in antkam’s answer. For large $n$, we can approximate the other players’ guesses as a Poisson process with density $n$. (The total number of guesses is fixed, but the resulting correlation between guesses appearing at different locations can be neglected as $n\to\infty$, since a guess at one location only reduces the density remaining for another location by a fraction $\frac1n$.) To simplify the calculations, I’ll do them for density $1$ and then rescale.

So we choose $0$ on the circle and then cut at $x$. The basic winning probability is $\frac1{n+1}\sim\frac1n$, and we need to calculate two corrections to this, dependent on $x$.

The case where we gain due to the cut is the one where $0\lt y\lt x\lt z$ with $y\gt z-y$. The probability for this to occur, conditional on $y$ being the first of the $n+1$ values, is

\begin{eqnarray} \int_{\frac x2}^xf_Y(y)\left(F_{Z-Y}(y)-F_{Z-Y}(x-y)\right)\mathrm dy &=& \int_{\frac x2}^x\mathrm e^{-y}\left(\mathrm e^{-(x-y)}-\mathrm e^{-y}\right)\mathrm dy \\ &=& \int_{\frac x2}^x\left(\mathrm e^{-x}-\mathrm e^{-2y}\right)\mathrm dy \\ &=&\frac x2\mathrm e^{-x}+\frac12\left(\mathrm e^{-2x}-\mathrm e^{-x}\right)\;. \end{eqnarray}

The case where we lose due to the cut is the one where $0\lt x\lt y\lt z$ with $y\lt z-y$. The probability for this to occur, conditional on $y$ being the first of the $n+1$ values, is

\begin{eqnarray} \int_x^\infty\mathrm f_Y(y)\left(F_{Z-Y}(\infty)-F_{Z-Y}(y)\right)\mathrm dy &=& \int_x^\infty\mathrm e^{-y}\mathrm e^{-y}\mathrm dy \\ &=& \int_x^\infty\mathrm e^{-2y}\mathrm dy \\ &=& \frac12\mathrm e^{-2x}\;. \end{eqnarray}

Subtracting the second result from the first yields

$$ \frac x2\mathrm e^{-x}-\frac12\mathrm e^{-x}\;, $$

and setting the derivative to $0$ yields the optimum at $x=2$. This needs to be rescaled by the density $n$, so the optimum asymptotically occurs at $\frac2n$, in agreement with antkam’s findings. The difference in the winning probability also has to be multiplied by $\frac1{n+1}\sim\frac1n$, the probability for $y$ to be the first of the $n+1$ values. So the optimal winning probability is asymptotically

$$ \left(1+\frac{\mathrm e^{-2}}2\right)\frac1n\approx\frac{1.068}n\;. $$