Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
Does the answer below correspond to what you were asking for? –  Did Apr 11 '11 at 17:27
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.