Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Markov sources/chains

  1. Oct 20, 2012 #1
    Im studying Markov sources at the moment and i have dificulty in solving and understanding one type of exercise.
    We have a binary markov source which generates the following chain of symbols.
    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 cant 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 cant 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.
  2. jcsd
  3. Oct 20, 2012 #2
    To be clear, can you define what p(x/y,z) means?
  4. Oct 20, 2012 #3
    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.
  5. Oct 20, 2012 #4
    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.
    Last edited: Oct 20, 2012
  6. Oct 20, 2012 #5
    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) isnt 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 dont think he speaks about somthing else because we also made the transition matrix.
    Last edited: Oct 20, 2012
  7. Oct 20, 2012 #6
    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.
  8. Oct 20, 2012 #7
    ohhh, this makes sense, p(0/0,1) gave me 5/8 too.

    Thanks a lot!!! i understood!!!
  9. Oct 20, 2012 #8
    Glad to help! Good luck!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook