0 votes

What is the stationary distribution for the following conditional probability table?

in Informed Search by AlgoMeister (1.6k points)

1 Answer

0 votes
0.3810

0.3016

0.3175

>> P=[ 0.6 0.3 0.1;

    0.4 0.2 0.4;

    0.1  0.4 0.5 ]

n=size(P,1)

E=eye(n);

M=[(P'-E);ones(1,n)];

N=[zeros(n,1);1]

pi=M\N
by Active (296 points)
Another way to do this can be to set the system up and then reduce the matrix to row-reduced echelon form.

To start with,

S = 0.6S + 0.4C + 0.1R
C = 0.3S + 0.2C + 0.4R
R = 0.1S + 0.4C + 0.5R
S + C + R = 1

We can make this into a system of equations:

-0.4S + 0.4C + 0.1R = 0
0.3S + -0.8C + 0.4R = 0
0.1S + 0.4C + -0.5R = 0
S + C + R = 1

This can be solved with a single command with MATLAB-like programs:

octave:15> B2 = [-0.4 0.4 0.1 0; 0.3 -0.8 0.4 0; 0.1 0.4 -0.5 0; 1 1 1 1 ]
B2 =

  -0.4000   0.4000   0.1000        0
   0.3000  -0.8000   0.4000        0
   0.1000   0.4000  -0.5000        0
   1.0000   1.0000   1.0000   1.0000

octave:16> rref(B2)
ans =

   1.0000        0        0   0.3810
        0   1.0000        0   0.3016
        0        0   1.0000   0.3175
        0        0        0        0

Thus,

S = 0.3810
C = 0.3016
R = 0.3175

Related questions

0 votes
1 answer
asked Feb 23, 2021 in MDP by Amrinder Arora AlgoMeister (1.6k points)
0 votes
2 answers
0 votes
1 answer
0 votes
2 answers
asked May 13, 2019 in Informed Search by Amrinder Arora AlgoMeister (1.6k points)
0 votes
3 answers
asked Mar 19, 2023 in Informed Search by Amrinder Arora AlgoMeister (1.6k points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...