Assignment 3

Assigned 2025-09-10, due 2025-09-17

Unless stated otherwise, assume $(X_n)$ is a time homogeneous Markov chain on a finite state space $\mathcal X$ with transition matrix $P$.

Question 1

We say $a \in \mathcal X$ is an absorbing state if $P(a, a) = 1$. Let $\mu$ be any stationary distribution of the Markov chain $(X_n)$. True or false: For any $x \in \mathcal X$ such that $x \neq a$ and there exists $N \in \N$ such that $P^N(x, a) > 0$ we must have $\mu(x) = 0$. Prove it, or find a counter example.
Consider the nearest neighbor random walk on $\set{0, N}$ which is absorbed at the endpoints ${0, N}$. That is $P(x, y) = 1/2$ if $x \in \set{1, \dots, N-1}$ and $y = x\pm 1$, $P(0, 0) = P(N, N) = 1$ and $P(x, y) = 0$ otherwise. Find all stationary distributions of this chain.

Question 2

Let $(X_n)$ be the nearest neighbor random walk on the integer lattice $\Z^d$. Does this Markov chain have a stationary distribution? Find it, or prove it doesn’t exist.

Question 3

We saw in this proposition that the expected reward function $u$ satisfies the (discrete) Dirichlet problem \begin{equation}\tag{D}\label{e:dirichlet} \left. \begin{aligned} (I - P) u &= 0 &&\text{in } V - S\,,\quad \\ u &= f && \text{in } S \,. \end{aligned} \right\} \end{equation} In general, there could be more than one solution to this system. So if you find a solution to \eqref{e:dirichlet}, you aren’t guaranteed that this solution you found is the expected reward $u(x) = \E^x f(X_{\tau_S})$ that you wanted to compute. In this question we provide a condition which guarantees the solution to \eqref{e:dirichlet} is unique.

Let $S \subseteq \mathcal X$, be such that for every $x \in \mathcal X - S$ there exists $N \in \N$, $y \in S$ such that $P^N(x, y) > 0$. Suppose $u$ solves \eqref{e:dirichlet}. Show that $\max_{\mathcal X} u = \max_S u$, and $\min_{\mathcal X} u = \min_S u$.
Under the same assumption as in the previous part, show that the solution to \eqref{e:dirichlet} is unique. (That is given $S$ satisfying the above condition, and given a function $f$, there is at most one function $u$ that solves \eqref{e:dirichlet}.)

Question 4

Let $S \subseteq \mathcal X$ and $f \colon \mathcal X - S \to \R$, $g \colon S \to \R$ be two given functions. Define \begin{equation} \tau = \min\set{ n \in \N \st X_n \in S } \quad\text{and}\quad u_n(x) = \E^x( \one_{\set{\tau > n}} f(X_n) + \one_{\set{\tau \leq n}} g(X_\tau) ) \,. \end{equation} Show that $u$ satisfies the system \begin{align} u_{n+1} &= P u_n &&\text{in } \mathcal X - S\,, \\ u_{0} &= f &&\text{in } \mathcal X - S\,, \\ u_n &= g &&\text{on } S \end{align}

Note: When $X_n$ is the nearest neighbor random walk on the lattice $h \Z^d$ for $h > 0$, this is exactly an explicit forward time discretization of the heat equation.

Note: You may be tempted to simplify the above system recursively and write $u_n = P^n u_0$. This, is not correct as stated. For us to have $u_n = P^n u_0$, we need $u_{n+1} = P u_n$ for every $x \in \mathcal X$; we only know it for every $x \in \mathcal X - S$. However, one can modify $P$ and define $P(x, y) = \one_{\set{x = y}}$ for every $x \in S$. This change does not change $\tau$ or $u$, and after making this change you can conclude $u_{n+1} = P u_n$ for every $x \in \mathcal X$, and so with this modified $P$ you will have $u_n = P^n u_0$.
The equations above don’t always have nice analytical solutions. They can, however, be found easily using a computer. In the gamblers ruin example, set $N = 100$, and let $u_n(k)$ be find the probability the gambler is bankrupt in time $n$, given he started with $$k$. Numerically find $u_n$ and plot it for $10$ values of $n$ that are geometrically spaced between $1$ and $5000$. For reference, your final result will look like this:

You only need to turn in a screenshot of a code snippet where you assemble the transition matrix $P$, where you compute $u_n$, and the output of your code.

Note: It may be tempting to write multiple for loops to compute $P$ and $u_n$; but it’s a lot better (and faster) if you use the library functions numpy has. You can construct $P$ using the functions diag and full and eye. You can perform matrix multiplication by either converting $P$ to a matrix (using asmatrix, matrix), or using the @ operator. You can take powers using matrix_power. You can generate the plot using something like:
```
kk = arange(N)
for n in geomspace(1, 5000, 10, dtype=int):
    # Compute un here
    plot(kk, un, label=f'n={n}')
legend()
# Can also save the output if needed.
# plt.savefig('figures/prob-ruin-vs-time.svg')
```

The remaining questions are interesting questions related to the material we are covering. In order to keep the length of the homework assignment reasonable, these questions are not part of your homework. They are included here as they might be interesting for some of you (and they may be moved to a later homework in future). There is no extra credit for doing them.

Optional question 5

Suppose $(X_n)$ is irreducible, and $u \colon \mathcal X \to \R$ is a function such that $(I - P)u = 0$ on the entire space $\mathcal X$, then must $u$ be a constant function? Prove it, or find a counter example.

Optional question 6

Let $S \subseteq \mathcal X$ and $\tau = \min \set{n \in \N \st X_n \in S}$ be the first hitting time to $S$. Suppose there exists $\epsilon > 0$, and $N \in \N$ such that for every $x \in \mathcal X$ we know $\P^x(\tau \leq N) > \epsilon$. For every $x \in \mathcal X$, show that $\P^x( \tau > k N) \leq (1 - \epsilon)^k$, and use this to show $\E^x \tau < \infty$.

Optional question 7

Let $h > 0$ and let $\mathcal X_h = h \Z^d = \set{ h k \st k \in \Z^d}$. Let $X_n$ be the nearest neighbor random walk on $\mathcal X_h$, and $P_h$ be the associated transition matrix. Let $u \colon \R^d \to \R$ be a twice continuously differentiable function. Compute \begin{equation} \lim_{h \to 0} (I - P) u \,. \end{equation} Your answer will involve the Laplacian of $u$. (In this case we recall $d (I - P)$ is the graph Laplacian, which explains the terminology.)

Optional question 8

Consider a tournament with $N$ teams where each team plays exactly $d$ matches. Each match has one winner (scored as $1$) and one looser (scored as $0$), and the teams are ranked using the page rank algorithm with $\beta = 0.1$, as on the previous homework.

Fix a $d$-regular graph with $N$ nodes (you can generate one using random_regular_graph), representing all the games that were played. This graph will have $E = Nd/2$ edges, and so there are $2^E$ different possibilities of tournament results. Let $\mathcal T_0$ be the set of all tournaments where the first team (node $0$ in the graph) is the only team that wins all games. Randomly generate $10^7$ such tournaments with $N=40$, $d=5$, and plot the distribution of the rank of the first team.

Note: For $N=10$ and $d = 3$ we constructed an example where exactly one team wins all matches, but is ranked in the bottom half. This question studies how typical this ranking is. For $N=10$, $d = 3$, you can brute force for loop compute all such tournaments and check exactly. For $N = 40$, $d = 5$, you have roughly $2^{100} \approx 10^{30}$ such tournaments and brute force for loop wont work anymore. We can, however, generate a tractable number of “randomly selected” tournaments outcomes, and check the rank distribution amongst these tournaments, which is what this question asks of you.

We will later revisit this question and address it with a little more care. Explicitly, we need to ensure the random selection of tournament outcomes is not “biased”. That is, we need to ensure our random selection algorithm guarantees any tournament in $T_0$ has an equal chance of being selected. In general this is hard to do in a manner that is computationally tractable. It’s interesting to think about how you may go about doing this now; we will later study general algorithms that can be used in this situation.

Optional question 9

Suppose you want to limit the spread of a disease in a group of people. One strategy is to choose an individual uniformly at random, and vaccinate them. Another strategy is to choose an individual uniformly at random, then choose one of their friends uniformly at random and vaccinate them. It turns out the second strategy is better (on average), as we see below. You can also view this as limiting the spread of news, where instead of vaccinating people you buy their support / silence.

Let $G = (V, E)$ be a graph representing the interaction between individuals.

Choose a point $x \in V$ uniformly at random, and remove $x$ and all edges connected to $x$ from $G$. What is the expected number of edges removed?
Choose a point $x \in V$ uniformly at random, then choose $y \in N(x)$ uniformly at random. Remove $y$ and all edges connected to $y$ from $G$. What is the expected number of edges removed?

For Erdös Renyi graphs, Jensen’s inequality shows that the expected number of edges removed in the second case is larger than that in the first case.