Stochastic Processes and Financial Mathematics
(part one)
4.2 Urn processes
Urn processes are ‘balls in bags’ processes. In the simplest kind of urn process, which we look at in this section, we have just a single urn (i.e. bag) that contains balls of two different colours.
At time \(0\), an urn contains \(1\) black ball and \(1\) red ball. Then, for each \(n=1,2,\ldots ,\) we generate the state of the urn at time \(n\) by doing the following:
-
1. Draw a ball from the urn, look at its colour, and return this ball to the urn.
-
2. Add a new ball of the same colour as the drawn ball.
So, at time \(n\) (which means: after the \(n^{th}\) iteration of the above steps is completed) there are \(n+2\) balls in the urn. This process is known as the Pólya urn. Pólya was a Hungarian mathematician who made contributions across a wide spectrum mathematics, in the first half of the 20th century.
Let \(B_n\) be the number of red balls in the urn at time \(n\), and note that \(B_0=1\). Set \((\mc {F}_n)\) to be the filtration generated by \((B_n)\).
Our first step is to note that \(B_n\) itself is not a martingale. The reason is that over time we will put more and more red balls into the urn, so the number of red balls drifts upwards over time. Formally, we can note that
\(\seteqnumber{0}{4.}{3}\)\begin{align} \E [B_{n+1}\|\mc {F}_n] &=\E [B_{n+1}\1_{\{(n+1)^{th}\text { draw is red}\}}\|\mc {F}_n] +\E [B_{n+1}\1_{\{(n+1)^{th}\text { draw is black}\}}\|\mc {F}_n]\notag \\ &=\E [(B_n+1)\1_{\{(n+1)^{th}\text { draw is red}\}}\|\mc {F}_n] +\E [B_n\1_{\{(n+1)^{th}\text { draw is black}\}}\|\mc {F}_n]\notag \\ &=(B_n+1)\E [\1_{\{(n+1)^{th}\text { draw is red}\}}\|\mc {F}_n] +B_n\E [\1_{\{(n+1)^{th}\text { draw is black}\}}\|\mc {F}_n]\notag \\ &=(B_n+1)\frac {B_n}{n+2}+B_n\l (1-\frac {B_n}{n+2}\r )\notag \\ &=\frac {B_n(n+3)}{n+2}>B_n.\label {eq:urn_Bn_submart} \end{align} We do have \(B_n\in m\mc {F}_n\) and since \(1\leq B_n\leq n+2\) we also have \(B_n\in L^1\), so \(B_n\) is a submartingale, but due to (4.4) \(B_n\) is not a martingale.
However, a closely related quantity is a martingale. Let
\[M_n=\frac {B_n}{n+2}.\]
Then \(M_n\) is the proportion of balls in the urn that are red, at time \(n\). Note that \(M_n\in [0,1]\). We can think of the extra factor \(n+2\), which increases over time, as an attempt to cancel out the upwards drift of \(B_n\). We now have:
\(\seteqnumber{0}{4.}{4}\)\begin{align*} \E [M_{n+1}\|\mc {F}_n] &=\E \l [M_{n+1}\1_{\{(n+1)^{th}\text { draw is red}\}}\,\Big |\,\mc {F}_n\r ] +\E \l [M_{n+1}\1_{\{(n+1)^{th}\text { draw is black}\}}\,\Big |\,\mc {F}_n\r ]\\ &=\E \l [\frac {B_n+1}{n+3}\,\1_{\{(n+1)^{th}\text { draw is red}\}}\,\Big |\,\mc {F}_n\r ] +\E \l [\frac {B_n}{n+3}\,\1_{\{(n+1)^{th}\text { draw is black}\}}\,\Big |\,\mc {F}_n\r ]\\ &=\frac {B_n+1}{n+3}\E \l [\1_{\{(n+1)^{th}\text { draw is red}\}}\,\Big |\,\mc {F}_n\r ] +\frac {B_n}{n+3}\E \l [\,\1_{\{(n+1)^{th}\text { draw is black}\}}\,\Big |\,\mc {F}_n\r ]\\ &=\frac {B_n+1}{n+3}\frac {B_n}{n+2}+\frac {B_n}{n+3}\l (1-\frac {B_n}{n+2}\r )\\ &=\frac {B_n^2+B_n}{(n+2)(n+3)}+\frac {(n+2)B_n-B_n^2}{(n+2)(n+3)}\\ &=\frac {(n+3)B_n}{(n+2)(n+3)}\\ &=\frac {B_n}{n+2}\\ &=M_n. \end{align*} We have \(M_n\in m\mc {F}_n\) and since \(M_n\in [0,1]\) we have that \(M_n\in L^1\). Hence \((M_n)\) is a martingale.
We can think of \(M_n=\frac {B_n}{n+2}\) as a compensation mechanism; \(B_n\) tends to increase, and we compensate for this increase by dividing by \(n+2\).
-
Remark 4.2.1 The calculation of \(\E [M_{n+1}\|\mc {F}_n]\) is written out in full as a second example of the method. In fact, we could simply have divided the equality in (4.4) by \(n+3\), and obtained \(\E [M_{n+1}\|\mc {F}_n]=M_n\).
On fairness
It is clear that the symmetric random walk is fair; at all times it is equally likely to move up as down. The asymmetric random walk is not fair, due to its drift (4.2), but once we compensate for drift in (4.3) we do still obtain a martingale.
Then urn process requires more careful thought. For example, we might wonder:
Suppose that the first draw is red. Then, at time \(n=1\) we have two red balls and one black ball. So, the chance of drawing a red ball is now \(\frac {2}{3}\). How is this fair?!
To answer this question, let us make a number of points. Firstly, let us remind ourselves that the quantity which is a martingale is \(M_n\), the proportion of red balls in the urn.
Secondly, suppose that the first draw is indeed red. So, at \(n=1\) we have \(2\) red and \(1\) black, giving a proportion of \(\frac {2}{3}\) red and \(\frac 13\) black. The expected fraction of red balls after the next (i.e. second) draw is
\[\frac 23\cdot \frac {(2+1)}{4}+\frac 13\cdot \frac 24=\frac {6+2}{12}=\frac 23\]
which is of course equal to the proportion of red balls that we had at \(n=1\).
Lastly, note that it is equally likely that, on the first go, you’d pick out a black. So, starting from \(n=0\) and looking forwards, both colors have equally good chances of increasing their own numbers. In fact, if we were to pretend, right from the start, that black was red, and red was black, we would see the same urn process. This type of fairness is known as symmetry. We’ve seen that \(B_n\) tends to increase (because we keep adding more balls), and we can think of \(M_n\) as a way of discovering the fairness ‘hiding’ inside of \(B_n\).
To sum up: in life there are different ways to think of ‘fairness’ – and what we need to do here is get a sense for precisely what kind of fairness martingales characterize. The fact that \((M_n)\) is a martingale does not prevent us from (sometimes) ending up with many more red balls than black, or vice versa. It just means that, when viewed in terms of \((M_n)\), there is no bias towards red of black inherent in the rules of the game.