Suppose a coin game for two players. At the beggining, both of the players have $n$ credits. On every round, the turn's player chooses how much they'll gamble, if it is 1 or 2 credits (of course you can only choose to gamble 1 if you or the other player have only one credit). Then, the coin is flipped: if it lands heads, player A wins; if not, player B wins. The winner gets all the gambled coins and it's the turn of the other player. The game ends when one player gets all of the coins to themselves. Consider the following game as an example:
(A and B each start with 4 credits)
Round 1, A's turn:
A chooses to gamble 2 credits. It lands tails, so B wins. A has 2 credit and B has 6.
Round 2, B's turn:
B chooses to gamble 1 credit. It lands heads, so A wins. A has 3 credit and B has 5.
Round 3, A's turn:
A chooses to gamble 2 credits. It lands tails, B wins. A has 1 credit and B has 7.
Round 4, B' turn:
B is forced to gamble 1 credit. It lands tails, B wins. A has 0 credits and B has 8.
The game ends, and B is the winner.
Now, let's consider the player's strategies:
A: chooses (when possible) randomly between 1 and 2 to gamble;
B: if has more credits than A, gambles 2 (when possible); if not, only 1 (that's to say if B has $x$ credits, then $x \leq n \Rightarrow 1$; $x > n \Rightarrow 2$).
Does B have more chances of winning than A?
Best Answer
The strategy has no bearing on the impact of the game. You can equivalently consider this game to be a fair random walk, starting at $N$, ending at either $0$ or $2N$ and with the option to select whether the next move will take you $2$ or only $1$ step back or forward (the choice alternates between you and an opponent).
Denote $P(X)$ as the probability we hit $2N$ before hitting $0$ starting from $X$.
Now in any strategy, consider the last step where either player selects $2$ as the jump size, after which we will use $1$ as long as the game goes on. (This point must exist), and let's assume the game is at point $X$
At this point, if the player selects $2$, chances of reaching $2N$ chances are $0.5*(P(X-2)+P(X+2))$.
If player selects $1$ instead, chances of reaching $2N$ are now $0.5*(P(X-1)+P(X+1))$.
Since we have that the game afterwards is an unbiased random walk, we use (from theory) the fact that the probability of a random walk at $X$ going to $2N$ is merely $X/2N$. Hence, by substituting this into the equations above, we find that both options are equivalent.
The completion of the proof simply takes this "backwards" to show that at no point, does the selection of $2$ versus $1$ matter.
The crux of this depends on the fact that the probability of reaching $2N$ is linear in terms of $X$, ie, $f(A+B)=f(A)+f(B)$. Otherwise, the player currently winning/losing might select $2$ over $1$.
And, since we showed this game is equivalent to a random walk, starting at the midpoint, then it follows that it is a fair $1/2$ game.