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.

  • 1
    $\begingroup$ So far this is just a special case of the general principle for estimating the probability of an event when given a sample: divide the number of occurrences by the sample size (except that you forgot the p14 case). Here you actually have three experiments, each one with its own sample. Maybe this is what you didn't realize. $\endgroup$ – Florian Oct 10 '10 at 23:13

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.

  • $\begingroup$ I figured this out after Florian's comment when he talked about "three experiments". Actually I can't believe I didn't get it the first time, it is kind of obvious, but I never dealt with any Markov model before, so I was confused. Thanks for reassuring me and providing this excellent formal explanation! $\endgroup$ – paprika Oct 11 '10 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.