%% Problem Sheet 7 % Stochastic Simulation close all; clear all; clc; %% Exercise 3 N = 10^5; % sample size % a) % transition matrix + initial distribution P = [1/6, 2/6, 2/6, 1/6; 0, 1/2, 1/2, 0; 1/6, 2/6, 2/6, 1/6; 1/2, 0, 0, 1/2]; lambda = [1/4, 1/4, 1/4, 1/4]; % money won/lost in each state money = [5, 10, -5, -10]; % simulate the Markov chain X = zeros(N,1); X(1) = find(rand < cumsum(lambda), 1); for i = 2:N X(i) = find(rand < cumsum(P(X(i-1),:)), 1); end % compute money won/lost per match money_per_match = mean(money(X)); fprintf('On average, you have won %f Euro per match.\n', money_per_match); % b) % compute and plot running average money_avg = zeros(N/10,1); for i = 1:(N/10) money_avg(i) = mean(money(X(1:i))); end figure(1); plot(money_avg); title('Running average of money won or lost per match'); %% Exercise 4 n = 6; % number of vertices m = 5; % number of colors N = 10^4; % sample size % adjacency matrix E = [0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0]; % initial coloring and vector for estimation X = [1 4 4 3 5 2]; atmost4 = zeros(N,1); % Gibb's sampler for i=1:N Y = X; % choose vertex at random v = ceil(n*rand()); % collect colors used by neighbors used = []; for j=1:n if E(v,j) == 1 used = [used, X(j)]; end end % draw uniformly from remaining colors not_used = setdiff(1:m, used); index = ceil(length(not_used)*rand()); Y(v) = not_used(index); % update X and remember if 4 or less colors have been used X = Y; atmost4(i) = (sum(hist(X,1:m)>0) <= 4); end fprintf('The fraction with 4 colors or less is %f\n', mean(atmost4));