Probability
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Thursday 20 August
We establish marginal and functional convex order comparisons for graphon mean-field systems on $\mathbb{R}^d$, including the infinite-horizon setting. A key difficulty is that convex order cannot in general be transferred through the usual particle approximation, which requires us to work directly with Euler schemes for the graphon mean-field system. Under a suitable dissipativity condition, we establish Euler approximation estimates that are uniform in both time and the agent label, and combine them with forward-backward induction arguments to obtain the convex order comparisons. For the infinite-horizon problem, dissipativity provides the required uniform-in-time stability, while an exponentially weighted $L^2$-space enables trajectory-level convergence and leads to the functional convex order on $[0,\infty)$. As an application, we derive value-function comparisons for a class of one-dimensional linear-quadratic graphon mean-field games.
Probability
Computing transient probabilities in Markovian queues with balking conditional on a fixed number of joined customers
We analyze the transient behavior of a Markovian queue with balking, conditional on exactly $K$ customers joining the system in a finite time interval $[0, T]$. A key quantity of interest is the cumulative number of balking customers, for which we consider the probability generating function (PGF) and derive an equation it satisfies. This approach circumvents the computational burden arising from dealing with high-dimensional Markovian system, which arises when attempting to directly compute the joint distribution of the cumulative number of balking customers together with the total number of joining customers and the number of customers in the system. To compute state transitions in $(t, T]$ efficiently, we examine the conditional state probability at time $T$ given the system state at time $T - u$, and show that it satisfies a linear differential equation in $u$. For piecewise-constant arrival rates, we develop a numerical procedure for evaluating the moment of the total number of balking customers, jointly with the cumulative number of joining customers and the number of customers in the system, under the condition that $K$ customers joined. We also present numerical examples that highlight counterintuitive behaviors arising from this conditioning, along with explanations of the underlying mechanisms.
Read the full abstract
Wednesday 19 August
Probability
Brownian Loops, Singular Homology, and Asymptotic Cycles
Let $M$ be a closed connected Riemannian manifold. A continuous semimartingale segment can be closed by a Borel family of paths of uniformly bounded length, producing a singular homology class $H_t\in H_1(M;\R)$. For every linear choice of smooth closed representatives of $H^1(M;\R)$, the corresponding Stratonovich homology differs from $H_t$ by a uniformly bounded term, almost surely and uniformly in time. The classes $H_t$ are additive under time shift up to a uniformly bounded error. For Brownian motion this comparison yields the Gaussian central limit theorem with covariance given by the normalized Hodge inner product, a functional central limit theorem for the polygonal interpolation of the closed homology classes, and the almost sure limit $H_t/t\to0$. For elliptic diffusions, the large-deviation principle of Galkin–Mariani passes to $H_T/T$ with the same rate function. The construction uses Schwartzman's closing procedure and is independent, at these asymptotic scales, of the chosen bounded closing family.
Read the full abstract
Probability · Cross-listed from math.ST
Poincaré's Inequality on Sliding-Window Occupation Count Kernels and the Optimal Normalized Spectral-Gap Constant
Let $P$ be an irreducible reversible Markov kernel on an $m$-state space $\Omega$, and denote its right spectral gap by $\Gap(P) =1-\lambda_2(P)$. From a stationary trajectory, let $K_t$ be the occupation-count vector of the length-$n$ window beginning at time $t$. The stationary pair $(K_0,K_1)$ defines a reversible projected count kernel $\widetilde P_n$. For each fixed $m\ge2$, define \[ c_m^\star= \inf_{\substack{|\Omega|=m,\ P\ \mathrm{irreducible\ and\ reversible} n\ge2}} \frac{n\Gap(\widetilde P_n)}{\Gap(P)}. \] We prove \[ \frac1{1080m}\le c_m^\star\le q_{m-2}, \qquad q_0=\frac14,\quad q_{r+1}=q_r(1-q_r). \] We also show $q_{m-2}=(m+\log m+O(1))^{-1}$, which implies that $c_m^\star=\Theta(m^{-1})$. Thus, the reciprocal optimal comparison cost $C_m^{\mathrm{opt}}=(c_m^\star)^{-1}$ has order $m$. In the two-state case, we determine the exact values $c_2^\star=1/4$ and $C_2^{\mathrm{opt}}=4$. %the exact constants for $m\ge3$ remain open. The lower bound also holds for $n=1$ and is uniform in $P$, including sparse and periodic kernels. The proof combines short-window decorrelation with an averaged anchor-excursion decomposition, a Green-kernel hitting estimate, and a stopped Carleson–Hardy inequality. A nested rare-state construction produces finite $m$-state witnesses whose normalized Rayleigh quotients approach $q_{m-2}$ through an ordered sequence of limits. For every fixed finite irreducible reversible aperiodic kernel on at least two states, $\Gap(\widetilde P_n)=\Theta_P(n^{-1})$.
Read the full abstract
Probability · Cross-listed from math.ST
Type-II Error Bounds for Test Supermartingales from Lower-Tail Hypotheses
In safe hypothesis testing with test supermartingals, Ville's inequality provides anytime-valid type-I error guarantees for every significance level $\alpha\in(0,1]$, if one rejects the null hypothesis whenever the wealth process first exceeds $\frac{1}{\alpha}$. Due to an inherent asymmetry, the type-II error does not have such guarantees: a heavy concentration of the probability on the lower tail of the log-increments can lead to one catastrophic bet that undoes any amount of accumulated evidence. This paper studies how different hypotheses on those lower-tail probabilities lead to different bounds on the type-II error of the sequential test. They all reduce to one master inequality, which bounds the type-II error at level $\alpha$, at a fixed horizon and sequentially, in terms of a one-sided Legendre transform of the (inverse-)moment generating function of the e-variables, evaluated at one number: the amount by which the lower bound of the accumulated e-powers exceeds $\log\frac{1}{\alpha}$. And, the step is lossless, in the sense, that it extracts exactly a constrained information projection. Every bound presented here is a corollary, obtained by a certain majorant of the above function. The hypotheses are: a finite negative moment; an exponentially small crash probability with a moment on the winning side; a wealth floor with a conditional variance, and its Bernstein variant, which interpolates between a Gaussian regime set by the variance and an exponential one set by the scale; a sub-Gaussian or bounded-tilt lower tail; bounded log-increments; and i.i.d. increments, where the majorant is the truth. We also provide an empirical-Bernstein variant. Each hypothesis may either be read as a condition on the e-variables one has, or as the price of betting with an approximation to the likelihood ratio rather than the ratio itself, which satisfies the weakest condition for free.
Read the full abstract
Probability · Cross-listed from math.ST
The Type-II Error of Test Supermartingales: e-Power versus the Chernoff-Stein Exponent
In safe hypothesis testing with test supermartingales, Ville's inequality provides anytime-valid type-I error guarantees for every significance level $\alpha\in(0,1]$, if one rejects the null hypothesis whenever the wealth process first exceeds $1/\alpha$. Due to an inherent asymmetry, the type-II error behaves differently. We prove two things about the latter, for a simple null and alternative. First, the mean growth rate $\mathbb{E}_{P_1}[\log E]$, the e-power, that Kelly betting and growth-rate-optimal e-variables maximise, bounds nothing on its own. For every level $c>0$, every $\alpha$ and horizon $t$ we construct e-variables of conditional e-power exactly $c$ whose probability of not rejecting by $t$ is arbitrarily close to one. It forces eventual rejection, but no finite-horizon guarantee follows. Second, the quantity that does control the type-II error is the Chernoff-Stein exponent of an e-variable, $\Lambda(E)=\sup_{s\ge0}\{-\log \mathbb{E}_{P_1}[E^{-s}]\}$, whose range is exactly determined: $\sup_E \Lambda(E)=\mathrm{KL}(P_0\|P_1)$, the classical Chernoff-Stein exponent, and so the ceiling of its own per-e-variable form. One conditional application of Hoelder's inequality per step gives it, for every test supermartingale on an arbitrary filtered space, with no independence or product structure; the i.i.d. case adds that it is matched, and attained by nothing. The e-power has its own ceiling, $\mathrm{KL}(P_1\|P_0)$, and that one is attained, $P_0$-a.s. uniquely, by the likelihood ratio $R$. The two optima are the same divergence in opposite arguments, at opposite ends of the flattened family $R^{\beta}/\mathbb{E}_{P_0}[R^{\beta}]$: the ceiling as $\beta\downarrow0$, $R$ at $\beta=1$. Which $\beta$ is best is settled by the horizon, exactly: $R$ is optimal at $t=\log(1/\alpha)/\mathrm{KL}(P_1\|P_0)$ alone, beaten by sharpening $(\beta>1)$ below it and by flattening above.
Read the full abstract
Probability
Nonlocality of Cover-Time Changes Under Edge Addition
Let $G$ be a finite connected simple graph, let $uv$ be a nonedge, and let $s$ be a starting vertex. We study the exact change in the expected cover time of simple random walk when $uv$ is inserted. A killed Green matrix update, combined with target-set inclusion-exclusion, gives an exact formula using only the original graph. The response can have either sign. Our main result is a nonlocality theorem. For every radius $r\geq 1$, we construct two marked configurations whose ambient-degree-labelled radius-$r$ neighbourhoods at $s,u,v$ are isomorphic but whose fixed-start cover-time responses have opposite signs. The construction also matches the three marked degrees, the marked distance, and the effective resistance $R_{uv}$. The two graphs have different orders; equal-order nonlocality remains open. We complement this result with a conductance interpolation theorem and an occupation interpretation of its high-conductance coefficient. After contracting $u$ and $v$, that coefficient is a positive multiple of the expected pre-cover occupation of the contracted vertex, and its zero case is classified exactly. A path with two pendant insertion endpoints is solved for all starting vertices and shows a sharp change of sign across the start set.
Read the full abstract
Probability
Penalisation of Two-Dimensional Brownian Motion
We study a penalisation problem for two-dimensional Brownian motion. Starting from the Wiener measure, we consider a family of probability measures obtained by weighting paths by a nonnegative functional $F_t$ depending on $t \geq 0$, $F_t$ being measurable with respect to the $\sigma$-algebra generated by the path up to time $t$. Under suitable assumptions on the penalisation process, we establish the weak convergence of these measures when $t \rightarrow \infty$. The limiting law is identified explicitly in terms of a $\sigma-$finite measure $\mathbf{W}^{(2)}$, which admits a path decomposition involving the last hitting time of a circle. This decomposition plays a central role in the analysis and yields a martingale representation of the limiting measure. where ordering and local time techniques are no longer available. The proofs rely on Laplace transform methods and Tauberian theorems, which replace excursion-theoretic tools and allow a precise identification of the limiting measure and its structural properties.
Read the full abstract
Probability
An optimal Poincaré inequality for the complex Ginibre log-gas
We establish an optimal Poincaré inequality for real-valued symmetric observables of the complex Ginibre log-gas. Equality is attained by the real and imaginary parts of the center-of-mass observable. Equivalently, we determine the exact spectral gap of the associated overdamped Langevin dynamics, for real symmetric observables. The Hessian of the energy of this log-gas is unbounded below, so standard convexity arguments do not directly apply. The proof instead combines a Vandermonde transform, a holomorphic projection, and a complex Gaussian d-bar spectral-gap estimate, corresponding to the constant-curvature case of the Hörmander-Berndtsson estimate. It is short and self-contained. It remains valid, beyond the quadratic potential, for rotationally invariant additive plurisubharmonic potential perturbations. Additionally, we provide four alternative proofs, two of which yield sum-of-squares formulas for the deficit, based respectively on a Hermite expansion and on an integrated Bochner-Kodaira formula, the other two use the spectral analysis of a two-sided number-operator factorization and a Hermite-Slater polynomial expansion. We furthermore present new results related to linear statistics, Gaussian factorization, polynomial eigenfunctions, log-Sobolev inequalities, matrix lift and eigenvector overlaps, and non-quadratic potentials.
Read the full abstract
Probability
Probabilistic Representation and Convergence of Gromov-Wasserstein Gradient Flows
Wasserstein gradient flows are intimately connected with evolution partial differential equations and diffusion processes. We take the first step in developing such connections for inner product Gromov–Wasserstein (IGW) gradient flows by studying the IGW gradient flow of the relative entropy $\mathsf{H}(\cdot\|\gamma)$ with respect to the standard Gaussian measure $\gamma$. We first show that $\mathsf{H}(\cdot\|\gamma)$ fails to be $\lambda$-convex along generalized or modified generalized IGW geodesics for any $\lambda \in \mathbb{R}$, and therefore falls outside the scope of the existing IGW gradient flow theory from Zhang et al. (2026). We bridge this gap by establishing a suitable local convexity estimate that enables the construction of the gradient flow and its extension to the infinite time horizon. We then obtain increasingly explicit representations of the resulting dynamics. Starting from a partial integro-differential equation, we derive a nonlinear Fokker–Planck equation and show that its second-moment dynamics decouple from the law as they satisfy an autonomous matrix ODE. This reduces the IGW dynamics to a linear, time-inhomogeneous Fokker–Planck equation, yielding a probabilistic representation as the time-marginal flow of a linear stochastic differential equation resembling the Ornstein–Uhlenbeck process. Finally, we study its asymptotic behavior by establishing exponential convergence of the flow to $\gamma$ in relative entropy.
Read the full abstract
Probability
A random walk on p-groups with a symmetric perfect pairing
The kernel of a random symmetric p-adic matrix is a random abelian group, equipped with a symmetric pairing. If we consider not only the matrix but also its top-left corners, we get a process valued in isomorphism classes of abelian groups, equipped with such a pairing. We show that when the matrix is Haar random, this process is a Markov chain, generated by an operator that we explicitly describe. We will also prove that this operator is reversible with respect to a Cohen-Lenstra type measure.
Read the full abstract
Probability · Cross-listed from math.CO
The critical probability for percolation on finite graphs
We determine the critical probability for Bernoulli bond percolation on essentially any finite graph. Namely, letting $\lambda(G)$ denote the spectral radius (maximum eigenvalue) of $G$, we prove that the critical probability is at $1/\lambda(G)$: above this probability there is typically a component of order $\Omega(\lambda(G))$, whereas below it all components are of order at most $O(\sqrt{|G|})$. These results in particular confirm a conjecture of Krivelevich and Samotij about percolation on graphs of a given average degree, and vastly extend theorems of Bollobás, Borgs, Chayes, and Riordan, who proved analogous results but only for dense graphs. Our theorems are optimal in many regimes, and also demonstrate that percolation has an unexpectedly subtle behaviour on graphs whose spectral radius is roughly the square root of their maximum degree.
Read the full abstract
Probability
Record times for coverage thresholds and maximal spacings
Let $X_1,X_2, \ldots $ be independent uniform random points in a bounded region $A \subset {\bf R}^d$ having a smooth boundary, $d \geq 1$. Let $B \subset A$ be compact. The _coverage threshold_ of $B$, $R_n$, is the smallest $r$ such that $B$ is covered by the balls of radius $r$ centred on $X_1,\ldots,X_n$. The _maximal spacing_ $\tilde{R}_n$ is the volume of the largest ball contained in $A \setminus \{X_1,\ldots,X_n\}$. We investigate the asymptotic frequency of _record times_ in the sequence $(R_n)$, that is times $n$ for which $R_n < R_{n-1}$. Let $N_m$ denote the number of records in the sequence $(R_n)$ up to time $m$, and let $\nu_m$ be the time at which the $m$th record value of the sequence $(R_n)$ occurs. For $B \subset A^o$, we show that almost surely, $N_n \sim \frac12 (\log n)^2$ and $\nu_n^{1/\sqrt{n}}\to \exp \big(\sqrt{2}\: \big)$ as $n \to \infty$, and likewise for $\tilde{N}_n$ and $\tilde{\nu}_n$, defined analogously in terms of $(\tilde{R}_n)$. But if $B=A$ and $d \geq 3$, then $N_n \sim \frac12 (1- \frac{1}{d}) (\log n)^2$ and $\nu_n^{1/\sqrt{n}}\to \exp \big( \sqrt{2d/(d-1)} \: \big)$. We also discuss the generalization (for fixed $k \in {\bf N}$) to $k$-coverage thresholds, maximal $k$-spacings and non-uniformly distributed points $X_i$ in $A$.
Read the full abstract
Probability
Boundedly exchangeable graphs
An infinite jointly exchangeable adjacency matrix is a mixture of graphon models, and its graph is almost surely empty or dense; classical matrix exchangeability therefore excludes sparse nonempty graphs. We study a point-process alternative, graph processes, whose vertices are identified with the atoms of a locally finite point process on a Polish latent space and whose edges are drawn conditionally independently from a symmetric connection kernel $W$. For a Poisson graph process with diffuse $\sigma$-finite intensity, we show that its edge measure is jointly exchangeable as a random measure if and only if $W$ is essentially constant. Non-constant kernels therefore require a different exchangeability notion. We introduce bounded exchangeability, under which every nontrivial bounded restriction determines an infinite jointly exchangeable adjacency matrix that is unique in distribution, with an associated local graphon representation. We then study threshold models on homogeneous Riemannian manifolds, in which Poisson-distributed vertices are connected whenever their intrinsic distance is at most a fixed threshold. On every infinite-volume manifold in this class, the model is sparse, its empirical degree distribution converges to a Poisson law, and its limiting clustering coefficient depends on an additional geometric parameter that can vary while the limiting degree law is held fixed.
Read the full abstract
Probability
Online Permutation Embedding: Optimal Stopping and Scaling Laws
We study optimal online algorithms for embedding a permutation $\pi$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $\pi=\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $\pi$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target permutations, as well as the extremal problem of identifying the permutations with largest expected online embedding time. Our second main result shows that, to first order, random permutations are strictly faster to embed than monotone permutations, which in turn are strictly faster to embed than the extremal permutations. This separation stands in sharp contrast to prevailing conjectures and heuristics in the offline theory of permutation embeddings.
Read the full abstract
Probability
A Sharp Joint Bias-Energy Envelope for Radial Clipping
Radial clipping does two things at once: it removes the part of a vector outside a ball and retains a bounded vector inside the ball. The removed part produces bias, while the squared norm of the retained part produces energy. We determine the exact joint price of these effects when only a $p$-moment, $1<p\le2$, is available. The problem turns out to be one-dimensional: everything is decided by the position of one point along a ray. At $\alpha=p\beta$, the extremal configuration changes. On one side a worst point can be chosen on the clipping sphere; on the other the unique positive extremal radius moves outside. When $p=2$, all inner radii tie in the first regime. The resulting constant is optimal both in the deterministic inequality and in the corresponding Hilbert-space stochastic problem. In the first regime, a symmetric law attains the bound. In the second, the supremum is not attained, but a two-point family with an increasingly rare outlier approaches it. We also show how the same transition determines the sharp bias-energy frontier. We conclude with statistical consequences and an application to online learning.
Read the full abstract
Probability
Proving Lehner's formulas via RDT – indefinite and asymmetric scenarios
The strong asymptotic freeness established in [28,53] allows for the study of norms of Gaussian matrix polynomials via corresponding free operator counterparts. For spectral edges of semicircular free counterparts to symmetric Kronecker-Gaussian matrices, Lehner in [39] determined closed-form analytical characterizations. As an alternative to classical spectral methods, in [62], we created a Random Duality Theory (RDT) based framework for studying these problems and reproved Lehner's formula for definite matrix coefficients. In this work, we develop the RDT machinery further and achieve strong progress in several key directions: (i) Symmetric Square Case: We consider indefinite matrix coefficients and provide spectral edges lower bounds that match Lehner's formula. (ii) Asymmetric Non-Square Variants: We establish RDT asymmetric analogues to Lehner formulas and prove that they lower-bound the spectral edges. (iii) Interlaced Decoupling Property: We uncover that the obtained analogues exhibit a remarkable interlaced decoupling property. Additionally, we consider semi-definite programming (SDP) formulations that allow for the practical solution of the obtained analytical characterizations. Theoretical predictions obtained through solving SDPs are compared to numerical simulations, showing a striking agreement even for problem dimensions on the order of a few hundreds.
Read the full abstract
Probability · Cross-listed from cs.LG
On the Slow Convergence to Trivial Solutions of Algorithms for Hard Optimization Problems
Hard combinatorial optimization problems, many of which are NP-hard, present fundamental algorithmic challenges. Average-case analysis on random instances has emerged as a powerful framework for understanding typical algorithmic performance beyond worst-case guarantees. A substantial body of work has established negative results: for sufficiently hard instances (often controlled by the underlying graph connectivity/constraints density), no known polynomial-time algorithm can significantly outperform naive heuristics in the double asymptotic limit where both problem size and constraints density tend to infinity. We revisit this picture by studying the finite-size behavior of some optimization algorithms across easy, intermediate, and hard regimes. Through rigorous analysis of large-graph asymptotics combined with numerical experiments on canonical problems (maximum independent set and maximum $K$-SAT), we demonstrate that while algorithms do eventually converge to theoretically predicted bounds, this convergence can be remarkably slow. In the intermediate regime where instances are already highly constrained, local algorithms achieve solutions substantially better than their predicted performance in the high-constraint-density limit. This gap between finite-regime and asymptotic behavior has important practical implications: sophisticated algorithmic design remains crucial even when asymptotic theory predicts inevitable failure.
Read the full abstract
Probability
The Parabolic Anderson Model's Total Mass at Small Times: Geometry, Fluctuations, and Renormalization
Let $D\subset\mathbb R^d$ be a bounded domain, let $\kappa>0$ be fixed, and let $W$ be a fractional Brownian sheet on $\mathbb R\times\mathbb R^d$. Consider the Stratonovich parabolic Anderson model (PAM) $\partial_tu_\kappa=(\frac12\Delta+\kappa W')u_\kappa$ with Dirichlet boundary condition on $D$ and the flat initial condition $u_\kappa(0,\cdot)=\mathbf 1_D$. We calculate exact asymptotics for the expectation and the standard deviation of the total mass $\int_Du_\kappa(t,x)~\mathrm d x$ as $t\to0$ under the assumption that $W$'s Hurst indices are all at least $1/2$ and that $u_\kappa$'s moments are finite for small enough $t>0$. In doing so, we uncover that these asymptotics are determined by a competition between three mechanisms: (1) $\mathbf{Geometry}$: The rate of heat diffusion through the boundary $\partial D$. (2) $\mathbf{Fluctuations}$: $W$'s time Hurst index. (3) $\mathbf{Renormalization}$: The singularity of deterministic Stratonovich corrections. As a result, we identify novel phase transition phenomena, which arise from the influence of $W$'s Hurst indices on the relative magnitudes of these contributions.
Read the full abstract
Probability · Cross-listed from q-fin.PR
When to Sell an Asset? - A Distribution Builder Approach
We consider the question of the optimal timing of the sale of an asset with stochastic dynamics. Our analysis is based on the method of the distribution builder introduced by Sharpe, Goldstein and Blythe [SGB00] for the purpose of optimal portfolio selection. Instead of specifying a utility function or risk aversion coefficient, this tool directly elicits the target distribution of the investor. We show how the problem of an optimal asset sale is in this setting linked to the problem of finding a Skorokhod embedding of a distribution into a diffusion process. In the case where the asset process follows a geometric Brownian motion and a specific family of distributions is targeted, one can observe a risk-return tradeoff.
Read the full abstract
Probability
Regularity Preservation for Jump-Type Stochastic Transport Equations with Singular Drift
We study a first-order stochastic transport equation driven by Brownian transport noise and a nonlinear state-dependent Poisson jump term. The drift vector field is merely integrable and satisfies the subcritical Krylov–Röckner condition. The dependence of the jump coefficient on the solution creates a nontrivial coupling between the solution value and its spatial gradient. To handle this coupling, we construct a stochastic characteristic system for the position, the solution value, and the gradient, and derive a characteristic representation by means of an Itô–Wentzell formula with jumps. For singular drifts, we combine smooth approximation, the Zvonkin transformation, estimates for stochastic flows, and stochastic Gronwall inequalities to pass to a weakly differentiable limit. Uniqueness is established directly in the weakly differentiable class through a renormalized energy estimate for the difference of two solutions, including the contribution of the Poisson compensator. Under suitable integrability and differentiability assumptions on the jump coefficient, we prove the existence and uniqueness of weakly differentiable solutions. We further show that the first-order spatial Sobolev regularity of the initial datum is preserved by the evolution.
Read the full abstract
Probability · Cross-listed from cs.DS
An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs
We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $\lambda$ is upper bounded by a constant and $\lambda(1 - \beta) \lesssim \Delta^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.
Read the full abstract
Probability
Randomly Permuted Orthogonal Products and Fast Dimension Reduction
We study the effect of random signed permutations on products of orthogonal matrices and their applications to fast dimension reduction. Let $A,B \in \mathbb{R}^{d\times d}$ be orthogonal matrices and let $\Sigma \in \mathbb{R}^{d\times d}$ be a uniformly random signed permutation matrix. We analyze the random orthogonal matrix \[ U=A \Sigma B, \] and show that, under mild assumptions on the size of the entries of $A$ and $B$, \[ \max_{i,j=1,\ldots,d} |U_{ij}| =O\left ( \sqrt{\frac{\log d}{d}}\right ) \] with high probability. As an application, we show that ORA, an analogue of the Kac walk in which every update is a $\pi/4$ rotation, reaches the same maximal entry scale after $O(d\log d)$ updates. This resolves a question of Jain et al. and improves the running time of their construction. We also show that parallel ORA reaches this scale after $O(\log d)$ rounds. We then study the random embedding \[ \Phi = \sqrt{\frac{d}{m}}\, P_I U D_{\xi'}, \] where $P_I$ restricts to $m$ coordinates and $\xi'$ is an independent Rademacher vector. We identify two parameters controlling norm preservation and show that, throughout the corresponding admissible range, $\Phi$ achieves optimal embedding dimension $m\asymp\varepsilon^{-2}\log(N)$. Finally, we extend the result to structured infinite models, including sparse vectors, low-rank matrices, and finite unions of subspaces.
Read the full abstract
Probability · Cross-listed from cs.CE
Process Optimization Under Uncertainty for Improving the Bond Quality of Polymer Filaments in Fused Filament Fabrication
This paper develops a computational framework to optimize the process parameters such that the bond quality between extruded polymer filaments is maximized in fused filament fabrication (FFF). A transient heat transfer analysis providing an estimate of the temperature profile of the filaments is coupled with a sintering neck growth model to assess the bond quality that occurs at the interfaces between adjacent filaments. Predicting the variability in the FFF process is essential for achieving proactive quality control of the manufactured part; however, the models used to predict the variability are affected by assumptions and approximations. This paper systematically quantifies the uncertainty in the bond quality model prediction due to various sources of uncertainty, both aleatory and epistemic, and includes the uncertainty and the model discrepancy in the process parameter optimization. Variance-based sensitivity analysis based on Sobol indices is used to quantify the relative contributions of the different uncertainty sources to the uncertainty in the bond quality. A Gaussian process (GP) surrogate model is constructed to compute and include the model discrepancy within the optimization. Physical experiments are conducted for calibration and validation of the physics model and also for validation of the optimum solution. The results show that the proposed formulation for process parameter optimization under uncertainty results in high bond quality between adjoining filaments of the FFF product.
Read the full abstract
Tuesday 18 August
Probability · Cross-listed from stat.ME
A Self-Exciting Model of Eddy Formation at Submesoscale
Ocean eddies are highly dynamic structures marked by frequent splitting and merging events. They exhibit complex spatio-temporal clustering that traditional Poisson models fail to capture. In this paper, a novel spatio-temporal Hawkes process is introduced to model self-exciting eddy fields on the basis of high-frequency ocean flow data. We formulate a triggering kernel that couples the self-excitation intensity with spatial deformation caused by the strain rate magnitude. To characterize the asymptotic behavior of the eddy field, we derive a Volterra integral equation that governs the expected eddy intensity over time and space. We develop an Expectation-Maximization (EM) algorithm that treats the unobserved parent-child relationships as latent branching structures for parameter estimation. We further extend this framework to accommodate a time-varying, non-homogeneous background intensity, modifying both the EM updates and the analytical Volterra solution accordingly. Finally, we propose a two-stage simulation framework utilizing a cluster representation algorithm. The simulated empirical paths of eddy formation are compared together with numerical solution of the Volterra equation for mean rate as validation of the Hawkes model.
Read the full abstract
Probability
On Samuels' Conjecture
Let $0\leq\mu_1\leq\cdots\leq\mu_n$ and let $\lambda>\sum_{i=1}^n\mu_i$. Let $X_1,...,X_n$ be independent nonnegative random variables satisfying $\mathbb{E}X_i=\mu_i$, and write $D_i := \lambda-\sum_{k=1}^{i-1}\mu_k$ for $1\leq i\leq n$. We prove that $$ \inf_{X_1,...,X_n} \mathbb{P}\left( \sum_{i=1}^nX_i<\lambda \right) = \min_{1\leq i\leq n} \prod_{j=i}^n \left( 1-\frac{\mu_j}{D_i} \right). $$ The bound is sharp and is attained. This proves Samuels' conjecture. Feige's conjecture is thereby resolved, since it follows immediately from the equal-means case. The proof is self-contained.
Read the full abstract
Probability
Asymptotics for Beta-Splitting Trees via Homogeneous Fragmentations and Meromorphic Potential Theory
Inspired by recent work of Aldous, Janson, and Pittel on the critical beta-splitting model, we study the full beta-splitting family for beta greater than minus two through a canonical continuous-time embedding into a homogeneous exchangeable fragmentation. In this representation, the frequency of a tagged fragment is described by a subordinator. We express the continuous height of a typical leaf, its occupation probabilities, the discrete height, and the total continuous-time length in terms of the potential measure of this subordinator. Renewal theory yields first-order asymptotics and a central limit theorem for the continuous height. A regenerative-composition representation gives Gaussian limits for the discrete height above and at the critical value, and a non-Gaussian power-law limit below it. We also obtain residue expansions for the potential measure and the mean continuous height using meromorphic potential theory and generalized Nevanlinna functions. Finally, we study the maximum continuous-time height, proving a law of large numbers and a mixed Gumbel limit. At the critical parameter value, this resolves an open problem of Aldous and Janson.
Read the full abstract
Probability
Critical tensor covariance at the Marchenko-Pastur threshold
For a centered, variance-one random variable $X$ with finite fourth moment, let $x$ be the vector of square-free degree-$d$ monomials in $n$ independent copies of $X$. At the critical scale $d^2/n \to \lambda \in (0,\infty)$, the normalized squared length of $x$ converges to the lognormal variable $R = \exp(\sqrt{\lambda v}\, Z - \lambda v/2)$, where $v = \mathbb{E} X^4 - 1$ and $Z$ is standard normal. If $\binom{n}{d}/N \to c \in (0,\infty)$, the sample covariance of $N$ independent copies of $x$ has an almost-sure limiting spectral law: the free compound-Poisson law with rate $1/c$ and jump distribution $\operatorname{Law}(cR)$. It reduces to Marchenko-Pastur when $\lambda v = 0$. The proof shows that subtracting the contribution of the sample length leaves vanishing quadratic-form fluctuations, even when $\mathbb{E} X^3 \neq 0$; length and direction need not be independent.
Read the full abstract
Probability · Cross-listed from math.ST
How far are $d$-dimensional copulas with uniform $(d-1)$-marginals from (total) independence?
We consider the family ${\mathcal{C}}_d^{\Pi_{d-1}}$ of all $d$-dimensional copulas whose $(d-1)$-dimensional marginals are all equal to the $(d-1)$-dimensional product copula $\Pi_{d-1}$ and tackle the natural question, `how far away' from the $d$-dimensional product copula $\Pi_d$ elements in ${\mathcal{C}}_d^{\Pi_{d-1}}$ can be. We provide definitive answers for both, the uniform metric $d_\infty$ as well as the stronger, conditioning-based metric $D_1$. The established results clearly indicate that the family ${\mathcal{C}}_d^{\Pi_{d-1}}$ is larger than one might expect.
Read the full abstract
Probability
The branching random walk in a uniform magnetic field : magnetization concentration and overlap distributions
Adding a uniform external magnetic field to a mean-field spin-glass model usually requires a new analysis specific to the model. The disordered system we consider corresponds to the Gaussian binary branching random walk (BRW) - in the spirit of Derrida and Spohn [21] and studied from the statistical-physics point of view by Jagannath [22] - and we prove that this is not the case : a single elementary observation - that the resulting Hamiltonian is still a BRW, now with independent, but non-identically distributed, displacements - allows us to use the available results for general BRW. Combining classical and recent results on general BRW (Biggins [3], Chauvin and Rouault [13], Mallein [25]), one obtains an essentially complete picture of the model in an external magnetic field : the ground state, the free energy, the one-step replica symmetry breaking (1-RSB) transition, and the limiting genealogical overlap distribution with Poisson-Dirichlet statistics for the Gibbs weights. We then prove a strong concentration result for the magnetization under the Gibbs measure at low temperature, giving its explicit optimal value. It turns out that this one-replica statement is not enough to control the classical Ising overlap between two independently sampled configurations : an elementary counterexample (Remark 4.1) shows that concentration of each replica's magnetization does not, by itself, determine their joint correlation. We address this by developing a two-replica large-deviation argument - resting on the classical method of types and the subadditivity of Shannon entropy, and taking the form of a uniform Chernoff bound over the joint empirical type of a pair of configurations, matched against a two-replica concentration estimate - which we use to obtain the distribution of a second (Ising) hypercube-type overlap.