DES - Demonstration of the State Holding Time for a Poisson Clock Structure

Arguments:

DES - Definition of ‘State Holding Time’ DES - Definition of ‘Poisson Clock Structure’ DES - Exponential Distribution DES - Definition of a ‘Poisson Process’

---

Objective:

Calculate the distribution of the State Holding Time for a Stochastic Timed Automata with Poisson Clock Structure

---

Summary:

Starting from:

$$F_i(t)=P(V(i)\le t)$$

Where:

• $F_i(t)$: cdf of the state holding time of state $i$
• $V_i(t)$: state holding time of state $i$

We want to arrive at:

$$\begin{array}{rl}& P(V(i)\le t)=\prod _{e\in \Gamma (x)}\sum _{n=0}^{\infty }P\left(\genfrac{}{}{0ex}{}{\text{ event }e\text{ occurs exactly }n\text{ times over}\left(0,t\right]}{\underline{\text{AND}}\text{ it does NOT trigger state transition}}\right)\\ & P(V(x)>t)=e^{-\left\{{\sum }_{e\in \Gamma (x)}{\lambda }_e\left[1-p(x\mid x,e)\right]\right\}t}\\ & \Rightarrow F_i(t)\text{has an exponential distribution}\end{array}$$

Useful to know:

$$P\left(\text{event e occurs exactly n times over }\left(0,t\right]\right)=\frac{(\lambda t{)}^n}{n!}{e}^{-\lambda t}$$

---

Demonstration:

Recalling that:

$$P(V(x)⩽t)=1-P(V(x)>t)$$

we start from computing $P(V(x)>t)$, for $t>0$.

Considering this small system as an example:

$$\begin{array}{rl}P(V(x)>t)& =\\ & =P\left(\text{ no state transition occurs over }\left(0,t\right]\right)\\ & =P\left(\bigcap _{e\in \Gamma (x)}\left\{\text{ nostate transition triggered by event e over }\left(0,t\right]\right\}\right)\\ & \text{< events are independent from each other >}\\ & =\prod _{e\in \Gamma (x)}P\left(\text{ nostate transition triggered by event }e\text{ over }\left(0,t\right]\right)\\ & =\prod _{e\in \Gamma (x)}P\left(\bigcup _{n=0}^{\infty }\left\{\genfrac{}{}{0ex}{}{\text{ event }e\text{ occurs exactly }n\text{ times over}\left(0,t\right]}{\underline{\text{AND}}\text{ it does NOT trigger state transition}}\right\}\right)\end{array}$$

• In the mini-system above $(\Delta )$ the $P\left(\text{ no state transition occurs over }\left(0,t\right]\right)$ is referring to the probability that from $x$ the event $e$ occurs and the state remain $x$.
• When we say does NOT trigger state transition than that means that the “riccioli” are to only events to be considered.

“Ricciolo”:

$$\begin{array}{rl}& \dots \text{continuing from before}\\ & =\prod _{e\in \Gamma (x)}\sum _{n=0}^{\infty }P\left(\genfrac{}{}{0ex}{}{\text{ event }e\text{ occurs exactly }n\text{ times over}\left(0,t\right]}{\underline{\text{AND}}\text{ it does NOT trigger state transition}}\right)\end{array}$$

Where $e^{(i)}$ is the $i$-th occurrence of event $e$, and $Y_{e^{(i)}}$ its lifetime. So:

$$\begin{array}{rl}& P\left(\text{event e occurs exactly n times over }\left(0,t\right]\right)=\\ & =P(Y_{e,1}+Y_{e,2}+\dots +Y_{e,n}<t,Y_{e,1}+Y_{e,2}+\dots +Y_{e,n+1}>t)\\ & \text{< preliminary result >}\\ & =\frac{(\lambda t{)}^n}{n!}{e}^{-\lambda t}\end{array}$$

Now lets consider instead:

$$\begin{array}{rl}& \prod _{e\in \Gamma (x)}\sum _{n=0}^{\infty }P\left(\genfrac{}{}{0ex}{}{\text{ event }e\text{ occurs exactly }n\text{ times over}\left(0,t\right]}{\underline{\text{AND}}\text{ it does NOT trigger state transition}}\right)=\\ & =\prod _{e\in \Gamma (x)}\sum _{n=0}^{\infty }\frac{({\lambda }_{e}t{)}^n}{n!}{e}^{-{\lambda }_{e}t}\cdot p(x\mid x,e{)}^n\\ & =\prod _{e\in \Gamma (x)}{e}^{-{\lambda }_{e}t}\sum _{n=0}^{\infty }\frac{{\left[({\lambda }_{e}t)\cdot p(x\mid x,e)\right]}^n}{n!}\\ & \text{knowing that: }{e}^x=\sum _{n=0}^{\infty }\frac{x^n}{n!}\\ & =\prod _{e\in \Gamma (x)}{e}^{-{\lambda }_{e}t}{e}^{{\lambda }_{e}p(x\mid x,e)t}\\ & =\prod _{e\in \Gamma (x)}{e}^{-{\lambda }_e\left[1-p(x\mid x,e)\right]t}\\ & =e^{-\left\{{\sum }_{e\in \Gamma (x)}{\lambda }_e\left[1-p(x\mid x,e)\right]\right\}t}\end{array}$$

So now we have that:

$$P(V(x)>t)=e^{-\left\{{\sum }_{e\in \Gamma (x)}{\lambda }_e\left[1-p(x\mid x,e)\right]\right\}t}$$

And we can calculate:

$$P(V(x)\le t)=1-P(V(x)>t)$$

So:

$$\begin{array}{rl}& P(V(x)\le t)=1-e^{-\left\{{\sum }_{e\in \Gamma (x)}{\lambda }_e\left[1-p(x\mid x,e)\right]\right\}t}\\ & \text{for }t\ge 0\end{array}$$

We have thus shown that $V(x)$ has an exponential distribution with rate:

$$\sum _{e\in \Gamma (x)}{\lambda }_e\left[1-p(x\mid x,e)\right]$$

Knowing that:

$$p(x\mid x,e)+p(x^{\prime }\mid x,e)=1$$

We can say that the rate is equal to:

$$\sum _{\genfrac{}{}{0ex}{}{e\in \Gamma (x)}{x^{\prime }\ne x}}{\lambda }_{e}p(x^{\prime }\mid x,e)$$

Knowing this we can also say that the average state holding time is:

$$E\left[V(i)\right]=\frac{1}{\sum {\lambda }_{e}p(x^{\prime }\mid x,e)}$$

---

More Generally:

We have considered for the example only 2 states, and only two possible events, where 1 changes state and the other doesn’t, so we can say:

$$p(x\mid x,e)+p(x^{\prime }\mid x,e)=1$$

Then

$$\text{Then: }1-p(x\mid x,e)=p(x^{\prime }\mid x,e)$$

So:

$$\begin{array}{rl}& \sum _{e\in \Gamma (x)}{\lambda }_e\left[1-p(x\mid x,e)\right]=\\ & =\sum _{e\in \Gamma (x)}{\lambda }_e\cdot p(x^{\prime }\mid x,e)\end{array}$$

Now instead of considering only a single event that keeps me from changing state consider more events (an undefined number). So, if we want to say the general probability of remaining in the same state, we can change:

$$p(x\mid x,e)\to \sum _{e\in \Gamma (x)}p(x|x,e_i)$$

Note that $e\in \Gamma (x)$ are all the events possible Also that if for example the event $e_4$ would change state than $p(x\mid x,e_4)=0$.

For the opposite instead, we are using two different states $x$ and $x^{\prime }$, so the general probability for changing state can be rewritten as:

$$\begin{array}{r}p(x^{\prime }\mid x,e)\to \sum _{x^{\prime }\ne x}\sum _{e\in \Gamma (x)}p(x^{\prime }|x,e_i)\end{array}$$

(Old result):

$$\sum _{\genfrac{}{}{0ex}{}{e\in \Gamma (x)}{x^{\prime }\ne x}}{\lambda }_{e}p(x^{\prime }\mid x,e)$$

(General result):

$$\text{rate:}\sum _{x^{\prime }\ne x}\sum _{e\in \Gamma (x)}p(x^{\prime }|x,e_i)$$

---