% Hi-Ho! Cherry-O (TM), Markov Chain Problem
% Copyright (C) 2002 Jeffrey Humpherys.
%

SPIN = 4;       % The number of possible spins.
N = 10;        % The number of cherries on tree.

%
% Fills the transition matrix.
%

A = zeros(N+1,N+1);
for i = 1:SPIN
    A = A + diag(ones(N+1-i,1),-i);
    A(N+1,N+1-i) = A(N+1,N+1-i) + SPIN - i;
end;

A = A + 2*diag(ones(N+1-2,1),+2);
A(1,1)=2; A(1,2)=2; A(N-1,N+1)=0; A(N+1,N+1)=3+SPIN;

for i = 1:N
    A(1,i) = A(1,i) + 1
end;

%
% Now normalize A to get the Markov chain.
%

A = (1/(SPIN+3))*A;

%
% The probability distribution (d), i.e., the probability that game is over by the ith move,
% will approach 1 in the limit as i goes to infinity (ITERATIONS).
%

ITERATIONS = 300;

d=zeros(1,ITERATIONS);
for i = 1:ITERATIONS
    B = A^i;
    d(i) = B(N+1,1);
end;
B=[];

%
% The probability density function is then the difference function on d.
%

prob_density = [0 diff(d)];

figure;
bar(prob_density(1:75));   % graph the density function

figure;
bar(d(1:75))               % graph the distribution function

%
% The expected value (mu) is the inner product of the probability density and the values of the random variable (X),
% which is just the number of turns taken.
%

X = [1:ITERATIONS]';
mu = prob_density * X