What is the convergence rate of this "infinite monkey"-type probability?

Question

Cross-posted from Math Stack Exchange, where it hasn’t received an answer yet:

Let $S$ be a finite set and $n,m\in\mathbb N$. Consider the process $R=(R_i)_{i\in\mathbb N}$ where all $R_i$ are iid uniformly distributed on $S$. I am trying to tackle the probability of the event \begin{equation} A_m(n):=\{\exists_{1\leq i<j\leq m+n}: (R_i,\dots,R_{i+n-1}) = (R_j,\dots,R_{j+n-1})\} \end{equation} as $m\to\infty$. It is straight forward to prove $\lim_{m\to\infty}\mathbb P(A_m(n)) = 1$, since the event "$(R_i,\dots,R_{i+n-1})=r$ infinitely often" constitutes a lower bound for every $r\in S^n$ and has probability $1$ using Borel-Cantelli.

I am now trying to find the rate of convergence of $\mathbb P(A_m(n))$ depending on $n$ but I am struggling to do so. It is clear that when $m< n$ the probability $\mathbb P(A_m(n))$ is rather small, since there necessarily would have to be an overlap with the two windows of length $n$. Moreover by the pigeonhole principle one can prove $\mathbb P(A_m(n))=1$ for $m$ large enough. However, I am interested in the convergence rate in between.

This question is related to the Infinite Monkey Theorem for which formulas for the expected hitting time of a certain word exist. But here I do not need to hit a specific word and I don't look at the expectation. Rather I am interested in hitting any word of length $n$ twice when hitting $n+m$ keys on the keyboard.

Context The question arises when looking at functions I deemed "autoregressive". See here. I am happy to provide more context if needed.

I appreciate any sort of help/reference/hint !

Answer 1

$\newcommand{\E}{\mathbb{E}}$ Here is a more detailed comment to explain things. For simplicity, let's consider the case when $S$ is fixed and $n$ is tending to infinity. Set $s = |S|$ As before, for $n,m$ let $X_{m}(n)$ be the number of pairs $1 \leq i < j \leq m$ for which you have $$(R_i,\ldots,R_{i+n-1}) = (R_j,\ldots,R_{j+n-1}).$$

First note that $$\E X \leq \binom{m}{2} s^{-n} $$ and so the action is really occurring when $m$ is like $\alpha s^{n/2}$ for some $\alpha$ (which we may allow to grow or shrink if we'd like). Let's discuss when $\alpha$ is constant, and the case when it grows will be analogous. To compute the variance, one of the best ways to do this is to write $$\mathrm{Var}(X) = \E(X(X-1)) + \E X - (\E X)^2\,.$$

When $\alpha$ is constant, it is not so bad to show $\E X \to \alpha^2 /2$. To handle $\E X(X-1)$, note that $X(X-1)$ is the number of pairs of pairs $(i_1,j_1)$, $(i_2,j_2)$ where the pairs are not identically equal for which we have the first displayed equation holds. This can then be handled by linearity of expectation once again, and it isn't so bad to show that $\E(X(X-1)) \to (\alpha^2 / 2)^2$ when $\alpha$ is constant. If $\alpha$ is growing, then a more detailed count of this expectation can be done, although the combinatorics seems potentially nasty depending on how much info you want.

To understand why it is Poisson in the limit when $\alpha$ is fixed, set $\lambda = \alpha^2 / 2$. To show Poisson convergence, the method moments states that you just need to show that for each $k$ you have $$\E X(X-1)(X-2)\cdots (X-(k-1)) \to \lambda^k\,.$$

This expectation can be interpreted as the expected number of $k$ pairs for which the first displayed equation holds simultaneously. The dominant term in the sum will be when the intervals do not overlap, and that will give you $\lambda^k$.