Stochastic Processes, practice problem taken from One Thousand Exercises in Probability

Question

I am struggling with probability and specifically markov chains. I find making them requires much creativity and insight. I took this problem from Grimmett's One Thousand Exercises in Probability and I am having difficulty setting up a markov chain and finding the transition probabilities for this example problem.

The question is:

A sequence $(W_n)_{ n>0}$ of random words is recursively made like this:

• $W_0$ is a word, with length $N$ and the letters are taken from the set $\{a,b\}$
• Suppose that $W_n$ is a word. Then we draw $N$ letters at random, one at a time with replacement from $W_n$. Then $W_{n+1}$ is the word of length $N$ obtained by recording the letters drawn.
• Let $X_n$ be the number of letter $a$'s within $W_n$

1. Argue $(X_n)_{ n>0}$ is a Markov chain and find the transition probabilities
2. Show $X$ is martingale wrt to filtration $(F_n)_{ n\ge 0}$ generated by $X$ itself.
3. Use the Optional Stopping theorem to compute $P_k (V_n < V_0)$ for $0 <k < N$

There are more parts to this problem but the main confusion is on 1,2 in how I can find the transition probabilities as I am lost.

Any help or tips would be greatly appreciated !

Answer 1

Note that if $(U_i)$ is an iid sequence, and $X_0$ is independent of $(U_i)$, then the recursively defined $X_{n+1} := f(X_n, U_n)$ is always a Markov chain with respect to its natural filtration, for any measurable $f$. (Check this yourself in the simple case of a countable state space.) In a discrete setting like we have here, measurability is typically obvious, so you can think of this as saying "any recursive thing where you get the next element by doing something to the previous one with an independent source of randomness will be Markov". The fact that $f$ does not depend on $n$ and the $U_n$ have the same distribution is what gives you that it is a (homogeneous) Markov (chain).

In your case, you get the next word $W_{n+1}$ from the previous one $W_n$ by taking an independent samples $(U^{(n)})$ with replacement of (1,2,..., $N$) and then using them as indices into $W_{n}$, so in your case $f(x, (u_1,\ldots, u_N)) = (x[u_1], ..., x[u_N])$.

For transition probabilities, you view $W_n$ as a bag of $A$ $a$'s and $B$ $b$'s with $A+B=N$. For each index, you have an $A/N$ chance of getting $a$ and $B/N$ chance of getting $b$. So the chance to go from $W_n$ to a fixed sequence $(x_1, \ldots, x_N)$ with $x_i \in \{a, b\}$ is $(A/N)^{A'} (B/N)^{B'}$ where $A',B'$ are the number of $a$'s or $b$'s in $(x_1,\ldots, x_N)$.

I'll stop here and let you think about it. In the future, if you have a question with many parts, ask them in separate questions as you progress.

Answer 2

1. The number of $a$'s in $W_n$ only depends on the numbers of $a$'s in $W_{n-1}$. To see this, note that there are $X_{n-1}$ $\ a$'s in $W_{n-1}$, so to generate $W_n$ we're drawing $N$ elements with replacement from a word with $X_{n-1}$ $\ a$'s and $N- X_{n-1}$ $\ b$'s. So the conditional probability distribution of $X_n$ is, after doing some counting : $$\begin{align}\mathbb P (X_n = x | X_{n-1},\ldots,X_0) &= \mathbb P (X_n = x | X_{n-1}) \\ &= {N\choose x}\left(\frac{X_{n-1}}{N}\right)^x \left(\frac{N-X_{n-1}}{N}\right)^{N-x} \\ &= {N\choose x}\left(\frac{X_{n-1}}{N}\right)^x \left(1-\frac{X_{n-1}}{N}\right)^{N-x}\end{align} $$ You just need to be a bit cautious about the states $X_{n-1}\in\{0,N\}$, which are absorbing states, I'll let you take care of it.
2. To show that $X$ is a martingale, you have to show that $\mathbb E[X_n|X_{n-1}] = X_{n-1}$. To do so, you can notice that the conditional distribution of $X_n|X_{n-1}$ is, as can be seen from question 1), a binomial distribution of parameters $(N,\frac{X_{n-1}}{N})$. So you can directly compute its mean and be able to conclude that it is indeed a martingale with respect to the filtration $(F_n)_{n\ge 0}$. (You also have to treat the case $X_{n-1}\in\{0,N\}$ separately).
3. What is $V$ ?