% 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