Markov processes

Show that any sequence of independent random variables taking values in the countable set $S$ is a Markov chain. Under what condition is this chain homogeneous?

A die is rolled repeatedly. Which of the following are Markov chains? For those that are, supply the transition matrix.

Let $\left\{ S_{n}: n \geq 0\right\}$ be a simple random walk with $S_{0} = 0$, and show that $X_{n} = \left|S_{n}\right|$ defines a Markov chain; find the transition probabilities of this chain. Let $M_{n} = \max \left\{ S_{k}: 0 \leq k \leq n\right\}$, and show that $Y_{n} = M_{n}-S_{n}$ defines a Markov chain. What happens if $S_{0} \neq 0$?

Let $X$ be a Markov chain and let $\left\{ n_{r}: r \geq 0\right\}$ be an unbounded increasing sequence of positive integers. Show that $Y_{r} = X_{n_{r}}$ constitutes a (possibly non-homogeneous) Markov chain. Find the transition matrix of $Y$ when $n_{r} = 2 r$ and $X$ is:

Let $X$ be a Markov chain on $S$, and let $I: S^{n} \rightarrow \left\{ 0,1\right\}$. Show that the distribution of $X_{n}, X_{n+1}, \ldots$, conditional on $\left\{ I\left(X_{1}, \ldots , X_{n}\right) = 1\right\} \cap \left\{ X_{n} = i\right\}$, is identical to the distribution of $X_{n}, X_{n+1}, \ldots$ conditional on $\left\{ X_{n} = i\right\}$.

Let $X$ be a Markov chain on $S$, and let $T$ be a random variable taking values in $\left\{ 0,1,2, \ldots \right\}$ with the property that the indicator function $I_{\left\{ T = n\right\} }$, of the event that $T = n$, is a function of the variables $X_{1}, X_{2}, \ldots , X_{n}$. Such a random variable $T$ is called a stopping time, and the above definition requires that it is decidable whether or not $T = n$ with a knowledge only of the past and present, $X_{0}, X_{1}, \ldots , X_{n}$, and with no further information about the future.

Show that

for $m \geq 0, i, j \in S$, and all sequences $\left(x_{k}\right)$ of states.

Let $X$ be a Markov chain with state space $S$, and suppose that $h: S \rightarrow T$ is one-one. Show that $Y_{n} = h\left(X_{n}\right)$ defines a Markov chain on $T$. Must this be so if $h$ is not one-one?

Let $X$ and $Y$ be Markov chains on the set $\mathbb {Z}$ of integers.

Let $X$ be a Markov chain. Which of the following are Markov chains?

Let $X$ be a Markov chain. Show that, for $1 < r < n$,

Let $\left\{ X_{n}: n \geq 1\right\}$ be independent identically distributed integer-valued random variables. Let $S_{n} = \sum_{r = 1}^{n} X_{r}$, with $S_{0} = 0, Y_{n} = X_{n}+X_{n-1}$ with $X_{0} = 0$, and $Z_{n} = \sum_{r = 0}^{n} S_{r}$. Which of the following constitute Markov chains:

A stochastic matrix $\mathbf{P}$ is called doubly stochastic if $\sum_{i} p_{i j} = 1$ for all $j$. It is called sub-stochastic if $\sum_{i} p_{i j} \leq 1$ for all $j$. Show that, if $\mathbf{P}$ is stochastic (respectively, doubly stochastic, sub-stochastic), then $\mathbf{P}^{n}$ is stochastic (respectively, doubly stochastic, sub-stochastic) for all $n$.

Let $X$ be a Markov chain on the finite state space $S$ with transition matrix $\mathbf{P}$, and let $\mathcal{C} = \left\{ C_{j}: j \in J\right\}$ be a partition of $S$. Let $Y_{n} = j$ if $X_{n} \in C_{j}$. The chain $X$ is called $\mathcal{C}$-lumpable if $Y$ is a Markov chain.

Show that $X$ is $\mathcal{C}$-lumpable if and only if, for $a, b \in J, \mathbb {P}\left(X_{n+1} \in C_{b} \mid X_{n} = i\right)$ is constant for $i \in C_{a}$.