Branching processes: Martingales and stopping rules

-

Martingale is an abstraction of "fair play." If a stochastic process is a martingale, some problems can be greatly simplified.

We continue our study of branching processes. \(X_n\) is the random variable representing the population size of the \(n\)-th generation (\(X_0 = 1\) is the initial condition).

See also:

Martingales

Consider the following conditional expectation: 

\[\mathbb{E}(X_{n+1}|X_0,X_1,\cdots,X_n) = \sum_{x}x\Pr(X_{n+1}=x|X_0,X_1,\cdots,X_n).\]

Here the sum is over all possible values of \(X_{n+1}\). Note that this conditional expectation itself is a random variable as it is conditioned on the random variables \(X_0, X_1, \cdots, X_n\) (not on their values). This expectations doesn't really depend on \(X_0,X_1,\cdots,X_{n-1}\), but it does depend on \(X_n\) (the Markov property!). Each individual out of \(X_n\) individuals produces \(\mu_1\) offsprings on average, so the above conditional expectation should be

\[\mathbb{E}(X_{n+1}|X_0,X_1,\cdots,X_n) = X_n\mu_1.\]

Let's introduce a new random variable:

\[Z_n = \frac{X_n}{\mu_n} = \frac{X_n}{\mu_1^n}.\]

Then, the above conditional expectation can be rearranged into

\[\mathbb{E}(Z_{n+1}\mu_1^{n+1}|X_0,\cdots,X_n) = Z_n\mu_1^{n+1}.\]

Cancelling the common factor \(\mu_1^{n+1}\), we obtain

\[\mathbb{E}(Z_{n+1}|X_0,\cdots,X_n) = Z_n.\tag{Eq:Martingale}\]

Thus, the conditional expectation \(Z_{n+1}\) is \(Z_n\). In general, a sequence of random variables \(\{Z_n\}\) that satisfies Eq. (Eq:Martingale) is called a martingale (with respect to the random variable sequence \(\{X_n\}\)).

The gambling martingale

The term "martingale" originates from a strategy in gambling (see Figure 1 below). A gambler bets 1 dollar in the first game. She doubles the bet in each subsequent game. That is, the bet is 2 dollars in the second game, 4 dollars in the third, etc. Assume that her first win is at the \(n\)-th bet. This means she wins \(2^n\) dollars after losing \(1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1\) dollars. Thus, in total, she has won 1 (\(= 2^n - (2^n -1)\)) dollar. This is a guaranteed method of winning! (Not recommended for obvious reasons.)

Figure 1: The gambling martingale.


Let \(Z_n\) be the gambler's total asset (or debt) at the \(n\)-th bet. Each \(Z_n\) is a random variable. Their possible values are:
\[\begin{eqnarray} Z_0 &=& \{1\},\\ Z_1 &=& \{0, 2\},\\ Z_2 &=& \{-2, 0, 2, 4\},\\ Z_3 &=& \{-6, -4, -2, 0, 2, 4, 6, 8\},\\ &\vdots&\nonumber \end{eqnarray}\]
In general, \(Z_n = \{-2^n + 2, -2^2 + 4, \cdots, 2^n -2, 2^n\}\), or
\[Z_n = \{-2^n + 2m + 2 | m = 0, 1, 2, \cdots, 2^n - 1\}\]
for \(n = 1, 2, 3, \cdots\). Any one of these outcomes has a probability \(1/2^n\). Thus, the (unconditional) expectation of \(Z_n\) is
\[\mathbb{E}(Z_n) =\sum_{m=0}^{2^n-1}\frac{1}{2^n}(-2^n + 2m + 2) = 1.\]
The conditional expectation of, say, \(Z_2\) given \(Z_0, Z_1\) is calculated as follows (see Figure 1):
\[\begin{eqnarray} \mathbb{E}(Z_2|(Z_0, Z_1) = (1,2)) &=& 4\cdot\Pr(Z_2=4|(Z_0,Z_1)=(1,2)) + 0\cdot\Pr(Z_2=0|(Z_0,Z_1)=(1,2))\nonumber\\ & =& 4\cdot\frac{1}{2} + 0\cdot\frac{1}{2} = 2,\\ \mathbb{E}(Z_2|(Z_0, Z_1) = (1,0)) &=& 2\cdot\Pr(Z_2=2|(Z_0,Z_1)=(1,0)) + (-2)\cdot\Pr(Z_2=-2|(Z_0,Z_1)=(1,0))\nonumber\\ & = & 2\cdot\frac{1}{2} - 2\cdot\frac{1}{2} = 0. \end{eqnarray}\]
Hence,
\[\mathbb{E}(Z_2|Z_0, Z_1) = \{0, 2\} = Z_1.\]
Similarly (exercise!), the conditional expectation of \(Z_3\) given \(Z_0, Z_1, Z_2\) is
\[\mathbb{E}(Z_3|Z_0, Z_1, Z_2) = \{4, 2, 0, -2\} = Z_2.\]
In general, we have
\[\mathbb{E}(Z_{n+1}|Z_0, Z_1,\cdots, Z_n) = Z_n.\]
Thus, \(\{Z_n\}\) is a martingale with respect to itself.

Example (Eg:RW). Let \(X_n, n = 0, 1, 2, \cdots\) be the random variable for the position of a walker in a symmetric random walk with \(X_0 = 0\). Let's show that \(X_n\) is a martingale with respect to itself. That is,
\[\mathbb{E}(X_{n+1}|X_n) = X_n.\]
To show this, note that, given whatever value of \(X_{n}\), the value of \(X_{n+1}\) is either \(X_{n} + 1\) or \(X_{n} - 1\), each with probability \(\frac{1}{2}\). Therefore,
\[\mathbb{E}(X_{n+1}|X_n) = \frac{1}{2}(X_{n} + 1) + \frac{1}{2}(X_{n} - 1) = X_{n}.\]
□

Stopping rules

Example (Eg:Y). Consider a random process, \(\{X_r\}, r = 0, 1, 2\cdots.\) We decide to stop when a specified conditions are met.
  1. We may want to stop at a specific time \(r = T\). In this case, \(T\) is known, and \(\mathbb{E}(X_T)\) is of interest.
  2. We may want to stop when \(X_r\) becomes greater than or equal to a certain value. In this case, the value (or range) of \(X_T\) is known when the process stops, but the stopping time \(T\) is unknown, and we are interested in \(\mathbb{E}(T)\), the expected stopping time.
Consider a symmetric (Markov chain) random walk that starts at position \(k\). Let \(X_n, n = 0, 1, 2, \cdots\) be the random variable of the position of the walk at step \(n\). The random variable \(Y_n = X_n^2 - n\) is a martingale with respect to \(X_n\). That is,
\[\mathbb{E}(Y_{n+1} | X_{n}) = Y_n.\]
To see this, note that \(X_{n+1}\) is either \(X_n + 1\) or \(X_n - 1\), each with probability \(\frac{1}{2}\) (See the above example (Eg:RW)). Therefore,
\[\begin{eqnarray} \mathbb{E}(Y_{n+1}|X_n) &=& \frac{1}{2}(X_n + 1)^2 + \frac{1}{2}(X_n-1)^2 - (n + 1)\\ &=& X_n^2 - n = Y_n.\end{eqnarray}\] □

Theorem (Stopping Theorem)

If \(\{Z_n\}\) is a martingale with respect to \(\{X_n\}, n = 0, 1, \cdots\) and \(T\) is a defined stopping time, and
  1. \(\Pr(T < \infty) = 1\),
  2. \(\mathbb{E}(|Z_T|) < \infty\),
  3. \(\mathbb{E}(Z_n|T>n)\Pr(T > n) \to 0\) as \(n \to \infty\),
then \(\mathbb{E}(Z_T) = \mathbb{E}(Z_0)\).
Proof. Omitted. (See also Optional stopping theorem.) ■

Example. The symmetric random walk starts at \(X_0 = k\). Suppose the walk stops at step \(n = T\) if either \(X_T = 0\) or \(X_T = a\) for some \(a\) is satisfied (This is the Gambler's Ruin problem. Remember?). What is the expected stopping time, \(\mathbb{E}(T)\)? From the above Example (Eg:Y), we know that \(Y_n = X_n^2 - n\) is a martingale with respect to \(X_n\). We can show that this martingale satisfies all the conditions for the Stopping Theorem (exercise!). Thus,
\[\mathbb{E}(Y_T) = \mathbb{E}(Y_0) = \mathbb{E}(X_0^2 - 0) = k^2.\]
On the other hand, we have
\[\begin{eqnarray} \mathbb{E}(Y_T) &=& \mathbb{E}(X_T^2 - T)\\ &=& \mathbb{E}(X_T^2) - \mathbb{E}(T)\\ &=& [0\times\Pr(X_T = 0) + a^2\times\Pr(X_T = a)] - \mathbb{E}(T)\\ &=& a^2\times\frac{k}{a} -\mathbb{E}(T) = ak - \mathbb{E}(T) \end{eqnarray}\]
where we used the result from the Gambler's Ruin Problem that \(\Pr(X_T = a) = k/a\). By combining these results, we have the expected stopping time:
\[\mathbb{E}(T) = k(a - k).\]

Comments

Post a Comment

Popular posts from this blog

Open sets and closed sets in \(\mathbb{R}^n\)

-
Image
Open sets In \(\mathbb{R}\), we have the notion of an open interval such as \((a, b) = \{x \in \mathbb{R} | a < x < b\}\). We want to extend this idea to apply to \(\mathbb{R}^n\). We also introduce the notions of bounded sets and closed sets in \(\mathbb{R}^n\). Recall that the \(\varepsilon\)-neighbor of a point \(x\in\mathbb{R}^n\) is defined as \(N_{\varepsilon}(x) = \{y \in \mathbb{R}^n | d(x, y) < \varepsilon \}\) where \(d(x,y)\) is the distance between \(x\) and \(y\). Definition (Open set) A subset \(U\) of \(\mathbb{R}^n\) is said to be an  open set  if the following holds: \[\forall x \in U ~ \exists \delta > 0 ~ (N_{\delta}(x) \subset U).\tag{Eq:OpenSet}\] That is, for every point in an open set \(U\), we can always find an open ball centered at that point, that is included in \(U\). See the following figure. Perhaps, it is instructive to see what is  not  an open set. Negating (Eq:OpenSet), we have \[\exists x \in U ~ \forall \delta > 0 ~ (N_{\delta}(x) \not
Read more

Euclidean spaces

-
Image
We would like to study multivariate functions (i.e., functions of many variables), continuous multivariate functions in particular. To define continuity, we need a measure of "closeness" between points. One measure of closeness is the Euclidean distance. The set \(\mathbb{R}^n\) (with \(n \in \mathbb{N}\)) with the Euclidean distance function is called a Euclidean space. This is the space where our functions of interest live. The real line is a geometric representation of \(\mathbb{R}\), the set of all real numbers. That is, each \(a \in \mathbb{R}\) is represented as the point \(a\) on the real line. The coordinate plane , or the \(x\)-\(y\) plane , is a geometric representation of \(\mathbb{R}^2\), the set of all pairs of real numbers. Each pair of real numbers \((a, b)\) is visualized as the point \((a, b)\) in the plane. Remark . Recall that \(\mathbb{R}^2 = \mathbb{R}\times\mathbb{R} = \{(x, y) | x, y \in \mathbb{R}\}\) is the Cartesian product of \(\mathbb{R}\) with i
Read more

Newton's method

-
Image
Newton's method (the Newton-Raphson method) is a very powerful numerical method for solving nonlinear equations.  Suppose we'd like to solve a non-linear equation \(f(x) = 0\), where \(f(x)\) is a (twice) differentiable non-linear function. Newton's method generates a sequence of numbers \(c_1, c_2, c_3, \cdots\) that converges to a solution of the equation. That is, if \(\alpha\) is a solution (i.e., \(f(\alpha) = 0\)) then,  \[\lim_{n\to\infty}c_n = \alpha,\] and this sequence \(\{c_n\}\) is generated by a series of linear approximations of the function \(f(x)\). Theorem (Newton's method) Let \(f(x)\) be a function that is twice differentiable on an open interval \(I\) that contains the closed interval \([a, b]\) (i.e., \([a,b]\subset I\)) and satisfy the following conditions: \(f(a) < 0\) and \(f(b) > 0\); For all \(x\in [a, b]\), \(f'(x) > 0\) and \(f''(x) > 0\). Let us define the sequence \(\{c_n\}\) by \[ \begin{eqnarray} c_1 &
Read more