Transition probabilities in a finite state machine 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?
 A: 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}$.
