Mathematical Reasoning

CTMC Path Measures

Posted on October 6, 2007 | 1 Comment

There are many problems in Computer Science where you have to work with the notion of paths for any given graph. For CTMCs we also need some kind of path notion. Consider the following CTMC:

CTMC

The above CTMC has a source state $s_0$ and a destination state $s_3$ . There a infinitely many paths which start in $s_0$ and end in $s_3$ . Some of them are:

$s_0\rightarrow s_1\rightarrow s_3$ ,
$s_0\rightarrow s_2\rightarrow s_3$ ,
$s_0\rightarrow s_1\rightarrow s_2\rightarrow s_3$ .

For CTMCs we are not only interested in paths but also in computing some probability measure for them. One of these measures is the probability to start in a source state $s_0$ and to move to some destination state $s_n$ in $T$ units of time,where the path is $s_0\rightarrow s_1\rightarrow\cdots\rightarrow s_{n-1}\rightarrow s_n$ . The path measure is computed as follows:

$\int_{0}^{T}\mathrm{Pr}(s_0,s_1,\tau_1)\int_{0}^{T-\tau_1}\mathrm{Pr}(s_1,s_2,\tau_2)\cdots\int_{0}^{T-\sum_{i=0}^{n-1}\tau_i}\mathrm{Pr}(s_{n-1},s_n,\tau_n)d\tau_n\cdots d\tau_1$

,where $\mathrm{Pr}(s_{i-1},s_i,\tau_i)=R_{s_{i-1},s_i}e^{-E_{s_{i-1}}\tau_i}$ is the probability density function to move from state $s_{i-1}$ to state $s_i$ at time $\tau_i$ . Recall that the probability distribution function to move from state $s_{i-1}$ to state $s_i$ in $\tau_i$ units of time is $\frac{R_{s_{i-1},s_i}}{E_{s_{i-1}}}(1-e^{-E_{s_{i-1}}\tau_i})$ .

For instance the probability to arrive in state $s_3$ in 10 min. for the above CTMC by traversing the path $s_0\rightarrow s_1\rightarrow s_2\rightarrow s_3$ :

$\int_{0}^{10}2e^{-2\tau_1}\int_{0}^{10-\tau_1}3e^{-7\tau_2}\int_{0}^{10-\tau_1-\tau_2}1e^{-2\tau_3}d\tau_3d\tau_2 d\tau_1$ .

→ 1 Comment

Posted in CTMC, Markov Chains, Stochastic Processes

Tagged CTMC, Path Measure

Article structure

Posted on October 4, 2007 | 3 Comments

I was thinking what should be the structure of the articles which I post:

Short, at most a page.
A lot of images .
Not too many formulas and not too much text.
More intuition.

And what I was thinking all the time is that this blog is useless and I should delete it, but anyway I will continue posting.

→ 3 Comments

Posted in General

CTMC Measures

Posted on October 4, 2007 | Leave a comment

In previous post I have defined the Continuous Time Markov Chain (CTMC) model. Now it would be interesting to compute some measures of interest. Consider a CTMC with two states $s_0$ and $s_1$ .

The first measure is the the probability to leave some state $s$ in $\Delta t$ units of time: $\mathrm{Pr}(W_s\le\Delta t)=1-e^{-E_s\Delta t}$ , where $W_s$ is the amount of time that the process stays in state $s$ and $E_s$ is the exit rate of state $s$ . For instance in the above CTMC the probability to leave $s_0$ in 10 minutes knowing that the exit rate is 2 costumers per minute is $1-e^{-20}$ .

The second measure is the probability to select the transition $s\rightarrow s'$ from state $s$ to state $s'$ . It is given by the formula $\mathrm{Pr}_{s,s'}=\frac{R_{s,s'}}{E_s}$ , where $R_{s,s'}$ is the rate from state $s$ to state $s'$ . For the above CTMC the probability to select transition $s_1\rightarrow s_0$ is $\frac{3}{3}=1$ . A more intuitive meaning of the second measure is that there is a guy in state $s_1$ who always flips a coin. And if it happens to be Heads (H) then he selects the transition otherwise for Tails (T) he does not select it. The trick with state $s_1$ is that the guy always flips a coin whose both sides are H.

The last measure is the probability to select the transition $s\rightarrow s'$ from state $s$ to state $s'$ in $\Delta t$ units of time. It is given by the formula $\mathrm{Pr}_{s,s'}(\Delta t)=\frac{R_{s,s'}}{E_s}(1-e^{-E_s\Delta t})$ . One might think that the last measure is the product of two probabilities: to select the transition $s\rightarrow s'$ and to leave the state $s$ . For instance the probability to select transition $s_0\rightarrow s_1$ in 10 minutes is $\frac{2}{2}(1-e^{-20})=1-e^{-20}$ .

→ Leave a comment

Posted in CTMC, Markov Chains, Stochastic Processes

Tagged CTMC, Measures

Continuous Time Markov Chains

Posted on September 28, 2007 | Leave a comment

I’m starting a series of articles on well-known stochastic processes denoted by Continuous Time Markov Chains (CTMC). A CTMC is an ordinary Markov chain with memoryless property and continuous time.
Definition. A CTMC is a tuple $\mathcal{C}=(\mathbb{S},\boldsymbol{\mathrm{R}})$ where:

$\mathrm{\mathbb{S}}=\left\lbrace 1,2,\dots,n\right\rbrace$ is a finite set of states, and
$\boldsymbol{\mathrm{R}}=\lbrack R_{i,j}\ge 0\rbrack\in\mathbb{R}^{n\times n}$ is a rate matrix, where $R_{i,j}$ is the rate between states $i,j\in \mathrm{\mathbb{S}}$ .

For instance an element of $\boldsymbol{\mathrm{R}}$ i.e., a rate is the number of (costumers) arrivals or departures per unit of time (10 costumers per hour). An example of a CTMC is shown below. The numbers on transitions denote the value of the rates. For instance the rate between state 1 and 2 is 1 and the rate between state 3 and 2 is 2.

The rate matrix for the above example is given by $\boldsymbol{\mathrm{R}}=\left(\begin{array}{cccc}0 & 1 & 0 & 0\\ 2 & 0 & 1 & 0\\ 0 & 2 & 0 & 1\\ 0 & 0 & 2 & 0\end{array}\right)$ .

Besides the rate matrix one can define also the exit rate diagonal matrix as $\boldsymbol{\mathrm{E}}=\mathrm{diag}\left[ E_{i}\right]\in\mathbb{R}^{n\times n}$ , where $E_{i}=\sum_{j\in \mathrm{\mathbb{S}}}R_{i,j}$ for all $i,j\in \mathrm{\mathbb{S}}$ , $i\ne j$ i.e., $E_{i}$ is the total exit rate of state $i$ . For the above CTMC the exit rate matrix results in $\boldsymbol{\mathrm{E}}=\left(\begin{array}{cccc}1 & 0 & 0 & 0\\ 0 & 3 & 0 & 0\\ 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 2\end{array}\right)$ .