Peer Revenue Fully funded

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics Probability

math.PR Watch Probability (sign in to use)

Thursday 16 July

Probability · Cross-listed from math.CO

Limit laws of random simplex tree-child networks

We prove that the longer and shorter Sackin indices of a uniformly random simplex tree-child network with $n$ taxa admit joint distributional limits after rescaling by $n^{-7/4}$. The limiting distributions are described by functionals of a Brownian excursion. We also identify the limiting law of the height after rescaling by $n^{-3/4}$, thereby answering a question of Zhang~(2022). Moreover, we establish sharp tail bounds for the height, which imply convergence of all moments in the above distributional limits. We further obtain a scaling limit for the entire height profile of the leaves. Finally, we determine the local limits of large simplex networks around the fixed root, a uniformly random vertex, and a uniformly random leaf.
Read the full abstract

Probability · Cross-listed from quant-ph

Counterexamples to additivity of minimum output $p$-Rényi entropy of quantum channels for all $p\ge 0$

The additivity of minimum output entropies is a central problem in quantum information theory. Nonadditivity is known for every Rényi order $p>1$, at the von Neumann point $p=1$, and for sufficiently small positive $p$, while much of the interval $0<p<1$ has remained open. In this work, we prove that for every $p>0$ there exist finite-dimensional quantum channels whose minimum output $p$-Rényi entropies violate additivity. Our proof combines two constructions: random projection-induced channels yield nonadditivity for $p>3/4$, and antisymmetric postprocessing extends the violation to all positive Rényi orders. Our estimates also improve the output-dimension bound obtained by Belinschi, Collins, and Nechita for additivity violation of minimum output von Neumann entropy.
Read the full abstract

All authors Debbie Leung, Benjamin Lovitz, Ion Nechita, Peixue Wu

Probability · Cross-listed from stat.CO

Delocalization of bias in unadjusted Hamiltonian Monte Carlo and underdamped Langevin

Unadjusted samplers such as unadjusted Hamiltonian Monte Carlo and underdamped Langevin are well-known to be biased. Metropolis–Hastings adjustment has been conventionally incorporated into Hamiltonian Monte Carlo to eliminate the bias. However, this adjustment can significantly increase the iteration complexity due to the small step size required for reasonable Metropolis acceptance rates. In this work, we extend the delocalization of bias phenomenon, previously established for the overdamped Langevin algorithm, to these two unadjusted algorithms. We show that to control the $W_2$ bias of any $K$-dimensional marginal of a high-dimensional distribution, $O(\sqrt{K})$ integration steps suffice up to $\log d$ terms, assuming either weak or sparse interactions among variables. The discrete-time integrators here introduce technical difficulties beyond those of the overdamped setting, which we address through a broadly applicable matrix-polynomial framework that characterizes their propagators. Our result for the underdamped Langevin algorithm is valid for all large friction parameters, implying that the Leimkuhler-Matthews integrator for the overdamped Langevin dynamics also exhibits delocalization of bias.
Read the full abstract

All authors Yifan Chen, Xiaoou Cheng, Jonathan Niles-Weed, Jonathan Weare

Probability

On the absence of blow-up in the 3D Navier-Stokes equations with transport noise

Establishing the global-in-time smoothness of solutions to the 3D Navier-Stokes equations (NSEs) with large initial data remains a long-standing open problem. In this paper, we prove that the 3D NSEs driven by a suitably chosen transport noise – a physically motivated stochastic perturbation – admit global-in-time smooth solutions with high probability. This regularizing effect holds uniformly for initial data in arbitrarily large balls of subcritical function spaces with positive smoothness.
Read the full abstract

Probability

Asymptotics for the Laplace transform of the Elephant Random Walk via Schwarz-Christoffel mappings

We derive the long time asymptotic behavior of the Laplace transform of the Elephant Random Walk (ERW). The ERW is a generalization of the Simple Random Walk in which the past influences the future evolution of the process according to some memory parameter. Its transition kernel is neither space nor time homogeneous and its transition probability at the $n$th step can be written as a function of $n$ and the position of the walk at time $n - 1$. A recurrence relation for its Laplace transform allows one to find a generating function governed by a transport-type PDE whose solution can be written in terms of a Schwarz-Christoffel mapping, allowing a precise analytic control. This enables to apply singularity analysis methods to estimate the Laplace transforms.
Read the full abstract

Probability · Cross-listed from math.OA

Strongly convergent matrix models for $q$-Gaussian algebras

We construct strongly convergent finite-dimensional random matrix models for finite $q$-Gaussian family in the range $\vert q \vert < \sqrt{2}-1$. The construction has two stages. First, we show that normalized sums of graph-product semicirculars over an Erdos-Renyi graph satisfy the $q$-Toeplitz relations up to an operator norm error converging to zero in probability. Using ultraproduct methods, this yields complete strong convergence, uniformly over all matrix coefficient dimensions, for noncommutative polynomials with bounded degree. Second, we use a quantitative tensor-GUE for graph-product semicirculars to convert these operator models into finite-dimensional random matrices. For every fixed polynomial degree, the convergence is uniform over coefficient dimensions that may be larger than the dimension of the random matrices. As applications, in the above range of $q$, the C$^\ast$-algebra generated by a finite $q$-Gaussian family is MF, and the Brown-Douglas-Fillmore extension semigroup of the nontrivial C$^\ast$-algebra generated by a finite $q$-Gaussian family is not a group.
Read the full abstract

Probability · Cross-listed from q-fin.TR

Existence and convergence of discrete-time Kyle models with multiple insiders

Foster and Viswanathan (1996) extend the discrete-time setting of Kyle (1985) to multiple informed traders who have partial information about the stock's terminal dividend. We resolve two long-standing open problems in this literature. First, we prove that an equilibrium exists in the setting of Foster and Viswanathan (1996). Second, as the number of trading times goes to infinity, we prove that the discrete-time equilibrium converges to the continuous-time equilibrium already proven to exist in Back, Cao, and Willard (2000).
Read the full abstract

Probability · Cross-listed from cs.LO

Towards realistic large random models of labeled transition systems and their 0-1 laws

Model checking is the automated verification of properties (specified in some modal logic) in labeled transition systems (LTSs); it is an essential tool in ensuring software systems function as intended. State spaces of software grow exponentially, and heuristics are needed to ensure model checking remains feasible in real-world applications. Heuristics, in turn, require a good understanding on the typical behaviour of LTSs. In this paper, we use random graph theory to create a probabilistic model of large LTSs. From a theoretical analysis of the creation of large LTSs, backed by empirical data from the Model Checking Contest, we endow these models with realistic parameter values. Then, we analyze the asymptotic behaviour of this model under LTL and CTL, two modal logics popular in model checking. We show that, depending on the precise model, as the size grows to infinity we either have a convergence law (for every formula, the probability that it holds converges to a limit) or a 0-1 law (...and this limit is 0 or 1). We also discuss the theoretical complexity of determining these limits, and give algorithms for doing so. These results are the starting point towards a deep theoretical understanding of typical LTS behaviour, and highlight the promising applicability of random graph theory to model checking. \keywords{Model checking \and Random graphs \and 0-1 laws
Read the full abstract

Probability

Sharp phase transition for percolation with short-range dependencies

We show sharpness of the phase transition for a nearest-neighbour percolation model on $\mathbb Z^d$, where vertices carry independent types and the percolation probability of edges depends on the type of the adjacent vertices. Our proof uses the OSSS inequality and adapts to our setup the method developed in Duminil-Copin et al. (2017) for the random cluster model. Additionally, we provide a more extensive study of the special case of combined Bernoulli bond and site percolation featuring a phase transition with two parameters.
Read the full abstract

Probability

Graph alignment in sparse inhomogeneous models via self-overlap

We develop a general framework for understanding when graph alignment is information-theoretically feasible in sparse inhomogeneous random graph models, by studying the set of vertices on which the underlying matching can be recovered. Our main theorem gives a general lower bound on this set by leveraging the balanced load function introduced by Hajek (1990). The corresponding obstruction is captured by a new graph parameter, the self-overlap, which measures the extent to which a graph can imitate itself under a non-trivial relabelling. We then show that this criterion is sharp in a broad class of sparse inhomogeneous models, recovering known Erdős–Rényi phenomena and yielding sharp thresholds for Chung–Lu graphs and stochastic block models.
Read the full abstract

Probability · Cross-listed from cs.LG

Causal Inference for Sequential Settings under Interference and Latent Confounding

We study causal inference under outcome interference for sequential, observational settings. Specifically, we consider settings where the binary outcomes over N units are Markovian across T time steps. At each time step, the outcomes of N units have dependencies captured through an Ising model; each outcome is also impacted through an external field capturing the effects of its treatment as well as latent confounders. Similar to panel data literature, these latent confounders are modeled to have a low-rank factor structure. Our data is a single sample from this high-dimensional distribution. To estimate causal quantities of interest, we provide a computationally efficient method based on Maximum Pseudo-Likelihood Estimation (MPLE) for learning the model parameters. Under mild assumptions, we establish non-asymptotic consistency for parameter estimation and show this translates to faithful estimation of causal quantities of interest after sampling from the learned model. We demonstrate the efficacy of the method through synthetic experiments as well as a real-world case-study investigating causal effects of vaccine rates on COVID-19 death rates within US counties nationwide.
Read the full abstract

Probability · Cross-listed from math.OC

Finite-Dimensional Feedback Stabilization of Nonautonomous Stochastic Parabolic Equations

We investigate finite-dimensional feedback stabilization for nonlinear nonautonomous stochastic parabolic equations driven by $Q$-Wiener, covering both additive and multiplicative perturbations. The control is given by a finite linear combination of localized indicator-type actuators whose supports are selected as part of the construction and may have arbitrarily small total measure. The feedback law is constructed by means of oblique projections onto suitable finite-dimensional subspaces. Within the variational Gelfand triple framework, we prove well-posedness of the closed-loop system under standard coercivity, growth, and global Lipschitz assumptions. By appropriately choosing the actuator configuration and feedback strength, we establish exponential mean-square stabilization of the stochastic dynamics and, for pure multiplicative noise, almost-sure stabilization. A fully discrete three-layer implementation complements the theoretical results. Numerical experiments illustrate the influence of number of actuators, noise intensity, and nonlinear effects on the closed-loop stabilization behavior.
Read the full abstract

Probability

On the degree distribution of large tentacular Bienaymé-Galton-Watson trees

We study Bienaymé-Galton-Watson trees conditioned to have $n$ vertices and $k_n$ leaves, where $k_n\to\infty$ while remaining negligible compared to $n$, i.e. $k_n=o(n)$. More precisely, we determine the asymptotic distribution of the outdegrees of these trees. We first show that the tree is asymptotically binary: the number of vertices with two children is asymptotically equal to the number of leaves, while almost all remaining vertices have exactly one child. Then, we identify the scales at which vertices with larger outdegrees emerge. For every $d\ge2$, the critical scale $k_n \sim cn^{(d-1)/d}$, $c>0$, is the threshold for the appearance of vertices with outdegree $d+1$. Below this scale, such vertices are absent with high probability; at the critical scale, their number converges to a Poisson distribution; above it, they satisfy a law of large numbers. Our proofs rely on the coding of Bienaymé-Galton-Watson trees by their Łukasiewicz paths and asymptotic estimates for associated random walks.
Read the full abstract

Probability

Anchored Nash inequalities and heat kernel bounds for a class of random conductance models with long-range jumps

We show anchored versions of the Nash inequality for discrete non-local divergence-form operators with degenerate weights. They allow to control the $L^{2}$-norm of a function by Dirichlet forms that are not uniformly elliptic. We then use them to provide on-diagonal heat kernel upper bounds for a class of random conductance models with degenerate jump rates allowing long-range jumps. The results are established on a class of graphs including the integer lattice and possibly correlated supercritical percolation clusters.
Read the full abstract

All authors Sebastian Andres, Xin Chen, Martin Slowik, Kun Yin

Probability

On the entropy of the log-normal distribution

In a paper by Novi Inverardi and Tagliani from 2024 it is claimed that the log-normal density has maximal entropy in the class of densities having the same moments as the log-normal density. We disprove the claim by finding a family of densities with larger entropy.

Probability · Cross-listed from cs.CC

Space-Entropy Lower Bounds for Random Sampling

We prove fundamental space lower bounds for exact random sampling using an entropy source of i.i.d. uniform bits. A classic result from information theory shows that generating $n$ discrete random variables $X_1, \dots, X_n$ requires at least $H(X_1, \dots, X_n)$ input random bits on average, where $H$ is the Shannon entropy function. How much space must a random sampling algorithm use in order to approach this information-theoretically optimal entropy bound? We prove that any random sampling algorithm that is exact for arbitrary discrete target distributions and consumes at most $H(X_1,\ldots,X_n)+\varepsilon n+o(n)$ input bits in expectation for every output process must use $\Omega(\log(1/\varepsilon))$ bits of space. In fact, i.i.d. sampling from the single distribution $\mathrm{Bernoulli}(1/3)$ already forces at least $(1/{5.116201}-o(1))\log(1/\varepsilon)$ bits of space. If the sampler handles a family of infinitely many Bernoulli distributions, we show a sharper bound of at least $\log(1/\varepsilon)$ bits of space. We also prove lower bounds for general i.i.d. sampling: for almost every distribution on $k$ outcomes, the space is at least $(1/(k+1)-o(1))\log(1/\varepsilon)$ bits. The proof technique is based on a graph-theoretic analysis of the amount of information that any algorithm can store in its state. Finite state spaces force short cycles around the state-transition graph, and the loss around such cycles reduces to Diophantine lower bounds on fractional parts of integer combinations of log-probabilities. To the best of our knowledge, these results comprise the first known space lower bounds for entropy-efficient random sampling.
Read the full abstract

Probability · Cross-listed from math.ST

Precise sample covariance spectral norm error – an RDT view

We study the sample covariance error of centered Gaussians. A remarkable breakthrough [66] established the correct error scaling order and explicitly revealed the critical role of both the effective rank and the true covariance spectrum. In this work, we move beyond scaling characterizations and determine the precise limiting value of the error's spectral norm. To do so, we develop a generic framework based on Random Duality Theory (RDT). Within this framework, we first determine closed-form, explicit RDT-based upper bounds. We then establish complementary lower bounds by introducing a novel bilinear-quadratic RDT lower-bounding mechanism. By combining this mechanism with a two-replica systems bounding strategy, we show that our lower and upper bounds match in large-dimensional contexts. Our theoretical results are supplemented with numerical evaluations and simulations, demonstrating an excellent agreement already for problem sizes on the order of thousands.
Read the full abstract

Probability · Cross-listed from cs.IT

Group Testing with Selectable Thresholds

We consider the problem of group testing, in which one seeks to identify a subset of defective items of size $k$ from a larger set of $n$ items based on pooled tests. We introduce a selectable threshold model, in which each test has an associated threshold that can be chosen, such that the test outcome is 1 if and only if the number of defectives in the test is no smaller than that threshold. In settings with a large or unbounded maximum threshold, we establish conditions under which high-probability recovery can be attained with a rate (i.e., the asymptotic ratio of $\log_2{n \choose k}$ to the number of tests) approaching its maximum possible value of 1. Moreover, in the case of a fixed maximum threshold, we establish an achievable number of tests using simple and computationally efficient decoding methods, and a converse that holds under suitable regularity conditions on the test design, with the two coinciding in the dense limit (i.e., $\theta$ approaching one in the scaling $k = \Theta(n^{\theta})$).
Read the full abstract

Wednesday 15 July

Probability · Cross-listed from math-ph

On Factorizing Aggregate Counting Distributions into Independent Latent Processes

Given only the probability distribution of an aggregate counting variable, what independent latent counting processes are compatible with the observation? Equivalently, when does a probability-generating function admit a factorization into normalized polynomials with nonnegative coefficients? We develop a mathematical theory of such positive factorizations. We introduce the positive factorization poset, whose elements are all positive factorizations ordered by refinement, and define the factorization entropy, measuring the maximal latent Shannon entropy compatible with the observed distribution. We prove a sharp entropy inequality, characterize the equality case by injectivity of the latent addition map, show that entropy optimization may be restricted to maximal atomizations, and exhibit examples where distinct maximal atomizations have different entropy. We further establish support-based obstructions to positive factorization, characterize the real-rooted and Hurwitz-stable sectors, prove a local stability theorem for coprime factorizations, determine exactly the factorable regions in degrees two and three, obtain an exact quartic Hurwitz volume, and investigate the geometry of the factorable region inside the probability simplex through exact calculations and Monte Carlo experiments. These results identify the positive factorization poset as a natural algebraic object associated with probability-generating functions and provide a framework for studying latent independent structure in aggregate counting statistics.
Read the full abstract

Probability · Cross-listed from quant-ph

Circuit complexity lower bounds for quantum spin glasses

A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with $n$, we prove that, for all sufficiently large fixed $p$, any circuit preparing an $n$-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth $\Omega_p(\log n)$. In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed $D$, a sufficiently large degree prefactor rules out depth-$D$ preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
Read the full abstract

Probability

NeuralChaos: Optimal Adapted Approximation of Square Integrable Predictable Processes

We address fundamental challenges in representing and computing $\mathbb{R}^{d}$-valued predictable square-integrable processes over $[0,T]$, collected in the space $\mathcal{H}^2_T(\mathbb{R}^{d})$. These processes are central to continuous-time stochastic control, reinforcement learning, and mathematical finance. Although Wiener-chaos expansions offer strong theoretical tools, traditional computational methods are hindered by the need for large chaos dictionaries and high-order iterated integrals. To overcome these obstacles, we introduce NeuralChaos – a neural operator architecture that produces elements of $\mathcal{H}^2_T(\mathbb{R}^{d})$ using only finitely many evaluations of the driving Brownian motion, while preserving predictability and square-integrability. We prove that NeuralChaos is dense in $\mathcal{H}^2_T(\mathbb{R}^{d})$ and achieves the best $N$-term chaoslet approximation rates for compressible and Malliavin–Sobolev regular processes. Moreover, compressibility is shown to be typical for processes from $\mathcal{H}^2_T(\mathbb{R}^{d})$ under non-degenerate sub-Gaussian sampling. In contrast, we show that finite-dimensional Markovian neural SDE models constitute a meagre and Gaussian-null subset in $\mathcal{H}^2_T(\mathbb{R}^{d})$, regardless of discretization, whereas compressible processes are generic. Numerical experiments on a stochastic optimal control problem and dynamic hedging highlight the practical effectiveness of our approach. Our results enable more efficient and expressive modelling in stochastic analysis and mathematical finance.
Read the full abstract

Probability · Cross-listed from cs.IT

Capacity of Uniform Noise Channels Under Average Input Power Constraints

The foundational work of Shannon (1948) identified the capacity of an additive noise channel under an average input power constraint as a mutual information maximization problem over input densities subject to a second moment constraint. However, a quantitative understanding of the channel capacity is significantly lacking even for very simple noise distributions beyond Gaussians. In particular, it is a long standing question to determine the capacity of channels with noise uniformly distributed over a centered interval. This paper settles this question by precisely characterizing the capacity and the corresponding capacity achieving input and output distributions of such channels. A key observation en route to these results is a certain periodization identity for the output density of a uniform noise channel which in turn allows for applications of Fourier analytic techniques.
Read the full abstract

Probability

Dimers, filters, and $q$-deformed real numbers

This article associates to each positive real number $x$ a dimer model on a snake graph with activity parameter $q>0$ whose structure is determined by the continued fraction expansion of $x$. When $x$ is rational, the model is finite and gives rise to a probability measure $\mu_{x,q}$ on perfect matchings. For irrational $x$, the model is infinite, and $\mu_{x,q}$ is defined as a limit over rational approximations to $x$; the main technical result of the paper shows that this limit is well defined and independent of the choice of rational approximants. $[[x]]_q$ denotes the odds that a $\mu_{x,q}$-random perfect matching includes a distinguished edge. When $x$ is rational, $[[x]]_q = q\:[x]_q$, where $[x]_q$ is the algebraic $q$-deformation introduced by Morier-Genoud and Ovsienko. This agreement, together with evidence from the irrational case, suggests a close connection between the probabilistic and algebraic constructions.
Read the full abstract

Probability · Cross-listed from stat.ML

Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs

We study sparse threshold random geometric graphs generated by high-dimensional spherical or Gaussian latent vectors. Although each edge has marginal probability $p$, shared latent variables make the adjacency entries dependent. At the connectivity scale $np=\Omega(\log n)$, the spherical adjacency matrix satisfies, with high probability,$\|A-\mathbb E A\|_{\mathrm{op}}=O\left(\sqrt{np\log n}+np\tau\right)$, where $\tau$ is the cap threshold; an analogous estimate holds for Gaussian vectors after controlling radial fluctuations. This sharpens the spectral bound in Liu, Mohanty, Schramm, and Yang (2023) under weaker assumptions and strengthens the global-synchronization guarantee of Abdalla, Bandeira, and Invernizzi (2024) for the homogeneous Kuramoto model. The leading eigenspace also estimates the latent geometry. When $np\gg\log n$, vector and relative Gram-matrix errors vanish for$\log(1/p)\ll d\ll np\log(1/p)/\log n$ in the spherical model and $\log^2(1/p)\log n\ll d\ll np\log(1/p)/\log n$ in the Gaussian model, improving the recovery conditions of Li and Schramm (2023). For the Gaussian mixture block model introduced there, a polynomial-time semidefinite program gives, to our knowledge, the first exact-recovery guarantee at the connectivity scale in a moderate-separation regime. At much larger separation, fixed edge density creates isolated vertices and makes exact recovery impossible. Our reusable decoupling and matrix concentration framework avoids trace-moment methods and applies broadly to random graph models with latent vectors.
Read the full abstract

Probability

The Swapping Mechanism for Interacting Diffusions: Framework, Comparison with Switching, and an Exactly Solvable Example

We develop a rigorous framework for the swapping mechanism for two interacting jump-diffusion processes: each particle evolves independently but their positions are exchanged at random times, providing a continuous-time description of the replica-exchange Monte Carlo. Under mild hypotheses we establish strong existence, pathwise uniqueness, and a forward Kolmogorov equation for the transition density. A symmetrisation identity links swapping to the more standard regime-switching: swapping densities are relabelled sums of switching sectors, so permutation-invariant observables of these processes coincide, while antisymmetric ones differ. We prove that under detailed balance and reversibility the swapping process never degrades the spectral gap, and that, under label invariance, the antisymmetric gap improves compared to the decoupled process. We also show that, for $N$ particles, swapping remains Markov on $\mathbb{R}^N$ with polynomial moment closures, whereas switching requires tracking the full symmetric group, highlighting a fundamental complexity difference. We conclude the work presenting an exactly solvable benchmark of two Brownian motions with constant drifts and swap rate. For this model we obtain closed-form transition densities in terms of modified Bessel functions, exact moments, and two-time correlations. The asymptotic analysis reveals persistent asymmetries, an effective diffusivity correction, and a convergence rate of order $s^{-1/2}$ in the fast-swap limit (where $s>0$ is the constant swap rate).
Read the full abstract

Probability · Cross-listed from math.CO

Online Beck–Fiala Down to Logarithmic Sparsity

The Beck–Fiala conjecture asserts that every matrix $A\in\{0,1\}^{n\times T}$ with at most $d$ nonzero entries in each column has discrepancy $O(\sqrt d)$. A major breakthrough result of Bansal and Jiang recently established the validity of the conjecture for $d \ge \log(T)^2$. The present article extends the validity of the classical offline Beck–Fiala conjecture to $d \ge \log(T)^{1+o(1)}$; moreover, the main thrust of the result is that it is actually obtained by an efficient online algorithm that minimizes prefix discrepancy. The result is also essentially optimal, since online prefix discrepancy is known to scale as $\omega(\sqrt{d})$ for $d =o(\log T)$. As an immediate corollary, the open question of online vector balancing in the Spencer setting is also resolved. The algorithm is based on a compactly supported Metropolis fixed-point walk, constructed by combining ideas from several recent works on the online Komlós problem. The proof was generated in conversation with ChatGPT 5.6 Pro; the authors provided high-level guidance in several rounds of prompting, followed by manual checking and rewriting of the proof.
Read the full abstract

Probability

Stochastic Domination of Gaussian Maxima: A Resolution of the Weak Simplex Conjecture

Let $R$ be an $m\times m$ correlation matrix satisfying $R-\mathbf{1}\mathbf{1}^{\mathsf T}/m\succeq0$, let $X\sim\mathcal{N}(0,R)$, and let $Z_1,\ldots,Z_m$ be independent standard Gaussian random variables. We prove $\max_i X_i\leq_{\mathrm{st}}\max_i Z_i$, with equality in distribution if and only if $R=I_m$. We use this comparison to resolve the Weak Simplex Conjecture: among $d+1$ equiprobable equal-energy signals in $\mathbb{R}^d$ transmitted over an additive white Gaussian noise channel, the regular simplex is the unique maximizer of the average probability of correct maximum-likelihood decoding at every signal-to-noise ratio. The same comparison proves the Simplex Mean Width Conjecture and gives the exact finite-energy performance of deterministic no-feedback AWGN codes with equiprobable messages, no restriction on the number of channel uses, and a maximal per-codeword energy constraint. The proof uses a Gaussian product inequality for log-concave functions whose first moments with respect to standard Gaussian measure vanish. A variational argument chooses one exponential tilt and one truncation endpoint in each coordinate so that this product inequality applies and a Gaussian change of measure returns all coordinates to the prescribed common threshold. A strict form of the product inequality also shows that, unless $R=I_m$, $\mathbb{P}\{X\leq c\mathbf{1}\}>\Phi(c)^m$ for every finite $c$, and hence gives the distributional equality statement. A Lean formalization is available at https://github.com/abhmul/weak-simplex-conjecture-lean.
Read the full abstract

Probability

Gilbert's disc model conditioned on the square lattice

We present a new percolation model on the two-dimensional lattice, which can be seen as a conditioned version of continuous percolation on the plane. Let us place a point uniformly at random in each cell of the grid $\mathbb{Z}^2$. These points correspond to the vertices of our graph, and we connect two points by an edge if their distance is less than a fixed radius $R$. We are interested in the radius from which there exists almost surely an infinite connected component. We also study two other critical radii specific to the geometry of our model: the smallest radius such that there exists a positioning of the points for which there is an infinite connected component, and the radius from which all points are connected to each other.
Read the full abstract

Probability

Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex

We establish the normalized covariance bound conjectured by Anari et al. (2026, Conjecture 3) for fixed-rank external-field measures. Let $d\ge2$ and $m\in[d-1]$. For $w\in(0,+\infty)^d$, let $\mathsf S$ be an $m$-subset of $[d]$ with rank-$m$ external-field law $\mathbb P(\mathsf S=S)=\frac{\prod_{i\in S}w_i}{e_m(w)},S\subseteq[d],|S|=m,$ where $e_m(w):=\sum_{T\subseteq[d], |T|=m}\prod_{\ell\in T}w_\ell$ is the $m$th elementary symmetric polynomial in $w_1,\dots,w_d$. Let $X:=(X_1,\dots,X_d)^\top$ be its indicator vector, i.e., $X_i=\mathbb I\{i\in\mathsf S\},i\in\{1,\dots,d\}.$ Let $\Sigma:=\mathrm{Cov}(X)$, put $v_i:=\Sigma_{ii}$ for each $i\in[d]$, and define $v:=(v_1,\dots,v_d)^\top,D:=\mathrm{diag}(v),V:=\sum_{i=1}^dv_i.$ We prove $\Sigma\succeq D-\frac{vv^\top}{V}.$ This improves the coefficient $1/2$ in the first version of our work (Cesari and Colomboni, 2026, Corollary 1.3) to the optimal universal value $1$. As a first corollary, we improve the coefficient in the pseudoinverse bound of Bacchiocchi et al. (2026, Lemma 2) from $2$ to the optimal value $1$. Specializing this bound to coordinate differences gives an alternative proof of our effective-resistance theorem from the first version of our work (Cesari and Colomboni, 2026, Theorem 1.1). The framework of Anari et al. (2026, Theorem 1 and Corollary 2) also yields unconditional correlated-sampling guarantees with stretch $6$ on the hypersimplex and $12$ on its at-most variant. Unconditional constant-stretch guarantees were first established in the first version of our work (Cesari and Colomboni, 2026, Corollaries 1.4 and 1.5), with constants $16$ and $32$, which we improve here to $6$ and $12$. These improved constants strengthen the positive resolution, established in the first version of our work, of the constant-stretch question posed by Naor et al. (2026, Theorem 2 and Section 5).
Read the full abstract

Probability · Cross-listed from math-ph

Log-Sobolev inequalities for boundary-driven anharmonic chains

We study the non-equilibrium steady state of a weakly anharmonic chain of $N$ oscillators driven at its boundary by Langevin thermostats at unequal temperatures. Under a perturbative weak-anharmonicity condition, we prove a full-gradient logarithmic Sobolev inequality whose constant is independent of the chain length $N$. For homogeneous pinned chains, an additional quantitative regularity assumption yields a boundary space-time logarithmic Sobolev inequality and relative-entropy decay on the same $O(N^3)$ relaxation time scale as the harmonic chain. The proof extracts a finite-dimensional Gaussian component from the boundary noise and compares conditional terminal-state laws by a change of variables. The estimates are uniform over bounded positive temperatures and require no near-equilibrium assumption on their difference.
Read the full abstract