7
$\begingroup$

You and n other players ( $n \ge 1$ ) play a game. Each player chooses a real number between 0 and 1. A referee also chooses a number between 0 and 1. The player who chooses the closest number to the referee's number wins. What should be your choice. Will it depend on $n$ ?

Assume that the n players (other than yourself) and the referee choose the numbers uniformly between 0 and 1.

Can someone give a sketch of the solution? I've been trying this but unable to produce an answer.

Edit:You may ignore two or more players choosing the same number

$\endgroup$
  • $\begingroup$ What happens if there are ties? For example, what happens if all the players choose $.5$? $\endgroup$ – lulu Jan 21 at 16:39
  • 1
    $\begingroup$ @lulu (with prob 1) none of the others will because they are choosing uniformly on [0,1]. $\endgroup$ – almagest Jan 21 at 16:40
  • $\begingroup$ Oh okay. I'll edit the question. $\endgroup$ – Siddharth Acharya Jan 21 at 16:40
  • $\begingroup$ @almagest I don't understand. If my choice is forced on me (or made by some impartial process) then what's the question? $\endgroup$ – lulu Jan 21 at 16:42
  • 4
    $\begingroup$ @almagest Ah, I see. The players, other than the special player, choose by machine. Got it. I think the other problem is more interesting...where everyone is trying to out think everyone else. $\endgroup$ – lulu Jan 21 at 16:44
16
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ +1 This is a wonderful answer, but is there a way to see some (small) part of this without calculus? E.g. why $x=1/2$ is not optimal for $n>4$ or perhaps for "large enough" $n$? $\endgroup$ – antkam Jan 21 at 18:58
  • 2
    $\begingroup$ Blows my mind that 1/2 is not optimal. Would love an intuitive explanation! $\endgroup$ – Kevin Wang Jan 22 at 3:36
  • $\begingroup$ @KevinWang - pls see if my answer below constitutes an intuitive explanation. Robert - I would also really appreciate if you would read it and provide any comments / suggestions / corrections. Thanks! $\endgroup$ – antkam Jan 23 at 0:04
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $+1$, very nice approach! Could you check the asymptotic winning probability in my answer against your simulations? $\endgroup$ – joriki Jan 25 at 11:26
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (1) My sim is at work, but YES I do remember staring at $1.06***$ and wondering what the heck is going on! Will confirm on Monday. (2) My so-called "simulation" is in fact "simulating" Robert's formula for $f(x)$! I.e. evaluating $f$ against a dense array of $x$ values to find max & argmax, something you can easily do too. (3) Basic Q: Why can we approximate with Poisson? There are exactly $n+1$ other points, so this is Poisson conditioned on there being $n+1$ "successes" or "arrivals", which makes it non-Poisson. Why is the Poisson approximation valid? $\endgroup$ – antkam Jan 25 at 14:43
  • $\begingroup$ (4) I also didn't understand either integral :( can you further explain? E.g. in the first one $e^{-y}$ in the interval $(x/2, x)$ obviously describe position of $y$, but how does $e^{-(x-y)} - e^{-y}$ describe what needs to happen with $z$ i.e. $x < z < 2y$? Similar question for the 2nd integral also... (5) But regardless of my questions, THANK YOU for finding a way to explain my sim results! :) $\endgroup$ – antkam Jan 25 at 14:47
  • $\begingroup$ Just re-did my so-called "sim" (see above) in an online python environment. At $n=10^5$ the win prob is $\approx 1.0677/n$. Bigger $n$ values died on me. You probably have access to much better computing resources for this < 20-line simulation. :) $\endgroup$ – antkam Jan 25 at 15:14
  • $\begingroup$ @antkam: I made some changes to the answer trying to address your questions. I don't prove rigorously that the process asymptotically becomes a Poisson point process (in fact I wouldn't know what exactly to prove for that and how to prove it), but it seems clear to me that the correlations caused by the fixed number of guesses become negligible with $n\to\infty$ because we're only interested in two events and they only deplete the available density by a fraction $\frac2n$. As regards your result $1.0677/n$: Agreement to five digits is good enough for me :-) $\endgroup$ – joriki Jan 25 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.