= Solution
At a fixed index, <independence> and uniformity give
$$
p=P(X_s=Y_s)=\sum_{j=0}^{k-1}\frac1{k^2}=\frac1k.
$$
The match indicators are independent <Bernoulli trial>[Bernoulli trials]. Thus the waiting times between successive matches are independent <geometric distribution>[geometric] variables on $\{1,2,\ldots\}$ with success <probability> $p$. Their <moment-generating function> is
$$
\sum_{r=1}^\infty p(1-p)^{r-1}e^{tr}
=\frac{pe^t}{1-(1-p)e^t},
$$
provided $(1-p)e^t<1$. Since $S_m$ is the sum of $m$ such waiting times,
$$
\boxed{M_{S_m}(t)=\left(\frac{e^t}{k-(k-1)e^t}\right)^m,
\qquad\mathbb ES_m=mk.}
$$
For $k>1$, the finite domain is $t<\log(k/(k-1))$. For $k=1$, every index is a match, so $S_m=m$ deterministically and the <moment-generating function> is $e^{mt}$ for every real $t$.
Back to article page
