[Math] Calculating probabilities for a $4$-state Markov model

algorithmsprobability

I need to write a piece of software that analyzes packet switched computer networks and calculates certain characteristics based on packet loss (the application is Voice over IP quality monitoring). One approach is to use the following $4$-state Markov model (as described here):

4-state markov model

State 1 – packet received successfully
State 2 – packet received within a burst
State 3 – packet lost within a burst
State 4 – isolated packet lost within a gap

State transitions are bound to certain criteria. This is how it is expected to work for a stream of network packets:

Loss pattern 000001100101010110110000000000000000000000001000000000
State        111113322323232332331111111111111111111111114111111111

An example algorithm I found stores the state changes in counter variables (e.g. state change 1->3 increments counter c13). So far I get it and I end up with these counters: $c_14, c_11, c_13, c_22, c_23, c_33.$

However, for the actual analysis I need to calculate the state transition probabilities from these counters. This is where the algorithm chokes. Besides the issue with zero divisions, I don't see the total number of packets incorporated into the probability calculation (this is from the pseudo code of the algorithm definition, $p_14$ is not included because they added $c_14$ to $c_11$):

p11 = c11/(c11 + c13)
p13 = 1 - p11
p31 = c31/(c31 + c32 + c33)
p32 = c32/(c31 + c32 + c33)
p33 = 1 - p31 - p32
p22 = c22/(c22 + c23)
p23 = 1 - p22

Is this even correct? I don't quite get what the author is doing here. Am I missing something? What's the correct way to calculate probabilities $p_14, p_11, p_13, p_22, p_23, p_33, p_31$ and $p_32?$

I hope you understand why I asked this here instead of on Stackoverflow: this is basically just about the calculation of the probabilities, the rest was provided for context.

Best Answer

There is one important rule for assigning probabilities to edges in a Markov model:

Let $i$ be a node, and $out(i)$ be the set of nodes to which $i$ is connected (via an outgoing edge). Then $\sum_{j \in out(i)}{P_{ij}} = 1$.

Consider your own model: As an instance, $out(4)=\{1\}$. Therefore, $P_{41}=1$. In other words, if we are in state 4, we will certainly go to state 1 at the next transition.

Now consider node 1. We have $out(1)= \{1,3,4\}$. Hence $P_{11}+P_{13}+P_{14}=1$. Using the counts:

$P_{11} = \frac{C_{11}}{C_{11}+C_{13}+C_{14}}$

$P_{13} = \frac{C_{13}}{C_{11}+C_{13}+C_{14}}$

$P_{14} = \frac{C_{14}}{C_{11}+C_{13}+C_{14}}$

I'm sure you can do the math for other nodes as well.

Related Question