A renewal theorem question

Solution 1:

I'm not sure how to apply the renewal theorem to solve this problem (I tried), but you can certainly solve it using a recurrence relation.

Take $A_m$ as the event that $X_1+\dots+X_n=m$ for some $n\geq 1$. Conditioning on $X_1$ yields $$\begin{eqnarray*}r_1 &=& \mathbb{P}(A_1) \\ &=& \frac{1}{4}\mathbb{P}(A_1|X_1=0)+\frac{1}{2}\mathbb{P}(A_1|X_1=1)+\frac{1}{4}\mathbb{P}(A_1|X_1=2) \\ &=& \frac{1}{4}\mathbb{P}(A_1)+ \frac{1}{2} \cdot 1 + \frac{1}{4}\cdot 0 \\&=& \frac{r_1}{4}+\frac{1}{2}\end{eqnarray*}$$ Solving for $r_1$ yields $r_1=\frac{2}{3}$. Similarly, $$\begin{eqnarray*}r_2 &=& \mathbb{P}(A_2) \\ &=& \frac{1}{4}\mathbb{P}(A_2|X_1=0)+\frac{1}{2}\mathbb{P}(A_2|X_1=1)+\frac{1}{4}\mathbb{P}(A_2|X_1=2) \\&=& \frac{1}{4}\mathbb{P}(A_2)+\frac{1}{2}\mathbb{P}(A_1)+\frac{1}{4}\cdot 1 \\ &=& \frac{r_2}{4}+\frac{r_1}{2}+\frac{1}{4}\end{eqnarray*}$$ Solve for $r_2$ and get $r_2=\frac{7}{9}$. Since $\mathbb{P}(A_m|X_1=j)=r_{m-j}$ for $m\geq 3$ and $j\in \{0,1,2\}$ we get $$\begin{eqnarray*}r_m&=& \mathbb{P}(A_m) \\ &=& \frac{1}{4}\mathbb{P}(A_m|X_1=0)+\frac{1}{2}\mathbb{P}(A_m|X_1=1)+\frac{1}{4}\mathbb{P}(A_m|X_1=2) \\ &=& \frac{r_m}{4}+\frac{r_{m-1}}{2}+\frac{r_{m-2}}{4}\end{eqnarray*}$$ This unveils the recurrence relation $$r_m=\frac{2}{3}r_{m-1}+\frac{1}{3}r_{m-2};r_1=\frac{2}{3},r_2=\frac{7}{9}$$ which has unique solution $$r_m=\frac{1}{4}\left(-\frac{1}{3}\right)^m+\frac{3}{4}$$ Taking $m\mapsto +\infty$ gives a limit of $\frac{3}{4}$. I would be very interested to see an approach using a renewal theorem.