Random Game Using Real Numbers

Question

The original question:

Alice and Bob play a game. To win the game, Alice needs $a$ points, and Bob needs $1$ point ($a$ is fixed for each game). In each round of the game, Alice picks a real number $x$. Then a coin is flipped, and Alice is awarded $x$ points if the coin comes up heads, and Bob is awarded $x$ points if the coin comes up tails. Assume Alice always plays optimally. Your task is to find the probability that Alice wins given she is using the best strategy.

This problem is a little difficult to formalize, so I will offer the following formalization. First, note that at the beginning of any round, we can normalize the game so that Bob needs exactly $1$ more point. We will define a strategy $s:\mathbb{R^+}\to\mathbb{R^+}$ as a function that takes as an input the number of points Alice needs, and outputs her choice $x$. Define $p_s(a)$ to be the probability that Alice wins the game needing $a$ points and playing strategy $s$. Let $S$ be the set of all strategies. Find $$p, p(a)=\sup_{s \in S}p_s(a).$$

First, we note that $p(a) = 1$ if $a = 1 - \epsilon < 1$, as Alice can choose a sufficiently small $x$ and play it repeatedly until she wins. I have included a formal proof below.

Second, we note that $p(1)$ still equals $1$. Pick $\epsilon, 2\epsilon, 4\epsilon, 8\epsilon, \dots$ until she has won one of these. For sufficiently small $\epsilon$, this will always happen before she is defeated by Bob. At this point, she is ahead of Bob by $\epsilon$, and the argument for $a < 1$ applies. Again, I have included a formal proof below

Clearly this also imples that $\lim_{a \to 1^+}p(a)=1$.

These are the easy cases. Now intuition suggests that $\lim_{a \to \infty}p(a)=\frac 12$ (she is forced to choose $x=a$ when $a$ is sufficiently large). I have not tried to prove this, but it does not seem too difficult.

Finally, I can show that $p(2) \geq \frac 34$. This is easily done by first having Alice choose $x=1-\epsilon$ for sufficiently small $\epsilon$. If she wins the points, invoke the $\lim_{a \to 1^+}$ case to win with probability $1$, and if not then choose $x=2$ to win with probability $\frac 12$. This strategy can be expanded to any $n \in \mathbb{N}$ by simply picking $1-\epsilon$ repeatedly, $n-1$ times. This shows that $p(n) \geq \frac 12 + 2^{-n+1}$ for natural numbers $n$.

Question: Can this bound be improved, shown to be tight, or extended to all real numbers?

---

Proof for a < 1: Consider the game in which Bob needs $1$ point and Alice needs $1-\epsilon, \epsilon > 0$ points. We will show that for every $\delta > 0$, there exists a strategy that allows Alice to win with probability at least $1-\delta$.

The strategy is simple: Alice will repeatedly choose $x=k$, where $k=\frac{\epsilon^2}{8(2-\epsilon)\log \delta}$. We note that once $2-\epsilon$ points have been awarded, one of the two players must have won. As a result, one of the two players will always have won after $\frac{2-\epsilon}{k}$ rounds have been played. Let $X_i, 1 \leq i \leq \frac{2-\epsilon}{k}$ be the indicator random variable that is $1$ if Bob wins round $i$ and $0$ otherwise, and let $X=\sum X_i$. Then clearly Bob is awarded a total of $Xk$ points, and so he wins only if $X \geq \frac 1k.$ Then, $$\begin{aligned} \Pr [\text{Bob wins}] =& \text{Pr }\left[X \geq \frac 1k\right] \\ =& \Pr \left[X \geq \frac 1k - \frac \epsilon {2k} + \frac \epsilon {2k}\right] \\ =& \Pr \left[X \geq \mathbb{E} [X] + \frac{\epsilon}{2k}\right] \\ =& \Pr \left[X \geq \mathbb{E} [X] \left(1+ \frac{\epsilon}{2-\epsilon}\right)\right] \\ \leq & \text{exp }\left(-\frac{2-\epsilon}{8k}\left(\frac{\epsilon}{2-\epsilon}\right)^2\right) \hspace{20 px} (*)\\ = & \delta \end{aligned}$$ where $(*)$ is due to Chernoff Bounds.

Proof for a=1: We will describe a set of strategies that allow Alice to win the game in which both she and Bob need $1$ point with probability $\geq 1-\delta$ for any $\delta > 0$.

Let $\delta ' = \frac \delta 2$, and $r=\frac{\delta '}2$. Alice will begin by choosing $x=r, 2r, 4r, 8r, \dots$ until either Bob wins the game, or until Alice wins any of these coin flips. It is easy to verify algebraically that the probability that Bob wins in this stage is $\leq \delta '$. Once Alice wins any coin flip, she is ahead of Bob by exactly $r$ points. At this point, she can abandon her current betting scheme, normalize Bob's points and play a strategy for $a<1$ that gives her a win chance of $1-\delta '$. By union bound, the probability of Bob winning is then $\leq 2\delta ' = \delta$, as desired.

Answer 1

Credit for this proof goes to a friend.

---

Theorem: $p(a) \leq \frac 12 +\frac 1{2a}$.

Proof: Begin by making a few simplifying assumptions. First, assume that Alice never chooses an $x$ that would give her more than $a$ points if she won. This means that when the game ends, Bob always has less than $a+1$ points, as $x \leq a$. Similarly, Alice always has exactly $a$ points if she wins.

Next, let $X$ be the random variable denoting Alice's points at the end of the game minus Bob's points at the end of the game. By a simple linearity of expectation argument, $\mathbb{E}[X]=0$. But the by the properties above, $$\begin{aligned} \mathbb{E}[X] &\leq p(a)(a-1)+(1-p(a))(-a-1)\\ \Rightarrow p(a) &\leq \frac {1+a}{2a} \end{aligned}$$

Answer 2

We can show that the upper bound \begin{align} p(a)\le 2^{-1}+2^{-a}&&{\rm(1)} \end{align} holds over all $a > 0$ and that we have equality, $p(n)=2^{-1}+2^{-n}$ at all positive integers $n$. Comparing with the bound \begin{align} p(a)\le 2^{-1}+(2a)^{-1}&&{\rm(2)} \end{align} given in the answer by DreamConspiracy, we see that (1) is the stronger bound over $a > 2$ and (2) is stronger over $1 < a < 2$. At $a=2$ they are equal and are also an equality, $p(2)=3/4$. In fact, it can also be shown that (2) is tight for an infinite sequence of points in the range $(1,2)$. Specifically, $p(a)=2^{-1}+(2a)^{-1}$ for $a=(1-2^{-n})^{-1}$ (any positive integer $n$).

To prove the bound (1), we can start with the following statement. In fact both of the bounds given above can be proved using this, but I just look at (1).

If $f:\mathbb{R}_+\to\mathbb{R}$ satisfies

1. $f(0)\ge1$
2. $f(a) \ge 1/2$, all $a$.
3. $f(a)\ge \frac12\left(f(a-x)+f(a/(1-x))\right)$ over $0 < x \le a$ and $x < 1$.

Then, $p(a)\le f(a)$ over all $a > 0$.

This is quite a standard argument for Markov processes. It is convenient to rescale the quantities to be relative to the number of remaining points Bob requires to win. i.e., just before the nth coin toss, let $a_n$ denote the remaining points Alice requires to win divided by the points Bob requires to win. So, $a_1=a$. Also let $x_n$ be the stake on the n'th toss divided by the points Bob requires. At the n'th toss, either of the following happens,

• Alice wins the toss and $a_{n+1}=a_n-x_n$ or, if $x_n\ge a_n$, Alice wins the game.
• Bob wins the toss and $a_{n+1}=a_n/(1-x_n)$ or, if $x_n\ge1$, Bob wins the game.

We suppose that Alice always chooses $x_n\le a_n$ as a larger value of $x_n$ cannot further increase her chance of winning. Also, if $x_n\ge1$ then Alice may as well also make sure that $x_n\ge a_n$ as it will ensure that she wins the game if it comes up heads and does not affect the result in case of tails (i.e., Bob wins the game).

Note that $a_n$ is a stochastic process, and consider defining a new process $X_n$ by $X_n=1$ if Alice has won before the nth toss, $X_n=0$ if Bob has won, and $X_n=f(a_n)$ otherwise. This is a supermartingale. If none has won by the n'th toss then, $$ \mathbb{E}[X_{n+1}\vert a_1,a_2,\ldots,a_n]=\frac12\left(f(a_n-x_n)+f(a_n/(1-x_n)\right)\le f(a_n)=X_n. $$ We have to be a bit careful here and consider the case $x_n\ge1$ separately. In this case we also have $x_n\ge a_n$, so Bob or Alice will win the game on the n'th toss, each with probability 1/2. The condition $f\ge1/2$ ensures that the inequality still holds.

So, by optional stopping for supermartingales,if $N$ is the toss at which someone wins the game, $$ f(a)=X_1\ge\mathbb{E}[X_N]=\mathbb{P}({\rm Alice\ wins}). $$ as required.

To prove bound (1), it just needs to be shown that $f(a)=\min(2^{-1}+2^{-a},1)$ satisfies property 3 above. For $a\le 1$, $f(a)=1$, and the inequality holds trivially. So, consider $a > 1$ and, wlog, suppose that $a-x\ge1$ (as the rhs of the inequality in statement 3 is decreasing in $x$ over $a-x\le1$). We need to show that $$ f(a)\ge\frac12\left(f(a-x)+f(a/(1-x)\right). $$ Plugging in the definition of $f$, subtracting 1/2 from both sides, and multiplying by $2^a$, we need to show $$ 1\ge2^{x-1}+2^{-ax/(1-x)-1}. $$ As the rhs is decreasing in $a$, it is enough to prove this at a=1. Setting $y=1-x$, then we just need to show that $$ g(y)\equiv2^{-y}+2^{-1/y}\le1 $$ over $0 < y < 1$. Taking the derivative, $$ g^\prime(y)=2^{-y}\log2\left(2^{y-1/y}y^{-2}-1\right) $$ The derivative of the term inside the parenthesis is $2^{y-1/y}y^{-2}(1-1/y)^2\log2$, which is positive. So over $0 < y <1$, $g$ is initially decreasing, then increasing, so its maximum is attained at the limits $g(0)=1$ or $g(1)=1$. This gives $g\le1$ as required.

Now that we have established the upper bound (1), consider the following strategy, (for arbitrarily small $\epsilon$),

1. if $1 < a_n < 2$ choose $x_n=a_n-1$
2. if $a_n\ge2$, choose $x_n=1-\epsilon$. Then, if the n'th toss is tails, so that $a_{n+1}=a_n/\epsilon$, choose $x_{n+1}$ large enough to ensure someone wins the game on the n+1'th toss.
3. if $a_n\le1$, use the strategy in the question to give Alice victory with probability as close to one as we like (say, $1-\epsilon$).

For positive integer $a=n$, conditional on coming up heads $n-1$ times, then Alice will then win with arbitrarily high probability. Otherwise, she wins with probability 1/2. This gives a lower bound, $$ p(n)\ge2^{-(n-1)}+(1-2^{-(n-1)})2^{-1}=2^{-1}+2^{-n}, $$ showing that (1) is an equality at positive integer $a$.

Next, we can show that bound (2) is an equality at each of the points $z_n\equiv(1-2^{-n})^{-1}$ for positive integer $n$. Using the strategy described above, if $a=z_n$, then it cane seen that $a_{k+1}=z_{n-k}$ if Alice loses the first $k$ tosses. It follows that Alice will win the game if she wins any of the first $n+1$ tosses (with arbitrarily high probability). So, $$ p(a)\ge 1-2^{-(n+1)}=1/2+1/(2a), $$ as required.

Finally, on the range $[1,2]$, I plotted the upper bound (2), the lower bound given by the probability of winning with the strategy above (denoted $p0(a)$), and numerically calculated $p(a)$ with an iterative optimisation. It can be seem that they coincide at the sequence of points $z_n$ but, elsewhere, the bound (2) does not look to be tight, and the strategy given above is suboptimal.

Answer 3

I do not see how you can have $p(a) > \frac{a+2}{2(a+1)} = \frac12+\frac{1}{2(a+1)}$ for any $a \gt 0$ and in particular how you can have $p(1) \gt \frac34$ or $p(\frac12) \gt \frac56$ even with Alice varying the stakes through the game

I am not convinced by your initial argument that for $a < 1$ Alice can get a probability of winning the match arbitrarily close to $1$ by using a constant small stake. My understanding of Gambler's Ruin is that the probability of winning overall with a fair coin will be $\frac{1}{a+1}$ (at least when the constant stake divides both $a$ and $1$, and close to this if the stake is relatively small but does not divide them)

My argument for the general case:

Let $W_A$ be the conditional expected amount that Alice gets, given that Alice wins the match. Clearly $W_A \ge a$

Let $W_B$ be the conditional expected amount that Bob gets, given that Bob wins the match. I would have thought $1 \le W_B \le a+2$, since the penultimate position cannot be more negative that $-1$ and so the final bet need never be bigger that $a+1$, which is enough to decide the match with a single bet from any position; if it were bigger then the same results could be obtained with a more complicated analysis of $W_A$ but that seems unnecessary

Then I would have thought that since you have a fair coin, you have $pW_A-(1-p)W_B =0$ and so $pa-(1-p)(a+2)\ge 0$ leading to $p \le \frac12+\frac1{2(a+1)}$

This is a bound rather than a strategy. Consider, as a strategy which gets arbitrarily close, choosing some small $\epsilon$ and using equal stakes to bet until you reach $a+\delta_a$ or $-1+\delta_{-1}$, both of these integer multiples of $\epsilon$ with both $\delta$s positive but less than or equal to $\epsilon$:

• You will reach $a+\delta_a$ first (Alice wins the match) with probability of $\frac{1-\delta_{-1}}{a+1-\delta_{-1}+\delta_{a}}\approx \frac{1}{a+1}$
• You will reach $-1+\delta_{-1}$ first (match still continuing) with probability $\frac{a+\delta_{a}}{a+1-\delta_{-1}+\delta_{a}}\approx \frac{a}{a+1}$; in this latter case your next bet can have stake $a+1-\delta_{-1}$ so
  • you reach $a$ this way (Alice wins the match) with overall probability $\frac{a+\delta_{a}}{2(a+1-\delta_{-1}+\delta_{a})}\approx \frac{a}{2(a+1)}$
  • you reach $-a-2+2\delta_{-1}$ (Bob wins the match) with the same overall probability

With this combined strategy, Alice wins the match with probability $\frac{a+2-2\delta_{-1}+\delta_{a}}{2(a+1-\delta_{-1}+\delta_{a})} \approx \frac12+\frac{1}{2(a+1)}$ and Bob wins the match with probability $\frac{a+\delta_{a}}{2(a+1-\delta_{-1}+\delta_{a})} \approx \frac12-\frac{1}{2(a+1)}$