Paths
Random walks one step at a time — lazy walks, barriers, gambler's ruin in closed form, the Brownian bridge, betting systems, running extremes and path statistics.
This module covers discrete processes whose state is a position and whose step is an increment: the simple and lazy random walk, walks stopped or clamped at barriers, the Brownian bridge, the doubling betting system, and the running high and low of a walk. Beside the step functions sit the closed forms that let a simulation be checked rather than trusted: the gambler’s ruin probability and expected duration, the variance of a bridge, and the reflection principle.
Conventions. Randomness comes from the caller as a stream of draws: u is a vector of uniforms in \([0, 1)\) (or z of standard normals for the bridge) and k is the index of the draw used at this step, counting from zero. A step is a mask, not a branch: \(2[u_k < p] - 1\) is \(+1\) with probability \(p\) and \(-1\) otherwise. A process that must remember several quantities carries them in one small vector — the running extremes carry [position, high, low] and the betting book carries [fortune, bet] — and these vectors start as zeros. In a process declaration (see the Walk, Lazy, Barrier, Bridge, Wager and Extremes sample models) the draws come from the declared stream and the trajectory is generated from the step.
For gambler’s ruin, a is the distance from the starting point down to the lower barrier and b the distance up to the upper barrier; ruin means reaching the lower one first.
open Prelude.Paths
One step of a walk
A simple random walk moves \(+1\) with probability \(p\) and \(-1\) otherwise. A lazy walk first stays put with probability hold, and uses the same single draw to decide the direction when it does move: \([0, \text{hold})\) means stay, and the rest of the interval is split in the proportion \(p\) to \(1 - p\).
stepOf
stepOf(u, k, p) · u uniform draws vector n · k draw index scalar · p probability of an up-step scalar → increment +1 or −1
Let \(u = (u_0, \dots, u_{n-1}) \in [0, 1)^n\) be independent uniform draws (positions counted from zero), let \(k \in \{0, 1, \dots, n-1\}\) be the index of the draw used at this step, and let \(0 \le p \le 1\). Then
\[\operatorname{stepOf}(u, k, p) = 2\,[\, u_k < p \,] - 1 \in \{-1, +1\} .\]The increment of a simple random walk at step k: \(+1\) when \(u_k < p\), \(-1\) otherwise.
Intuition A coin flip turned into a move: heads \(+1\), tails \(-1\). Adding these up gives the position of the walker. The draw is looked up by its index k, so step \(k\) always reads the same number from the stream and a run is reproducible.
Use it when you simulate a \(\pm 1\) random walk: a gambler’s fortune at unit stakes, a price that ticks up or down, a particle on a line, a running score over repeated trials. The average drift per step is \(2p - 1\). For a walker that sometimes stands still use lazyOf; to stop or bound the walk, feed the increment to frozen or clamped.
random-walkssimulation
def stepOf(u, k, p) ≔ 2 · (elementAt(u, k) < p) − 1
lazyOf
lazyOf(u, k, p, hold) · u uniform draws vector n · k draw index scalar · p probability of up given a move scalar · hold probability of standing still scalar → increment −1, 0 or +1
Let \(u \in [0, 1)^n\) be independent uniform draws, \(k \in \{0, \dots, n-1\}\) a draw index, \(0 \le p \le 1\) the probability of moving up given a move, and \(0 \le h \le 1\) (the argument hold) the probability of standing still. Then
The increment of a lazy walk at step k: 0 with probability hold, otherwise \(+1\) with probability \(p\) and \(-1\) with probability \(1 - p\). One draw decides both questions.
Intuition A walker who sometimes hesitates. Pausing slows the walk down without changing which way it tends to go, and it breaks the strict odd/even rhythm of a simple walk (which alternates between even and odd positions), so the walk’s distribution can settle.
Use it when time runs in fixed ticks but most ticks change nothing: a price that often does not trade, a queue that is quiet most seconds, a player who can pass. It is also the standard way to make a chain aperiodic before studying its long-run behaviour. The mean step is \((1 - h)(2p - 1)\), and hold = 0 gives back stepOf.
random-walkssimulationlong-run-behaviour
def lazyOf(u, k, p, hold) ≔ moving(u, k, hold) · (2 · upward(u, k, p, hold) − 1)
Building blocks
moving(u, k, hold)— Let \(u \in [0, 1)^n\), \(k \in \{0, \dots, n-1\}\) and \(0 \le h \le 1\). Then \(\operatorname{moving}(u, k, h) = [\, u_k \ge h \,]\). 1 when draw k is at leasthold, so the walk moves.upward(u, k, p, hold)— Let \(u \in [0, 1)^n\), \(k \in \{0, \dots, n-1\}\), \(0 \le p \le 1\) and \(0 \le h \le 1\). Then \(\operatorname{upward}(u, k, p, h) = [\, u_k < h + (1 - h)\,p \,]\). 1 when draw k falls below hold + (1 − hold)·p, so a move goes up.
Barriers
A reflecting barrier clamps the position and the walk keeps moving along the wall; an absorbing barrier freezes it for good once it touches either end. For a walk started \(a\) above the lower barrier and \(b\) below the upper one, with \(r = q/p\) and \(q = 1 - p\), the probability of reaching the upper barrier first and the expected duration of the game are
\[P(\text{win}) = \frac{r^a - 1}{r^{a+b} - 1}, \qquad E[T] = \frac{a - (a + b)\,P(\text{win})}{1 - 2p}\]At \(p = \tfrac12\) both are \(0/0\); the fair game has its own forms, \(P(\text{ruin}) = b/(a+b)\) and \(E[T] = ab\), and the combined functions choose between the two.
In the statements below, \(\operatorname{guarded}(v) = v + [\,\lvert v \rvert < 10^{-300}\,] \cdot 10^{-300}\) is the divisor guard listed under the building blocks of this section.
clamped
clamped(x, low, high) · x position scalar or tensor · low lower barrier scalar · high upper barrier scalar → clamped position
Let \(x\) be a position (a real, or a tensor of positions taken entrywise) and let \(L \le H\) (the arguments low and high) be the barriers. Then
The position held inside \([L, H]\): a reflecting barrier.
Intuition Walls that stop you without ending the game: a walker pushed against a wall stays on it until a step takes it back inside. The position saturates at the limit instead of passing it.
Use it when a quantity has hard limits but keeps evolving: stock in a warehouse of fixed capacity, a battery’s charge, a buffer’s occupancy, a score capped at both ends. Apply it after the move, clamped(x + d, low, high); it works entrywise on tensors. The wall is “sticky” (the walker can sit on it), not a mirror. When touching a limit should end the walk, as bankruptcy does, use frozen.
bounded-processessimulation
def clamped(x, low, high) ≔ max(low, min(high, x))
inside
inside(x, low, high) · x position · low lower barrier · high upper barrier → flag 1 or 0
Let \(x \in \mathbb{R}\) be a position and \(L < H\) (the arguments low and high) the barriers. Then
1 while the position is strictly between the barriers, 0 once it has reached either.
Intuition “Is the game still on?” as a number: 1 while strictly between the barriers, 0 once on or past either. Multiplying by it replaces an if.
Use it when you mask increments (as frozen does), measure how long a simulated game lasted by summing the flag along a trajectory (to compare with durationOf), or mark which runs are still alive at a given step. The inequalities are strict, so a position exactly on a barrier counts as finished.
hitting-timesabsorption-analysis
def inside(x, low, high) ≔ (x > low) · (x < high)
frozen
frozen(x, low, high, d) · x position · low lower barrier · high upper barrier · d increment → next position
Let \(x \in \mathbb{R}\) be a position, \(L < H\) (the arguments low and high) the barriers, and \(d \in \mathbb{R}\) the increment. Then
One step of a walk with absorbing barriers: the increment d is applied while the walk is strictly inside, and ignored once it has touched a barrier.
Intuition An absorbing barrier: once the walker touches either end, every later increment is ignored and the position stays put for good, like a gambler who is broke or has reached the target and walked away.
Use it when you simulate a game that ends at a boundary: gambler’s ruin, a firm that goes bankrupt, a sequential trial stopped at an efficacy or futility bound. Over many runs, the share that end at low should match ruinOf. The position is not clamped, so an increment larger than the distance left carries the walker past the barrier before it freezes; with \(\pm 1\) steps and integer barriers that cannot happen. For walls that do not end the walk, use clamped.
absorption-analysissimulationrandom-walks
def frozen(x, low, high, d) ≔ x + inside(x, low, high) · d
biasedWin
biasedWin(p, a, b) · p up probability scalar, not ½ · a distance to the lower barrier · b distance to the upper barrier → probability scalar
Let \(0 < p < 1\) with \(p \ne \tfrac12\) be the probability of an up-step, let \(a, b \in \mathbb{N}\) be the distances to the lower and upper barriers, and let \(r = \operatorname{odds}(p) = (1 - p)/\operatorname{guarded}(p)\). Then
\[\operatorname{biasedWin}(p, a, b) = \frac{r^{a} - 1}{\operatorname{guarded}\big(r^{a+b} - 1\big)} .\]The probability of reaching the upper barrier before the lower one, for \(p \ne \tfrac12\).
Intuition A small edge compounds over a long game. With \(r = q/p\), the chance of reaching the top first moves exponentially in the distances: with \(p > \tfrac12\) the top becomes nearly certain even from far below, and with \(p < \tfrac12\) a distant target becomes nearly hopeless.
Use it when you want the chance of hitting a profit target before a stop-loss with a known per-trade win rate, reaching a goal at a casino with a house edge, or a population reaching a threshold before it dies out. It is only valid for \(p \ne \tfrac12\): at exactly ½ it returns 0, which is wrong. For any \(p\) use 1 − ruinOf(p, a, b).
absorption-analysisrisk-measurement
def biasedWin(p, a, b) ≔ (odds(p) ^ a − 1) / guarded(odds(p) ^ (a + b) − 1)
biasedRuin
biasedRuin(p, a, b) · p up probability scalar, not ½ · a distance to the lower barrier · b distance to the upper barrier → probability scalar
Let \(0 < p < 1\) with \(p \ne \tfrac12\) and \(a, b \in \mathbb{N}\) the distances to the lower and upper barriers. Then
\[\operatorname{biasedRuin}(p, a, b) = 1 - \operatorname{biasedWin}(p, a, b) .\]The probability of reaching the lower barrier first, \(1 - P(\text{win})\), for \(p \ne \tfrac12\).
Intuition Whatever does not end at the top ends at the bottom. Its lesson is how a slight disadvantage turns into near-certain ruin: at \(p = 0.4\), a player 3 units from ruin chasing a gain of 7 goes broke about 96% of the time.
Use it when you need the risk of ruin for a bettor, trader or insurer with a known, non-zero edge between two stopping levels. It is the raw biased formula: at exactly \(p = \tfrac12\) it returns 1 instead of \(b/(a+b)\). Prefer ruinOf, which gives the same number off ½ and the right one at ½.
risk-measurementabsorption-analysis
def biasedRuin(p, a, b) ≔ 1 − biasedWin(p, a, b)
fairRuin
fairRuin(a, b) · a distance to the lower barrier · b distance to the upper barrier → probability scalar
Let \(a, b \in \mathbb{N}\) be the distances to the lower and upper barriers. Then
\[\operatorname{fairRuin}(a, b) = \frac{b}{\operatorname{guarded}(a + b)} .\]The ruin probability of a fair game, \(b / (a + b)\).
Intuition In a fair game the expected fortune never changes, so the chance of finishing at the top times the width \(a + b\) must equal the starting cushion \(a\). Ruin is what is left: the more ambitious the target relative to the cushion, the likelier ruin.
Use it when the game has no edge: coin-flip bets, a symmetric random walk exiting a band, two players with \(a\) and \(b\) chips betting one chip at a time (it is the chance that the first loses everything). It takes no \(p\); when the game might be biased, use ruinOf.
risk-measurementabsorption-analysis
def fairRuin(a, b) ≔ b / guarded(a + b)
ruinOf
ruinOf(p, a, b) · p up probability scalar · a distance to the lower barrier · b distance to the upper barrier → probability scalar
Let \(0 < p < 1\) be the probability of an up-step and \(a, b \in \mathbb{N}\) the distances to the lower and upper barriers. Let \(\epsilon = [\, \lvert p - \tfrac12 \rvert < 10^{-12} \,]\) and \(p' = p + 0.01\,\epsilon\). Then
\[\operatorname{ruinOf}(p, a, b) = \epsilon \cdot \operatorname{fairRuin}(a, b) + (1 - \epsilon) \cdot \operatorname{biasedRuin}(p', a, b) .\]The probability of ruin for any \(p\): the fair form when \(p\) is within \(10^{-12}\) of ½, the biased form otherwise. Use this rather than biasedRuin unless \(p\) is known to be unfair.
Intuition A dispatcher: the fair formula at ½, the biased one elsewhere. Both are computed and a mask picks one, with \(p\) nudged off ½ on the discarded side so it cannot produce a NaN that would poison the result.
Use it when you need a ruin probability and do not want to special-case the fair game: risk of ruin for a strategy with win rate \(p\) and unit stakes, the chance a cash buffer runs out before a target is met. It assumes \(\pm 1\) steps and whole-number distances. Values of \(p\) very close to ½ but outside the \(10^{-12}\) window use the biased formula, which is then a ratio of tiny numbers and loses some digits.
risk-measurementabsorption-analysisrandom-walks
def ruinOf(p, a, b) ≔ evenOdds(p) · fairRuin(a, b) + (1 − evenOdds(p)) · biasedRuin(clear(p), a, b)
fairDuration
fairDuration(a, b) · a distance to the lower barrier · b distance to the upper barrier → expected steps scalar
Let \(a, b \in \mathbb{N}\) be the distances to the lower and upper barriers. Then
\[\operatorname{fairDuration}(a, b) = a\,b .\]The expected length of a fair game.
Intuition A fair walk covers a distance \(d\) in about \(d^2\) steps, not \(d\), because it wanders back and forth. \(ab\) is that rule for a two-sided band, and it is largest when the walk starts in the middle.
Use it when you need the expected number of rounds until a fair game ends, or how long a symmetric random quantity stays inside a band, such as a price moving by ticks between two trigger levels. It is a mean only. For a game with an edge use durationOf.
hitting-timesrandom-walks
def fairDuration(a, b) ≔ a · b
biasedDuration
biasedDuration(p, a, b) · p up probability scalar, not ½ · a distance to the lower barrier · b distance to the upper barrier → expected steps scalar
Let \(0 < p < 1\) with \(p \ne \tfrac12\) and \(a, b \in \mathbb{N}\) the distances to the lower and upper barriers. Then
\[\operatorname{biasedDuration}(p, a, b) = \frac{a - (a + b)\,\operatorname{biasedWin}(p, a, b)}{\operatorname{guarded}(1 - 2p)} .\]The expected length of a biased game.
Intuition Wald’s identity: the expected final gain equals the drift per step, \(2p - 1\), times the expected number of steps. The final gain is \(b\) on a win and \(-a\) on ruin, so dividing its expectation by the drift gives the game length. A strong drift ends the game fast.
Use it when you want the expected length of a game with an edge: rounds until a disadvantaged gambler busts or reaches a target, trades until a stop-loss or take-profit triggers. Valid only for \(p \ne \tfrac12\): at exactly ½ the guarded divisor makes it astronomically large. Prefer durationOf, which handles both cases.
hitting-timesrandom-walks
def biasedDuration(p, a, b) ≔ (a − (a + b) · biasedWin(p, a, b)) / guarded(1 − 2 · p)
durationOf
durationOf(p, a, b) · p up probability scalar · a distance to the lower barrier · b distance to the upper barrier → expected steps scalar
Let \(0 < p < 1\) and \(a, b \in \mathbb{N}\) the distances to the lower and upper barriers. Let \(\epsilon = [\, \lvert p - \tfrac12 \rvert < 10^{-12} \,]\) and \(p' = p + 0.01\,\epsilon\). Then
\[\operatorname{durationOf}(p, a, b) = \epsilon \cdot a\,b + (1 - \epsilon) \cdot \operatorname{biasedDuration}(p', a, b) .\]The expected length of the game for any \(p\), choosing the fair or biased form as ruinOf does.
Intuition The same dispatch as ruinOf, for game length. A fair game lasts about the product of the two distances; a strong edge usually shortens it, because the drift carries the walk to one barrier. A mild edge toward a far barrier can lengthen it instead, since the walk now tends to travel the long way.
Use it when you need the expected game length for any \(p\). Pair it with ruinOf to describe a game fully: how likely ruin is and how long it takes. It also sizes a simulation: a run much shorter than several times this number will cut many games off before they finish.
hitting-timesrandom-walkssimulation
def durationOf(p, a, b) ≔ evenOdds(p) · fairDuration(a, b) + (1 − evenOdds(p)) · biasedDuration(clear(p), a, b)
Building blocks
odds(p)— Let \(0 < p \le 1\). Then \(\operatorname{odds}(p) = (1 - p)/\operatorname{guarded}(p)\). The ratio q/p of down to up probability.guarded(v)— Let \(v\) be a tensor of any shape. Then, entrywise, \(\operatorname{guarded}(v) = v + [\,\lvert v \rvert < 10^{-300}\,] \cdot 10^{-300}\).vwith every entry of magnitude below 1e-300 (in practice, every exact zero) increased by 1e-300, a safe divisor.evenOdds(p)— Let \(p \in \mathbb{R}\). Then \(\operatorname{evenOdds}(p) = [\, \lvert p - \tfrac12 \rvert < 10^{-12} \,]\). 1 when p is within 1e-12 of ½.clear(p)— Let \(p \in \mathbb{R}\). Then \(\operatorname{clear}(p) = p + 0.01 \cdot [\, \lvert p - \tfrac12 \rvert < 10^{-12} \,]\). Moves a fair p off ½ for the biased branch that is about to be discarded, so that branch does not produce NaN.
The Brownian bridge
A bridge is a walk pinned at both ends. At step \(k\) of \(n\), with \(m = \max(n - k, 1)\) steps remaining, the construction moves toward the target by an equal share of the remaining distance and adds noise whose scale shrinks to zero at the last step, so the endpoint is reached exactly:
\[x_{k+1} = x_k + \frac{\text{to} - x_k}{m} + z_k \sqrt{\frac{m - 1}{m}}\]The variance of a standard bridge at time \(t\) is \(t(n - t)/n\): zero at both ends and largest in the middle.
bridgeOf
bridgeOf(x, to, n, k, z) · x current position · to end point scalar · n total steps · k current step · z standard normal draw scalar → next position
Let \(x \in \mathbb{R}\) be the current position, \(y \in \mathbb{R}\) (the argument to) the end point, \(n \in \mathbb{N}\) the total number of steps, \(k \in \{0, 1, \dots, n\}\) the current step, and \(z \in \mathbb{R}\) a standard normal draw. Let \(m = \max(n - k, 1)\). Then
One step of a discrete Brownian bridge from x toward to. Pass one element of a stream of standard normals as z.
Intuition A wanderer with a train to catch: at each step it closes an equal share of the remaining gap to to, and its random wobble shrinks as the deadline approaches, vanishing on the last step so the endpoint is hit exactly.
Use it when you fill in a realistic random path between two known values: intraday prices between a known open and close, sensor readings missing between two measurements, a simulated path that must end at a given level (for example to check whether it crossed a barrier on the way). z must be a standard normal draw from the caller; the noise has unit variance per step, so multiply z by your own scale if needed. For a path with a free end use stepOf.
interpolationsimulation
def bridgeOf(x, to, n, k, z) ≔ x + pull(x, to, n, k) + z · bridgeScale(n, k)
bridgeSpread
bridgeSpread(n, t) · n total steps · t time scalar → variance scalar
Let \(n > 0\) be the total number of steps and \(0 \le t \le n\) a time. Then
\[\operatorname{bridgeSpread}(n, t) = \frac{t\,(n - t)}{\operatorname{guarded}(n)} .\]The variance of the bridge at time t.
Intuition Uncertainty is zero where the path is pinned and greatest in between. The curve \(t(n - t)/n\) is a parabola that peaks at \(n/4\) halfway along: the middle is the point farthest from both known ends.
Use it when you put an error band on an interpolated value, such as the straight line between two measurements \(\pm 2\sqrt{\operatorname{bridgeSpread}(n, t)}\), check a simulated bridge’s spread, or decide where one extra measurement would remove the most uncertainty (the middle). It assumes unit variance per step; multiply by \(\sigma^2\) for another step variance.
uncertainty-quantificationinterpolation
def bridgeSpread(n, t) ≔ t · (n − t) / guarded(n)
Building blocks
remaining(n, k)— Let \(n, k \in \mathbb{N}\). Then \(\operatorname{remaining}(n, k) = \max(n - k, 1)\). Steps still to go, at least one.pull(x, to, n, k)— Let \(x, y \in \mathbb{R}\) (the argumentsxandto) and \(n, k \in \mathbb{N}\). Then \(\operatorname{pull}(x, y, n, k) = (y - x)/\max(n - k, 1)\). The deterministic move toward the end point.bridgeScale(n, k)— Let \(n, k \in \mathbb{N}\) and \(m = \max(n - k, 1)\). Then \(\operatorname{bridgeScale}(n, k) = \sqrt{\max(m - 1, 0)/m}\). The noise scale, which falls to zero on the final step.
The doubling system
The classic martingale betting system: after a win the bet resets to the stake, after a loss it doubles. Whatever the staking rule, a fair game stays fair — the expected fortune is always the starting fortune — which is the content of the optional stopping theorem. The book is a vector [fortune, bet] that starts at zeros; a bet of zero is read as “open at the stake”.
fairStake
fairStake(start) · start starting fortune scalar → expected fortune scalar
Let \(F_0 \in \mathbb{R}\) (the argument start) be the starting fortune. Then
The expected fortune of a fair game under any staking rule: the starting fortune itself. It is stated so that a simulated system can be compared against it.
Intuition No staking plan turns a fair game into a winning one: the expected fortune stays at the start. A doubling system does not change the average, only its shape, trading many small wins for rare huge losses.
Use it when you need the reference line for a simulated betting or position-sizing strategy on a fair game: the average final fortune over many runs should sit on it, and a persistent gap points to a bug or to draws that are not fair, not to a clever system. It holds for fair games; with \(p \ne \tfrac12\) the expected fortune drifts with the edge.
model-validationrisk-measurement
def fairStake(start) ≔ start
bookAt
bookAt(book, stake, u, k, p) · book [fortune, bet] vector 2 · stake base bet scalar · u uniform draws vector n · k draw index · p win probability scalar → updated [fortune, bet] vector 2
Let \((F, \beta) \in \mathbb{R}^2\) (the argument book, positions 0 and 1) be the current fortune and bet, \(s > 0\) (the argument stake) the base bet, \(u \in [0, 1)^n\) independent uniform draws, \(k \in \{0, \dots, n-1\}\) a draw index, and \(0 \le p \le 1\) the win probability. Let
Then
\[\operatorname{bookAt}\big((F, \beta), s, u, k, p\big) = \Big( F + \beta' (2w - 1),\;\; w\, s + (1 - w)\, 2\beta' \Big) .\]One round of the doubling system: the current bet is won or lost on draw k, the fortune moves by that bet, and the next bet is the stake after a win or twice the bet after a loss.
Intuition Double after every loss, so the first win recovers all the losses plus one stake. The catch is the losing streak: \(L\) losses in a row cost \(s(2^L - 1)\), and the next bet is \(2^L s\). Most runs creep up; a few fall off a cliff.
Use it when you run the martingale system as a process step to see its heavy left tail, or to study “average down after a loss” sizing rules in trading. Nothing caps the bet or stops the game at zero: the fortune can go negative as if credit were unlimited. Add a table limit or a stopping rule yourself if you want a realistic bankroll.
risk-measurementsimulation
def bookAt(book, stake, u, k, p) ≔ settled(elementAt(book, 0), openingBet(elementAt(book, 1), stake), u, k, p) · (positions(book) = 0) + nextBet(openingBet(elementAt(book, 1), stake), stake, u, k, p) · (positions(book) = 1)
Building blocks
wonAt(u, k, p)— Let \(u \in [0, 1)^n\), \(k \in \{0, \dots, n-1\}\) and \(0 \le p \le 1\). Then \(\operatorname{wonAt}(u, k, p) = [\, u_k < p \,]\). 1 when round k is won.settled(fortune, bet, u, k, p)— Let \(F, \beta \in \mathbb{R}\) (the argumentsfortuneandbet) and \(w = [\, u_k < p \,]\). Then \(\operatorname{settled}(F, \beta, u, k, p) = F + \beta\,(2w - 1)\). The fortune after the bet is won or lost.nextBet(bet, stake, u, k, p)— Let \(\beta, s \in \mathbb{R}\) (the argumentsbetandstake) and \(w = [\, u_k < p \,]\). Then \(\operatorname{nextBet}(\beta, s, u, k, p) = w\,s + (1 - w)\,2\beta\). The stake after a win, double the bet after a loss.openingBet(bet, stake)— Let \(\beta, s \in \mathbb{R}\) (the argumentsbetandstake). Then \(\operatorname{openingBet}(\beta, s) = \beta + [\, \beta = 0 \,]\, s\). The bet, or the stake when the bet is still zero.
Running extremes
The high-water mark and the low of a walk are carried along with the position, so a path never has to look back over its own history. The marks vector is [position, high, low], and the high and low are compared against the new position after the step.
The reflection principle gives the chance that a fair walk ever reaches a level: every path that crosses the level and comes back has a mirror image that stays above, so
\[P\Big(\max_{t \le n} S_t \ge \ell\Big) \approx 2\big(1 - \Phi(\ell / \sqrt{n})\big)\]using the normal approximation to the endpoint.
drawdownOf
drawdownOf(high, x) · high running maximum · x current position → drawdown
Let \(M \in \mathbb{R}\) (the argument high) be the running maximum and \(x \in \mathbb{R}\) the current position. Then
How far the position is below its high-water mark.
Intuition How far you are below your best point so far: the loss an investor feels, measured from the peak rather than from the start.
Use it when you track risk on an equity curve or account balance (current drawdown, and maximum drawdown as the largest value along a path), or any level measured against its record, such as a reservoir below its highest fill. Take the high from element 1 of the marksAt vector, so the peak is carried along the path rather than recomputed.
risk-measurementdrawdown-analysis
def drawdownOf(high, x) ≔ high − x
marksAt
marksAt(marks, u, k, p) · marks [position, high, low] vector 3 · u uniform draws vector n · k draw index · p up probability → updated [position, high, low] vector 3
Let \((x, M, L) \in \mathbb{R}^3\) (the argument marks, positions 0, 1 and 2) be the current position, high and low, \(u \in [0, 1)^n\) independent uniform draws, \(k \in \{0, \dots, n-1\}\) a draw index, and \(0 \le p \le 1\) the up probability. Let
Then
\[\operatorname{marksAt}\big((x, M, L), u, k, p\big) = \big( x',\;\; \max(M, x'),\;\; \min(L, x') \big) .\]One step of a simple random walk that also updates its running maximum and minimum.
Intuition Carry the record high and low along with the walker, updated against where it now stands, so the extremes cost one comparison per step instead of a scan back over the whole history.
Use it when a simulation cares about extremes, not just the endpoint: maximum drawdown distributions, whether a price ever touched a barrier level, peak queue length, the highest flood level. It uses \(\pm 1\) steps as stepOf does, and the zero starting vector means the walk starts at 0 with high and low 0. Compare the fraction of runs whose high reaches a level with reflectedTail. For other increments, follow the same pattern with your own step.
risk-measurementsimulationrandom-walks
def marksAt(marks, u, k, p) ≔ walked(marks, u, k, p) · (positions(marks) = 0) + risen(elementAt(marks, 1), walked(marks, u, k, p)) · (positions(marks) = 1) + fallen(elementAt(marks, 2), walked(marks, u, k, p)) · (positions(marks) = 2)
reflectedTail
reflectedTail(level, n) · level level to reach scalar · n number of steps scalar → probability scalar
Let \(\ell \in \mathbb{R}\) (the argument level) be the level to reach and \(n > 0\) the number of steps. Then
where \(\Phi\) is the standard normal distribution function computed by normalCdf from Distributions.
The approximate probability that a fair ±1 walk of n steps reaches level at some point.
Intuition Mirror images: every path that touches the level and ends below it has a twin, reflected after the first touch, that ends above it. So reaching the level at some point is about twice as likely as ending above it, and the endpoint is close to normal.
Use it when you want a quick chance that a fair, driftless quantity ever reaches a threshold within \(n\) steps: a price touching a stop-loss, a backlog crossing a limit, accumulated error exceeding a tolerance. It assumes a fair \(\pm 1\) walk started at 0 and uses the normal approximation with no continuity correction, so it is rough for small \(n\). It is not clipped: a level of 0 gives 1 and a negative level gives more than 1.
risk-measurementhitting-times
def reflectedTail(level, n) ≔ 2 · (1 − normalCdf(0, sqrt(n), level))
Building blocks
risen(high, x)— Let \(M, x \in \mathbb{R}\) (the argumentshighandx). Then \(\operatorname{risen}(M, x) = \max(M, x)\). The new running maximum.fallen(low, x)— Let \(L, x \in \mathbb{R}\) (the argumentslowandx). Then \(\operatorname{fallen}(L, x) = \min(L, x)\). The new running minimum.walked(marks, u, k, p)— Let \((x, M, L) \in \mathbb{R}^3\) (the argumentmarks), \(u \in [0, 1)^n\), \(k \in \{0, \dots, n-1\}\) and \(0 \le p \le 1\). Then \(\operatorname{walked}((x, M, L), u, k, p) = x + 2\,[\, u_k < p \,] - 1\). The position after step k, read once and used three times bymarksAt.
Reading a trajectory
A trajectory is a tensor with one row per step. These functions read a single column from it and summarise a single series: its range, how often it crosses a level upward, and the series lagged by one step.
trackOf
trackOf(path, w) · path trajectory matrix n×w · w column index scalar → column vector n
Let \(X \in \mathbb{R}^{n \times m}\) (the argument path) be a trajectory and \(w \in \{0, 1, \dots, m-1\}\) a column position counted from zero. The intended result is
but the code takes the positions \(j\) from widths(path), which does not produce a vector (see below), so the definition as written does not compute this.
Intended to read column w (counting from zero) of a trajectory, for example the fortune or the bet of a betting book. In the current release this definition fails at run time with an einsum rank error, because its widths helper applies a vector operation to a matrix. Until it is corrected, read a column with your own contraction against a one-hot, for example einsum("tw,w->t", path, mask).
Intuition A process that carries several quantities, such as [fortune, bet] or [position, high, low], produces a trajectory with one column per quantity. Reading one of them is a contraction against a one-hot over the columns, like selecting one series from a table.
Use it when you would pull a single series out of a multi-quantity trajectory to pass on to spanOf, crossingsOf or drawdownOf. As documented above, this release fails at run time with a rank error, so for now build the one-hot mask yourself and write einsum("tw,w->t", path, mask).
trajectory-analysissimulation
def trackOf(path, w) ≔ einsum("tw,w->t", path, widths(path) = w)
spanOf
spanOf(v) · v series vector n → range scalar
Let \(v \in \mathbb{R}^n\) be a series. Then
\[\operatorname{spanOf}(v) = \max_i v_i - \min_i v_i ,\]with the maximum and minimum read as the largest and smallest order statistics (greatest and least from Statistics).
The distance between the largest and the smallest value of the series.
Intuition The distance from the lowest to the highest value: how much ground the series covered, ignoring the order in which it visited it.
Use it when you want a quick measure of variability: a day’s price range, a temperature swing, how far a simulated walk wandered (for a fair walk it grows roughly like \(\sqrt{n}\)). It rests on two extreme values, so one outlier sets it; for a spread that uses every value, use a standard deviation. When the order matters, for example a fall from a peak, use drawdownOf.
risk-measurementtrajectory-analysis
def spanOf(v) ≔ greatest(v) − least(v)
crossingsOf
crossingsOf(v, level) · v series vector n · level level scalar → count scalar
Let \(v = (v_0, \dots, v_{n-1}) \in \mathbb{R}^n\) be a series (positions counted from zero), \(\ell \in \mathbb{R}\) (the argument level) a level, and let \(v_{-1} = 0\). Then
The number of upward crossings of level: steps where the series is at or above the level after being below it on the previous step. The value before the first element is taken as 0, so a series that starts at or above a positive level counts one crossing at the start.
Intuition Each upward crossing is one “episode” of going over the line: the series is at or above the level now and was below it a step ago. It counts how often the threshold was breached, not how long the series stayed above it.
Use it when you count exceedance events: load going over capacity, glucose going high, a river flooding, a price breaking a resistance level. A walk that keeps coming back to a level crosses it often. Mind the start: the value before the first element is taken as 0, so a series that starts at or above a positive level counts one crossing at step 0.
event-countingthreshold-exceedance
def crossingsOf(v, level) ≔ einsum("t->", (v ≥ level) · (previousOf(v) < level))
previousOf
previousOf(v) · v series vector n → lagged series vector n
Let \(v = (v_0, \dots, v_{n-1}) \in \mathbb{R}^n\) (positions counted from zero). Then
\[\operatorname{previousOf}(v)_i = \sum_{j=0}^{n-1} [\, i - j = 1 \,]\, v_j = \begin{cases} 0, & i = 0, \\ v_{i-1}, & i = 1, \dots, n-1 . \end{cases}\]The series lagged by one step. It builds an n×n mask. Diffusions uses it for quadratic variation.
Intuition Slide the series one place to the right and put a 0 in front. Now “previous” and “current” line up entry by entry, so every lag-one comparison becomes elementwise arithmetic.
Use it when you need increments v − previousOf(v), step-to-step changes, lag-one tests (as crossingsOf does) or quadratic variation. The first “previous” is 0, so the first increment equals \(v_0\); drop it unless the series really starts from 0. It builds an n×n mask, so keep series to a few thousand points.
trajectory-analysistime-series-differencing
def previousOf(v) ≔ einsum("ij,j->i", held(positions(v)) − laid(positions(v)) = 1, v)
Building blocks
widths(path)— Let \(X \in \mathbb{R}^{n \times m}\) and \(c_j = \sum_t X_{tj}\) its column sums. Then \(\operatorname{widths}(X) = \operatorname{positions}(C)\) where \(C \in \mathbb{R}^{m \times m}\) has \(C_{ij} = c_j\); becausepositionsexpects a vector and \(C\) is a matrix, this fails with a rank error instead of giving the intended column positions \(0, 1, \dots, m-1\). The column positions of a trajectory; used bytrackOf.
Examples
Gambler’s ruin, fair and biased
A player starts 3 units above ruin and stops on gaining 7.
open Prelude.Paths
fn ruinChance(p, a, b) ↦ ruinOf(p, a, b)
fn gameLength(p, a, b) ↦ durationOf(p, a, b)
using Examples;
var fairRuin = Walks.RuinChance(0.5, 3.0, 7.0);
var biasedRuin = Walks.RuinChance(0.4, 3.0, 7.0);
var fairSteps = Walks.GameLength(0.5, 3.0, 7.0);
var biasedSteps = Walks.GameLength(0.4, 3.0, 7.0);
Output (verified, rounded to 6 decimal places):
ruin fair = 0.7
ruin biased = 0.958087
duration fair = 21
duration biased = 12.904352
The fair game is ruined with probability \(7/10\) and lasts \(3 \times 7 = 21\) steps on average. At \(p = 0.4\), \(r = 1.5\) and \(P(\text{win}) = (1.5^3 - 1)/(1.5^{10} - 1) \approx 0.0419\), so ruin is nearly certain and comes sooner.
A bridge’s spread and the reflection principle
open Prelude.Paths
fn bridgeVariance(n, t) ↦ bridgeSpread(n, t)
fn reachTail(level, n) ↦ reflectedTail(level, n)
using Examples;
var middle = Walks.BridgeVariance(10.0, 5.0);
var reach = Walks.ReachTail(10.0, 100.0);
Output (verified, rounded to 6 decimal places):
bridge = 2.5
reflected = 0.317311
Halfway along a ten-step bridge the variance is \(5 \cdot 5 / 10\). A fair walk of 100 steps reaches 10, one standard deviation, with probability about \(2(1 - \Phi(1)) \approx 0.3173\).
One step of a walk, its extremes and a betting book
The draws are 0.3, 0.7 and 0.1, and every step reads draw 1 (0.7) with \(p = 0.5\), so each of these steps loses.
open Prelude.Paths
fn oneStep(u, k, p) ↦ stepOf(u, k, p)
fn nextMarks(marks, u, k, p) ↦ marksAt(marks, u, k, p)
fn nextBook(book, stake, u, k, p) ↦ bookAt(book, stake, u, k, p)
using Examples;
using MLambda.Hilbert.Runtime;
var u = new[] { 0.3, 0.7, 0.1 };
var step = Walks.OneStep((Tensor)u, 1.0, 0.5);
var marks = Walks.NextMarks((Tensor)new[] { 2d, 3d, -1d }, (Tensor)u, 1.0, 0.5);
var book = Walks.NextBook((Tensor)new[] { 0d, 0d }, 1.0, (Tensor)u, 1.0, 0.5);
Output (verified):
step1 = -1
marks = [1, 3, -1]
book = [-1, 2]
The walk at 2 steps down to 1, below its high of 3 and above its low of −1. The empty book opens at the stake of 1, loses it, and doubles the next bet to 2.
Crossings and range of a path
open Prelude.Paths
fn upCrossings(v, level) ↦ crossingsOf(v, level)
fn rangeOf(v) ↦ spanOf(v)
using Examples;
using MLambda.Hilbert.Runtime;
var crossings = Walks.UpCrossings((Tensor)new[] { 0d, 1, 2, 1, 0, 1, 2, 3 }, 2.0);
var span = Walks.RangeOf((Tensor)new[] { 0d, 1, 2, 1, 0, -1, 2, 3 });
Output (verified):
crossings = 2
span = 4
The first series rises through 2 at positions 2 and 6. The second runs from −1 to 3.