I am currently working through (at least I'm trying to) Parrondos' Paradox. Specifically the following instance:
- Game 1: unfair coin flip with winning probability $\frac{1}{2} - \varepsilon$, where $\varepsilon = 0.005$.
- Game 2: If the current winnings are a multiple of 3, we flip a coin with winning probability of $p_1 = \frac{1}{10} - \varepsilon$, else we flip a coin with winning probability $p_2 = \frac{3}{4} - \varepsilon$.
- Game 3: We randomly choose Game 1 or Game 2, each with probability $\frac{1}{2}$.
What I am struggling with is showing that Game 2 is actually a losing game. As a general setting, I let $X_n^{(i)}$ be the winnings from game $i$ after the $n$-th round (i.e. $X_0=0$ and $X_1$ is either 1 or -1 and so on). The sequence $(X_n^{(i)})_{n\in\mathbb{N}_0}$ is a markov chain with state space $\mathbb{Z}$. First of all, my understanding of game $i$ being a losing game is, that $\lim_{n\to \infty} X_n^{(i)} = -\infty$.
For game 1, I was able to show this, as it simply is a transient random walk on $\mathbb{Z}$. Hence we can model $X_n^{(1)}$ as a sum of iid Bernoulli-variables $Z_n$, where $\mathbb{P}(Z_n = 1) = \frac{1}{2} - \varepsilon$ and $\mathbb{P}(Z_n=-1) = \frac{1}{2} + \varepsilon$. This leads us to $$ X_n^{(1)} = \sum_{k=1}^n Z_n. $$
By the strong law of large numbers, we get $\frac{1}{n}X_n^{(n)}\overset{\text{a.s.}}{\longrightarrow} \mu$, where $\mu = \mathbb{E}(Z_1) = -2\varepsilon$. Thus $X_n^{(1)}$ asympotically equals $n\mu$, and since $\mu<0$, we get $\lim_{n\to\infty}X_n^{(1)} = -\infty$, hence game 1 is a losing game.
Game 2 is currently the part, where I am struggling. I first considered simply establishing the transition matrix for $X^{(2)}$ but I am unsure on how I should go on from that. Then I had the idea of investigating which coin flip will occur more often (i.e. if we use the good coin with $p_2$ or the bad coin with $p_1$). For that, I chose $Y_n = X_n^{(2)} \mod 3$ and got the transition matrix
$$ P_Y = \begin{bmatrix}0 & p_1 & 1-p_1\\1-p_2 & 0 & p_2\\p_2 & 1-p_2&0\end{bmatrix}. $$
Furthermore, we can easily show that $Y$ is ergodic and has the stationary distribution $\pi = (\pi_1,\pi_2,\pi_3)$ which I numerically evaluated as $$ \pi_1 \approx 0.384 \qquad \pi_2 \approx 0.154 \qquad \pi_3 \approx 0.462. $$ The problem I'm having is using this information to show that $\lim_{n\to\infty}X_n^{(2)} = -\infty$, as I can't simply model $X^{(2)}$ as a sum of iid Bernoulli-variables. The only idea I currently have is very vague: $$ \mathbb{P}(X_n^{(2)} - X_{n-1}^{(2)} = 1) \to (\pi_2 + \pi_3)p_2 + \pi_1p_1 = \hat p $$ and use this as a probability for an iid sequence $Z^{(2)}_n$ of Bernoulli-variables and set $\mathbb{P}(Z_n^{(2)}=1) = \hat p$ and $\mathbb{P}(Z_n^{(2)} = -1) = 1-\hat p$ and then set $$ X_n^{(2)} \approx \sum_{k=1}^n Z_k^{(2)}. $$
Edit:
After a bit of consideration, I am certain that my approach from above is correct, since the winning probability converges to $\hat p$, as $$ \mathbb{P}(\text{win 2}=1) = \\ \mathbb P(\text{win 2} | Y_n = 0)\mathbb{P}(Y_n=0) + \mathbb P (\text{win 2} | Y_n = 1)\mathbb{P}(Y_n=1) + \mathbb{P}(\text{win 2} | Y_n=2)\mathbb{P}(Y_n=2)\\ =p_1\mathbb{P}(Y_n=0) + p_2(\mathbb{P}(Y_n=1) + \mathbb{P}(Y_n=2)) $$ by the law of total probability. From our previous observations we get $\mathbb P(Y_n=0) \to \pi_1$, $\mathbb P(Y_n=1) \to \pi_2$ and $\mathbb P(Y_n=2) \to\pi_3$, hence $$ \mathbb{P}(\text{win 2}) \to \hat p. $$
That means that $X^{(2)}$ essentially behaves like a random walk with $p=\hat p$ (where $p$ denotes the probability of the iid Bernoulli-variables being 1, analogous to game 1). Since $\hat p < \frac{1}{2}$ (which we can verify numerically), we get $\lim_{n\to\infty} X_n^{(2)} = -\infty$.
The Paradox: The source which stated the problem (which is my university professor), claims that the game 3 I proposed is a winning game, meaning that the (asymptotic) winning probability is greater than $\frac{1}{2}$. This is very much not intuitive to me (probably the reason why it is called a paradox), as my line of thought currently is
$$ \mathbb{P}(\text{win 3}) = \mathbb{P}(\text{win 3}|\text{play 1}) \mathbb{P}(\text{play 1}) + \mathbb{P}(\text{win 3}|\text{play 2}) \mathbb{P}(\text{play 2}), $$ i.e. another application of the law of total probability. With this, I get $$ \mathbb{P}(\text{win 3}|\text{play 1}) = \mathbb{P}(\text{win 1})\\ \mathbb{P}(\text{win 3}|\text{play 2}) = \mathbb{P}(\text{win 2}), $$ resulting in $$ \mathbb{P}(\text{win 3}) = \frac{1}{2}(\mathbb{P}(\text{win 1}) + \mathbb{P}(\text{win 2})) \to \frac{1}{2}\left(\frac{1}{2} - \varepsilon + \hat p\right)<\frac{1}{2}. $$
I have a slight hunch, that the additional wins/losses from game 1 mess with the stationary distribution of $X^{(2)}$, but I am currently unsure how to show this.
Edit 2: Since I asked something similar after @joriki already gave an exceptional answer to my original question, I want to quickly outline my final solution. Similarly to game 2, we consider the markov chain $Y_n = X_n^{(3)} \mod 3$, determine the transition probabilities with the law of total probability, compute the stationary distribution of $Y$ and can thus argue that asymptotically, the expected winnings at game $n$, denoted $\mathbb{E}(X_n^{(3)})$, are positive.
