Let $(d, m) \in \mathbb{N}^2$, and let $X_1, \dots, X_m$ be drawn identically uniformly and independently over $[d]$. For $(i,j,k) \in [d]^3$ we define the event $S_{ijk}$ in the following way $$S_{ijk} = \left\{ \sum_{t = 2}^{m} \boldsymbol{1}\left\{ X_{t-1} = i \right\} \cdot \boldsymbol{1}\left\{ X_{t} = j \right\} = 1 \text{ and } \sum_{t = 2}^{m} \boldsymbol{1}\left\{ X_{t-1} = i \right\} \cdot \boldsymbol{1}\left\{ X_{t} = k \right\} = 1 \right\}$$ I am interesting in finding a closed form expression for $\mathbf{P}(S_{ijk})$, the probability of that event.
Please correct me if I am wrong, but here are a few elements I gathered so far:
- For $t \in [2 \dots m]$ the $(X_{t-1}, X_t)$ are uniformly distributed over $[d] \times [d]$, although (as @did pointed out) they are not independent.
- The value of $\mathbf{P}(S_{ijk})$ should be independent of $i$.
- It seems reasonable to split into two cases depending on whether $j = k$ or not.