Exponentials of stochastic band matrices

Question

Edit: I should probably say the motivation: I was interested in modeling the probability of winning a heads-up poker match if the players will play until one player goes bust. Because the game is zero sum (given that either player is the big blind with equal probability), the assumptions given in my answer show that the probability of winning is indeed just proportional to stack size.

---

This may be a duplicate, but I've done some searching and I can't find exactly this problem setting, probably due to not knowing the right terminology for how to refer to the transition matrix.

I'm considering absorbing random walks $\{X_t\}$ which have symmetric transition probabilities inside a window of size $k$. For example, on $\{0, 1, 2, \dots, 100\}$, with $k=3$ if $X_t = 5$ \begin{align*} P[X_{t+1} = 4] &= P[X_{t+1} = 6]\\ P[X_{t+1} = 3] &= P[X_{t+1} = 7]\\ P[X_{t+1} = 2] &= P[X_{t+1} = 8]\\ \end{align*}

When the walk is within $k$ of the endpoint, the allowable transitions are truncated on both sides, e.g. if $X_t = 1$, $P[X_t = 3] = 0$.

I wanted to figure out the probability of the walk being absorbed at the upper endpoint, so I did some numerical experiments with walks on the integers from 0-100. I calculated $T^n$ for the transition matrix $T$ and a large $n$. I then looked at $(T^n)_{i, 100}$ to see the probability of being absorbed at 100. It appears that the value is always equal to $i/100$, regardless of how I set the transition distribution or window-size.

The transition matrix for a walk on the integers in $[0, N]$ has the following properties (Edit: This list is missing an important assumption so the conjecture is not true):

1. $T$ is (row) stochastic
2. $T$ is a band matrix with upper and lower band size $k$
3. $T_{i, j} = 0$ if $|i - j| > \max (i, N - i)$
4. $T_{i,i + r} = T_{i, i - r}$ (this is the main property I don't know the name of)
5. $T_{0, 0} = T_{1, 1} = 1$

I would like a proof or counterexample of the following statement: \begin{equation*} \lim\limits_{n \to \infty} (T^n)_{i, N} = i/N \end{equation*}

If the statement above is true, is it still true if the transition distributions are no longer left-right symmetric, but it's still the case that $E[X_{t + 1}] = X_t$?

Answer 1

As soon as I got around to posting my initial solution, I thought of a solution which only relies on elementary probability, so I think the linear algebra point of view isn't very helpful for this problem.

Two assumptions:

1. $0$ and $N$ are absorbing states and all other states are transient
2. $E[X_t] = X_{t-1}$

Using assumption 2: \begin{align*} \lim\limits_{t\to\infty} E[X_t | X_0 = i] &= X_0 + \sum\limits_{t=0}^\infty E[X_t - X_{t - 1} | X_0 = i]\\ &= i\\ \end{align*}

Define $A = \lim\limits_{t \to \infty} X_t$. If you exchange the limit and expectation above (which I think it's easy to show you can), this shows that $E[A | X_0 = i] = i$.

But since $A \in \{0, N\}$ by assumption 1, this implies \begin{align*} E[ A | X_0 = i] &= N P(A = N | X_0 = i)\\ i &= N P(A = N | X_0 = i)\\ \frac{i}{N} &= P(A = N | X_0 = i)\\ \end{align*}

Answer 2

I ended up finding a pretty unsatisfying solution, I'm sure there some relevant theorems which make this trivial but I was unable to find them. If you know the right way to do this, please post an answer!

I failed to specify in the question that I was assuming that every off-diagonal element in the band is non-zero, which is really important because the identity matrix satisfies the conditions given above.

It turns out that you can prove this statement given two much weaker conditions. If:

1. Every state other than $0$ and $N$ is transient
2. $E[X_t | X_{t-1} = i] = i$

Then: \begin{align*} \lim\limits_{t \to \infty} (T^t)_{i, 0} &= \frac{N - i}{N}\\ \lim\limits_{t \to \infty} (T^t)_{i, N} &= \frac{i}{N}\\ \end{align*}

Let $V = \lim\limits_{n \to \infty} T^n$

Here's an outline of my (overly complicated) argument:

1. $V$ exists and has a two-dimensional eigenspace with eigenvalue 1
2. The two limiting values stated above give two eigenvectors of $T$ with eigenvalue 1
3. These are also eigenvectors of $V$ (and therefore span the eigenspace)
4. The columns of $V$ are exactly equal to those values (rather than being some linear combination of them)

My attempt

1. $V$ exists and has a two-dimensional eigenspace with eigenvalue 1

From the definition of $V$: \begin{align*} V_{ij} &= \lim\limits_{t \to\infty} \left(T^t\right)_{ij}\\ &= \lim\limits_{t \to \infty} P[X_t = j | X_0 = i] \end{align*}

For $j=0$ and $j=N$, the quantities in the limit above are all increasing because the state is absorbing, and are bounded above by 1, so the limits exist. For all other columns, the relevant state is transient and so the limits are zero. The only non-zero columns of $V$ are then the zeroth and $N$th columns.

Since $0$ and $N$ are absorbing states, $V_{0, 0} = V_{N, N} = 1$ and $V_{0, N} = V_{N, 0} = 0$. $V$ is therefore rank 2, as it has two linearly independent non-zero columns. This means that the dimension of the eigenspace associated with $\lambda = 1$ is at most 2.

2. The conjectured values make up an eigenvector of $V$

Any eigenvector, $\mathbf{w}$, of $T$ with eigenvalue 1 is also an eigenvector of $V$ with eigenvalue 1: \begin{align*} V\mathbf{w} &= \left(\lim\limits_{t \to \infty} T^t \right) \mathbf{w} \\ &= \left(\lim\limits_{t \to \infty} T^{t - 1} \right)T \mathbf{w} \\ &= V\mathbf{w}\\ \end{align*}

The martingale assumption implies that $\mathbf{b} = [0, 1/N, 2/N, \dots, 1]$ is an eigenvector of $T$ (and therefore of $V$ as well): \begin{align*} (T\mathbf{b})_i &= \sum\limits_{j=0}^N P[X_t = j | X_{t-1} = i]\frac{j}{N}\\ &= \frac{1}{N} E[X_t | X_{t-1} = i]\\ &= \frac{i}{N} = b_i \end{align*}

Similarly, $\mathbf{a} = [1, (N-1)/N, \dots, 0]$ is an eigenvector which is linearly independent of $\mathbf{b}$, so these eigenvectors span the eigenspace which was shown to be of dimension at most 2.

3/4. $\mathbf{a}$ and $\mathbf{b}$ are the non-zero columns of $V$

All the columns of $V$ must be eigenvectors of $T$ because $TV = V$, and so the N-th column of $V$, $V_N$, satisfies: \begin{equation*} V_N = \alpha \mathbf{a} + \beta \mathbf{b} \end{equation*} for some $\alpha$ and $\beta$.

$V_{0,N} = 0$ and $V_{N, N} = 1$, so $\alpha = 0$ and $\beta = 1$.

Therefore $p_i = V_{i, N} = \frac{i}{N}$, and a similar argument shows $V_{i, 0} = \frac{N - i}{N}$.