Markov Chains and Recurrence

Consider a one-dimensional simple symmetric random walk: \(S_n=x+\sum _{k=1}^{n}X_k\), where \(x\) is where the walk starts and \(\{X_n:n\geq 1\}\) are i.i.d. with \[ \mathbb {P}(X_n=1)=\mathbb {P}(X_n=-1)=1/2. \]

1. Compute the probability that starting at \(x=0\) the random walk will hit \(-1\) before it hits \(b\in \mathbb {N}\). Deduce from this that the random walk is recurrent, i.e. starting at 0 the random walk will return to 0 with probability 1.
2. Compute the mean time it takes the random walk to go from \(x=0\) to \(-1\). Deduce from this that the random walk is null recurrent, i.e. starting at 0, the mean time it takes to return to 0 is infinite.

(Hint: Prove first that when \(x=0\) both \(S_n\) and \(S_n^2-n\) are martingales.)

Let \(P\) be the transition matrix for a finite irreducible aperiodic Markov chain, and assume that \(P\) is doubly stochastic (row and column sums are 1). Find the limit \(\lim _{n\to \infty }P_{ij}^n\) for all \(i\) and \(j\), and provide justification.

Consider the Markov chain in the set of nonnegative integers with transitions \(P(n,0)=1-P(n,n+1)=p_n>0\) for each \(n\ge 0\). Give necessary and sufficient conditions on the sequence \(\{p_n\}\) for the chain to be (a) positive recurrent, (b) null recurrent, and (c) transient.

Consider the Markov chain in the state space \(S=\{\ldots ,-2,-1,0,1,2,\ldots \}\) with transitions \(P(i,i+2)=p\) and \(P(i,i-1)=1-p\), where \(0<p<1\). Determine for which \(p\) this chain is recurrent and for which \(p\) it is transient.

Consider the Markov chain in the state space \(S=\{\ldots ,-2,-1,0,1,2,\ldots \}\) with transitions \(P(i,i+2)=p\) and \(P(i,i-1)=1-p\), where \(0<p<1\). Determine for which \(p\) this chain is recurrent and for which \(p\) it is transient.

A thinker who owns \(r\) umbrellas travels back and forth between home and office, taking along an umbrella (if there is one at hand) in rain (probability \(p\)) but not otherwise (probability \(q=1-p\)). Let the state be the number of umbrellas at hand, irrespective of whether the thinker is at home or at work. Set up the transition matrix, and show that the Markov chain approaches equilibrium (i.e., the ergodic theorem is applicable). Find the steady-state probability of his getting wet, and show that five umbrellas will protect him at the \(5\%\) level against any climate (any \(p\)).

A thinker who owns \(r\) umbrellas travels back and forth between home and office, taking along an umbrella (if there is one at hand) in rain (probability \(p\)) but not otherwise (probability \(q=1-p\)). Let the state be the number of umbrellas at hand, irrespective of whether the thinker is at home or at work. Set up the transition matrix, and show that the Markov chain approaches equilibrium (i.e., the ergodic theorem is applicable). Find the steady-state probability of his getting wet, and show that five umbrellas will protect him at the \(5\%\) level against any climate (any \(p\)).