This is a simplified version of the first problem I ever attempted to solve in MATLAB. For my original problem, I was trying to figure out the probability of being on any square in the board game Monopoly. That is a difficult problem from a book-keeping sense, but the essence of the problem is in today’s Puzzler.
With the rules shown in the diagram, what is the probability of being on each of the four squares after each of the first twenty turns?
I can think of two good ways of solving today’s Puzzler. I look forward to seeing how everyone else does it.
Take a little bit and work on the Puzzler. I don’t want to give away strategies before you get a chance to work on the puzzle, so I am just showing the results of each method in the preview below, but not saying what the method was.
[There is a typo in the comments on this second video. It should say the probability of moving from Square 4 to Square 1, not the other way around. Sorry!]
Discussion of code and critiques should be placed in the comments. [Click here]
Comments are closed.
11 CommentsOldest to Newest
gencoins = @(x)rand(2,x)>0.5; % anonymous function to generate the coins probs(1,:) = [1,0,0,0]; % First step probability is always square 1 nTrials = 1e6; % How many trials are we running to determine probabilities curPos = zeros(1,nTrials); for n=2:20 coins = gencoins(nTrials); twoTails = ~any(coins); curPos = mod(curPos+sum(coins),4); curPos(twoTails)=0; probs(n,:) = sum(bsxfun(@eq,curPos.',[0,1,2,3]))/nTrials; endThanks for running these puzzles, Doug! Dan
function probs = game(steps) N = 4; % number of game states % Basic transition matrices % move(k) corresponds to "move k squares" move = @(k)circshift(eye(N),[0 k]); % go(k) corresponds to "go to square k" go = @(k)ones(N,1)*((1:N)==k); % Build the actual transition matrix M = 1/2 * move(1) + 1/4 * move(2) + 1/4 * go(1); % Compute probabilities if steps < inf % Finite number of steps: intermediate distributions are computed % using successive matrix-vector products state = (1:N)==1; for i = 1:steps state = state*M; probs(i, 1:N) = state; end else % Infinite number of steps: stationary distribution is computed % (assuming it exists) by solving a linear system probs = [zeros(1,N) 1] /[M-eye(N) ones(N,1)]; end