Probability · Cross-listed from math.CO
Limit laws of random simplex tree-child networks
Víctor J. Maciá and Benedikt Stufler
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$
Debbie Leung, Benjamin Lovitz, Ion Nechita et al. (+1 more)
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
Yifan Chen, Xiaoou Cheng, Jonathan Niles-Weed et al. (+1 more)
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
Antonio Agresti
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
Juan Esaul González Rangel
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
Martijn Caspers and Enli Chen
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
Jin Choi and Kasper Larsen
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
Milan Lopuhaä-Zwakenberg
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
Olivier Henry and Peter Mörters
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
Louis Vassaux
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
Phevos Paschalidis, Constantinos Daskalakis and Devavrat Shah
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
Behzad Azmi, Jonas von der Heydt and Sergio Rodrigues
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
Vanessa Dan
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
Sebastian Andres, Xin Chen, Martin Slowik et al. (+1 more)
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
Christian Berg and Henrik Laurberg Pedersen
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
Thomas L. Draper and Feras A. Saad
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
Mihailo Stojnic
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
Trung-Khang Tran, Daniel McMorrow and Jonathan Scarlett
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 ▾