Generator matrix, transition semigroup and Kolmogorov equations of a finite chain

[14/86%]

Show

LaTeX

Show LaTeX

Problem 15.3 from Athreya K.B., Lahiri S.N. "Measure Theory and Probability Theory" [AtLa06]More problems in Chapter 15 "Stochastic Processes"

Solve the Kolmogorov's forward and backward equations for the following special cases of birth and death processes:

(a)

Poisson process: $\alpha_{i} \equiv \alpha , \beta_{i} \equiv 0$ ,

(b)

Yule process: $\alpha_{i} \equiv i \alpha , \beta_{i} \equiv 0$ ,

(c)

On-off process: $\alpha_{0} = \alpha , \alpha_{i} = 0, i \geq 1$ ,

\beta _{1} = \beta , \beta _{i} = 0, i = 0,2, \ldots ,

(d)

$M / M / 1$ queue: $\alpha_{i} = \alpha , i \geq 0, \beta_{i} = \beta , i \geq 1, \beta_{0} = 0$ ,

(e)

$M / M / s$ queue: $\alpha_{i} = \alpha , i \geq 0, \beta_{i} = i \beta , 1 \leq i \leq s$ and $= s \beta$ , $i > s$ ,

\beta _{0} = 0,

(f)

Pure death process: $\beta_{i} \equiv \beta , i \geq 1, \beta_{0} = 0, \alpha_{i} = 0, i \geq 0$ .

Problem 7.10 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 7 "Markov processes with countable-state spaces"

(a)(b)

(a)

Consider the two-state Markov process of Example 7.3.1 with $q_{01} = \lambda$ and $q_{10} = \mu$ . Find the eigenvalues and eigenvectors of the transition rate matrix $\mathbf{Q}$ .

(b)

If $\mathbf{Q}$ has $\mathsf{M}$ distinct eigenvalues, the differential equation $d[P(t)]/dt = [Q][P(t)]$ can be solved by the equation

[P(t)] = \sum _{i=1}^{\mathsf{M}}\overrightarrow {\nu }_{i}e^{t\lambda _{i}}\overrightarrow {p}_{i}^{\mathsf{T}},

where $\overrightarrow {p}_{i}$ and $\overrightarrow {\nu }_{i}$ are the left and right eigenvectors of eigenvalue $\lambda_{i}$ . Show that this equation gives the same solution as that given for Example 7.3.1.

Problem 6.10.1 from Grimmett G.R., Stirzaker D.R. "Probability and Random Processes" [GrSt20]More problems in Section 6.10 "Kolmogorov equations and the limit theorem"

(a)(b)(c)

Let $N < \infty$ , and let $\mathcal{Q}$ be the space of $N \times N$ matrices with real entries, with norm

|Q| = \sup _{\mathbf{x} \neq \mathbf{0}} \frac{|Q \mathbf{x}|}{|\mathbf{x}|}, \quad Q \in \mathcal{Q}

where $\left|\mathbf{y}\right|$ is the Euclidean norm of the vector $\mathbf{y}$ , and the supremum is over all non-zero column vectors.

(a)

Show for $Q_{1}, Q_{2} \in \mathcal{Q}$ that

\left|Q_{1}+Q_{2}\right| \leq \left|Q_{1}\right|+\left|Q_{2}\right|, \quad \left|Q_{1} Q_{2}\right| \leq \left|Q_{1}\right| \cdot \left|Q_{2}\right|

(b)

Show for $Q \in \mathcal{Q}$ that $E_{n} := \sum_{k = 0}^{n} Q^{k} / k!$ converges with respect to $\left|\cdot \right|$ to a limit which we denote $E = E(Q)$ .

(c)

Show that $E(Q_{1}+Q_{2}) = E(Q_{1}) E(Q_{2})$ if $Q_{1}$ and $Q_{2}$ are commuting elements of $\mathcal{Q}$ .

Problem 6.10.5 from Grimmett G.R., Stirzaker D.R. "Probability and Random Processes" [GrSt20]More problems in Section 6.10 "Kolmogorov equations and the limit theorem"

Let $X = \left(X_{t}: t \geq 0\right)$ be a Markov chain with generator $\mathbf{G} = \left(g_{i j}\right)$ on the finite state space $S$ , and let $f: S \rightarrow \mathbb {R}$ be a function, which we identify with the vector $f = (f(i): i \in S)$ . Show that

\mathbf{G} f(i) = \sum _{j \in S} g_{i j}(f(j)-f(i))

where $\mathbf{G} f$ denotes the standard matrix multiplication. Show that

\mathbf{G} f(i) = \lim _{t \rightarrow 0} \frac{1}{t}\left[\mathbb {E}_{i}\left[f\left(X_{t}\right)\right]-f(i)\right], \quad i \in S

and deduce that

\mathbb {E}_{i}\left[f\left(X_{t}\right)\right] = f(i)+\int _{0}^{t} \mathbb {E}_{i}\left[\mathbf{G} f\left(X_{s}\right)\right] d s

Problem 6.15.17 from Grimmett G.R., Stirzaker D.R. "Probability and Random Processes" [GrSt20]More problems in Section 6.15 "Problems"

Show that not every discrete-time Markov chain can be imbedded in a continuous-time chain. More precisely, let

\mathbf{P} =\left[\begin{smallmatrix} \alpha & 1-\alpha \\ 1-\alpha & \alpha \end{smallmatrix}\right] \quad \text{ for some } 0 < \alpha < 1

be a transition matrix. Show that there exists a semigroup $\left\{ \mathbf{P}_{t}\right\}$ of transition probabilities in continuous time such that $\mathbf{P}_{1} = \mathbf{P}$ , if and only if $\frac{1}{2} < \alpha < 1$ . In this case show that $\left\{ \mathbf{P}_{t}\right\}$ is unique and calculate it in terms of $\alpha$ .

Problem 6.9.1 from Grimmett G.R., Stirzaker D.R. "Probability and Random Processes" [GrSt20]More problems in Section 6.9 "Continuous-time Markov chains"

(a)(b)(c)

Let $\lambda \mu > 0$ and let $X$ be a Markov chain on $\left\{ 1,2\right\}$ with generator

\mathbf{G} =\left[\begin{smallmatrix} -\mu & \mu \\ \lambda & -\lambda \end{smallmatrix}\right]

(a)

Write down the forward equations and solve them for the transition probabilities $p_{i j}(t), i, j =$ 1,2.

(b)

Calculate $\mathbf{G}^{n}$ and hence find $\sum_{n = 0}^{\infty }\left(t^{n} / n!\right) \mathbf{G}^{n}$ . Compare your answer with that to part (a).

(c)

Solve the equation $\pi \mathbf{G} = \mathbf{0}$ in order to find the stationary distribution. Verify that $p_{i j}(t) \rightarrow \pi_{j}$ as $t \rightarrow \infty$ .

Problem 6.9.2 from Grimmett G.R., Stirzaker D.R. "Probability and Random Processes" [GrSt20]More problems in Section 6.9 "Continuous-time Markov chains"

(a)(b)

As a continuation of the previous exercise, find:

(a)

$\mathbb {P}\left(X(t) = 2 \mid X(0) = 1, X(3 t) = 1\right)$ ,

(b)

$\mathbb {P}\left(X(t) = 2 \mid X(0) = 1, X(3 t) = 1, X(4 t) = 1\right)$ .

Problem 6.9.11 from Grimmett G.R., Stirzaker D.R. "Probability and Random Processes" [GrSt20]More problems in Section 6.9 "Continuous-time Markov chains"

Let $X$ be the continuous-time Markov chain on the finite state space $S$ with generator $\mathbf{G} = \left(g_{i j}\right)$ . Show from first principles that the transition probabilities satisfy

p_{i j}(h) = \begin{cases} 1+g_{i i} h+\mathrm{o}(h) & \text{ if } i = j \\ g_{i j} h+\mathrm{o}(h) & \text{ if } i \neq j\end{cases}

Problem 36.3 from Коршунов Д.А., Фосс С.Г. "Сборник задач и упражнений по теории вероятностей" [КоФо03]More problems in Section 36 "Jump Markov Processes"

Prove that, in the differentiable case, the transition probabilities of a homogeneous jump Markov process with finitely many states satisfy the forward Kolmogorov equations

p'_{ij}(t) = \sum _{k} p_{ik}(t)q_{kj},

as well as the backward Kolmogorov equations

p'_{ij}(t) = \sum _{k} q_{ik}p_{kj}(t).

Problem 36.4 from Коршунов Д.А., Фосс С.Г. "Сборник задач и упражнений по теории вероятностей" [КоФо03]More problems in Section 36 "Jump Markov Processes"

Let a homogeneous jump Markov process have two states 0 and 1, where, say, 0 means that some subject is healthy, and 1 that they are ill. Find the transition probabilities, if the transition intensity matrix equals

Q = \begin{pmatrix} -\lambda & \lambda \\ \mu & -\mu \end{pmatrix}

for some $\lambda , \mu > 0$ . Find the limit of the transition probabilities $p_{ij}(t)$ as $t \to \infty$ .

Problem 36.10 from Коршунов Д.А., Фосс С.Г. "Сборник задач и упражнений по теории вероятностей" [КоФо03]More problems in Section 36 "Jump Markov Processes"

Some particle moves among three states as a homogeneous jump Markov process with transition intensity matrix

Q = \begin{pmatrix} -2\lambda & \lambda & \lambda \\ \lambda & -2\lambda & \lambda \\ \lambda & \lambda & -2\lambda \end{pmatrix}.

Find the transition probabilities over time $t$ and their limits as $t \to \infty$ .

Problem 3.9.3 from Жуковский М.Е., Родионов И.В., Шабанов Д.А. "Основы теории случайных процессов" [ЖРШ16]More problems in Chapter 3.9 "Continuous-Time Markov Chains"

Let the $n \times n$ matrix $Q=\left(q_{i j}\right)_{i, j=1}^{n}$ be such that $q_{i j} \geqslant 0$ for $i \neq j$ and $\sum_{j=1}^{n} q_{i j}=0$ for every $i=1, \ldots , n$ . Prove that then the matrices

P(t) = e^{tQ} := I_n + tQ + \frac{t^2}{2!}Q^2 + \frac{t^3}{3!}Q^3 + \ldots

form a stochastic semigroup.

Problem 3.9.5 from Жуковский М.Е., Родионов И.В., Шабанов Д.А. "Основы теории случайных процессов" [ЖРШ16]More problems in Chapter 3.9 "Continuous-Time Markov Chains"

The transition probabilities of the Markov chain $\left(X_{t}, t \geqslant 0\right)$ with phase space $\mathcal{X} = \left\{ 1,2,3\right\}$ have the form:

\begin{align} p_{11}(h)& =1-\lambda h+o(h), & p_{12}(h)& =\lambda h+o(h), & p_{13}(h)& =o(h) \\ p_{21}(h)& =o(h), & p_{22}(h)& = 1 - \mu h + o(h), & p_{23}(h)& = \mu h + o(h) \\ p_{31}(h)& = \nu h + o(h), & p_{32}(h)& = o(h), & p_{33}(h)& =1 - \nu h + o(h), \end{align}

as $h \to 0+$ . Prove that such a chain satisfies the condition of the ergodic theorem. Find its infinitesimal matrix and stationary distribution.

Problem 10.96 from Прохоров А.В., Ушаков В.Г., Ушаков Н. "Задачи по теории вероятностей" [ПУУ86]More problems in Chapter 10 "Random Processes"

(a)(b)

Find the probability $P_{0}(t)$ that the system $M \mid M \mid 1 \mid 0$ is free at time $t$ , if the intensity of the input flow equals $\lambda$ , the mean service time is $\mu^{-1}$ , and:

(a)

at time $t = 0$ the system was free;

(b)

at time $t = 0$ the system was busy.

References

[AtLa06] Athreya K.B., Lahiri S.N. Measure Theory and Probability Theory. Springer, 2006.

[Gal13] Gallager R.G. Stochastic Processes: Theory for Applications. Cambridge University Press, 2013.

[GrSt20] Grimmett G.R., Stirzaker D.R. Probability and Random Processes. 4th ed., Oxford University Press, 2020.

[КоФо03] Коршунов Д.А., Фосс С.Г. Сборник задач и упражнений по теории вероятностей. 2-е изд., Новосибирский государственный университет, 2003.

[ЖРШ16] Жуковский М.Е., Родионов И.В., Шабанов Д.А. Основы теории случайных процессов. МФТИ, 2016.

[ПУУ86] Прохоров А.В., Ушаков В.Г., Ушаков Н. Задачи по теории вероятностей. Наука. Главная редакция физико-математической литературы, 1986.