1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Aug 17 '21 at 7:19
  • $\begingroup$ 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? $\endgroup$ Aug 17 '21 at 7:29
  • 1
    $\begingroup$ @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? $\endgroup$
    – D.W.
    Aug 17 '21 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.