%% Markov Version of Gambler's Ruin
clc
format compact
format short g
%%Models the gambler's ruin problem for n states and N iterations
n=20 % Number of states
N=100000 % number of iterations
A = [1:n-1;zeros(2,n-1)]'; % A matrix with all states and space to count ending points
for k=1:N
    starting = round((n-1)*rand+.5);
    walker=starting;
    while (n*walker-walker^2>0)
        walker = walker+sign(randn);
    end
    A(starting,2+walker/n)=A(starting, 2+walker/n)+1;
end
A
B=A;
for j=1:n-1
    rowtotal = sum(A(j,2:3));
    B(j,2:3)=B(j,2:3)/rowtotal;
end
B

%%% Solutions Using Markov Chains (Matrix Method)
n=7;
N=40;
toprow=[0 1/2 zeros(1,n-1)];
C=toeplitz(toprow,toprow);
C(1,1:2)=[1 0];
C(n+1,n:n+1)=[0 1];
C;

IterateMatrix=zeros(N+1,n+1)
Starting=5;
IterateMatrix(1,Starting+1)=1;
for j=1:N
    IterateMatrix(j+1,:)=IterateMatrix(j,:)*C;
end
IterateMatrix
eigenvalues=sort(eig(C)')
max(eigenvalues.*(eigenvalues<1))