# Why does random noise in recurring task periods result in uniform period offsets?

I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $$10n$$ minutes from now for all positive $$n$$. If instead I choose 50/50 between ten minutes and ten minutes plus one second, eventually all offsets (in seconds) relative to the start of a ten-minute period becomes equally likely (or rather we converge towards that), according to my simulations. Why is that?

Once more, with formality:

Let $$a_{0,0} = 1$$ and $$\{a_{1,0}, \ldots, a_{n-1,0}\} = \{0\}$$. (Think of each $$a_{i,0}$$ as representing one minutes within the hour; its value is the probability of the task running during that minute.)

Let some offsets $$D \subseteq \{0, \ldots, n\}$$ be given, with $$D$$ containing at least one pair of numbers $$d_1$$ and $$d_2$$ such that $$gcd(d_2 - d_1, n) = 1$$. (The offsets are uniformly sampled gaps between two successive runs of the task.)

Let $$a_{i,t+1} = \frac{1}{\|D\|} \cdot \sum_{\delta \in D} a_{i-\delta,t}$$

Conjecture: $$\forall i \in \{0, \ldots, n-1\}: \lim_{t \rightarrow \infty} a_{i,t} = \frac{1}{n}$$

In other words, if we interpret the $$a_{i,*}$$ for each $$t$$ as a discrete probability distribution, it converges towards the uniform distribution on $$\{0, \ldots, n-1\}$$ as $$t$$ increases.

Is this true? How does one go about proving this? Is it more true or easier to prove if $$D$$ is restricted to be an interval?

This basically comes down to a fact about what happens when you take a normally distributed random variable (with large variance) and reduce it modulo 10.

Let $$X_i$$ denote the additional offset (in minutes) in the $$i$$th iteration compared to the previous iteration. After $$n$$ iterations, let $$Y=X_1+\dots+X_n$$. Then $$Y \bmod 10$$ represents the offset of the last iteration, relative to the next lowest multiple of 10 minutes.

The $$X_i$$ are iid, so by the Central Limit Theorem, $$Y$$ is approximately Gaussian with mean $$n/120$$ and standard deviation $$\sqrt{n}/2$$.

Now, when $$Z \sim \mathcal{N}(n/120,\sqrt{n}/2)$$ and $$\sqrt{n}/2$$ is much larger than 10, $$Z \bmod 10$$ is approximately uniformly distributed. I don't have a simple intuitive explanation for this, but if you want a very crude intuition, you can very roughly approximate $$Z$$ as distributed uniformly at random on the range $$[n/120-\sqrt{n}/2,n/120+\sqrt{n}/2]$$, and then if you take the uniform distribution on such a large interval and reduce it modulo $$10$$, the result will be approximately uniformly distributed. I realize this is not likely to be a convincing proof.

• I had noticed that if $D = \{k, k+1\}$ you see binomial distributions the first few ($n$?) iterations. The CLT had come to mind, but I didn't know how to get from converging-to-Gaussian to converging-to-uniform, exactly the step where you appeal to intuition. Do you know of a rigorous proof of that step? Aug 17 '21 at 7:19
• Here's my first idea: if you have a derived continuous distribution $Y_n$ with finite mean and variance that's an increasing function of $n$, maybe with more constraints, by choosing $n$ large enough the $\textrm{mod}$ buckets become arbitrarily fine grained relative to $Y_n$. Since $Y_n$ is continuous the differences across neighboring buckets can be made arbitrarily small by making the buckets smaller (and the convergence gap to Z can be made arbitrarily small), therefore we can get arbitrarily close to a uniform. Does this work, if formalized? Do I need uniform continuity? Aug 17 '21 at 7:29
• @JonasKölker, I don't know of a formal proof that "Gaussian mod m is approximately uniform when m is small compared to the standard deviation of the Gaussian". Perhaps you could ask for that on Math.SE?
– D.W.
Aug 17 '21 at 16:06