= Solution
At each index the two independent uniform symbols match with <probability> $p=k/k^2=1/k$. The match indicators are independent across indices. Consequently the waiting times between successive matches are independent geometric random variables on $1,2,\ldots$ with success <probability> $p$, and $S_m$ is their sum.
For one waiting time $G$, summing the <geometric series> gives $\mathbb Ee^{tG}=pe^t/[1-(1-p)e^t]$. Independence yields
$$
\boxed{M_{S_m}(t)=\left(\frac{e^t/k}{1-(1-1/k)e^t}\right)^m,\qquad
\mathbb ES_m=mk.}
$$
For $k>1$ the <moment-generating function> is finite for $t<\log(k/(k-1))$. When $k=1$, every index matches, $S_m=m$ deterministically and the formula reduces to $e^{mt}$ for every real $t$.
Back to article page
