Papers

We analyse reverse-mode automatic differentiation (AD) for discrete probabilistic programs. Our construction is formulated in the framework of Combinatory Homomorphic Automatic Differentiation (CHAD), treating AD as a structure-preserving transformation of programs, guided by a denotational semantics. The main case study is the finite atomic distribution monad, whose computations have finite support and differentiable weights. The key point is that differentiating probabilistic programs requires cotangents to flow backwards not only through deterministic computations, but also through the probabilistic structure itself. We define the corresponding reverse-mode code transformation and prove its correctness, for handled real-output programs, by a categorical logical-relations argument. Although the paper focuses on finite discrete probability, the construction gives a reusable pattern for differentiating discrete-output algebraic effects, including finite multiset non-determinism (e.g., from fork-join parallelism), exceptions, and writer-style accumulation (e.g., for in-place accumulation of high-dimensional vectors). More broadly, we view this work as a foundational step towards extending CHAD to richer probabilistic languages and to other algebraic effects with handlers.

We study signature controlled differential equations (Sig-CDEs), that is, path-dependent controlled differential equations (CDEs) whose vector fields factor through the signature map. Working on spaces of stopped Hölder paths, we develop an existence, uniqueness, and stability theory for general path-dependent CDEs, and translate these pathwise well-posedness criteria into conditions on the corresponding signature functionals. We then prove dynamic universality: simply parametrized Sig-CDEs approximate the solution path of any well-posed path-dependent CDE arbitrarily well, uniformly over bounded sets of controls and initial histories, with global variants obtained using weighted spaces. Within this framework, entire maps of group-like elements provide a specific class of Sig-CDEs. Using a new class of limiting tensor spaces, we recast Sig-CDEs as infinite-dimensional classical CDEs and prove their well-posedness via a gauge-type scaling argument, thereby establishing a principled way to lift generic path-dependent dynamics. Lastly, we study truncated Sig-CDEs as finite-dimensional differential equations on step$-N$ Lie groups under intrinsic conditions, that is, with well-posedness formulated in terms of the underlying group metric.

We extend a previously introduced one-dimensional diffusion model on the space of probability measures, defined via the rearranged stochastic heat equation by, penalizing the dynamics with an additional entropy-driven gradient-descent term. By means of a splitting argument, we prove that despite the opposite effects of rearrangement and entropy minimization, the resulting penalized stochastic heat equation is well defined. We study several properties of the associated dynamics and show, in particular, that solutions admit a density satisfying a corrected version of the Dean–Kawasaki equation. The smoothing properties established for the stochastic heat equation are shown to persist.

We develop an efficient online algorithm to sample a sequence of discrete random variables using an entropy source of i.i.d. fair coin flips, in a standard model of real computation where real-valued probabilities are represented by rational approximations. For any sequence $F_1, F_2, \dots$ of probability distributions, our sampler generates $n$ outputs $X_1 \sim F_1, \dots, X_n \sim F_n$ using at most $\mathbb{E}\left[H(F_1) +\dots + H(F_n)\right] + O(\log n)$ coin flips in expectation while carrying $O(\log n)$ bits of persistent space, where $H$ is the Shannon entropy. Under standard assumptions, we prove that the space used by our sampler to achieve this information-theoretically optimal entropy rate is asymptotically optimal. The key idea is to replace the global arithmetic-decoding sampling scheme of Han and Hoshi (1997) with a local discrete uniform state, yielding an exponential reduction in space for a given entropy loss. Our approach applies to distributions with irrational probabilities and countably infinite supports, generalizing recent randomness-recycling methods beyond finite rational distributions with bounded denominator.

We study the Kac particle system associated with the spatially homogeneous Boltzmann equation with non-cutoff collision kernels in the moderately soft potential regime $-1<\gamma<0$. We prove uniqueness in law for the particle system and, in particular, establish an explicit convergence rate from the empirical measure of the Kac particle system to the weak solution of the Boltzmann equation in Wasserstein-2 distance, assuming that the initial datum $f_0$ has finite Fisher information and polynomial moments. To the best of our knowledge, this provides the first quantitative convergence rate for the Kac particle system in the soft potential setting.

In this paper, we analyze the diffusion limit of Join-the-Shortest-Queue (JSQ) load balancing policies for a system with many parallel queues where each queue is being served by a server with a potentially different service rate. Prior asymptotic analyses of JSQ policies assumed servers to have service rates from a finite set which does not capture scenarios in modern data centers where service rates can vary at the level of individual servers. For systems with individually heterogeneous servers, tracking the empirical queue length distribution for each possible service rate becomes infeasible. To overcome this difficulty, we develop a framework based on measure-valued processes and provide a unified analysis of all JSQ-based load balancing policies under general tie-breaking rules. Our analysis identifies two key objects that distinguish the performance of different tie-breaking rules in the Halfin–Whitt regime, namely, the limiting fairness process which describes how idle servers are distributed across different service rates and the limiting routing measure which describes how arriving jobs are assigned across different service rates. In addition to characterizing the diffusion limits for different tie-breaking rules, we identify the tie-breaking rule which asymptotically minimizes the steady-state distributions of the diffusion-scaled total number of jobs and the diffusion-scaled number of waiting jobs. In proving these results, we develop crucial coupling-based sample-path comparisons which provide both policy-independent steady-state bounds and lower bounds to prove asymptotic optimality.

We prove cutoff in total variation distance for the discrete-time Kac walk on $S^{n-1}$ started from a coordinate vector. The cutoff occurs at $ C_{\mathrm{BRW}}n\log n$, where $C_{\mathrm{BRW}} \approx 3.8916$ is an explicit constant determined by the speed of the leftmost particle in a branching random walk. In particular, the cutoff location is not at the conjectured time $ 2n\log n$.

We consider coupled stochastic systems decomposed into exterior, boundary, and interior variables, with the boundary variables sometimes carrying the directed structure of a sensor and actuator. The central question is when the conditional law of histories factorises, and how this path space statement is detected by log likelihoods, by Girsanov changes of measure, and by information theoretic quantities used in nonequilibrium statistical physics. The basic object is a regular conditional probability on a path space. Under domination by clamped reference laws, the boundary property becomes multiplicative separation of a Radon–Nikodym derivative, or equivalently additive separation of a path log likelihood. For Itō diffusions this log likelihood is computed by Girsanov's theorem; its expectation is the quadratic control energy appearing in the Föllmer entropy identity and in the stochastic control formulation of Schrödinger bridge problems. When exact factorisation fails, the remaining coupling is measured by conditional mutual information, namely the relative entropy between the true boundary-conditioned path law and the product of its conditional marginals. This gives a common language for boundary screening, path likelihood inference, controlled changes of path law, and the thermodynamic value of mutual information.

We prove a quantitative propagation of chaos estimate and a central limit theorem for the particle system associated with a class of degenerate kinetic McKean–Vlasov SDEs with external drifts and singular interaction kernels in Kato's class. In particular, the interaction kernel can be in the mixed $L^q_tL^{p_v}_vL^{p_x}_x$-space, where $\frac2q+\frac{3d}{p_x}+\frac d{p_v}<1$. For the associated $N$-particle system, we obtain a path-space relative entropy bound of order $k/N$ for the first $k$ particles, assuming only entropic chaoticity of the initial data. The key ingredients are kinetic Krylov–Khasminskii estimates and a conditional Hilbert-space subgaussian estimate for empirical interaction fields. For the CLT, we also prove a Berry–Esseen-type bound for finite-dimensional projections.

We study multidimensional semilinear stochastic evolution equations driven by multiplicative noise and subject to rough initial data. The drift and diffusion coefficients are assumed to take values in negative fractional order spaces and may exhibit temporal singularities at the initial time. Our main results establish well-posedness and pathwise spatio-temporal regularity of the solutions when these coefficients are globally Lipschitz, and we prove the existence, uniqueness, and pathwise regularity of maximal local solutions when the coefficients are locally Lipschitz. The local Lipschitz condition is formulated with respect to a specific time-weighted norm. This enables the application of our theoretical results to linear stochastic partial differential equations, as well as to a broad class of models with non-globally Lipschitz nonlinearities. These include the stochastic Burgers, Allen–Cahn, Fisher–KPP, and Burgers–Fisher equations, alongside the Ginzburg–Landau system and models featuring exponential growth, such as the stochastic solid fuel ignition model.

We establish a general criterion ensuring the absence of infinite connected components at criticality for a broad class of two-dimensional dependent percolation models. Our assumptions include monotonicity, stationarity and ergodicity, positive association, a quantitative decoupling condition, continuity in the percolation parameter, and trivial behavior at the extremes. As application, we show how our criterion recovers known results for classical dependent percolation models, such as Gaussian level-set percolation and Boolean percolation.

We prove a novel characterization of the exponential distribution via a linear combination of order statistics. The theorem established herein generalizes the previous characterization theorem given in Milošević and Obradović (2016a). The proof relies on properties of Stirling numbers of the second kind, which are derived for this purpose and may be of independent interest.

We derive an explicit representation for the distribution of a Lévy process with total stochastic resetting and use it to investigate the asymptotic behaviour of the corresponding transition densities. The proposed approach applies to several important classes of Lévy processes, including relativistic stable processes, and yields new asymptotic estimates for their transition densities.

Memory encoded in the environment mediates interactions between active agents, from trail-following organisms to synthetic active matter depositing persistent tracks. Although such memory is known to strongly affect transport, its consequences for collective first-passage phenomena remain largely unexplored. Here we study $N$ one-dimensional random walkers interacting through a shared trail field. We characterize the $k^{\rm th}$ (among $N$) arrival time at a fixed target, and the probability that exactly $k$ walkers in $[0,1]$ reach one boundary before the other. For the broad class of self-interacting walkers with a saturating response to the trail, we derive exact expressions for the corresponding persistence exponents and splitting probabilities. Strikingly, despite the strong history-dependent correlations generated by the common environment, splitting probabilities are exactly identical whether walkers explore simultaneously or one after another. This invariance breaks down for nonsaturating trail interactions. Our results follow from an exact representation of the collective trail field and establish a framework for first-passage phenomena in systems coupled through persistent environmental memory.

We construct a punctured Wilson–evolving-set coupling for finite reversible Markov chains. The transformed evolving set carries a Markov trajectory up to its exit from a punctured domain, whereas the ordinary evolving set gives the corresponding probabilities after de-biasing. Applied to Wilson's algorithm with exponential killing, the final-point projection yields the root law and an ordered factorization of the probability that several prescribed vertices are roots. We identify this factorization with a probabilistic Schur-complement decomposition of the known determinantal root formula. The survival projection yields an evolving-set representation of hitting probabilities before killing. This representation gives a quantitative consequence which does not follow from the root process alone. On graphs of polynomial growth satisfying a Gaussian heat-kernel upper bound, in dimension larger than four, we obtain exponential localization at scale $q^{-1/2}$ for two-point forest connectivity, up to the natural finite-volume correction, and the bound $\mathbb E[|C_q(x)|]\leq Cq^{-2}$. Dirichlet eigenvalues in successively punctured domains also give product bounds for prescribed root events. We record a determinant-free Poisson-type concentration bound for the number of roots, while making explicit that the determinantal description gives the sharper Bernoulli decomposition. The complete graph is computed exactly and discrete tori, bottleneck graphs and the hypercube are treated as examples.

We prove that the stationary and worst-case expected meeting times of two independent continuous-time random walks on the largest component of the Erdős-Rényi random graph $G(n,p)$ have order $n$ throughout the strictly supercritical, the slightly supercritical and the critical regimes. Using these bounds along with a fine-tuned combination of comparison inequalities due to Oliveira (2012) and Kanade-Mallmann-Trenn-Sauerwald (KMS, 2023), we deduce that expected coalescence time and full voter-model consensus also have order $n$ throughout these three regimes.

We show the Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resetting the velocity to be an independent Gaussian random variable between each simulation. We show that when the target distribution is log-concave and satisfies an $\alpha$-Talagrand inequality (for example, if the target distribution is $\alpha$-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean $\Theta(\alpha^{-1/2})$, then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\alpha^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we use a sequence of random integration times from the triangular distribution with exponentially increasing means, then the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\varepsilon^{-1/2})$. Our analysis relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.

In spatially structured populations, rare neutral mutations can spread through large regions during a range expansion, a phenomenon known as gene surfing. Whether deleterious mutations can also surf remains poorly understood. To address this question, we study a deterministic version of the spatial Muller's ratchet, given by an infinite system of reaction-diffusion equations describing an asexual population subject to mutation, migration, and density-dependent reproduction and death. After establishing that the system of PDEs is well-posed, we analyse the distribution of deleterious mutations within the population. In the monostable regime, we derive quantitative bounds on the ratio between the density of individuals carrying a given number of mutations and the density of mutation-free individuals. Under a Fisher-KPP condition, we further determine the spreading speed of the population into an empty habitat, confirming non-rigorous computations of Foutel-Rodier and Etheridge. Finally, using a tracer dynamics approach, we show that deleterious mutations cannot surf deterministic waves: although they are present at the expansion front, they only arise as recent descendants of the wild type.

Non-stationary time evolution of interacting particle systems is in general a rather difficult topic however, exceptional examples are known where hidden processes within the model make the description manageable. These hidden processes often take the form of a finite number of interacting random walks and in some cases, rather than being hidden, were very explicitly revealed as second class particles associated with the model. The examples of asymmetric exclusion and exponential bricklayers model are known in this context, where such distributional structure was demonstrated in infinite volume. Here we find boundary mechanisms that save this remarkable structure in finite volume of the model with semi-open boundaries that let ordinary particles, but not the shocks, through. This finding also allows to characterise nontrivial two-species, non-reversible stationary distributions subject to our special boundary rates.

The spiked mixture model (SMM) has been introduced as a probabilistic model that generalizes the single-spike (Wishart) model to a mixture model form. With applications ranging from imaging mass spectrometry in the life sciences to hyperspectral imaging in computer vision, it is crucial to understand under which circumstances its signals can be recovered from noisy measurements. The highly multiplexed nature of these measurement types furthermore necessitates such analysis to hold in highdimensional settings. In this paper, we prove that the extreme eigenvalues of the covariance matrix from the SMM exhibit a phase transition in high-dimensional regimes. We show that this phase transition, and thus signal recovery by extreme eigenvalues, depends on several interacting factors: the correlation between spikes (i.e., how similar in content underlying signals are), the energy parameters (i.e., the absolute strength of each underlying signal), and the mixture probabilities (i.e., how likely it is to encounter each underlying signal). This work provides sharp information-theoretic bounds on the parameters needed to detect one or more spikes from extreme eigenvalues of the SMM covariance matrix, and these guarantees could potentially impact any application of the SMM. Understanding this interplay could serve as a tool for driving experimental design in analytical chemistry and life sciences.

We study a scheduled-arrival process in which deterministic arrival times are perturbed by i.i.d. unpunctuality random variables. For the empirical mean of independent copies of the resulting counting process, we prove a sample-path large deviations principle on $D([0,T])$, equipped with the Skorokhod topology. As an application, we derive large deviation principles for the corresponding workload process under deterministic and random service setting. In the deterministic service case, we also identify the exponentially tilted arrival path associated with a rare workload overflow event.

For a fixed integer $j\ge1$ and $0<p<1$, we study the probability generating function (pgf) equation \[ (1+2p)\,g(x)=2p\,x^{j}+g\bigl(x-px+px^{2}\bigr),\qquad 0\le x\le1 , \] which governs the limiting degree distribution $\{p_k\}$ of a family of evolving network models. The cases $j=1$ and $j=2$ are the treelike fast-growth model of Feng and Hu and the homogeneous evolving network of Feng, Li and Hu. We prove that for every $j$ the equation has a unique pgf solution, of mean $2j$, and we determine its coefficient tail exactly: \[ p_k=k^{-1-\rho}\,\Psi_j(\log_\lambda k)+o\bigl(k^{-1-\rho}\bigr), \] where $\lambda=1+p$, $\rho=\log(1+2p)/\log(1+p)$ is independent of $j$, and $\Psi_j$ is continuous, strictly positive and $1$-periodic, with explicit Fourier coefficients. This resolves two conjectures of Feng and coauthors: (1) the power-law order $p_k=\Theta(k^{-1-\rho})$ and (2) its refinement to the multiplicatively periodic form $p_k\sim\Psi_j(\log_\lambda k)\,k^{-1-\rho}$. The periodic factor is genuinely non-constant for $p$ near $1$, and, for the two network models, for all $p$ outside a discrete set. Consequently, $p_k$ is asymptotic to no constant multiple of $k^{-1-\rho}$. Our method is a self-contained local analysis of the supercritical Galton-Watson process with offspring law $1+\mathrm{Bernoulli}(p)$, inspected at an independent geometric time. This time-changed process solves the equation observed by Feng and coauthors. The main results of this paper were obtained by the multi-agent system Eureka and have subsequently been verified by the authors.

We study the well-posedness theory of a coupled modulated Korteweg-de Vries (KdV) system on the circle with a time non-homogeneous modulation acting on the linear dispersion term. When the coupling parameter is equal to one, it has been recently proved that given any $s\in \mathbb{R}$, the resulting modulated KdV system is globally well-posed in $H^s(\mathbb{T})\times H^s(\mathbb{T})$, with a sufficiently irregular modulation. For couplings different from one, we use Diophantine conditions to characterize the resonances and prove that (under further restrictions on the coupling constant) for any $s\in \mathbb{R}$ the coupled modulated KdV system is globally well-posed in $H^s(\mathbb{T})\times H^s(\mathbb{T})$. This result differs from its unmodulated counterpart where it is known that global well-posedness holds for $s\ge s_*\in (5/7,1]$.

Recovering two-dimensional Ito generators from trajectory data is difficult because drift increments have low signal-to-noise, bivariate weak designs can be ill-conditioned, and unconstrained tensor estimates need not be positive semidefinite. We study WG-SINDy estimator combining covariance-shaped spatial kernels, a ridge-stabilized local-polynomial projection, adaptive-LASSO/STLSQ selection, one in-sample per-component feasible diagonal GLS pass, and a PSD projection–Cholesky read-out with mild isotropic shrinkage. The released estimator uses a data-dependent full-cloud smoother and one in-sample per-component feasible diagonal GLS pass; accordingly, we do not claim exact finite-sample martingale cancellation or a feasible-GLS efficiency theorem for the reported implementation. We evaluate the estimator on 29 synthetic two-dimensional systems: 19 meet their declared per-system recovery contracts, eight are retained as named limits, and two remain scoped reviews. Across the 19 PASS rows, the median central-grid drift metric is 0.204 and the median tensor error is 0.0397. Among the six systems with a finite, non-degenerate off-diagonal target, the median $a_{12}$ cosine is 0.997. Positive-semidefinite validity is imposed by construction. These results are synthetic, in-sample sampled-region diagnostics and do not establish universal or real-data recovery.

Starting from the classic result of Wentzell, we derive a conditional forward equation and an associated stochastic Dupire PDE for a local-stochastic-volatility model (LSV). As an application, we obtain a density-weighted Rao–Blackwell estimator for the leverage function in LSV. We also derive an SPDE for a rolling expiry vanilla option, in the spirit of the Musiela parametrization in interest rate modeling.

We consider inhomogeneous random graphs in which vertices are assigned i.i.d.\ random weights, pairs of distinct vertices are connected by an edge independently with a probability that is a bi-variate function of the weights of the vertices, and single vertices are connected to themselves by a self-loop independently with a probability that is a uni-variate function of the weight of the vertex. We apply a renormalisation transformation in which vertices are aggregated into groups of equal size according to a greedy algorithm, namely, distinct groups of aggregated vertices are connected by an aggregated edge if and only if there is at least one edge connecting two constituent vertices across the groups, while a group of aggregated vertices is connected to itself by an aggregated self-loop if and only if there is at least one self-loop at an internal vertex or one edge connecting a pair of distinct internal vertices. We analyse what happens when the renormalisation transformation is iterated. In particular, we show that, starting from appropriately scaled connection functions, the iterated renormalised graphs converge to a two-parameter family of random graphs, acting as an attractor in a universality class. We consider a light-tailed regime, for which the scaling limit is a homogeneous Erdős–Rényi random graph, and a heavy-tailed regime, for which the scaling limit is an inhomogeneous random graph with stable infinite-mean random weights and an exponential disconnection function. Different scalings are needed for the two regimes. Which of the two regimes prevails depends on the choice of the connection functions and the choice of the law of the random weights.

We study spatial averages of the mild solution to a one-dimensional space–time fractional stochastic heat equation driven by space–time white noise. For fixed \(t>0\), we prove a quantitative central limit theorem for the normalized spatial average over \([-R,R]\): as \(R\to\infty\), its law converges to the standard normal law at rate \(R^{-1/2}\) in total variation distance. The proof relies on the Malliavin–Stein method, combined with precise estimates for the space–time fractional heat kernel and for the Malliavin derivative of the mild solution. We further establish a functional central limit theorem.

We study homogeneous diffusion martingales evolving in a bounded state space $D=[a,b]$, where $a$ and $b$ are zeros of the diffusion coefficient. We call a process of the form $Z_t=\mathbb{E}[B\mid\mathcal{F}_t]$, with $B$ a Bernoulli random variable, a Bernoulli-Doob martingale. Our main results establish a complete equivalence: every such diffusion martingale is a Bernoulli-Doob martingale (Theorem 2) and, conversely, every continuous time-homogeneous Markov Bernoulli-Doob martingale on a Brownian filtration arises from such a diffusion (Theorem 3). The intuitive reason is that a bounded martingale has constant expectation while accumulating variance, so it converges to the maximum-variance distribution with given mean and range, namely the Bernoulli. We further show that this Bernoulli limit is truly asymptotic: for any fixed finite horizon $T$, the probability of not yet having reached the boundary is strictly positive (Theorem 4), even when the individual boundaries are accessible. We clarify the relationship between Feller's boundary classification, the pathwise SDE framework, and the martingale constraint, showing that the martingale property forces absorption at any attainable boundary. The theory is illustrated with the $\Phi$-martingale, the Jacobi martingale, and applications to credit-risk modelling.

For a regular higher order Markov chain, its reduced first order chain may be reducible. When the reduced first order chain is reducible, it does not have a unique stationary distribution. However, it has been shown that the probability distribution of the current state of a regular higher order chain converges to a unique limiting probability distribution. In this paper, we interpret this limiting distribution as a marginal stationary distribution and prove some properties of marginal stationary distributions. We then establish some convergence rate results for such type of convergence. Finally, we introduce two types of marginal mixing times, which extend the notions of mixing times for first order Markov chains to higher order chains.

We show that a random sample from an arbitrary probability measure on $\mathbb{R}^d$ is close to a low-discrepancy point set. Namely, after moving only a small fraction of the sample points in expectation, one obtains an $n$-point set with star discrepancy $\operatorname{polylog}(n)/n$ with respect to the original measure.