Probability of two algorithmically produced symbol streams matching over $n$ symbols I have two algorithmically generated streams. 
The first is just 1,2,3... repeated as many times as needed to fill the block of $n$ symbols in a trial, but it has memory of the sequence, i.e., for the next trial it will pick up where it left off.
The second selects from the set ${1,2,3}$ uniformly, except when the prior two symbols were the same, whereby it will then select uniformly from among the remaining two symbols. It too has memory of the prior trial, e.g. if the first symbol of a trial matches the last symbol of the last trial, the next symbol will be from the reduced set.
Both algorithms are run side-by-side/simultaneously, that is, when a trial is done, both have generated the same number $n$ symbols and retain state memory as needed, i.e, once the first trial is made, the algorithms will always have the memory of the last result of the last trial.
I'm interested in calculating the probability that for a given trial, both output the same stream of $n$ symbols, and I'm stuck - I'm not sure how to even approach this.
 A: In the first run, the special rule for two successive identical symbols is irrelevant, since a sequence can already no longer match the deterministic sequence when this rule gets invoked. Thus the probability is simply $\left(\frac13\right)^n$.
In the long run, the probability that a symbol in the second stream is the same as the previous symbol is given by the stationary distribution of a Markov chain:
$$
\pmatrix{p_=\\p_\neq}\quad\to\quad\pmatrix{0&\frac13\\1&\frac23}\pmatrix{p_=\\p_\neq}\;.
$$
The stationary distribution has $p_==\frac13p_\neq$ and thus $p_==\frac14$. Thus, in the long run, a run starts without restrictions with probability $p_\neq=\frac34$, and then has probability $\left(\frac13\right)^n$ to match, and starts with the restriction with probability $p_==\frac14$ and then has probability $\frac12\left(\frac13\right)^{n-1}$ to match, for a total of
$$
\frac34\left(\frac13\right)^n+\frac14\cdot\frac12\left(\frac13\right)^{n-1}=\frac98\left(\frac13\right)^n\;,
$$
so the restriction raises the probability by a factor $\frac98$.
Between the two cases (first run and long run), you can get more complicated results using recurrence relations.
