Pólya’s Urn Long-Term Probability

martingalespolya-urn-model

I am tasked with the following problem:

Let $M_n$ be the fraction of white balls in Pólya's urn after $n$ draws, where you start with one white and one black ball, and after every draw, you add another one of the color you drew to the urn. Suppose that we know that $M_{20}=\frac{7}{22}$. Prove that:

$$P\Big\{M_\infty>\frac{3}{4}\Big|M_{20}=\frac{7}{22}\Big\}<\frac{4}{9}$$

I already know that $M_\infty=\lim_{n\rightarrow\infty}M_n$, i.e. after some arbitrary time $n$, the proportion stabilizes around some fraction between $[0,1]$, and that this is uniformly distributed. I was thinking about using the Martingale Convergence Theorem, since this proportion is bounded by $1$, but I wasn't certain how to apply it to this problem, or if it is even appropriate to use in this circumstance. Any suggestions as to how to start would be sincerely appreciated. Cheers.

Best Answer

Try using Markov's inequality. Realistically speaking, your probability should be very, very close to $0$. But this inequality provides an (rather weak) upper bound that is just slightly less than $\frac{4}{9}$, which I believe is what you are looking for. You should also use the Optional Sampling Theorem or the Martingale Property along the way.