1

Space $=S=\{0,1,2,\cdots\}$
Transition probabilities $P(n,n+1)=p, P(n,0)=1-p$
$T_n$ is the first time the Random Variable returns to $n$

I want to show that $P_n(T_n<\infty)=P(T_n<\infty|X_0=n)=1\,\,\forall n\in\mathbb N$

I was able to show $P_0(T_n<\infty)=P_n(T_0<\infty)=1\,\,\forall n\in\mathbb N$

I wanted to combine the two somehow to show the result I require. Any hints?

I heuristically know the two statements I have already proved imply the condition I want to prove, but I was looking for a mathematical solution

Anvit
  • 3,379
  • You didn't introduce $T_n$. – joriki Feb 07 '20 at 13:51
  • Sorry, I thought it was Standard notation, I'll add it – Anvit Feb 07 '20 at 13:52
  • Hmm -- then apparently I don't understand what $P_0$ and $P_n$ are. I thought they were the probability distribution after $0$ and $n$ steps, respectively, but that doesn't seem to make sense now. – joriki Feb 07 '20 at 13:56
  • $P_0$ is the probability when you have $X_0=0$ given. $P_n$ is $X_0=n$ given – Anvit Feb 07 '20 at 13:57
  • Ah, OK. That would have been clearer if you'd used $:=$ instead of $=$ between that and what it's defined to be. – joriki Feb 07 '20 at 14:00
  • you may as well prove (1) that you have a single communicating class, and (2) recurrence or transience is an equivalence relation for states in the same communicating class. There are many ways at this -- a common one is that iff you return to a state WP1 then the expected number of renewals (returns to starting state) tends to $\infty$-- but if a single state in the class is transient then you can bound the expected number of renewals by expected value of some geometric r.v. N.b. your chain is called an "Age" chain associated with renewal processes. – user8675309 Feb 07 '20 at 20:57

1 Answers1

1

The standard method to compute the probability of reaching some state is to write done a system of linear equation. Fix $n$ and for any $k \in \{0,1,2 \ldots \}$ write $h_k = \mathbb{P}_k (T_n < \infty)$. Markov property allows you write the following for any $k \in \{0,1,2 \ldots \}$

$$ h_k = (1-p)h_{0} + p h_{k+1}.$$

Now if you already proved that $h_0 = 1$ (as you claim you have), taking $k=0$ in the equation above gives you $h_1 = 1$. By induction you get that $h_n = 1$ as well, i.e. the result you were looking for.

Morgan
  • 56