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)

Monday 14 September

Probability

Limits of descent-biased trees

We investigate scaling and local limits of random trees biased according to their number of descents. A descent in a rooted labeled tree $t$ is a parent-child pair such that the label of the parent is greater than the label of the child, and the total number of descents is denoted by $\mathrm{des}(t)$. For $n \geq 1$ and $q_n \geq 0$, we consider the probability measure on trees of size $n$ where each tree $t$ is chosen with a probability proportional to $q_n^{\mathrm{des}(t)}$. We study the resulting random tree $\mathcal{T}_n^{(q_n)}$ properly rescaled as $n \to \infty$, and focus on two regimes for the bias parameter $q_n$. When $q_n = q \in (0,1]$ is fixed, we prove that $\mathcal{T}_n^{(q)}$ converges in distribution to the Brownian Continuum Random Tree. When $q_n = a/n$ for some fixed $a > 0$, we prove that $\mathcal{T}_n^{(q_n)}$ converges in distribution to a random non-trivial dendron constructed from a Poisson-Dirichlet sequence. We complement these results with a description of the Benjamini-Schramm local limit of $\mathcal{T}_n^{(q_n)}$ in all regimes of parameters. Our proofs rely on analytic combinatorics to find the asymptotics of certain statistics of the tree, and on a probabilistic analysis of the structure of descent-biased random trees.
Read the full abstract

Probability · Cross-listed from math.OC

Eventual convexity for separable chance constraints with skewed generalized hyperbolic random variables

Chance constraints are widely used in optimization under uncertainty. This paper aims to show the eventual convexity (EV) of chance constraints with skewed generalized hyperbolic (GH) random variables. We prove that the densities of GH distributions are $\alpha$-decreasing, and obtain exact convex reformulations for separable jointly chance constraints with GH distributions. We provide numerical results to compute the $\alpha$-decreasing threshold parameters and show the EV of the feasible set together with the computational tractability to solve the associated optimization problems.
Read the full abstract

Probability

Entropy and singularity of spectral and pivotal sets in planar percolation

The spectral sample and pivotal set of a percolation crossing have the same one- and two-coordinate inclusion probabilities under the uniform product measure. We prove that both Shannon entropies are comparable to total influence for critical square-lattice bond and triangular-lattice site crossings, with matching estimates at every retained nonroot spatial resolution. The triangular entropy bounds are uniform over a class of inhomogeneous near-critical product measures. For critical triangular-site square crossings, the two laws are asymptotically mutually singular: an elementary triangular face is forbidden in the pivotal set and occurs with positive density in a large spectral sample. Every fixed face density below an explicit threshold has nonempty spectral probability comparable to $R^2\alpha_4(R)^2$, while the nonempty overlap of the two laws has decay exponent $11/12$. Their minimum expected symmetric-difference distance over all couplings is comparable to total influence. Geometric separation persists after independent thinning whenever the retention probability $\rho_R$ satisfies $\rho_R^3R^2\alpha_4(R)\to\infty$; the face detector fails when this quantity tends to zero. The proofs combine spatial encoding, arm estimates, local Fourier cancellation, and an exact six-cycle coercivity inequality preserved under exterior conditioning.
Read the full abstract

Probability

Occupation BAsed Propagation of Chaos for MacKean Vlasov Forward Backward Systems with Jumps and Monotone Sources

We study robust Mckean-Vlasov Forxard Backward systems with jumps under a nondominated family of probability measures. The backward equation contains a lawdependent nonsmooth monotone source motivated by asymmetric loss aversion. We establish well-posedness and stability of the system, analyze its Yosida regularization, and develop quantitative particle approximations. The main difficulty comes from the discontinuity of the minimal selection across switching interfaces, which prevents the use of direct Lipschitz estimates. To overcome this difficulty, we combine forward propagation of chaos with occupation estimates for the limiting forward process. Importantly, no occupation estimate is required for the particle system. Under a second-moment occupation condition, we obtain an improved joint convergence rate for the particle and Yosida approximations, controlling the forward and backward states, the martingale integrands, and the accumulated source. We also verify the required occupation conditions for several concrete jump models, including affine stable-like dynamics, predictable variable jump amplitudes, and a non-affine class obtained by smooth conjugacy
Read the full abstract

All authors Tcheick Kayembe Tshiswaka, Rostin Mabela Matendo, Simon NTumba Badibanga, Jean-Pierre Bosonga Bofeki Lounga

Probability

Optimal Time-Dependent Jump Truncation for Time-Singular Lévy Processes

We study optimal jump truncation for the additive time-singular pure-jump model of the form $X_T=\int_0^T t^{-\sigma} dZ_t$, where $Z$ is a Lévy process and $\sigma\ge 0$. For a fixed expected jump cost, we minimize the residual small-jump variance over measurable time-dependent cutoffs. Under regularity and tail assumptions on the Lévy measure, we prove that the problem admits an optimal cutoff, unique up to a.e. equality, of the form $r^\ast(t)=(c^\ast t^\sigma)\wedge 1$. In the symmetric $\alpha$-stable case, we obtain explicit matched-cost comparisons with the classical fixed cutoff and show that within the admissible non-truncated regime the Dynamic Cutting family is strictly better than the classical fixed cutoff whenever $0<\sigma<1/2$. Finally, for symmetric Lévy measures and cutoffs satisfying the corresponding $L^p$-integrability assumptions, we derive the weak-error bound $W_p(r)\le C_p \mathcal{E}^{p/2}(r)$, $0<p<2$, demonstrating that any cutoff which minimizes the residual variance also minimizes the corresponding upper bound for the weak error.
Read the full abstract

Probability

Invasion dynamics with vanishing fitness for a quasi-critical birth-death process

We study the invasion dynamics of populations exhibiting positive density-dependent effects. We start with a single individual and consider a single-type birth and death process. The initial individual growth rate vanishes but it increases with the population density, proportionally to the number of individuals divided by a scaling parameter $K$. Before reaching the macroscopic scale~$K$, the population process is almost critical. %{\color{red} Although the process remains asymptotically critical throughout the invasion phase, three distinct dynamical regimes emerge.} We prove that the probability for the population to reach the macroscopic level $K$ decreases as $1/\sqrt{K}$ as $K$ goes to infinity. We also describe the associated trajectories and show that invasion can be split into three time periods. First, the process needs to escape from zero, and conditioning on survival, it grows linearly until the order $\sqrt{K}$. The scaled process is approximated by a diffusion, as for critical branching process, with an additional drift term coming from cooperation, which breaks the branching property. Second, in intermediate scale $\sqrt{K}$, we observe another diffusion, surviving with positive probability, without conditioning. Finally, beyond $\sqrt{K}$ scale, the process can be approximated by a classical macroscopic ODE limit. The proof of the first phase involves change of probability and characterization of uniform integrability of martingales, while the two other phases rely on uniform approximations on polynomial time scales.
Read the full abstract

All authors Vincent Bansaye, Nadia Belmabrouk, Xavier Erny, Simon Girel

Probability

Bipodal optimizers in the upper-tail variational problem for regular subgraph densities

Let $H$ be a fixed $d$-regular graph with $d\ge2$, and let $t(H,\cdot)$ denote its homomorphism density. We study the upper-tail event $t(H,G(n,p))\ge r^{|E(H)|}$ for fixed $0<p<r<1$ in a dense Erdős–Rényi random graph $G(n,p)$. Near the Lubetzky–Zhao replica-symmetric phase boundary and away from the exceptional target density $(d-1)/d$, we prove that the optimizer of the Chatterjee–Varadhan variational problem on the symmetry-breaking side is bipodal (two-block) and unique up to relabeling. Its block parameters depend analytically on $(p,r)$. To treat the exceptional boundary point, where the nonexceptional theory degenerates, we construct an analytic curve approaching that point from the symmetry-breaking side along which the unique optimizers are nonconstant rank-one bipodal graphons. In both settings, we derive asymptotic expansions of the edge-density deficit and the rate function that governs the exponential decay of the upper-tail probability. Moreover, the conditioned random graph converges in cut distance to the corresponding bipodal optimizer as $n\to\infty$. As $(p,r)$ approaches the phase boundary from the symmetry-breaking side, the optimizers converge to their constant limits through two distinct mechanisms. For each fixed nonexceptional target density, one block shrinks to zero measure, giving convergence in $L^1$ but not in $L^\infty$. Along the exceptional curve, both blocks remain macroscopic: their sizes tend to $1/2$ and all three block densities tend to $(d-1)/d$, yielding convergence in $L^\infty$.
Read the full abstract

All authors Sangho Lim, Seonghyuk Im, Taeyoung Kim, Kyeongsik Nam, Hongseok Yang

Probability

Independence properties for tree beta models

This paper is devoted to introduce new probabilistic tree-based models complementing already known Matsumoto-Yor and Hamza-Vallois tree models with two tree beta-type models.

Probability

Palm Disintegration and Height-Profile Recovery for Projected Hardy–Szegő Zeros

We study the horizontal projection of the upper-half-plane Hardy–Szegő zero process after independent height-dependent thinning, with height retained as an unobserved mark. We identify the reduced Palm law of the projected process by disintegrating over the missing height coordinate, describe the conditional law of the two heights associated with a pair of projected points and its near- and far-separation limits, and obtain the small-spacing asymptotic for the right nearest neighbour. We then study recovery of the height profile from the projected second-order structure. The resulting covariance transform uniquely determines every compactly supported finite positive height measure and, for separated finite unions of intervals, yields uniform Lipschitz recovery of all endpoints, even when the number of intervals is unknown but bounded.
Read the full abstract

Probability

Spectral Gap Bounds for Langevin Dynamics in Mixed Spherical Spin Glasses

We prove lower bounds on the relaxation time $1/\gamma_{N,\beta}$ of Langevin dynamics for mixed spherical spin glasses with even mixture $\xi(x)=\sum_{p\ge4}\gamma_p^2x^p$, under a one-step-replica-symmetry-breaking-type standing assumption of strict threshold separation $E_0(\xi)>E_1(\xi)>E_2(\xi)$; the pure spherical $p$-spin glass with even $p\ge4$, for which the assumption is a theorem, is recovered as a corollary. The main result is an aggregate Eyring-Kramers bound whose exponent sums conductances over the exponentially many index-one saddles above the lowest saddle level $-NE_1(\xi)$, combining the saddle complexity $\Theta_{1,\xi}$ with a half-determinant Hessian statistic – an entropic contribution that the classical single-saddle picture misses. The single new random-matrix ingredient of the mixed model is that the conditional Hessian at a critical point is a randomly shifted GOE matrix: the radial derivative is no longer determined by the energy (Euler's identity degenerates exactly in the pure case), and every landscape rate becomes a one-dimensional supremum over the scalar shift with a Gaussian penalty. At low temperature the aggregate exponent exceeds the unconditional free-energy bound by $\frac12\log(\beta e)-\Xi^{\mathrm{EK}}_{1,\xi}(-E_1(\xi))-C_{\xi,b}\beta^{-1/2}$ with $-\Xi^{\mathrm{EK}}_{1,\xi}(-E_1(\xi))\ge\frac14\log\xi''(1)+\frac14>0$, so the refinement is a strict improvement for all sufficiently large fixed $\beta$; the onset temperature and constants $b_*(\xi)$ and $C_{\xi,b}$ produced by the proof are not numerically explicit. Two companion results – a sequential Arrhenius bound with the explicit constant $E_0(\xi)-E_1(\xi)$ and a fixed-temperature free-energy bound – come with complete, self-contained proofs. All bounds are one-sided; identifying the mechanism the dynamics actually realizes would require a matching upper bound, which remains open.
Read the full abstract

Probability · Cross-listed from math.CO

Thresholds and Fluctuations for Colorful Arithmetic Progressions in Sparse Random Colorings

In this paper, we derive thresholds and fluctuations for arithmetic progressions with prescribed color patterns in sparse random colorings of $[n]:=\{1, 2, \ldots, n\}$, where each element of $[n]$ is colored independently according to a given probability vector. For any admissible ordered palette of colors, we determine the full multi-parameter threshold region for the appearance of a colorful arithmetic progression. The threshold is governed by two competing mechanisms: a global first-moment condition and a local color-availability condition, resulting in a polyhedral satisfiability region, with a piecewise-polyhedral threshold surface. In the satisfiability region we establish asymptotic normality for the number of colorful arithmetic progressions of a given length, with an explicit rate of convergence in Wasserstein distance. On the threshold surface, we identify three distinct asymptotic regimes: Poisson, compound Poisson with mixed Poisson jumps, and compound Poisson with uniform jumps, after an appropriate normalization. These results provide a complete description of the threshold and fluctuation behavior of general colored arithmetic progressions under sparse random colorings, in a unified framework that interpolates between classical uncolored/monochromatic progressions in binomial random subsets and multicolored, including rainbow, arithmetic progressions.
Read the full abstract

Probability · Cross-listed from cs.DS

Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input

The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\ldots,A_n\in\mathbb{R}^{n\times n}$ with $\|A_i\|\le1$ there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ with $\|\sum_{i=1}^n\varepsilon_iA_i\|=O(\sqrt n)$. We prove it: a signing of discrepancy below $8\sqrt n$ always exists. We also give a randomized algorithm that finds a signing of discrepancy below $12\sqrt n$ with failure probability at most $p$. The algorithm uses $n^{3+o(1)}\operatorname{polylog}(1/p)$ arithmetic operations in the real-arithmetic model. This matches the size $n^3$ of the dense input up to subpolynomial factors. In the other direction, we prove that for every $n$ there are collections of symmetric matrices such that every signing has discrepancy at least $(2-o(1))\sqrt{n}$. We present three different proofs of the matrix Spencer conjecture. The key to every proof is a hereditary small-ball estimate. This is a lower bound on the Gaussian measure of the spectral body $\{x\in \mathbb{R}^n:\|\sum_ix_iA_i\|\le R\}$ that holds for every subfamily of the matrices. The other ingredient turns that Gaussian measure into a partial signing. We give three approaches to obtain such a signing. The first one covers the cube by partially signed faces through Gaussian concentration with a constant $7\cdot10^9$. The second proof replaces the covering by a projection lemma with explicit parameters for a constant $156000$. The third proof turns Gaussian measure into signs by a lossless coding, with no union bound. It proves the estimate at the right radius with smooth spectral barriers and certified coefficients. It gives a constant below $7.88$. For algorithms, the main idea is to project Gaussian points onto a smoothed spectral body. The $n^{3+o(1)}$ time algorithm tracks the Gibbs matrix of that body across coordinate-descent steps with sketched increments and random refreshes.
Read the full abstract

Probability

From torpid to rapid mixing: group averaging for a weakly interacting Ising star

We study lazy single-site Metropolis dynamics $P_{\beta}$ at inverse temperature $\beta \geq 0$ on $\{-1,+1\}^d$ for an Ising star with additional signed interactions among the leaves. If the absolute row sums of the leaf-interaction matrix are at most $\kappa\le1/2$, the worst-case total-variation mixing time of $P_{\beta}$ is at least of order $d\exp\{c\beta(d-1)\}$ for $\beta\ge1$, with universal $c>0$. Averaging over global spin reversal reduces the mixing time to $\mathcal O(d^2(1+\beta))$ for both $GP_\beta G$ and $(P_\beta+G)/2$, where $G$ is the Gibbs kernel induced by the partition of the state space into spin-reversal orbits $\{-x,x\}$. Partition-function interpolation gives the lower bound for $P_\beta$. The upper bounds follow from Wu's Dobrushin inequality and a decomposition into projection and restriction chains. This gives an explicit example in which group averaging turns an exponentially slow chain into a polynomially fast one.
Read the full abstract

Probability

The threshold for online balancing of i.i.d. binary vectors

Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$–sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck–Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = \Theta(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^t\sigma_i X_i\right\|_\infty$ is of order \[ \Theta\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $\Theta(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $\Theta(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck–Fiala model.
Read the full abstract

Probability

Majority dynamics on sparse random graphs

Consider a simple undirected graph $G$ on $N$ vertices, with each vertex holding an opinion from one of two options. Starting from the initial opinions on day 1, we run majority dynamics: on each subsequent day, all vertices simultaneously adopt the majority opinion among their neighbors, retaining their current opinion in case of a tie. A well-studied conjecture of Benjamini, Chan, O'Donnell, Tamuz, and Tan states that if $G$ is drawn from the random binomial model $\mathbb{G}(N,p)$, and if the starting opinions are chosen uniformly at random, then as long as $pN \to \infty$ the network will converge to 99% consensus with high probability. We confirm this conjecture as long as $pN \ge N^{\varepsilon}$ for any fixed $\varepsilon > 0$, showing that full unanimity is reached with high probability in $O(1/\varepsilon)$ days. This result improves on a line of results by Fountoulakis, Kang, and Makai, who achieve $\varepsilon = 1/2$; Chakraborti, Kim, Lee, and Tran, who achieve $\varepsilon = 2/5$; and Jaffe, who achieves $\varepsilon = 1/3$. The proof technique involves iteratively revealing the "opinion histories" for each vertex through time, keeping track of the degrees between every vertex and each of $2^k$ opinion history classes on day $k$. Our analysis of this process requires intricate estimates for degree-constrained random graph models using graph enumeration tools from the work of McKay and Wormald as well as Canfield, Greenhill, and McKay, and their extensions by Liebenau and Wormald. In doing so, we connect the discrete dynamics to a deterministic idealized process, whose leading-order behavior is described by conditional Gaussian probabilities and expectations.
Read the full abstract

Probability · Cross-listed from math.CO

Long-range expanders: construction and cutoff

Long-range expansion is a combinatorial graph property introduced to construct metric spaces with strong quantitative obstructions to low-distortion embeddings. Such extremal constructions are motivated by fundamental questions in metric geometry and nonlinear functional analysis. However, the only known constructions of long-range expander sequences are random regular graphs; the problem of constructing explicit sequences, especially with logarithmic girth, remains open. We resolve this question in strong form by proving that the Ramanujan condition implies long-range expansion. In particular, classical Ramanujan constructions (such as LPS graphs) give explicit long-range expander sequences with logarithmic girth. We also clarify that long-range expansion implies spectral expansion, and both implications are strict. While long-range expansion, the Ramanujan property, and spectral expansion are strictly separated, it is a priori not clear how robust these gaps are. We next compare them from a dynamics perspective: how do the different notions of expansion affect the mixing rate of random walks? Our second main result is that, from a dynamics perspective, LRE and the Ramanujan property are equivalent. We show that the random walk on any LRE sequence has the same cutoff location and Gaussian limit profile as on a Ramanujan graph. This incidentally offers intermediate progress between cutoff for Ramanujan graphs—proven by Lubetzky and Peres—and the long-standing conjecture of cutoff for transitive spectral expanders.
Read the full abstract

Probability

Sharp Gaussian Asymptotics for Marginals of Euclidean Balls

We study Gaussian approximation for probability measures obtained by normalizing one-dimensional profile functions, with one-dimensional marginals of Euclidean balls as the principal example. We first establish quantitative concentration estimates near the set of maximizers. For profiles with a unique nondegenerate maximizer, we give sufficient conditions under which centering at the maximizer and rescaling according to the local quadratic approximation of the logarithm of the profile yield densities that converge in $L^1(\mathbb{R})$ to the standard Gaussian density. We then specialize to one-dimensional marginals of Euclidean balls in $\mathbb{R}^n$. Writing $N=n-1$, we consider two standardizations of the marginal distribution: one determined by the logarithmic curvature at the maximizer, and the other by the exact standard deviation. For each standardization, we identify the first-order correction, of order $N^{-1}$, to the standard Gaussian density in $L^1(\mathbb{R})$. These expansions also determine the corresponding first-order corrections to the probabilities of symmetric intervals and the leading terms of the total variation distances from the standard Gaussian distribution. In particular, under exact-variance standardization, the total variation distance is asymptotic to an explicit positive constant times $N^{-1}$. Consequently, the previously known $O(N^{-1})$ bound for approximation by the Gaussian distribution with the same variance is sharp in order.
Read the full abstract

Probability

Moderate deviations and laws of the iterated logarithm for geometric functionals in the sparse regime

We prove moderate deviation principles and laws of the iterated logarithm in the sparse regime for geometric and topological functionals associated with $k$-point connected components. These limit theorems are established at both the measure-valued and vector-valued levels, for Poisson and binomial point processes. As applications, we derive corresponding results for component counts in random geometric graphs and Čech complexes and for counts of Morse critical points.
Read the full abstract

Probability · Cross-listed from stat.ML

Steady-State Convergence of Stochastic Approximation

For constant-stepsize stochastic approximation (SA), the iterates converge in distribution to a stationary law that depends on the stepsize $\alpha.$ Steady-state convergence (SSC) concerns the limit of the scaled stationary distribution as $\alpha \downarrow 0.$ Existing SSC theory requires i.i.d. or additive noise and global differentiability of the mean operator, and yields suboptimal rates. We develop a unified SSC theory for constant-stepsize contractive SA driven by Markovian, multiplicative noise, covering both locally differentiable and locally nondifferentiable mean operators. A key methodological contribution is a multi-step universality framework that progressively reduces the original stochastic recursion to tractable auxiliary dynamics while preserving its steady-state limit. Under local quadratic linearization at the fixed point, we obtain a Gaussian approximation of the scaled steady state at the optimal rate $O(\sqrt{\alpha})$ in Wasserstein-2 distance, which further gives finite-time Gaussian approximations for the raw iterates. In the locally nondifferentiable regime, we establish a general SSC result and show that the leading-order asymptotic bias can be of order $\sqrt{\alpha}$, in contrast to the $\alpha$-order bias in the smooth regime. We apply the theory to Markovian linear SA and asynchronous Q-learning, neither of which is covered by prior results. We further propose a bias-reduction scheme for Q-learning that requires no knowledge of the local smoothness regime, validated by numerical experiments.
Read the full abstract

Probability

Limit theorems for amnesic elephant Random walks with random increment sizes

We introduce a generalized amnesic elephant random walk in which, at each time, the direction of an underlying amnesic elephant random walk selects one of two increment distributions, while the actual increment is sampled from the corresponding independent sequence. The selected distribution does not need to determine the sign of the increment. This construction combines memory reinforcement, amnesia, and randomness in jump sizes. Assuming finite second moments, we establish central limit theorems and functional limit theorems, identifying diffusive, critical, and superdiffusive regimes determined by the memory and amnesia parameters. We further prove a Gaussian fluctuation theorem around the random superdiffusive limit, with an explicit limiting variance that captures the contributions of both the underlying amnesic walk and the random jump magnitudes. For the special case without amnesia, we also establish stable limit theorems and their functional counterparts when the increments belong to the domain of attraction of a non-Gaussian stable law, in the regime where heavy-tailed jumps dominate the memory contribution.
Read the full abstract

Sunday 13 September

Probability

Diffusion processes with $b\in L_{(p,q),\text{loc}}$

We present some conditions in case $b\in L_{(p,q),\text{loc}}$ sufficient to guarantee the existence of a strong Markov diffusion process with drift $b$ and uniformly nondegenerate bounded matrix-valued diffusion. An example is given to illustrate how close these conditions are to be necessary.
Read the full abstract

Probability

A constructive solution to Talagrand's Gaussian convexification problem

Talagrand asked for a construction of a large convex subset of a bounded Minkowski sum of a large Gaussian set. We first prove a stronger nonsymmetric existential statement: if $A\subset\mathbb{R}^n$ is measurable and $\gamma_n(A)>2/3$, then $A+A+A$ contains a compact convex set of Gaussian measure at least $1/2$. Let now $A$ be closed with $\gamma_n(A)\ge7/8$, let $\Phi$ be the standard Gaussian distribution function, and put $a_0=\Phi^{-1}(3/4)$. For every $\Lambda>1$ and every $0<p<2\Phi(\Lambda a_0)-1$ we construct a centrally symmetric finite polytope $C\subset\Lambda(A+A+A)$ with $\gamma_n(C)\ge p$. Thus measure $3/4$ is obtained for every $\Lambda>1.705510\ldots$. We give matching upper and lower bounds for the optimal high-measure dilation and show that the dilation profile used by the construction is sharp among all symmetric half-measure cores. Finally, if $\gamma_n(A)\ge5/6+\eta$, we construct, for every $0<\varepsilon\le1/2$, a centered ellipsoid $E_\varepsilon$ with $\gamma_n(E_\varepsilon)\ge1-\varepsilon$ and \begin{equation} \frac{c}{\Phi^{-1}(1-\varepsilon/2)}\sqrt{\frac{\log n}{n}}\,E_\varepsilon\subset A+A+A. \end{equation} Both the dimension dependence and the dependence on $\varepsilon$ are optimal up to constants. The construction also gives a six-summand theorem for balanced sets and a second finite construction based on subgaussian tests.
Read the full abstract

2609.14832 · 13 Sep · 25 pages, no figures. Substantially revised and expanded: the constructive result now holds for every exterior dilation greater than 1; added a nonsymmetric three-sum theorem, optimality results for the measure–dilation tradeoff, a constructive high-measure ellipsoid theorem, and further balanced-set and subgaussian consequences

Probability

Variance of random greedy independent sets in triangle-free graphs

Inspect the vertices of a finite simple graph in uniformly random order, accepting each vertex if none of its neighbors has previously been accepted. Let $X_G$ be the number of accepted vertices. For every triangle-free graph with $n\ge2$ vertices and $e$ edges, we prove $\operatorname{Var}(X_G)\le e((n-2)/n)^2$, with equality precisely for edgeless graphs and connected stars. In particular, among trees of a given order, the star uniquely maximizes the variance, with value $(n-1)(n-2)^2/n^2$. Known expected vertex-deletion stability already yields the elementary baseline $\operatorname{Var}(X_G)\le e$. We obtain the sharp finite-order refinement by combining a stronger centered first-choice estimate with a triangle-free edge-count identity in the law of total variance.
Read the full abstract

Probability

A Superdiffusive Local Limit Theorem for the Elephant Random Walk and the Breakdown of Log-Concavity

Let $(S_n)_{n\geq 1}$ be the one-dimensional Elephant Random Walk (ERW) in the superdiffusive regime, with memory parameter $p\in(3/4,1)$ and first-step bias $\mathbb{P}(S_1=1)=q$. Set $a=2p-1\in(1/2,1)$. If $f_{q,a}$ denotes the density of the superdiffusive limit $L_{q,a}$, we prove the uniform local limit theorem $\lim_{n\to\infty}\sup_{j\in\mathbb{Z},\,j\equiv n\;(\mathrm{mod}\;2)}\left|\frac{n^a}{2}\mathbb{P}(S_n=j)-f_{q,a}(j/n^a)\right|=0$. The proof uses the exact recurrence for the probability mass function of $S_n$, yielding uniform $O(n^{-a})$ and $O(n^{-2a})$ bounds for the p.m.f. and its first discrete differences, respectively. We then disprove a conjecture of Guérin, Laulin, Raschel and Simon concerning eventual log-concavity. Writing $L_a=L_{1,a}$ and $f_a=f_{1,a}$, let $a_{\rm ev}$ be the eventual-log-concavity threshold and let $a_\star$ be the upper failure threshold for log-concavity of $f_a$. Their results imply $a_{\rm ev}\geq(\sqrt{5}-1)/2$, and we prove $(\sqrt{5}-1)/2\leq a_{\rm ev}\leq\min\{0.80399,a_\star\}\leq a_\star<0.918$. The bound $a_\star<0.918$ follows from the first three exact moments of $L_a$ and the sharp skewness inequality for centered log-concave distributions, while $a_{\rm ev}\leq0.80399$ follows from a certified finite-order analysis of the exact p.m.f. recurrence. Direct numerical iterations provide evidence that $a_{\rm ev}\approx0.80399$, equivalently $p_{\rm ev}\approx0.902$.
Read the full abstract

Probability

Least-Variable Harmonic Matrix-Exponential Distributions

Concentrated matrix-exponential (CME) distributions are random clocks approximating a fixed time, with quality measured by the squared coefficient of variation (SCV); a well-known construction builds such clocks from products of cosine-squared terms under shared exponential damping, but the number of these terms, and hence the number of parameters to optimize, grows with the order. Since exhaustive search over the full parameter space becomes prohibitively expensive at high orders, previous work has relied on low-dimensional heuristic parametrizations rather than the true optimum. We introduce a strictly larger class of common-damping harmonic densities, built from an arbitrary nonnegative trigonometric polynomial rather than such a product. For each fixed pair of scalar parameters, coefficient optimization reduces to a single eigenvalue problem, leaving a two-dimensional nonlinear search independent of the order. The enlargement leaves the infimum unchanged from that of the classical cosine-squared construction. Applying this exact characterization at the orders where the three-parameter heuristic allows comparison gives smaller reported SCV values, with larger gains at higher orders. Separately, an explicit harmonic construction gives an $O(N^{-2})$ upper bound on the attainable SCV, where $N$ is the ME representation budget, compared with the Erlang distribution's linear rate $1/N$.
Read the full abstract

Probability · Cross-listed from math.ST

Two short proofs of incompatibility for correlation matrices

Let $P_d$ be the elliptope of $d \times d$ correlation matrices, and, for a standardised law $F$, let $S_d^F$ be the set of correlation matrices of random vectors with all margins $F$. We give two short proofs. First, an eleven-term representation of $|x|^4$ as a sum of fourth powers of linear forms on $\mathbb{R}^4$ yields $S_{11} \neq P_{11}$ for uniform margins. Second, the six diagonals of the regular icosahedron yield $S_6^F \neq P_6$ for arcsine margins. Together with a result of Devroye and Letac, this gives $S_d^F = P_d$ if and only if $d \le 5$, settling a conjecture of theirs.
Read the full abstract

Probability · Cross-listed from q-bio.PE

Evolution of Fast and Slow Life Histories in Resource-Constrained Populations with Mass-Mortality Events

We study the evolution of the speed of life history in populations competing for a single growth-limiting resource subject to demographic stochasticity and mass mortality events. We focus on a quasi-neutral regime in which competing types have equal resource-use efficiency but differ in life-history speed. In the large-carrying-capacity scaling limit, we reduce the model to a one-dimensional jump-diffusion supported on the manifold of ecological equilibria. The drift and diffusion components capture the joint effects of demographic stochasticity and density regulation, while the jump component is driven by the catastrophic mortality events. Using this limiting process, we derive a first-order approximation for the fixation probability of an invading type that differs slightly in life history speed from the resident population. Calculations show that small demographic events tend to favor slower life histories, whereas catastrophic mortality events create transient periods of resource abundance that benefit faster types. The interaction of these two evolutionary forces allows for the existence of a nontrivial evolutionarily attractive life-history speed, which is an increasing function of the frequency and intensity of the catastrophic mortality events. These results provide a rigorous mathematical framework for some classical r/K-selection arguments, and furthermore demonstrate how mass mortality events can maintain selection for faster life histories even in resource-constrained populations.
Read the full abstract

Probability · Cross-listed from math.GN

A New Approach to Universal Measurability

V. Fedorchuk, A. Chizogidze, and T. Banakh in 2003 and V. Bogachev in 2024 posed the following questions: (i) is it true that $P_\tau(X)$ is $C$-embedded in $P_\sigma(X)$; (ii) Is it true that $P_R(X)$ is $C$-embedded in $P_R(\beta X)$ if and only if $X$ is pseudocompact, where $P_\sigma$, $P_\tau$, and $P_R$ are the functors of probability $\sigma$-additive on the Baire $\sigma$-algebra, $\tau$-additive, and Radon measures on the space $X$? The answers to these questions are negative. However, if instead of probability measures we consider the corresponding alternating measures $M_\sigma$, $M_\tau$, and $M_R$, the situation changes. It is proved that (i) $M_\tau(X)$ is $C$-embedded in $M_\sigma(X)$; (ii) $M_R(X)$ is $C$-embedded in $M_R(\beta X)$ if and only if $X$ is pseudocompact. The question of $C$-embedding of measure spaces is an extension of the question of coincidence of measure spaces, which is a development of the classical concepts of universally measurable and universal measure zero sets. A general theorem is obtained, which leads to the mentioned results.
Read the full abstract

Probability · Cross-listed from math.CO

The Colomo-Pronko conjecture for frozen-corner alternating sign matrices

We prove the Colomo-Pronko conjecture for alternating sign matrices with a prescribed square of zeros at a corner, for all matrix sizes and freezing parameters. A known multiple-integral formula for the frozen-corner count yields determinant representations built from fixed polynomial kernels. We relate these kernels to the conjectured determinant through an inverse identity for the commutator of a signed Pascal matrix with reversal. In odd dimension, the comparison uses the one-dimensional nullspace and projection along it to eliminate the central coordinate. Combined with the asymptotic analysis of Colomo and Pronko, our result removes the conjectural assumption from their GUE Tracy-Widom fluctuation theorem for the intersection of the frozen boundary with the main diagonal in uniformly random alternating sign matrices. The finite-dimensional algebraic core of the proof has been formalized in Lean 4.
Read the full abstract

Probability · Cross-listed from math.CO

Poisson laws and exterior stability for random alternating tensors

For fixed $k\ge3$, we determine the critical law of totally isotropic $r$-spaces for a uniform random map $\Theta_N:\Lambda^k\mathbb {F}_q^N\to\mathbb {F}_q^m$. At the exact balance $m\binom rk=r(N-r)$, the entire null configuration is asymptotically an independent Bernoulli subset of $\operatorname{Gr}(r,\mathbb {F}_q^N)$ in total variation, uniformly in $q$ and $m$. Consequently, the counting measure $\Xi_r$ is asymptotically a Poisson point process, and its total mass $X_{N,r}$ is asymptotically Poisson. An exterior-rank stability theorem shows that near-extremal families decompose into Grassmann clusters with uniformly controlled span deficiency. We obtain quantitative rates and identify the first exterior-dependence scale. We also show that rare null $(r+1)$-spaces force high-order factorial-moment divergence, while the fixed-target bilinear cases $m=1,2$ exhibit non-Poisson critical behavior.
Read the full abstract