%% Problem Sheet 2
% Stochastic Simulation

%% Exercise 5

close all; clear all; clc;

% transition matrix
P = [0, 1/2, 1/2, 0, 0;
     1/2, 0, 1/2, 0, 0;
     0, 0, 0, 1/2, 1/2;
     0, 0, 0, 0, 1;
     0, 0, 0, 1, 0];
 
% sample size and empty vectors
n = 10^3;
tau5 = zeros(n, 1);
tau6 = zeros(n, 1);

for i = 1:n
    % initialize Markov chain and time
    X = 1;
    t = 1;
    while (tau5(i) == 0) || (tau6(i) == 0) % until both taus are reached
        % go one step further
        U = rand();
        X(t+1) = find(U < cumsum(P(X(t),:)), 1); % (X changes size)
        % check if we are at tau5
        if (tau5(i) == 0) && (X(ceil(t/2)+1) >= 4)
            tau5(i) = t;
        end
        % check if we are at tau6
        if (tau6(i) == 0) && (X(t+1) == 3)
            tau6(i) = t;
        end
        t = t+1;
    end
end

fprintf('Estimated expectation of tau5: %f\n', mean(tau5));
fprintf('Estimated expectation of tau6: %f\n', mean(tau6));


%% Exercise 6

close all; clear all;

n = 10^5;
success = zeros(n,1);

for i=1:n
    % initialize MC
    X = 0; % (this time we save only the current value of X, 
           %  not the whole chain)
    t = 1;
    while (X ~= 8) && (X ~= -1) % until we get the to -1 or 10
        % simulate another step
        U = rand();
        if U <= 1/4
            X = X-1;
        elseif U <= 3/4;
            % do nothing (stay in state X)
        else
            X = X+1;
        end
        t = t+1;
    end
    % check if we stopped because we were in state 8
    success(i) = (X == 8);
end

fprintf('Estimated probability: %f\n', mean(success));