Probability with an urn 
Given an urn with $5$ balls: red or blue. We draw a ball from the urn and replace this ball with a ball of the other color. We repeat this process until all balls have the same color.
Prove that with probability one all balls have the same color ultimately. Hint: give an upper bound for the probability that you replace a ball more than nn times for all $n\in\mathbb{N}$ and use the continuity of the probability measure.

I have no idea how to do this question, although I know that I need to use the squeeze theorem and the continuity to prove that the given probability is equal to $1$. Could someone help?
 A: I did not understand the hint you gave, so let's do this the Markov way. Define the set of states $S=\{0,1,2\}$. We are in state $0$ if there are $0$ balls of one type (red or blue) and that means automatically that there are $5$ balls of the other type. We are in state $1$ if there is only one blue ball or only one red ball in the urn. I think you can guess what state 2 means. Define $X_k$ the state of timestep $k$. Furthermore define $p^{(n)}_{ij}:=\mathbb{P}(X_n = j  \ | \ X_{n-1}=i)$. Since the timestep $n$ is not important at all we have $p^{(n)}_{ij} = p_{ij}$. You can easily check that:
\begin{align}
p_{00}&=1\\
p_{10}&= \frac{1}{5} , \ \ \ \ \  p_{12}=\frac{4}{5}\\
p_{22}&= \frac{3}{5} , \ \ \ \ \  p_{21}=\frac{2}{5}
\end{align}
And the ones not mentioned above are zero.  Now define:
\begin{align} 
f_i:= \mathbb{P}(\text{Ending at state 0} | X_0 = i)
\end{align}
So $f_i$ is simply the probablity you end up with an urn with 5 blue balls or 5 red balls when you have started in state $i$. Now you can check that if you would start in state $1$ then you can either go to state 0 then you have finished, or go to state $2$ and have probablity $f_2$ to ever end up at $0$. We can make similar statements when starting at 2. So we have:
\begin{align}
\begin{cases}
f_1= \frac{1}{5}+\frac{4}{5}f_2\\
f_2 = \frac{2}{5}f_1 + \frac{3}{5}f_2
\end{cases}
\end{align}
Now solving this give the unique solution $f_1=f_2=1$. So you will always end up in state 0 in other words there is some time you will get an urn with only blue balls or only red balls. 
I hope it is clear. However I can fully understand that this needs some digestion if you have not seen Markov chains yet. 
A: Just to provide an alternative approach that follows the hint given in the OP.  By simplicity:


*

*let us define $ R_iB_j$ any configuration including $i$ red balls and $j$ blue balls. 

*let us focus on the probability that we have to replace a ball more than $n$ times (i.e., the probability that, after replacing $n$ balls, we still have not obtained the configuration with all balls of the same color), and let us call this probability $P_n$;

*in addition, let us define as $q_k$ the probability that, given we have arrived to the ${(k-1)}^{th}$ replacement without achieving the objective of having all balls of the same color, we do not get this objective in the successive step (i.e., the ${k}^{th}$ replacement also fails).
Based on these definitions, the probability $P_n$ that after $n$ replacements we still have not obtained the configuration with all five balls of the same color is given by
$$P_n=q_1 \cdot q_2 \cdot q_3... q_{n} = \prod_{k=1}^{n} q_k$$
Now note that $q_k$ ranges between $1$ (if the configuration after the ${(k-1)}^{th}$ step is of the type $ R_2B_3$ or  $ R_3B_2$  and then makes impossible to achieve the objective in the successive step) and $4/5$ (if the configuration after the ${(k-1)}^{th}$ step is of the type $R_1B_4$ or    $ R_4B_1$ ). So we can write 
$$P_0 \supseteq P_1  \supseteq P_2  \supseteq P_3... \supseteq P_n$$
Also, since there is a non-zero probability that the $R_1B_4$ or  $ R_4B_1$ configurations occur, we have 
$$\cap_{n=0}^{\infty} P_n=0$$
Now we only have to apply the continuity of probability theorem. This states that:


*

*if a sequence of events $ A_j $ satisfies $A_1 \subseteq A_2 \subseteq  A_3  \subseteq···\,\,$ and $\cup_{j=1}^{∞}=A \,\,$, then $ A_j $ "increases" to $A$ (this is often written as $A_j \nearrow A\,\,$);

*similarly, if a sequence of events $ B_j $ satisfies $B_1 \supseteq B_2 \supseteq  B_3  \supseteq···\,\,$ and $\cap_{j=1}^{∞}=B\,\,$, then $ B_j $ "decreases" to $B$ (this is often written as $B_j \searrow B\,\,$). 
From this we get 
$$\lim_{n \rightarrow \infty} P_n=0$$
which directly implies that, if $n \rightarrow \infty \,\,$, with probability $1$ all balls have the same color ultimately.
A: Let's look at a simpler modified process where we have more control. Assume we start with 4 blue balls and 1 red ball. We'll ask about the probability of fixing all balls to be red. If the initial configuration were different, then it would just fix at red with a higher probability. Furthermore, if it doesn't fix to red after the first 4 steps, then we will start over with 4 blue and 1 red in this modified process. 
If the original, unmodified process, hasn't fixed during the first 4 steps, the probability it fixes during the next 4 steps is bounded below by that of this modified process. To understand that, just realize that the original process can start with 3 one color and 2 the other color as well. And all we have to do to fix all balls the same color is to at least draw the 2 and replace them in two steps. Furthermore it can fix in either color. Here we are forcing it to start with 4 blue and want all 4 to be replaced in the next 4 steps. One might desire to work this out carefully and actually calculate all possible situations though. I will not do that here.
Let $T$ be the time that we stop this modified process. Of course, $T=4,8,12,\ldots$ only since we have no choice but to draw all 4 blue balls in a row for the modified process.
$$P(T=4)=\frac45\cdot\frac35\cdot\frac25\cdot\frac15=\frac{48}{625}.$$
Furthermore, if $T>4$, we reset the process and ask about the next 4 steps. We get that
$$\begin{aligned}
P(T=4k)&=P(\text{first $4(k-1)$ draws didn't fix the color, but the next $4$ draws do})\\
&=\frac{48}{625}\left(1-\frac{48}{625}\right)^{k-1}.
\end{aligned}$$
since each set of 4 draws are independent and we reset the process after each 4 draws.
The probability that we eventually fix this modified process with all 5 red balls is the probability that $T=4k$ for some $k$.
$$\begin{aligned}
P(\cup_{k=1}^\infty\{T=4k\})&=\sum_{k=1}^\infty P(T=4k)\\
&=\sum_{k=1}^\infty\frac{48}{625}\left(1-\frac{48}{625}\right)^{k-1}\\
&=\frac{48}{625}\cdot \frac{1}{1-\left(1-\frac{48}{625}\right)}=1.
\end{aligned}$$
Now back to the original process where we don't reset the balls every 4 steps. Let $\tau$ be the number of steps until this process stops. We can see that 
$$P(4(k-1)<\tau\leq 4k)\geq P(T=4k)$$
thus 
$$\sum_{k=1}^\infty P(\tau=k)\geq \sum_{k=1}^\infty P(T=4k)=1.$$
Thus eventually all balls will be the same color with probability $1$.
Although this doesn't directly use continuity of measure, you can alter it slightly to see that 
$$P(\text{eventually all one color})
=P(\cup_{k=1}^\infty \{\tau\leq k\})
=\lim_{k\rightarrow\infty}P(\{\tau\leq k\})=1$$
using the modified process here to get a lower bound on $P(\{\tau\leq k\})$. It should look like a partial geometric series as used above.
A: (I cannot make anything out of the hint and the strict orders coming with it.)
The game has three states $k\in\{0,1,2\}$, whereby $k$ denotes the smaller of the numbers of red, resp., blue balls in the urn. If we are in state $0$ the game is over. From  state $1$ we move with probability ${1\over5}$ to state $0$ and with probability ${4\over5}$ to state $2$. From state $2$ we move with probability ${2\over5}$ to state $1$ and remain with probability ${3\over5}$ in state $2$. Denote by $E_k$ $(k\in\{1,2\})$ the expected number of steps to reach state $0$ when we are in state $k$. Then
$$E_1=1+{4\over5}E_2,\qquad E_2=1+{2\over5}E_1+{3\over5}E_2\ ,$$
which leads to $E_1=15$, $E_2=17.5$.
Now for the actual question: Let $p$ be the probability that we get to state $1$ only a bounded number of times, but not to state $0$ (which would end the game). This is only possible if there is an $N\geq1$ such that after $N$ steps we are locked in state $2$ forever. This happens with probability $\left({3\over5}\right)^\infty=0$. It follows that $p=0$. This means that with probability $1$ we  reach state $0$ after a finite number of moves or get to state $1$ an infinite number of times without ever choosing the path to state $0$. The probability for the latter is again $0$.
A: Let's say we got $k$ red balls and $l$ red blue with $k>l$ (note that this also works the other way around: if there are more blue ones than red ones $k$ will be red so that $k>l$ still applies, and as soon as $l > k$ (so that $l = 3$ and $k = 2$) they swap values too.).
The chance that $k$ will increase of course is $p = \frac{l}{5}$. Now if $k = 3$, it means that even if this fails $k = 3$ still is true, since $k$ and $l$ will swap values ($k>l$). Now if we say the chance that $k$ will become 4 is $p = 1 - \frac{3}{5} = 0.4$ (which is constant, because $k > l$) and $n$ is the amount of times we try, we can say we got a form of binomial distribution here, so 
$$\lim_\limits{n\to \infty}p(k = 4) = \binom{n}{1} * 0.4^1 * (1 -0.4)^{n - 1} = 1$$
Because you said ultimately, I figured we could do this an infinite amount of times. Now we can assume that in our urn, even if we started out with $k=3$, $k=4$.  Now we can do the same thing again, actually, since we try an infinite amount of times, so $k = 3$ always will become $k = 4$. The chance that $k$ will become 5 (once again constant) is $p = 1 - \frac{4}{5} = 0.2$. Now the last part
$$\lim_\limits{n\to \infty}p(k = 5) = \binom{n}{1} * 0.2^1 * (1 -0.2)^{n - 1} = 1$$
So ultimately, for $\lim_\limits{n \to \infty} p(k = 5) = 1$, there will be 5 balls with the same color in your urn.
