Confusion regarding transition function and initial distribution (Markov chains)

Question

I was learning about Markov chains from my lecturer's handwritten notes, but I got stuck at "transition functions". It will be a quite a while until I get to ask the lecturer about what he meant. So it would help me a lot if someone could clarify my confusion meanwhile. I'm trying to summarize what I read:

Some systems have the property that given the present state, the past states have no influence on the future. This is called Markov property.

$$P(x_{n} = x_{n+1}|x_0=x_0,x_1=x_0,...,x_n=x_n) = P(x_{n+1}=x_{n+1}|x_n=x_n)$$ for every choice of the non-negative integer $n$.

If $$P(x_{n+1} = y|x_n = x)$$ then transition probability is independent of $n$. Then it is of stationary transition probability.

A Markov Chain is a discrete parameter (time) state space stochastic process satisfying Markov property. We are interested in stationary transition probability.

Okay, so far so good. But now comes the confusing part:

Transition function and initial distribution:

Let $x_{n}$, $n\geq 0$ be a Markov Chain having state "sp" $F$

Then the function $P(x,y)$ is defined by $P(x,y)=P(x_{1}=y|x_{0}=x)$; $x,y\in F$.

This is called the transition function of the chain.

$$P(x,y) \geq 0 \ \forall x,y \in F$$

$$\sum_{y}P(x,y) = 1 \ \forall x\in F$$

Since the Markov chain has stationary probability we see that

$$P(x_{n+1} = y|x_{n}=x) = P(x,y)$$

$$P(x_{n+1} = y|x_0 = x_0, x_1 = x_1, ..., x_n = x) = P(x,y)$$

This is a one-step transition probability.

$$\pi_0(x) = P(x_0 = x)$$ (where $x\in F$)

$$\pi_0(x) \geq 0$$

$$\sum_{x}\pi_0(x) = 1$$

Questions:

1. In the first line, I'm not sure what "sp" stands for (the handwriting was not clear for that portion). Moreover, what does $F$ stand for?

2. Why is $\sum_{y}P(x,y) = 1 \ \forall \ x \in F$ ?

3. What do they mean by "stationary probability" in this context? Why is $P(x_{n+1} = y|x_{n}=x) = P(x,y)$?

Answer 1

1. "State space $F$"
2. That's an assumption. It's (part of) the definition of a transition kernel.
3. I don't particularly like this use of stationary, but it appears your lecturer means the chain is time homogeneous. This simply means the transition kernel doesn't depend on time, or $\mathbb{P}\{X_{n + 1} = x \, \mid \, X_{n} = y\} = \mathbb{P}\{X_{1} = x \, \mid \, X_{0} = y\}$ independently of $n$.

Does your course have a textbook? If not, you might consider Googling the book "Markov Chains and Mixing Times" by Levin, Peres, and Wilmer. It (or rather the first edition) is available freely on Yuval Peres's website. Chapter 1 is a good place to start if you're just learning Markov chains for the first time.