-1

Let $\{X_n\}_{n=0}^{\infty}$ be a Discrete Time Markov Chain (DTMC) with finite state space $X$. For any state $y \in X$ we define $Ty := \inf\{n \ge 1 \mid X_n = y\}$.

Let $p(n)(x, y)$ denote the $n$-step transition probability of going from state $x$ to $y$. For $n \ge $1, let $$f(n)(x, y) := P r(Ty = n\mid X_0 = x).$$ Prove that for all $n \ge 1$ and all $x, y \in X$, $p(n)(x, y) = $$\sum_{k=0}^n f(k) (x, y)p(nāˆ’k) (y, y)$

I don't understand how to start with the proof.

ViktorStein
  • 4,838
Laila
  • 3
  • 2

1 Answers1

0

We have:

$p(n)(x,y)=P(X_n=y|X_0=x)$

So if $X_n=y$ this means that the first time that $X$ hits $y$ shall be before $n$. Told another way $Ty|_{X_0=x} \le n$. Worst case scenario, it hits $y$ after $n$ steps.

We can than split (law of total probability) using the partition $\{Ty=k\}$:

$P(X_n=y|X_0=x)=\sum_{k=0}^nP(X_n=y|X_0=x,Ty=k)P(Ty=k|X_0=x)$

Than we recognize:

$P(Ty=k|X_0=x)=f(k)(x,y)$

and:

$P(X_n=y|X_0=x,Ty=k)=P(X_n=y|X_k=y)=p(n-k)(y,y)$

Thomas
  • 4,029