I recently came upon a scenario described in the Magic: the Gathering subreddit, where a player had a situation in which the win or lose scenario was not obvious. It was a rather old post, but linked to recently in a question about indeterminable situations in Magic.
The question involves coin flipping and thus is probabilistic in nature, i.e. there is a chance that the player would win, but would it be guaranteed?
The scenario is as follows: The opponent is a 6 life and has Leonin Elder in play. Our player has Filigree Sages and Wirefly Hive in play and access to arbitrary amounts of mana. It is the opponents end step and for whatever reason our player will lose the game at the end of his next turn.
Because our player has access to arbitrary amounts of mana, he may through Filigree Sages activate Wirefly Hive an arbitrary number of times. Each time Wirefly Hive is activated he flips a coin and if it comes up heads he gets a 2/2 creature token, which he can attack with next turn. If it comes up tails, he looses all the creature tokens again and will have to start over. This is fairly simple, he should just need 3 consecutive success to win, right? But there is a catch here.
The opponent had the Leonin Elder in play, which means their life total goes up by 1 every time one of the tokens is created by Wirefly Hive. Okay, so the 3 success would create 3 tokens netting him 3 life. We still can win from here. We will need 3 more tokens to counter act this life gain and the life gain from the additional tokens. So we actually needed 6 consecutive successes. Still another catch?
Every time we try for consecutive successes and fail to get enough the opponent gains more life points, thus each successive attempt will require more consecutive successes. I.e. every time we fail to win it gets harder to win. But we can repeat infinitely, shouldn’t we be guaranteed to win at some point?
Removing all the Magic lingo the problem becomes the following “simple” game:
There are two players $ A $ and $ B $. $ A $ starts with $ N $ points and $ B $ with 0 points. If at any time $ B $ has the same amount (or more) points than $ A $, then $ B $ wins. $ B $ may flip a coin and on heads $ B $ gains 2 points and $ A $ 1 point. On tails $ B $ looses all their points. What is the probability that $ B $ wins?
Here comes math.
We may model this problem using a stochastic process $ \{X_n\} $. $ X_n $ will be the state that our opponent is at $ n $ life. Then the probability of moving from state $ X_n $ to $ X_m $ is $ \mathcal P(X_m|X_n) $. In essence, we would flip a coin until a) we fail, or b) have enough consecutive successes to finish our opponent, which we model as moving to the state $ X_0 $. For example, if we are in state $ X_1 $, then there is 50% probability of succeeding a flip, which gains our opponent 1 life up to 2 and gives us a 2/2 creature that may win us the game, and 50% probability of us failing the flip, which leaves us in the current state. Note that in this state there is no rising difficulty.
Suppose we are in the state $ X_2 $, then the probabilities look like $$ \mathcal P(X_0|X_2) = 0.25, \quad \mathcal P(X_2|X_2) = 0.50, \quad \mathcal P(X_3|X_2) = 0.25, $$ and $ \mathcal P(X_i|X_2) = 0 $ for all other $ i $.
The full collection of transition probabilities $ p_{ij} = \mathcal P(X_i|X_j) $, $ i,j \in \mathbb N_0 = \{0,1,2,\dots\} $, is given by the formula $$ p_{ij} = \begin{cases} \frac1{2^j} & \text{if $ i=0$,} \\ \frac1{2^{i-j+1}} & \text{if $ 0<j\leq i < 2j $}\\ 0 & \text{otherwise}. \end{cases} $$
If there was only finitely many states we could describe our probability of being in any particular state as a vector, but since there is no upper limit, we can’t truly. However, we are not out of luck. Since the probability of getting to $ X_0 $ appear to be decreasing at higher states we can approximate the true process by a truncated one. We pick some $ N > 0 $ and say that $ X_N $ is the state where we lose the game. We will let $ \mathcal P(X_i|X_n) $ remain as before as long as $ i,n < N $. Then $$ \mathcal P(X_N|X_n) = 1 – \sum_{i=0}^{N-1}\mathcal P(X_i|X_n). $$ We may then define the transition matrix $ P_N $, which has the elements $$ (P_N)_{ij} = \begin{cases} p_{ij} & \text{if $ 0\leq i,j < N $}, \\ 1-\sum_{k=0}^{N-1}p_{kj} & \text{if $ i=N $ and $ j < N $}, \\ 1 & \text{if $ i=j=N $}, \\ 0 & \text{otherwise}. \end{cases} $$
For example, if $ N = 5 $ the matrix looks like this $$ P_5 = \begin{bmatrix} 1 & \frac12 & \frac14 & \frac18 & \frac1{16} & 0 \\ 0 & \frac12 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac12 & 0 & 0 & 0 \\ 0 & 0 & \frac14 & \frac12 & 0 & 0 \\ 0 & 0 & 0 & \frac14 & \frac12 & 0 \\ 0 & 0 & 0 & \frac18 & \frac7{16} & 1 \end{bmatrix}. $$ If $ N = 9 $, $$ P_9 = \begin{bmatrix} 1&\frac12&\frac14&\frac18&\frac1{16}&\frac1{32}&{\frac{1}{64}}&{\frac{1}{128}}&{\frac{1}{256}}&0 \\ 0& \frac12 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0&0&\frac12&0&0&0&0&0&0&0 \\ 0&0&\frac14&\frac12&0&0&0&0&0&0\\ 0&0&0 &\frac14&\frac12 & 0 & 0 & 0&0&0\\ 0&0&0&\frac18&\frac14&\frac12 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 &\frac18&\frac14&\frac12&0&0&0\\ 0&0 &0&0&\frac1{16}&\frac18&\frac14&\frac12&0&0 \\ 0&0&0&0&0&\frac1{16}&\frac18&\frac14&\frac12&0 \\ 0&0&0&0&0&\frac1{32}&{\frac{7}{64}}&{\frac{31}{128}}&{\frac{127}{256}}&1 \end{bmatrix}. $$
By picking a starting state $ X_\ell $, which is represented by a vector $ \mathbf v_\ell $ with elements 0 except for the $ \ell $’th element (counting from 0), which is 1, and multiplying the vector by the matrix $ P_N $ repeatedly,
$$ P_N^k\mathbf v_\ell = \overbrace{P_N\cdot P_N \cdots P_N}^{\text{$ k $ times}}\mathbf v_\ell = \mathbf w, $$
we get the probability of ending up in any particular state. By increasing $ N $ and $ k $ until $ \mathbf w = (w_0,w_1,\dots,w_N) $ stabilizes (in a certain sense) we may find a quite accurate probability of us winning from any given state.
For instance, for the scenario described in the beginning, $ \ell = 6 $, the probability of winning would be just under 4.7%, while the likelihood of getting caught in a spiral of the opponent gaining life is the remaining 95.3%.
The above was obtained by taking $ N = k = 50 $, which yields the result 4.685865122%, and increasing to $ N = k = 100 $ only adds $ 8\times 10^{-9} $% to this probability.
As a final note, since in official Magic: the Gathering rules one can only shortcut a loop by stating that it will be repeated some $ n $ times, not until a given condition or state is satisfied, the official ruling would be to try to play out the coin flips and if it doesn’t succeed in the first couple of tries you would have to yield the match or likely lose the match due to slow play warnings.