I have asked this question on stats.se.com but I did not receive an answer. Given is the description of a probabilistic finite state machine and I want to 'translate this' into a Markov process 'on it'. The input is (in the most simple case)

  • A finite set of states $S = \{s^{(1)}, ..., s^{(N)}\}$
  • A function $\Delta^d : S \times S \to [0,1]$ such that for every $s$, $\sum_{t \in S} \Delta^d(s,t) = 1$ (indicates the probability of moving from $s$ to $t$).
  • An initial distribution $I^d : S \to [0,1]$ such that $\sum_{t \in S} I^d(t) = 1$ (indicating the probability for the initial state).

We imagine this input as a probabilistic finite state machine that offers 'different runs through it'. A single concrete (infinitely long) run is a sequence $s = (s_n)_{n \in \mathbb{N}}$ where $s_n \in S$ for every $n$. In order to understand this process better we attempt to model these runs by outcomes of random variables $S = (S_n)_{n \in \mathbb{N}}$. The question is simple:

Can we construct $S_n$ concretely and if so, how?

My attempt:

Of course we could simply assume that there are infinitely many RV $S_n$ and then state assumptions like the markovian property $$p(s_n|s_1,...,s_{n-1}) = p(s_n|s_{n-1})$$ and the coupling between the $S_n$ and the input (for example, $p(s_1) = I^d(s_1)$ and if $s_m = s_n$ and $s_{m-1} = s_{n-1}$ then $p(s_n|s_{n-1}) = p(s_m|s_{m-1}) = \Delta^d(s_{n-1},s_n)$). However, we could also 'construct' these random variables (except for the first one) in a natural way: We simply follow the rules given by the input:

What the input actually wants to state is that $\Delta^d$ gives rise to a single random variable $\Delta : S \times \Omega \to S$ such that for every $s,t \in S$, $$P[\Delta(s,\cdot) = t] = \Delta^d(s, t)$$ i.e. $\Delta$ selects (in a random fashion) the next state given that the current state is $s$. This should philosophically be in line with the assumptions above because in some sense, $$''S_n|S_{n-1} = S_m|S_{m-1} = \Delta''$$ for all $m,n$.

We have a first random variable $S_1 : \Omega \to S$ and for this one we assume that $P(S_1=s_1) = I^d(s_1)$. Now for $S_2$ we construct it as $$S_2(\omega) = \Delta(S_1(\omega), \omega)$$ i.e. see what the first sampled state was and then follow the 'way of $\Delta$'.

Of course I want to see that these constructions are in line now. Hence I want to have $$p(s_2|s_1) = \Delta^d(s_1, s_2)$$ but all I get is $$p(s_2|s_1) = P[S_2=s_2|S_1=s_1] = \frac{P(\omega | \Delta(S_1(\omega), \omega) = s_2 ~\text{and}~ S_1(\omega)=s_1)}{I^d(s_1)}$$ and this is equal to the desired outcome $\Delta^d(s_1, s_2)$ iff. $$P[\Delta(s_1, \cdot) = s_2 ~\text{and}~ S_1=s_1] = \Delta^d(s_1, s_2) \cdot I^d(s_1) = P[\Delta(s_1, \cdot) = s_2] \cdot P[S_1=s_1]$$ but assuming that the random variables $\Delta(s_1, \cdot)$ ('close' to $S_2$) and $S_1$ are independent is somewhat like assuming that $S_2$ and $S_1$ are independent (which should not be true!).

Am I modelling it in a wrong way?


The Markov chain construction you want you should able to find in any text on Markov chains/processes or even in texts on probability/stochastic processes in general. Yet, it is simpler to give the construction than to look for it in the literature.

Indeed, let $p_0:=I^d$ and $p:=\Delta^p$, the "initial distribution" and the transition matrix, respectively. Let $S_0$ be any random variable (r.v.) such that $P(S_0=s)=p_0(s)$ for all $s\in S$. For each natural $n$ and each $s\in S$, let $X_{n,s}$ be a r.v. such that $S_0,(X_{1,s})_{s\in S},(X_{2,s})_{s\in S},\dots$ are independent and $P(X_{n,s}=t)=p(s,t)$ for all natural $n$ and all $s$ and $t$ in $S$. Finally, with $S_0$ already defined, define the r.v. $S_n$ for all natural $n$ recursively by the condition that $S_n=X_{n,s}$ on the event $\{S_{n-1}=s\}$, for each $s\in S$.

Then for any natural $n$ and any $s_0,\dots,s_n$ in $S$, \begin{multline*} P(S_n=s_n|S_0=s_0,\dots,S_{n-1}=s_{n-1}) =\frac{P(S_0=s_0,\dots,S_{n-1}=s_{n-1},S_n=s_n)}{P(S_0=s_0,\dots,S_{n-1}=s_{n-1})} \\ =\frac{P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1},X_{n,s_{n-1}}=s_n)} {P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})} =P(X_{n,s_{n-1}}=s_n) \end{multline*} and, similarly, \begin{multline*} P(S_n=s_n|S_{n-1}=s_{n-1}) =\frac{P(S_{n-1}=s_{n-1},S_n=s_n)}{P(S_{n-1}=s_{n-1})} \\ =\frac {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1},X_{n,s_{n-1}}=s_n)} {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})} \\ =\frac {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})\,P(X_{n,s_{n-1}}=s_n)} {\sum_{s_0,\dots,s_{n-2}}P(S_0=s_0,X_{1,s_0}=s_1,\dots,X_{n-1,s_{n-2}}=s_{n-1})} \\ =P(X_{n,s_{n-1}}=s_n). \end{multline*} So, \begin{equation} P(S_n=s_n|S_0=s_0,\dots,S_{n-1}=s_{n-1})=P(S_n=s_n|S_{n-1}=s_{n-1})=P(X_{n,s_{n-1}}=s_n) =p(s_{n-1},s_n), \end{equation} so that $S_0,S_1,\dots$ is indeed a Markov chain with "initial distribution" $p_0$ and transition matrix $p$.

  • $\begingroup$ So, essentially the answer is 'yes, assume that $\Delta(s_1,\cdot)$ and $S_1$ are independent'... But I see now that this makes sense: $s_1$ is just any symbol and in fact we want $\Delta(s, \cdot)$ to be independent from $S_1$ (or $S_0$ depending where we start to count) because the 'chance of taking any transition' should not be influenced by the state before... it is always the same independently of what happened beforehand. $\endgroup$ – Fabian Werner Feb 15 '18 at 8:34
  • $\begingroup$ Also, the idea of taking an infinite amount of iid copies of the transition variable is better because it naturally resembles the transitions (the outcome of the $n$-th transition variable is the decision of the finite state automata at the $n$-th point in time) and it also allows us to collect all independence assumptions at once and then define all the state variables at once (in contract to my approach where one needs to assume, define, addume, define, etc). THANKS!!! I understand this much better now :-) $\endgroup$ – Fabian Werner Feb 15 '18 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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