🔢 mathematics

A Linear Variance Bound for Ballistic Deposition

This paper establishes a linear variance bound for the height of the standard continuous-time ballistic deposition process in all dimensions by adapting Aldous's martingale argument to derive tail bounds on first hitting times and applying Penrose's duality theorem.

Original authors: Timothy Sudijono

Published 2026-09-22

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Timothy Sudijono

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a surface growing unevenly, like a pile of sand being dropped grain by grain, or a layer of paint accumulating on a wall. In physics and mathematics, scientists study how such surfaces evolve over time to understand everything from how crystals form to how traffic jams move. One specific model for this growth is called ballistic deposition. In this scenario, imagine tiny blocks falling from the sky at random locations on a grid. When a block lands, it doesn't just sit where it hits; if there is a neighbor already there, it sticks to the side, creating a jagged, uneven landscape. The central question for decades has been about the roughness of this landscape. Specifically, if you watch the height of the pile at a single spot, how much does it fluctuate? Does the variation in height grow slowly, like the square root of time, or faster, like the two-thirds power of time? For one-dimensional piles, experts have long suspected the fluctuations follow a very specific, complex pattern known as the KPZ universality class, which predicts a growth rate of the two-thirds power. However, proving this rigorously has been incredibly difficult, and until now, the best mathematical guarantees on how fast these fluctuations could grow were quite loose.

A new study by Timothy Sudijono provides a significant step forward by establishing a firm, linear limit on how much the height of this growing surface can vary. The research proves that for a pile growing in any number of dimensions, the variance of the height at a specific point is at most proportional to the time elapsed. In simpler terms, if you wait twice as long, the potential for the height to deviate from its average grows only linearly, not exponentially or in some more chaotic fashion. This result holds true whether the surface is growing on a simple line, a flat plane, or in higher-dimensional space. The author achieves this by shifting the perspective from the growing surface itself to a "dual" process, a mathematical mirror image that tracks when new layers would arrive at different spots. By analyzing the timing of these arrivals, the study uses a clever argument involving probability and randomness to show that the surface cannot fluctuate wildly.

The core of the discovery relies on a technique that treats the growth process as a race against time. Instead of trying to measure the height directly, which is complicated by the fact that adding a single block can have unpredictable effects far into the future, the researcher looks at the time it takes for the surface to reach a certain height. This approach transforms the problem into one of timing. The study demonstrates that the time it takes for the surface to grow by one unit is highly predictable and follows a specific pattern of concentration. If the surface grows too fast or too slow, the mathematical tools used in the paper show that such events are exponentially unlikely. By inverting this relationship, the author translates these tight bounds on time into tight bounds on the height. The proof involves showing that the average time required to reach a new height increases steadily and does not flatten out, ensuring that the surface cannot accelerate its growth in a way that would cause massive fluctuations.

This work does not claim to have solved the entire mystery of how these surfaces behave, nor does it confirm the specific two-thirds power law predicted for one-dimensional piles. Instead, it sets a hard ceiling on the chaos. It rules out the possibility that the height fluctuations could grow as fast as the square of the time, a scenario that would imply a much wilder, less controlled growth process. The findings are rigorous mathematical proofs, not simulations or guesses, meaning the results are certain within the logic of the model. The study confirms that while the surface is indeed rough and unpredictable in the short term, its long-term behavior is constrained by a linear relationship with time. This provides a crucial foundation for future research, offering a reliable boundary that any more detailed theory must respect. By establishing that the variance is bounded by a constant times the time, the paper brings a new level of clarity to a problem that has resisted precise mathematical description for years, showing that even in a system driven by random chance, there are strict limits to the disorder.

Technical Summary: A Linear Variance Bound for Ballistic Deposition

Problem Statement
The paper addresses the fundamental question of the order of fluctuations for the surface height, $f(t,0)$ , in the standard continuous-time ballistic deposition process on the lattice $\mathbb{Z}^d$ . While it is widely conjectured that this model belongs to the Kardar-Parisi-Zhang (KPZ) universality class—implying that the variance of the height should scale as $t^{2/3}$ in one dimension—rigorous results have been scarce. Prior to this work, the only established rigorous bounds were a lower bound of $\Omega(\log t)$ and a trivial upper bound of $o(t^2)$ , both due to Penrose [10]. The specific goal of this note is to establish a rigorous upper bound on the variance of the surface height in all dimensions $d \ge 1$ .

Methodology
The author employs a strategy distinct from the bounded differences or concentration inequalities typically applied to last-passage percolation representations, noting that the effect of updates on future heights in ballistic deposition is generally unbounded. Instead, the proof relies on three main components:

Duality Transformation: The paper utilizes a duality theorem established by Penrose [10]. This result equates the distribution of the ballistic deposition height $f(t,0)$ (started from a flat profile) to a "delayed next-arrival" process $H_t$ . Specifically, $f(t,0) \stackrel{(d)}{=} H_t$ , where $H_t$ is the supremum of a next-arrival process $\eta(t,x)$ evolving autonomously from a seed initial configuration. The next-arrival process $\eta$ is Markovian and updates according to specific rules: at a clock ring $(t,x)$ , the height at $x$ increases by 1, and the heights at neighbors $y \sim x$ update to $\max\{\eta(t-,x), \eta(t-,y)\}$ .
Martingale Argument for Hitting Times: Adapting an argument by Aldous [20], the author analyzes the first hitting times $T_n = \inf\{t : H_t \ge n\}$ of the maximum of the next-arrival process. By constructing a "remaining-time martingale" $M_t = \mathbb{E}[T_n \mid \mathcal{F}_t] - \mathbb{E}[T_n]$ and examining the generator of the process, they demonstrate that specific exponential transformations of $M_t$ are supermartingales. This relies crucially on the monotonicity of the update maps and the surface-growth structure of $\eta$ .
Inversion and Mean Spacing: The concentration bounds derived for the hitting times $T_n$ are inverted to obtain tail bounds for the height process $H_t$ using the relation $P(T_n \le t) = P(H_t \ge n)$ . A critical technical step involves establishing that the sequence of hitting time means $\mu_n = \mathbb{E}[T_n]$ is not "too flat." The author proves a lower bound on the mean differences $\mu_{n+k} - \mu_n$ , showing they grow linearly with $k$ (modulo logarithmic corrections), which is necessary to translate the hitting time concentration into a linear variance bound for the height.

Key Results
The primary result is Theorem 1.1, which establishes an exponential tail bound for the deviation of the height from its mean. For every dimension $d \ge 1$ , there exist constants $c_d, C_d \in (0, \infty)$ such that for all $t \ge 1$ and $r \ge 0$ :
$P(|f(t,0) - \mathbb{E}f(t,0)| \ge r) \le C_d \exp\left\{-c_d \frac{r^2}{t + r}\right\}$
As a direct consequence, the paper proves the linear variance bound:
$\text{Var}f(t,0) \le C_d t, \quad t \ge 1$
This result holds for all dimensions $d \ge 1$ .

Significance and Claims
The paper claims to provide the first rigorous $O(t)$ upper bound on the variance of the surface height for the standard ballistic deposition model in any dimension. The author notes that while this bound is weaker than the conjectured $O(t^{2/3})$ scaling of the KPZ class, it represents a significant improvement over the previous $o(t^2)$ bound.

The significance of the work lies in the methodology:

It demonstrates the utility of adapting Aldous's martingale argument for monotone surface growth processes to derive tail bounds on hitting times.
It shows how inverting these tail bounds, combined with a duality theorem, can yield variance bounds for the height process even when standard concentration inequalities (like bounded differences) fail due to unbounded update effects.
The author suggests that this strategy may prove useful for analyzing variants of the ballistic deposition model where traditional approaches are unfruitful.

The paper remains modest regarding the KPZ conjecture, acknowledging that the $O(t)$ bound does not confirm the $t^{2/3}$ scaling but narrows the gap between known rigorous results and physical conjectures. The work is presented as a note establishing this specific bound, with the rigorous proof of the variance bound being the central contribution.

More like this