%% Compute Expected Commute Time
% The expected commute time from state i to state j is the expected time required for a Markov chain to transition from state i to state j (the expected first hitting time ht\left(i,j\right)), then back to state i (ht\left(j,i\right)). Formally, the expected commute time is
% C\left(i,j\right)=ht\left(i,j\right)+\;ht\left(j,i\right).
% Create a "dumbbell" Markov chain containing 10 states in each "weight" and three states in the "bar."
% Specify random transition probabilities between states within each weight.
% If the Markov chain reaches the state in a weight that is closest to the bar, then specify a high probability of transitioning to the bar.
% Specify uniform transitions between states in the bar.

rng(1); % For reproducibility
w = 5;                              % Dumbbell weights
DBar = [0 1 0; 1 0 1; 0 1 0];        % Dumbbell bar
DB = blkdiag(rand(w),DBar,rand(w));  % Transition matrix

% Connect dumbbell weights and bar
DB(w,w+1) = 1;                       
DB(w+1,w) = 1; 
DB(w+3,w+4) = 1; 
DB(w+4,w+3) = 1;

mc = dtmc(DB);

% Plot a digraph of the Markov chain mc. Suppress node labels.

figure;
graphplot(mc);

%
% Consider computing the expected commute time from state 1 to state 10.
% Compute ht(1,10), the expected first hitting time for state 10 beginning from state 1.

ht = hittime(mc,10);
ht1to10 = ht(1);

% Compute ht(10,1), the expected first hitting time for state 1 beginning from state 10.

ht = hittime(mc,1);
ht10to1 = ht(10);

% Compute the expected commute time from state 1 to state 10.

C1to10 = ht1to10 + ht10to1

% The expected commute time from state 1 to state 10 and back is 236.62 time steps.
% Copyright 2019 The MathWorks, Inc.
%