What is the probability of a symbol occurring after another in a stream of symbols Suppose we have a message M (stream of symbols), that is comprised of finite individual symbols let's say A, B, C, ... and each symbol has a known probability of occurrence and is independent of the other symbols.
The question is, what is the probability of one symbol occurring after another in a sample drawn from the message's distribution. for example, what is the probability of B occurring right after A in the message: M = "AABBBBCCACDD".
In other words, what is the probability of event "AB" or any other two symbols for that matter like "AC", "Ad", etc in the stream/message
 A: Let $X_1X_2...X_n$ be the string of $n$ independent random letters, and let $E_i$ be the event $X_iX_{i+1}=AB$ for $i\in\{1,\ldots,n-1\}.$ Then $p:=P(E_i)=p_Ap_B,$ and the probability that at least one of the $E_i$ occur in the random string is, by inclusion-exclusion:
$$\begin{align}&P\left(\bigcup_{i=1}^{n-1}E_i\right)\\[2ex]
&=\sum_{i=1}^{n-1} P(E_i)-\sum_{i=1}^{n-3}\,\sum_{j=i+2}^{n-1}P(E_iE_j)+\sum_{i=1}^{n-5}\,\sum_{j=i+2}^{n-3}\,\sum_{k=j+2}^{n-1}P(E_iE_jE_k)-\ldots\\[2ex]
&\quad\quad\quad ... +(-1)^{s+1}P(E_t..E_{n-5}E_{n-3}E_{n-1})\tag{1}\\[2ex]
&\quad\quad\quad\quad\quad\quad \text{where $s={\left\lfloor{n/2}\right\rfloor}\ $ and $\ t=1$ if $n$ is even, else $t=2$}\\[2ex]
&=p\sum_{i=1}^{n-1}1 -p^2\sum_{i=1}^{n-3}\,\sum_{j=i+2}^{n-1}1+p^3\sum_{i=1}^{n-5}\,\sum_{j=i+2}^{n-3}\,\sum_{k=j+2}^{n-1}1-\ldots +(-1)^{s+1}p^{s}\tag{2}\\[2ex] 
&=\sum_{k=1}^{\left\lfloor n/2\right\rfloor} (-1)^{k+1} c_k\,p^k\tag{3}
\end{align}$$
where the first few coefficients are found by direct computation to be as follows:
$$\begin{align}
c_1 &=n-1=\binom{n-1}{1}\\[2ex]
c_2 &={n^2 - 5 n + 6\over 2}=\binom{n-2}{2}\\[2ex]
c_3 &={n^3 - 12 n^2 + 47 n -60\over 6}=\binom{n-3}{3}\\[2ex]
\ldots
\end{align}$$
leading to
$$P\left(\bigcup_{i=1}^{n-1}E_i\right)=\sum_{k=1}^{\left\lfloor n/2\right\rfloor} (-1)^{k+1} \binom{n-k}{k}\,p^k.$$
Here's a plot showing the behavior as a function of $p:=p_Ap_B$, for various string-lengths $n$:

Note that always $p_Ap_B\in[0,1/4],$ because we must have $0\le p_A+p_B\le 1,$ i.e., $0\le p_Ap_B\le p_A(1-p_A)\le 1/4.$

Explanatory example ($n=6$):
Applying inclusion-exclusion, we must first add the probabilities of the following $5$ events $E_i$, where places with a dot can be any letter in the alphabet:
1   AB....
2   .AB...
3   ..AB..
4   ...AB.
5   ....AB

Note: $\binom{n-1}{1}=\binom{5}{1}=5$ is the number of ways to place $1$ pair $AB$ among $n$ positions.
This totals $5p$, from which we must then subtract the sum of probabilities of the following $6$ events of form $E_iE_j$:
1'  ABAB..
2'  AB.AB.
3'  AB..AB
4'  .ABAB.
5'  .AB.AB
6'  ..ABAB

Note: $\binom{n-2}{2}=\binom{4}{2}=6$ is the number of ways to place $2$ pairs $(AB, AB)$ without overlap among $n$ positions.
The running total is now $5p-6p^2$, to which we must add the sum of probabilities of the following $1$ event:
1'' ABABAB

Note: $\binom{n-3}{3}=\binom{3}{3}=1$ is the number of ways to place $3$ pairs (AB, AB, AB) without overlap among the $n$ positions.
Thus, the final total probability is $5p-6p^2+p^3.$
