1

enter image description here

I only have problem about (b).

My efforts:

Consider the special case in which all transition probabilities are 1. Then the first return probabilities are $f^n_{jj}=1$ when $n=r$ and $f^n_{jj}=0$ when $n\neq r$. Since the problem requires $n>r$, any $\alpha$ works for this case. $$\begin{bmatrix}0&1&0&0 \\\\ 0&0&1&0 \\\\ 0&0&0&1 \\\\ 1&0&0&0\end{bmatrix}$$

Next consider the case in which not every transition probability is 1. Then at least one of them is less than 1. If that less-than-1 probability is only on row $j$ of the transition matrix, then the result is similar to the all-1 case and any $\alpha$ works. $$\begin{bmatrix}p_j&q_j&0&0 \\\\ 0&0&1&0 \\\\ 0&0&0&1 \\\\ 1&0&0&0\end{bmatrix}$$

Since the problem requires $n>r$, the state must not be in $j$ for $n\leq r$. Suppose the state is in $i$ when $n=r$. Then we have $0<p^r_{ji}<1$. If no $p_{ik}$ is one, then we can simply take $\alpha$ to be the largest of these $p_{ik}$ and the $r$th root of $p^r_{ji}$. But if there is one, I don't know what to do. Since the 1 increases the number of transitions and also the desired $\alpha$.

Junk Warrior
  • 346

1 Answers1

0

Let $f^k_{jj}$ be the first time return probability in $k$ steps. Since $j$ is recurrent, $\sum^\infty_{k=1}f^k_{jj}=1$.

Let $p_n$ = Pr(return after $n$). We have the following relationships of events:

{return after $n+1$} $\subset$ {return after $n$}

{return after $n$} = {return at $n+1$} $\cup$ {return after $n+1$}

Let $a_n=\sum^n_{k=1}f^k_{jj}$.

Pr(return after $n+1$)

= Pr(return after $n+1$|after $n$)Pr(after $n$) \begin{equation} =\frac{\sum_{k>n+1}f^k_{jj}}{\sum_{k>n}f^k_{jj}}p_n =\frac{1-\sum_{k=1}{n+1}f^k_{jj}}{1-\sum^n_{k=1}f^k_{jj}}p_n =\frac{1-a_{n+1}}{1-a_n}p_n=\frac{1-a_n-f^{k+1}_{jj}}{1-a_n}p_n =(1-\frac{f^{k+1}_{jj}}{1-a_n})p_n \end{equation}

Let $\alpha$ = max{sup$_{n>r}(1-\frac{f^{k+1}_{jj}}{1-a_n}),\sqrt[r]{p_r}$}.

Junk Warrior
  • 346