Solving Binary Markov Sources Exercises

[Drao92]

Hello,
Im studying Markov sources at the moment and i have dificulty in solving and understanding one type of exercise.
Exercise:
We have a binary markov source which generates the following chain of symbols.
0010111001010111100001010011
It asks me to find p(0/0,0), p(0/0,1)... p(1/0,0), p(1/0,1).
All i know is that we have 26 possibilities, but i can't understand how to "read" them.
Like, p(1/0,1)=p(1,0/0,1) would be 010? But if is it like this how can i find p(0/0,1)=p(0,0/0,1) because i can't write it in the same way with 3 symbols.
One thing i have in my mind is that i find p(1/0,1) and then p(0/0,1) would be 1-p(1/0,1).
I hope you understand what i mean, english is not my first language :D and please help me if you can.
Thanks,
Drao

 

[digfarenough]

To be clear, can you define what p(x/y,z) means?

 

[Drao92]

In my course it says its a conditioned probability.
p(1,0/0,0) is the probability of markov source to move from state 0,0 in state 1,0.

 

[digfarenough]

Oh, ok. As I have always seen it, a pipe | is used instead of a slash /. I will write p(b,c|a,b) to be the probability of transitioning from state (a,b) to (b,c).

I'm not sure why you say there are 26 possibilities, so I might be misunderstanding, but if I understand correctly:

To find the probabilities, you can simply count them in the output.

For example, in the output 0000000000000
We can see that p(0,0|0,0) = 1 because all 00s are followed by an 0, and p(0,1|0,0) = 0 because no 00 is followed by a 1. As you implied, p(b,c|a,b) can be written p(c|a,b), so we can also just write p(0,0|0,0) = p(0|0,0) = 1 and p(0,1|0,0) = p(1|0,0) = 0.

In the output 001000, we first see that (0,0) goes to (0,1) one time and (0,0) goes to (0,0) once, so p(0,1|0,0) = p(1|0,0) = 0.5 and p(0,0|0,0) = p(0|0,0) = 0.5.
(Also, of course p(1,0|0,1) = p(0|0,1) = 1 and p(0,0|1,0) = p(0|1,0) = 1, but p(1,1|0,1) = p(1|0,1) = 0).

So to find the probabilities, you just have to count the number of times each transition occurs. A quick way to do this is draw the four-state chain and go through your symbol sequence one at a time, tracing your way through the diagram of the chain and making a mark each time you follow a transition. Then at the end, count up the marks on the transitions and use those to find the probabilities.

I hope that is helpful. Please let me know if I have misunderstood.

 

[Drao92]

I said there are 26 posibilities because there are 27 symbols and we can group 3 consecutive symbols by 26 times. This is how we solved in class.
For exemple: p(0/0,0)=2/26, p(0/0,1)=4/26, p(1/0,1)=4/26, p(0/1,0)=5/26... What i think he did is: He count how many states of p(0/0,0) are and he divided by 26.
My teacher said p(0/0,1)+p(1/0,1) isn't equal with 1 because he wrote the chain wrong, but its absurd because we can have p(0/0,1)+p(1/0,1)=1 only when only these states are found in the output if we divide each numer of state found by 26.
Moreover don't think he speaks about somthing else because we also made the transition matrix.

 

[digfarenough]

Oh, there are 26 transitions in that sequence, yes. and 8 transition probabilities you need to calculate.

You should not divide the counts by 26, though. p(0|a,b) and p(1|a,b) should be divided by the number of times ab appears in the sequence.

001 011 100 101 011 110 000 101 001 1
0 010 111 001 010 111 100 001 010 011
00 101 110 010 101 111 000 010 100 11

There are 8 triples that begin with 01. Three of them are 011, so p(1|0,1) = 3/8 and five are 010 so p(0|0,1) = 5/8.

Now p(1|0,1) + p(0|0,1) = 1.

 

[Drao92]

ohhh, this makes sense, p(0/0,1) gave me 5/8 too.

Thanks a lot! i understood!

 

[digfarenough]

Glad to help! Good luck!