Distinguishing independent Bernoulli trials from a 2-state Markov Chain

Question

Given is a sequence of zeros and ones $x=(x_1,\dots,x_n)$ that could have been be drawn in one of two ways:

1) as success indicators in Bernoulli experiments with probability of success p (e.g. by tossing a biased coin), or

2) as sequence of states (0 or 1) in a random realisation of a Markov chain with {a transition probabilities matrix $\mathbf{P}.$

The challenge is to determine which way the given data were actually produced and how to estimate the corresponding parameters $p$ of $\mathbf{P}.$

Answer 1

Consider three processes:

(1) Independent tosses $X_i$ of a biased coin with Heads probability $\theta = 0.3.$ The long-run proportion of Heads ($1$'s) is $0.3.$

(2) A Markov Chain $Y_i$ with state space $\{0,1\}$ and 'change probabilities' $\alpha = p_{01} = .3,\,$ $\beta =p_{10} = .7,$ so that both rows of the transition matrix are the same $[1 - \beta = \alpha].$ Although 'disguised' ad a Markov chain, this is a purely independent process. The long-run distribution is $\lambda = (.7, .3).$

(3) A Markov Chain $Z_i$ with the same state space, but with change probabilities $\alpha = p_{01} = .03,\,$ $\beta = p_{10} = .07,$ so that the chain tends to move infrequently. However, because of the choices of $\alpha$ and $\beta,$ the long-run distribution is again $\lambda = (.7, .3).$

If each process is run through 10,000 steps (in R statistical software), the proportion of $1$'s is found to be about $.03$ in each case. However, autocorrelation function plots (for 40 lags) are about the same for the $X$- and $Y$-processes, but the $Z$-process shows significant autocorrelations through many steps. (If you haven't heard of 'autocorrelation' you can google it.)

set.seed(1234)
m = 10000;  x = rbinom(m, 1, .3)
mean(x)
[1] 0.2959

m = 10000;  y = numeric(m);  n = 1:m
alpha = 0.3;  beta = 0.7;  y[1] = 0                 
for (i in 2:m)  {
  if (y[i-1]==0)  y[i] = rbinom(1, 1, alpha)
  else            y[i] = rbinom(1, 1, 1 - beta)  }
mean(y)
[1] 0.3019

m = 10000;  z = numeric(m);  n = 1:m
alpha = 0.03;  beta = 0.07;  z[1] = 0                 
for (i in 2:m)  {
  if (z[i-1]==0)  z[i] = rbinom(1, 1, alpha)
  else            z[i] = rbinom(1, 1, 1 - beta)   }
mean(z)
[1] 0.3123

par(mfrow=c(1,3))
acf(x);  acf(y);  acf(z)
par(mfrow=c(1,1))

Of course, the autocorrelations of lag $0$ show correlation $1.$ For larger lags, autocorrelations outside the dotted blue bands are deemed significantly greater than $0.$ The one-step Markov dependence decays very slowly in a chain that does not move 'easily'.

Without doing a formal runs test, we note that the $X$- and $Y$-processes show average run lengths of about 2.4 [as expected: $.5(1/\alpha + 1/\beta) = 2.38$] steps. By contrast, the $Z$-process shows average run lengths of about 23 steps.

rle(x); mean(rle(x)$lengths)
Run Length Encoding
  lengths: int [1:4208] 4 1 8 1 1 1 9 1 1 2 ...
  values : int [1:4208] 0 1 0 1 0 1 0 1 0 1 ...
[1] 2.376426

rle(y); mean(rle(y)$lengths)
Run Length Encoding
  lengths: int [1:4236] 4 1 6 1 1 1 2 4 5 1 ...
  values : num [1:4236] 0 1 0 1 0 1 0 1 0 1 ...
[1] 2.360718

rle(z); mean(rle(z)$lengths)
Run Length Encoding
  lengths: int [1:442] 19 6 37 16 26 91 1 6 25 10 ...
  values : num [1:442] 0 1 0 1 0 1 0 1 0 1 ...
[1] 22.62443