It is desired to use arithmetic encoding on a stationary bin

It is desired to use arithmetic encoding on a stationary, binary Markov random source {Xi ; i = 1,
2, 3,……}. The transition probability matrix P for this source is given below.
P =

(a) If the cumulative probability distribution function F( ) is defined on binary sequences from
the source as F(sequence) = Pr{0.X1X2X3X4X5 0.sequence}, where sequence denotes a binary
sequence of length 5, and the notation 0.sequence denotes the number less than 1 which is a
dyadic fraction (i.e. sum of powers of (1/2)), evaluate F(0 1 1 1 0) by pursuing an arithmetic
encoding strategy.

(b) How many bits of F(0 1 1 1 0) = 0. F1F2F3 …….. can be known for sure if it is not known
how the rest of the sequence X1X2X3X4X5 continues from the output of the source?

Solution

a)
As binary sequence length given 5.
So transition probability matrix will be as follows:

1/5 2/5 3/5 4/5
2/5 1/5 4/5 3/5

So evaluating F(0 1 1 1 0) ===> 0x1/5 x 1x2/5 x 1x3/5 x 1x4/5 x 0x2/5 ===> 0

b) As function F has input length 5, So total known bits will be (5-1) x 2 = 8
i.e transition probability matrix elements will be 8