Transition probabilities in a finite state machine

Question

Assume I have a finite state machine and a bunch of tokens. Transitions happen every time a token is inserted. Transitions are based on the token (i.e. at state S, inserting a blue token would give a different result from, say, inserting a red token). There is one state designated as the 'goal'. How would I go about calculating the probability of reaching the goal for randomly throwing tokens to the machine?

Answer 1

Let $(X_n)_{n\ge 0}$ be our Markov chain, let $T$ be the set of all tokens and let token $a$ have transition matrix $P_a$. Then $\mathbb{P}(X_1=j|X_0=i,\text{next token is t})=(P_t)_{ij}$.

By the law of total probability $$\mathbb{P}(X_1=j|X_0=i)=\sum_{t\in T} (P_t)_{ij}\mathbb{P}(\text{next token is t}|X_0=i)$$

I hope this is what you are after. Then you just use this probability and the usual calculations of hitting probabilities.

Example

Let's say there are 4 states and 2 tokens (red, blue). The transition matrixes for the two tokens are

$$P_r=\begin{pmatrix} \frac{1}{2} & \frac{1}{4} & 0 & \frac{1}{4}\\ \frac{1}{2} & 0 & 0 & \frac{1}{2}\\ 0 & 0 & 1 & 0\\ 0&0&0&1 \end{pmatrix},P_b=\begin{pmatrix} \frac{1}{3} & \frac{2}{3} & 0 & 0\\ \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3}\\ 0 & 0 & 1 &0\\ 0&0&0&1 \end{pmatrix}$$ where the third and fourth states are absorbing and represent goal and failure respectively.

Let's say the probability of receiving a red token is $\frac{1}{2}$ if the current state is $1$ and $\frac{2}{3}$ if the current state is $2$. Then $$P=\begin{pmatrix} \frac{1}{2}\cdot \frac{1}{2}+\frac{1}{2}\cdot \frac{1}{3} & \frac{1}{2}\cdot \frac{1}{4}+\frac{1}{2}\cdot \frac{2}{3} & 0&\frac{1}{2}\cdot \frac{1}{4}\\ \frac{2}{3}\cdot \frac{1}{2}+\frac{1}{3}\cdot \frac{1}{3} & 0 & \frac{1}{3}\cdot \frac{1}{3} & \frac{2}{3}\cdot \frac{1}{2}+\frac{1}{3}\cdot \frac{1}{3}\\ 0 & 0 & 1&0\\ 0&0&0&1 \end{pmatrix}=\begin{pmatrix} \frac{5}{12} & \frac{11}{24} & 0&\frac{1}{8}\\ \frac{4}{9} & 0 & \frac{1}{9}& \frac{4}{9}\\ 0 & 0 & 1&0\\ 0&0&0&1 \end{pmatrix}$$

Now, let $h_i$ be the probability of hitting the goal (state $3$) given that the current state is $i$. Then $$h_3=1, h_4=0$$ $$h_1=\frac{5}{12} h_1+\frac{11}{24} h_2$$$$h_2=\frac{4}{9} h_1+\frac{1}{9}$$ And the solution to those equations is $h_1=\frac{11}{82},h_2=\frac{7}{41}$.