Try it from a phone: Stochastic timer.
Introduction
I wanted an exercise timer which is able to randomly plan max efforts into a cardio session whilst respecting recovery time. That is, I wanted it both to be non-deterministic whilst avoiding stacking sprints together.
A simple model is a Bernoulli process with \(p_0\) deciding the probability
of mode \(A\) (max effort) versus mode \(B\) (steady effort). We can break the
exercise schedule into \(10\) second blocks, simulate out a sequence and merge
equal modes into spans. For example, say we wanted to spend \(10\%\) of the
time sprinting, let \(p_0=0.1\), here is a sample BBBBBBABBBBBBABBBBBB which
would result in the following schedule B (60), A(10), B(60), A(10), B(60).
The balance is not deterministic, but sampling with replacement of
\((A,B)\) at rates \((p_0, 1-p_0)\) will eventually reach \(p_0\) fraction of \(A\)
almost surely.
The problem is that the local dynamics can be weird. For example, with
\(p_0=0.25\), a plan like A(25) B(100) is just as likely as any other local
distribution, and for longer sessions locally weird schedules become more
likely.
To improve this, I wanted to make \(p_t\) dependent on the mode selected at \(t-1\). That is, selecting \(A\) at \(t-1\) should make selecting mode \(B\) more likely at \(t\), and vice-versa. The rest of this blog post describes a particular solution to this problem.
Updating \(p_0\)
How should we set \(p_{t+1} \mid A_t\) and \(p_{t+1} \mid B_t\)? Directly adding to or multiplying \(p_t\) will lead to overflows in one or both cases without clipping, so it makes sense to use a sigmoid transform such that \(p_t = \sigma(x_t)\). Then, we can safely have two parameters \(\alpha < 0 < \beta\) such that \(p_{t+1} \mid A_t = \sigma(x_t + \alpha)\) and \(p_{t+1} \mid B = \sigma(x_t + \beta)\).
What fraction of \(A\) do \(\alpha,\beta\) imply?
The \(\alpha\), \(\beta\) parameters are abstract and would be difficult to set directly, so it is helpful to re-parameterise the model in terms of something intuitive such as the long term fraction of \(A\) implied by \(\alpha,\beta\). At every step \(t\), the probability of \(A\) is \(\sigma(x_t)\), and therefore the expected count over \(n\) steps is just \(N_A = \sum_{t=0}^n \sigma(x_t)\), thus the expected fraction is \(p^\star = N_A / n\).
If we write down an expression for \(x_n = x_0 + N_A \alpha + (n-N_A)\beta\) and reorder to \(\frac{x_n - x_0}{n} = p^\star \alpha + (1-p^\star)\beta\), we note that as \(n \to \infty\), if \(\frac{x_n - x_0}{n} \to 0\), then straightforwardly \(p^\star \approx \frac{\beta}{\beta-\alpha}\).
\(\frac{x_0}{n} \to 0\) is certain since \(x_0\) is a constant. What remains is to reason about whether \(\frac{x_n}{n}\) converges to infinity or zero. Lets attempt a proof by contradiction. The cases to cover are (1) \(\frac{x_n}{n} \to \pm\infty\) , (2) \(\frac{x_n}{n} \to c, c \ne 0\) and (3) non-convergence. If all can be shown to lead to contradiction, it must be that case that \(\frac{x_n}{n} \to 0\).
Regarding (1) \(x_n \le |x_0| + n \max(|\alpha|,|\beta|)\), so \(\frac{x_n}{n} \le \frac{|x_0|}{n} + \max(|\alpha|,|\beta|)\), therefore \(\frac{x_n}{n} \to \infty\) is impossible.
Regarding (2) say \(\frac{x_n}{n} \to c, c>0\) then certainly \(x_n \to +\infty\), but then \(\sigma(x_n) \to 1\), which means that mode \(A\) occurs asymptotically all the time, and the average increment tends to \(\alpha < 0\): a contradiction given \(c > 0\). The same argument can be made conversely for \(x_n \to -\infty\).
I needed help from an LLM regarding (3): If \(\frac{x_n}{n}\) failed to converge to zero, then for some \(\epsilon > 0\), \(x_n\) would have to exceed \(\pm\epsilon n\) infinitely often. Repeated crossings of either boundary require events whose probabilities decrease geometrically, so infinitely many crossings have probability zero. Nor can the process remain beyond either boundary, because there the corrective event becomes overwhelmingly likely and drives it back. Hence \(\frac{x_n}{n} \to 0\) almost surely.
What about non-determinism?
Given \(p^\star \approx \frac{\beta}{\beta-\alpha}\) there are infinitely many \(\alpha,\beta\) values which will produce the same result. Intuitively, small absolute differences between offsets will cause smaller changes at \(p_t\) thus preserving randomness whilst large values are more likely to compel the next symbol. Lets formalise this.
At the most random setting, the target \(A\) fraction is just a random Bernoulli process, which we can achieve by setting \(p^\star = \sigma(x_0),\alpha=\beta=0\). Meanwhile, at the least random setting, we want the mode realisation to be sequential. For example, if mode \(A\) should occur at a rate of \(0.25\) then the local pattern should look like \(ABBB\) or \(BABB\); most of the time. We can achieve this as follows. For every \(A\) occurrence, we’d like \(\frac{1-p^\star}{p^\star}\) \(B\)s, so we set \(\alpha = \frac{-u(1-p^\star)}{p^\star}\), \(\beta = u\), with \(u\) such that \(\sigma(x_0 - u) = 0.0001\). For example, if we wanted \(3\) \(B\)s for every \(A\) we would set \(x_0 =logit(0.25)\) and \(\alpha=-3u ,\beta=u\) with \(u_{max}=logit(0.25)-logit(0.0001)\). Since every \(u_{max}\) is calculated to make the probability of \(B\) very likely (\(0.9999\)), every \(\alpha\) update will require \(3\) \(\beta\) updates to undo it and return to \(x_t=x_0\).
A simple way to graduate between random and locally deterministic is to declare a variable \(0 \le d \le 1\) and use it to scale \(P(A_t \mid x_t = x_0 - u)\) between \(p^\star\) (random) and \(0.0001\) (locally deterministic). We can set \(u\) such that \(\sigma(x_0 - u) = p^\star(1-d) + 0.0001d\) which maintains the extremes whilst graduating between them for intermediate values of \(d\).
Final parameters
The fraction of mode \(A\) is set by \(0 < p^\star < 1\) and the level of determinism is controlled by \(0 \le d \le 1\).
Completing the app
All that remains is to simulate the process as parameterised above on-demand, and merge repeating modes to create perpetual stochastic mixed effort exercise schedule with mathematical guarantees. You can try the PWA app here (optimised for mobile).