MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a markov chain with finite space { 0,1,..n} with transition probability matrix whose entries are $P_{ij}$. Let

$f_{ij}^n$ = probability that starting from state $i $ it goes to state $j$ first time.

Question 1. What are the necessary and sufficient condition arbitrary $a_{ij}^{n}$ needs to satisfy to be valid $f_{ij}^{n}$ of some markov chain ?

Qustion 2. If existence of such a markov chain is shown, can we calculate $P_{ij}$ given valid $f_{ij}^n$ ? ( I mean, is there any algorithm to calculate?)

share|cite|improve this question
Does the answer below correspond to what you were asking for? – Did Apr 11 '11 at 17:27

Re 2, for $n=1$, $P_{ij}=f^1_{ij}$ for every $i\ne j$ and $1-P_{ii}$ is the sum of $f^1_{ij}$ over $j\ne i$, hence one recovers trivially $P$ from $f^1=(f^1_{ij})_{ij}$.

Re 2 again, on the contrary, there is no hope to recover $P$ from $f^n=(f^n_{ij})_{ij}$ in general, for any given $n\ge2$. For example, the two (deterministic) one-step rotations on the discrete circle with $2n$ vertices, clockwise and counterclockwide, yield the same matrix $f^n$ although their transition matrices $P$ are different.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.