2024-10-29 | | Total: 30
For a square matrix $A$, Gaussian elimination with partial pivoting (GEPP) results in the factorization $PA = LU$ where $L$ and $U$ are lower and upper triangular matrices and $P$ is a permutation matrix. If $A$ is a random matrix, then the associated permutation from the $P$ factor is random. We are interested in studying properties of random permutations generated using GEPP. We introduce and present probabilistic results for groups of simple and nonsimple butterfly permutations of order $N = p^n$ for prime $p$, on which GEPP induces the Haar measure when applied to particular ensembles of random butterfly matrices. Of note, the nonsimple butterfly permutations include specific $p$-Sylow subgroups of $S_{p^n}$ for each prime $p$. Moreover, we focus on addressing the questions of the longest increasing subsequence (LIS) and the number of cycles for butterfly permutations. Our proof techniques utilize the explicit structural recursive properties of these permutations to answer what are traditionally hard analytical questions using simpler tools. For simple butterfly permutations, we provide full distributional descriptions and Law of Large Numbers (LLN) or Central Limit Theorem (CLT) type results for each statistic. For nonsimple $p$-nary butterfly permutations, we establish lower and upper power law bounds on the expected LIS of the form $N^{\alpha_p}$ and $N^{\beta_p}$ where $\frac12 < \alpha_p < \beta_p < 1$ for each $p$ with $\alpha_p = 1 - o_p(1)$. Additionally, we determine the aysmptotic form for the number of cycles scaled by $(2 - \frac1p)^n$ that limit to new distributions we introduce depending only on $p$ whose positive integer moments satisfy explicit recursion formulas for each $p$; in particular, this characterizes a full CLT result for the number of cycles for any uniform $p$-Sylow subgroup of $S_{p^n}$.
We present a method to obtain sharp local propagation of chaos results for a system of N particles with a diffusion coefficient that it not constant and may depend of the empirical measure. This extends the recent works of Lacker [14] and Wang [24] to the case of non constant diffusions. The proof relies on the BBGKY hierarchy to obtain a system of differential inequalities on the relative entropy of k particles, involving the fisher information.
We consider the contact process with dormancy, where wake-up times follow a renewal process. Without infection between dormant individuals, we show that the process under certain conditions grows at most logarithmically. On the other hand, if infections between dormant individuals are possible, the process survives with positive probability even on finite graphs.
In this paper we consider the multispecies stirring process on the discrete torus. We prove a large deviation principle for the trajectory of the vector of densities of the different species. The technique of proof consists in extending the method of the foundational paper [1] based on the superexponential estimate to the multispecies setting. This requires a careful choice of the corresponding weakly asymmetric dynamics, which is parametrized by fields depending on the various species. We also prove the hydrodynamic limit of this weakly asymmetric dynamics, which is similar to but different from the ABC model in [2]. Using the appropriate asymmetric dynamics, we also obtain that the mobility matrix relating the drift currents to the fields coincides with the covariance matrix of the reversible multinomial distribution, which then further leads to the Einstein relation
The large deviations theory for heavy-tailed processes has seen significant advances in the recent past. In particular, Rhee et al. (2019) and Bazhba et al. (2020) established large deviation asymptotics at the sample-path level for Lévy processes and random walks with regularly varying and (heavy-tailed) Weibull-type increments. This leaves the lognormal case -- one of the three most prominent classes of heavy-tailed distributions, alongside regular variation and Weibull -- open. This article establishes the \emph{extended large deviation principle} (extended LDP) at the sample-path level for one-dimensional Lévy processes and random walks with lognormal-type increments. Building on these results, we also establish the extended LDPs for multi-dimensional processes with independent coordinates. We demonstrate the sharpness of these results by constructing counterexamples, thereby proving that our results cannot be strengthened to a standard LDP under $J_1$ topology and $M_1'$ topology.
The $\lambda$-biased random walk on a binary tree of depth $n$ is the continuous-time Markov chain that has unit mean holding times and, when at a vertex other than the root or a leaf of the tree in question, has a probability of jumping to the parent vertex that is $\lambda$ times the probability of jumping to a particular child. (From the root, it chooses one of the two children with equal probability.) For this process, when $\lambda<1$, we derive an $n\rightarrow \infty$ scaling limit for the cover time, that is, the time taken to visit every vertex. The distributional limit is described in terms of a jump process on a Cantor set that can be seen as the asymptotic boundary of the tree. This conclusion complements previous results obtained when $\lambda\geq 1$.
We obtain a uniform boundary Harnack principle (BHP) on any open sets for a large class of non-local operators on metric measure spaces under a jump measure comparability and tail estimate condition, and an upper bound condition on the distribution function for the exit times from balls. These conditions are satisfied by any non-local operator $\mathcal{L}$ that admits a two-sided mixed stable-like heat kernel bounds when the underlying metric measure spaces have volume doubling and reverse volume doubling properties. The results of this paper are new even for non-local operators on Euclidean spaces. In particular, our results give not only the scale invariant but also uniform BHP for the first time for non-local operators on Euclidean spaces of both divergence form and non-divergence form with measurable coefficients.
We investigate the probability that a random polynomial with independent, mean-zero and finite variance coefficients has no real zeros. Specifically, we consider a random polynomial of degree $2n$ with coefficients given by an i.i.d. sequence of mean-zero, variance-1 random variables, multiplied by an $\frac{\alpha}{2}$-regularly varying sequence for $\alpha>-1$. We show that the probability of no real zeros is asymptotically $n^{-2(b_{\alpha}+b_0)}$, where $b_{\alpha}$ is the persistence exponents of a mean-zero, one-dimensional stationary Gaussian processes with covariance function as $\mathrm{sech}((t-s)/2)^{\alpha+1}$. Our work generalizes the previous results of Dembo et al. [DPSZ02] and Dembo \& Mukherjee [DM15] by removing the requirement of finite moments of all order or Gaussianity. In particular, in the special case $\alpha = 0$, our findings confirm a conjecture by Poonen and Stoll [PS99, Section 9.1] concerning random polynomials with i.i.d. coefficients.
Scrambling the standard 3x3x3 Rubik's Cube corresponds to a random walk on a group containing approximately 43 quintillion elements. Viewing the random walk as a Markov chain, its mixing time determines the number of random moves required to sufficiently scramble a solved cube. With the aid of a supercomputer, we show that the mixing time is at least 26, providing the first non-trivial bound.
In this paper, we study the evolution of the zero-temperature random field Ising model as the mean of the external field $M$ increases from $-\infty$ to $\infty$. We focus on two types of evolutions: the ground state evolution and the Glauber evolution. For the ground state evolution, we investigate the occurrence of global avalanche, a moment where a large fraction of spins flip simultaneously from minus to plus. In two dimensions, no global avalanche occurs, while in three or higher dimensions, there is a phase transition: a global avalanche happens when the noise intensity is small, but not when it is large. Additionally, we study the zero-temperature Glauber evolution, where spins are updated locally to minimize the Hamiltonian. Our results show that for small noise intensity, in dimensions $d =2$ or $3$, most spins flip around a critical time $c_d = \frac{2 \sqrt{d}}{1 + \sqrt{d}}$ (but we cannot decide whether such flipping occurs simultaneously or not). We also connect this process to polluted bootstrap percolation and solve an open problem on it.
In this paper, we consider the exact fractional variation for the temporal process of the solution to the fractional stochastic heat equation on $\mathbb{R}$ driven by a space-time white noise, and as an application we give the estimate of drift parameter.
We introduce the Langevin deformation for the Rényi entropy on the $L^2$-Wasserstein space over $\mathbb{R}^n$ or a Riemannian manifold, which interpolates between the porous medium equation and the Benamou-Brenier geodesic flow on the $L^2$-Wasserstein space and can be regarded as the compressible Euler equations for isentropic gas with damping. We prove the $W$-entropy-information formulae and the the rigidity theorems for the Langevin deformation for the Rényi entropy on the Wasserstein space over complete Riemannian manifolds with non-negative Ricci curvature or CD$(0, m)$-condition. Moreover, we prove the monotonicity of the Hamiltonian and the convexity of the Lagrangian along the Langevin deformation of flows. Finally, we prove the convergence of the Langevin deformation for the Rényi entropy as $c\rightarrow 0$ and $c\rightarrow \infty$ respectively. Our results are new even in the case of Euclidean spaces and compact or complete Riemannian manifolds with non-negative Ricci curvature.
We define the symmetric exclusion process (SEP) on random neighbourhood graphs drawn from Poisson point processes on complete connected Riemannian manifolds equipped with a Gibbs reference measure. We obtain diffusions with drift induced by the potential of the Gibbs measure as hydrodynamic limits. This is a consequence of the duality between the (SEP) and random walks approximating weighted Laplacians. We also lift the (SEP) to principal bundles, and we obtain horizontal diffusions with drift as hydrodynamic limits. Examples include the orthonormal frame bundle with the horizontal Laplacian which plays a central role in the Eells-Elworthy-Émery construction of Riemannian Brownian motion.
Let $P_s\phi(x)=\mathbb{E}\, \phi(X^x(s))$, be the transition semigroup on the space $B_b(E)$ of bounded measurable functions on a Banach space $E$, of the Markov family defined by the linear equation with additive noise $$ d X(s)= \left(AX(s) + a\right)ds + BdW(s), \qquad X(0)=x\in E. $$ We give a simple probabilistic proof of the fact that null-controlla\-bility of the corresponding deterministic system $$ d Y(s)= \left(AY(s)+ B\mathcal{U}(t)x)(s)\right)ds, \qquad Y(0)=x, $$ implies that for any $\phi\in B_b(E)$, $P_t\phi$ is infinitely many times Fréchet differentiable and that $$ D^nP_t\phi(x)[y_1,\ldots ,y_n]= \mathbb{E}\, \phi(X^x(t))(-1)^nI^n_t(y_1,\ldots, y_n), $$ where $I^n_t(y_1,\ldots,y_n)$ is the symmetric n-fold Itô integral of the controls $\mathcal{U}(t)y_1,\ldots \mathcal{U}(t)y_n$.
In this article, we consider the multiplicative chaos measure associated to the log-correlated random Fourier series, or random wave model, with i.i.d. coefficients taken from a general class of distributions. This measure was shown to be non-degenerate when the inverse temperature is subcritical by Junnila (Int. Math. Res. Not. 2020 (2020), no. 19, 6169-6196). When the coefficients are Gaussian, this measure is an example of a Gaussian multiplicative chaos (GMC), a well-studied universal object in the study of log-correlated fields. In the case of non-Gaussian coefficients, the resulting chaos is not a GMC in general. However, for inverse temperature inside the $L^1$-regime, we construct a coupling between the non-Gaussian multiplicative chaos measure and a GMC such that the two are almost surely mutually absolutely continuous.
We obtain approximation results for general positive linear operators satisfying mild conditions, when acting on discontinuous functions and absolutely continuous functions having discontinuous derivatives. The upper bounds, given in terms of a local first modulus of continuity, are best possible, in the sense that we can construct particular sequences of operators attaining them. When applied to functions of bounded variation or absolutely continuous functions having derivatives of bounded variation, these upper bounds are better and simpler to compute than the usual total variation bounds. The particular case of the Bernstein polynomials is thoroughly discussed. We use a probabilistic approach based on representations of such operators in terms of expectations of random variables.
Recently, a conjecture about the local bulk statistics of complex eigenvalues has been made based on numerics. It claims that there are only three universality classes, which have all been observed in open chaotic quantum systems. Motivated by these new insights, we compute and compare the expectation values of $k$ pairs of complex conjugate characteristic polynomials in three ensembles of Gaussian non-Hermitian random matrices representative for the three classes: the well-known complex Ginibre ensemble, complex symmetric and complex self-dual matrices. In the Cartan classification scheme of non-Hermitian random matrices they are labelled as class A, AI$^\dag$ and AII$^\dag$, respectively. Using the technique of Grassmann variables, we derive explicit expressions for a single pair of expected characteristic polynomials for finite as well as infinite matrix dimension. For the latter we consider the global limit as well as zoom into the edge and the bulk of the spectrum, providing new analytical results for classes AI$^\dag$ and AII$^\dag$. For general $k$, we derive the effective Lagrangians corresponding to the non-linear $\sigma$-models in the respective physical systems. Interestingly, they agree for all three ensembles, while the corresponding Goldstone manifolds, over which one has to perform the remaining integrations, are different and equal the three classical compact groups in the bulk. In particular, our analytical results show that these three ensembles have indeed different local bulk and edge spectral statistics, corroborating the conjecture further.
In this paper, we propose a new class of splitting methods to solve the stochastic Langevin equation, which can simultaneously preserve the ergodicity and exponential integrability of the original equation. The central idea is to extract a stochastic subsystem that possesses the strict dissipation from the original equation, which is inspired by the inheritance of the Lyapunov structure for obtaining the ergodicity. We prove that the exponential moment of the numerical solution is bounded, thus validating the exponential integrability of the proposed methods. Further, we show that under moderate verifiable conditions, the methods have the first-order convergence in both strong and weak senses, and we present several concrete splitting schemes based on the methods. The splitting strategy of methods can be readily extended to construct conformal symplectic methods and high-order methods that preserve both the ergodicity and the exponential integrability, as demonstrated in numerical experiments. Our numerical experiments also show that the proposed methods have good performance in the long-time simulation.
For the discrete-time or the continuous-time Markov spin models for image generation when each pixel $n=1,..,N$ can take only two values $S_n=\pm 1$, the finite-time forward propagator depends on the initial and final configurations only via their overlap. The large deviations properties with respect to the number $N$ of pixels are analyzed for the overlap and/or the magnetization during the forward noising dynamics and during the backward reconstructive dynamics for various initial conditions, namely (i) a single image (ii) a mixture of two images (iii) when the initial condition corresponds to the Curie-Weiss mean-field ferromagnetic model.
We present a stochastic model for two successive SIR (Susceptible, Infectious, Recovered) epidemics in the same network structured population. Individuals infected during the first epidemic might have (partial) immunity for the second one. The first epidemic is analysed through a bond percolation model, while the second epidemic is approximated by a three-type branching process in which the types of individuals depend on their position in the percolation clusters used for the first epidemic. This branching process approximation enables us to calculate, in the large population limit and conditional upon a large outbreak in the first epidemic, a threshold parameter and the probability of a large outbreak for the second epidemic. A second branching process approximation enables us to calculate the fraction of the population that are infected by such a second large outbreak. We illustrate our results through some specific cases which have appeared previously in the literature and show that our asymptotic results give good approximations for finite populations.
We extend the Gibbs conditioning principle to an abstract setting combining infinitely many linear equality constraints and non-linear inequality constraints, which need not be convex. A conditional large large deviation principle (LDP) is proved in a Wassersteintype topology, and optimality conditions are written in this abstract setting. This setting encompasses versions of the Schrödinger bridge problem with marginal non-linear inequality constraints at every time. In the case of convex constraints, stability results for perturbations both in the constraints and the reference measure are proved. We then specify our results when the reference measure is the path-law of a continuous diffusion process, whose law is constrained at each time. We obtain a complete description of the constrained process through an atypical mean-field PDE system involving a Lagrange multiplier.
We adapt Stein's method to isoperimetric and geometric inequalities. The main challenge is the treatment of boundary terms. We address this by using an elliptic PDE with an oblique boundary condition. We apply our geometric formulation of Stein's method to obtain stability of the Brock-Weinstock inequality, stability of the isoperimetric inequality under a constraint on Steklov's first non-zero eigenvalue, and stability for the combination of weighted and unweighted perimeters. All stability results are formulated with respect to the $\alpha$-Zolotarev distance, $\alpha$ $\in$ (0, 1], that we introduce to interpolate between the Fraenkel asymmetry and the Kantorovich distance.
The first goal of the present paper is to study residualities of the set of uniform $P$-ergodic Markov semigroups defined on abstract state spaces by means of a generalized Dobrushin ergodicity coefficient. In the last part of the paper, we explore uniform mean ergodicities of Markov semigroups.
In this paper, we consider the problem of estimating the interaction parameter $p$ of a $p$-spin Curie-Weiss model at inverse temperature $\beta$, given a single observation from this model. We show, by a contiguity argument, that joint estimation of the parameters $\beta$ and $p$ is impossible, which implies that estimation of $p$ is impossible if $\beta$ is unknown. These impossibility results are also extended to the more general $p$-spin Erdős-Rényi Ising model. The situation is more delicate when $\beta$ is known. In this case, we show that there exists an increasing threshold function $\beta^*(p)$, such that for all $\beta$, consistent estimation of $p$ is impossible when $\beta^*(p) > \beta$, and for almost all $\beta$, consistent estimation of $p$ is possible for $\beta^*(p)<\beta$.
A major limitation of machine learning (ML) prediction models is that they recover associational, rather than causal, predictive relationships between variables. In high-stakes automation applications of ML this is problematic, as the model often learns spurious, non-causal associations. This paper proposes mechanism learning, a simple method which uses front-door causal bootstrapping to deconfound observational data such that any appropriate ML model is forced to learn predictive relationships between effects and their causes (reverse causal inference), despite the potential presence of multiple unknown and unmeasured confounding. Effect variables can be very high dimensional, and the predictive relationship nonlinear, as is common in ML applications. This novel method is widely applicable, the only requirement is the existence of a mechanism variable mediating the cause (prediction target) and effect (feature data), which is independent of the (unmeasured) confounding variables. We test our method on fully synthetic, semi-synthetic and real-world datasets, demonstrating that it can discover reliable, unbiased, causal ML predictors where by contrast, the same ML predictor trained naively using classical supervised learning on the original observational data, is heavily biased by spurious associations. We provide code to implement the results in the paper, online.