I currently have a probability class tutorial question that I have no idea where to begin. At first instinct, I thought it may have been a CTMC question or branching question, but now I have no idea, any help would be greatly appreciated!
Question:
A node goes down $1$ step with probability $p$ and up $t$ steps with probability $1-p$.
Let $X_n=Y_1+\ldots +Y_n$ where $(Y_n)$ is i.i.d with $P(Y_1 = -1) = p$ and $P(Y_1 = t ) = 1-p$.
Assuming that at $n=0$ the node is at $0$,
a) find $P(X_n = 0)$.
b) find a simple sequence $(u(n))$ such that $P(X_{(t+1)n} = 0) \sim u(n)$.
I know that if $p=0$ or $p=1$ then the answer to a) is 0. I have trouble with the case $0<p<1$. I've also worked out that if the node takes $t$ steps up, then it must take $t$ steps back as well to get to the initial point. And I am not sure as well, but I think we can use the $\phi (u)$ formula.
That $X_n=0$ means that there was $i$ steps $+t$ and $n-i$ steps $-1$ with $+t\cdot i-1\cdot(n-i)=0$, that is, $i=n/(t+1)$. Hence $P[X_n=0]=0$ if $n$ is not a multiple of $t+1$ and, for every $n\geqslant0$, $$ P[X_{(t+1)n}=0]={(t+1)n\choose n}(1-p)^np^{tn}. $$ Stirling's formula yields that, when $n\to\infty$, $$ P[X_{(t+1)n}=0]\sim\frac{c}{\sqrt{n}}\vartheta^n, $$ with $$ c=\sqrt{2\pi}\sqrt{\frac{t+1}t},\qquad \vartheta=(t+1)^{t+1}t^{-t}(1-p)p^t. $$ Note that $\vartheta=1$ if $p=t/(t+1)$ (this is the zero drift case) and $\vartheta\lt1$ otherwise.