# A coin tossing game with random probabilities

Let $p$ a random variable, uniformed distributed in $[0,1]$. Two player $A$ and $B$ play the following game:

Starting from A, a player gets a random value $p(\omega)\in[0,1]$, and he has two choices:

i) He can flip a coin, with a probability $p(\omega)$ of an head. If he get an head he wins the game, otherwise the other player will play with the same distribution $p$.

ii) He can pass the turn to the other player, but giving him a penalized distribution, namely $p$ is replaced, for that turn, by an uniform distribution on $[0,1-p(\omega)]$

Suppose that both players play optimally, i.e. they choose between (i) and (ii) the one which gives the highest probability of winning.

What is the probability of a winning for the first player?

EDIT: let me try to clarify how the game is played. At each turn, the current player gets a random probability $p$ in the following way: if in the previous turn his adversary has flipped the coin (without getting head, in which case the game ended), he takes $p$ uniformly in $[0,1]$. If his adversary hasn't flipped the coin, he takes $p$ uniformly in $[0,1-\tilde{p}]$, where $\tilde{p}$ is the probability his adversary play with during the previous turn. Now the current player can choose if to flip the coin (with a winning probability $p$), or to pass the turn.

• 1) $p$ is fixed and known? 2) what did you try? – zhoraster Sep 24 '15 at 4:16
• I want to know in the first case, if $A$ doesn't get a head, will $B$ flip a coin with a probability $p(\omega)$ of a head, or $B$ will get another coin with another random probability in $[0,1]$ of a head? – Asydot Sep 24 '15 at 4:52
• As the prior comments suggest, the rules for this game are not at all clear. Is $p(\omega)$ fixed for the entire game? If not, when does it change? On its face, it appears that B has no strategic decisions to make. Is that true? If it is not, when does B get a choice? – lulu Sep 24 '15 at 11:45
• I've edited my question. I hope now the rulesare much clear. – Capublanca Sep 24 '15 at 13:14
• I think the rule may not clear still. For example, if $A$ takes $p$ and passes the turn, while $B$ take $p' \in [0,1-p]$ and passes the turn again. Now, will $A$ take $p''$ in $[0,1-p']$ or $[0,1-p-p']$? By your description, it seems to be the former; however, if $p'<\frac{1}{2}$, it won't be a penalized distribution anymore. – Asydot Sep 25 '15 at 7:56

The optimal strategy is to always flip the coin.

First, assume that the first player always flips the coin. Then the second player always draws $p$ from $[0,1]$ and has two options. If she flips, her winning probability is $p+\frac12(1-p)E$, where $E$ is her winning probability averaged over $p\in[0,1]$; the first term represents that she wins immediately, and the second term represents that she wins after the first player flips and fails. If she passes, her winning probability is $(1-\frac12(1-p))E$, the probability that she wins after the first player flips and fails. The difference is $p+\frac12(1-p)E-(1-\frac12(1-p))E=p(1-E)\ge0$. Thus, if the first player always flips, it is optimal for the second player to always flip.

It follows that the first player's winning probability when both players always flip is a lower bound for the first player's optimal winning probability. If the first player draws $p$, his winning probability if both players always flip is $p+\frac12(1-p)E$ (where $E$ is again his winning probability averaged over $[0,1]$), and integrating over $[0,1]$ yields $E=\frac12+\frac12(1-\frac12)E$, so $E=2/3$. Thus, if both players always flip, the first player's winning probability, having drawn $p$, is $p+\frac12(1-p)\frac23=\frac13+\frac23p$. Thus the optimal winning probability $E_p$ having drawn $p$ satisfies $\frac13+\frac23p\le E_p\le1$.

Now we can use this bound to show that it is in fact optimal to always flip. Having drawn $p$, a player can flip to get a winning probability

$$1-(1-p)\int_0^1E_s\,\mathrm ds$$

or pass to get a winning probability

$$1-\frac1{1-p}\int_0^{1-p}E_s\,\mathrm ds\;.$$

The difference is

\begin{align} &-(1-p)\int_0^1E_s\,\mathrm ds+\frac1{1-p}\int_0^{1-p}E_s\,\mathrm ds\\ ={}&\left(\frac1{1-p}-(1-p)\right)\int_0^{1-p}E_s\,\mathrm ds-(1-p)\int_{1-p}^1E_s\,\mathrm ds\\ \ge{}&\left(\frac1{1-p}-(1-p)\right)\int_0^{1-p}\left(\frac13+\frac23s\right)\,\mathrm ds-(1-p)\int_{1-p}^11\,\mathrm ds\\ ={}&\frac13\left(\frac1{1-p}-(1-p)\right)\left((1-p)+(1-p)^2\right)-p(1-p)\\ ={}&\frac13p\left(p^2-p+1\right)\\ \ge{}&0\;. \end{align}

• can you explain me how you get $(1-(p-1)/2)E$ for the probability for the second player to win passing the turn, assuming the first player always flip? – Capublanca Sep 25 '15 at 23:30
• If the second player pass the turn, the first player flip a coin with a probability of head taken uniformly in $[0,p]$. Hence his probability of win should be $\int_0^pxdx=p^2/2$. So the second player wins with probability $(1-p^2/2)E$. Am i missing something? – Capublanca Sep 25 '15 at 23:40
• @Capublanca: You are. The density when drawing uniformly from $[0,p]$ is $\frac1p$, not $1$. Thus the probability is $\frac1p\int_0^px\mathrm dx=p/2$. Or, more intuitively, since the density is uniform, the expected value is the midpoint of the interval, $p/2$. – joriki Sep 26 '15 at 0:02
• Yeah, you're completely right! I'm continuing to read your answer. Thank you for your patience. – Capublanca Sep 26 '15 at 0:07
• It all works, great answer! So to obtain a more interesting situation maybe one can increase the penality (at least for small $p$): for example if A pass the turn with $p$ then B gest his probability uniformly in $[0,1.5p]$. What do you think? – Capublanca Sep 26 '15 at 0:25