# Markov chain problem

## Main Question or Discussion Point

[SOLVED] Markov chain problem

Hi, all! This is not a homework thing or something like that. I'm just curious.

Suppose a Markov chain p(n+1)=Q*p(n), where Q=[q11, q12; q21, q22] is the transition probability matrix and p(n)=[p1(n);p2(n)] is the probability vector.

Given Q and p(1), we can generate a realization from it, i.e., a sequence of ones and zeros.

Now I want to do the inverse. Given a long enough sequence of ones and zeros, Q can be obtained by counting the number of changes from zero to zero(which will be q11), zero to one(q12), one to zero(q21), and one to one(q22). But, how can I get the initial probability vector p(1) from this sequence? Maximum Likelihood Estimation, blah blah? I don't know about that. Please, someone give me a clue how I can do this. Or is it impossible to do that from just only one realization sequence?

Related Set Theory, Logic, Probability, Statistics News on Phys.org
EnumaElish
Homework Helper
How is the realization r linked to p? If p1 > 0.5 then r = 1, otherwise r = 0?

Oh, I forgot that. The realization is not deterministic but stochastic through a kind of random number generation according to the probability vector. If p1=.4 and p2=.6, then the probability that a zero will come out is 40 percent and the probability that a one will come out is 60 percent.

EnumaElish
Homework Helper
So how do you construct your sequence of 1's and 0's? Toss a coin, with a 1 on one side and a 0 on the other?

It's a good idea. You can use any sequence if it is composed of zeros and ones.

For example, you are given this sequence: 010100101101001011010010111010.
Then, you can get Q as [3/14, 11/15; 11/14, 4/15].
And, I have no idea how I can get p(1) from this.

EnumaElish
Homework Helper
Two ideas:
1. assume uniform initial probability, p = 0.5
2. assume stationary Markov, then solve p = Qp.

NateTG
Homework Helper
It's impossible to completely determine the probability matrix from samples, even if we stipulate that it's a markov process, but it is possible to use statistics to find what the probabilities are likely to be.

Any probability matrix where all entries are non-zero is can produce any sequence. For example, a process with the probability matrix:
$$$\left[ \begin{array}{cc} \frac{1}{2}& \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \\ \end{array} \right]$$$
Will produce any particular sequence of length $n$ with probability $\frac{1}{2^n}$.

So, assuming even initial distribution it would generate 010100101101001011010010111010 about
$\frac{1}{2^{30}}$ of the time.

The probability matrix you produced
$$$\left[ \begin{array}{cc} \frac{3}{14}& \frac{11}{15} \\ \frac{11}{14} & \frac{4}{15} \\ \end{array} \right]$$$
Is just the one that has the highest likelihood of producing the sequence you gave, but, because the sample is relatively small, there really isn't a whole lot confidence that it's correct.

This 'reversing probability' stuff is a bit more advanced.

What about MAP(Maximum A Posteriori) esimation, $$\hat{x}$$=argmax$$p(x|y)$$, since we're interested in the random variable $$x$$, p(1) in this case, given data as the realization $$y$$, in this case the sequence? I feel like this will work. The a posteriori pdf $$p(x|y)$$ can be calculated using Bayes's theorem $$p(x|y)=\frac{p(y|x)}{p(y)}p(x)$$ where $$p(x)$$ is the a priori pdf, $$p(y)$$ is the marginal pdf, and $$p(y|x)$$ is proportional to the likelihood function. And we can put $$\left[\begin{array}{c} .5\\ .5\\ \end{array}\right]$$ in the place of the a priori pdf $$p(x)$$ using maximum entropy principle as EnumaElish did in the first idea. But, I don't know how to calculate the rest of things. Now I'm seeking for the calculation in some books, but I haven't found yet. I guess it's just MLE(Maximum Likelihood Estimation) after all. But, I don't know how to do that.

Last edited:
I don't like the stationarity assumption because I want to deal with a sequence even like this: 010100100100000000000000000000000110100101.

EnumaElish
I did a mistake. You're right EnumaElish. Any Q has it's own eigenvectors at least one. So your stationarity assumption will be okay. And it seems the best idea for my problem currently.