function b = is_markov(XX,PP)
% XX is a list of (row-)sequences over some alphabet
% NOTE: here, we're assuming the alphabet is 0,1
% and that the XX are ordered in increasing binary
% PP(j) is the probability assigned to the jth sequence in the list
% a distribution is Markov if
% P(X_{i+1}=x_{i+1} | X_1...X_i=x_1...x_i) = P(X_{i+1}=x_{i+1} | X_i=x_i)
% note: 19/02/2006-- this example demonstrates
% that a non-1-to-1 function of a markov chain is not nec. markov!
% in this case, it's state collapse
% cf. mequiv3

XX = char(XX+48); % converting XX to char array
[N,n] = size(XX);

b = 1;
tol = 1e-10;

for i=1:n-1
    % check the Markov condition for X_{i+1}
    for j=0:2^(i+1)-1
        % compute "long-history" cond prob
        prefs = dec2bin(j,i+1);  % the prefix string
        X_i1 = prefs(end);
        kk1 = strmatch(prefs(1:end-1),XX);
        kk2 = strmatch(prefs,XX);
        Ppref = sum(PP(kk1));
        Pjoin = sum(PP(kk2));
        cp_long = Pjoin/Ppref;
        % compute "short-history" cond prob
        Xi = prefs(end-1);
        kk1 = strmatch(Xi,XX(:,i));
        kk2 = strmatch([Xi X_i1],XX(:,i:i+1));
        Ppref = sum(PP(kk1));
        Pjoin = sum(PP(kk2));
        cp_short = Pjoin/Ppref;
        
        b = b & (abs(cp_long-cp_short)<tol);
        if ~b
            'not markov'
            keyboard
        end
    end
    
    if b
        fprintf('markov up to i=%d \n',i);
    end
end

return