CyberSec Research

We study graph bootstrap percolation on the Erd\H{o}s-R\'enyi random graph ${\mathcal G}_{n,p}$. For all $r \ge 5$, we locate the sharp $K_r$-percolation threshold $p_c \sim (\gamma n)^{-1/\lambda}$, solving a problem of Balogh, Bollob\'as and Morris. The case $r=3$ is the classical graph connectivity threshold, and the threshold for $r=4$ was found using strong connections with the well-studied $2$-neighbor dynamics from statistical physics. When $r \ge 5$, such connections break down, and the process exhibits much richer behavior. The constants $\lambda=\lambda(r)$ and $\gamma=\gamma(r)$ in $p_c$ are determined by a class of $\left({r\choose2}-1\right)$-ary tree-like graphs, which we call $K_r$-tree witness graphs. These graphs are associated with the most efficient ways of adding a new edge in the $K_r$-dynamics, and they can be counted using the Fuss-Catalan numbers. Also, in the subcritical setting, we determine the asymptotic number of edges added to ${\mathcal G}_{n,p}$, showing that the edge density increases only by a constant factor, whose value we identify.

Pick $N$ random points $U_1,\cdots,U_{N}$ independently and uniformly in a triangle ABC with area 1, and take the convex hull of the set $\{A,B,U_1,\cdots,U_{N}\}$. The boundary of this convex hull is a convex chain $V_0=B,V_1,\cdots,$ $V_{\mathbf{n}(N)}$, $V_{\mathbf{n}(N)+1}=A$ with random size $\mathbf{n}(N)$. The first aim of this paper is to study the asymptotic behavior of this chain, conditional on $\mathbf{n}(N)=n$, when both $n$ and $m=N-n$ go to $+\infty$. We prove a phase transition: if $m=\lfloor n\lambda\rfloor$ where $\lambda>0$, this chain converges in probability for the Hausdorff topology to an (explicit) hyperbola ${\cal H}_\lambda$ as $n\to+\infty$, while, if $m=o(n)$, the limit shape is a parabola. We prove that this hyperbola is solution to an optimization problem: among all concave curves ${\cal C}$ in $ABC$ (incident with $A$ and $B$), ${\cal H}_\lambda$ is the unique curve maximizing the functional ${\cal C}\mapsto {\sf Area}({\cal C})^{\lambda} {\sf L}({\cal C})^3$ where ${\sf L}({\cal C})$ is the affine perimeter of ${\cal C}$. We also give the logarithm expansion of the probability ${\bf Q}^{\triangle \bullet\bullet}_{n,\lfloor n\lambda\rfloor}$, that $\mathbf{n}(N)=n$ when $N=n+\lfloor n\lambda\rfloor$. Take a compact convex set $\mathbf{K}$ with area 1 in the plane, and denote by ${\bf Q}^{\mathbf{K}}_{n,m}$ the probability of the event that the convex hull of $n+m$ iid uniform points in $\mathbf{K}$ is a polygon with $n$ vertices. We provide some results and conjectures regarding the asymptotic logarithm expansion of ${\bf Q}^{\mathbf{K}}_{n,m}$, as well as results and conjectures concerning limit shape theorems, conditional on this event. These results and conjectures generalize B\'ar\'any's results, who treated the case $\lambda=0$.

We consider independent long-range percolation models on locally finite vertex-transitive graphs. Using coupling ideas we prove strict monotonicity of the critical points with respect to local perturbations in the connection function, thereby improving upon previous results obtained via the classical essential enhancement method of Aizenman and Grimmett in several ways. In particular, our approach allows us to work under minimal assumptions, namely shift-invariance and summability of the connection function, and it applies to both undirected and directed bond percolation models.

We extend the functional Breuer-Major theorem for Gaussians to the Poisson case, where the stationary sequence arises from a Poisson point process. We use the $L^p$ spectral gap inequality of Poisson point process as a tool to prove tightness.

Let $M$ be an irreducible transition matrix on a finite state space $V$. For a Markov chain $C=(C_k,k\geq 0)$ with transition matrix $M$, let $\tau^{\geq 1}_u$ denote the first positive hitting time of $u$ by $C$, and $\rho$ the unique invariant measure of $M$. Kemeny proved that if $X$ is sampled according to $\rho$ independently of $C$, the expected value of the first positive hitting time of $X$ by $C$ does not depend on the starting state of the chain: all the values $(E(\tau^{\geq 1}_X~|~C_0=u), u \in V)$ are equal. \par In this paper, we show that this property follows from a more general result: the generating function $\sum_{v\in V}E(x^{\tau_v^{\geq 1}}~|~C_0=u)\det(Id-xM^{(v)})$ is independent of the starting state $u$, where $M^{(v)}$ is obtained from $M$ by deleting the row and column corresponding to the state $v$. The factors appearing in this generating function are: first, the probability generating function of $\tau^{\geq 1}_v$, and second, the sequence of determinants $(det(Id-xM^{(v)}),v\in V),$ which, for $x=1$, is known to be proportional to the invariant measure $(\rho_u,u\in V)$. From this property, we deduce several further results, including relations involving higher moments of $\tau_X^{\geq 1}$, which are of independent interest.

We find conditions for stationary measures of random dynamical systems on surfaces having dissipative diffeomorphisms to be absolutely continuous. These conditions involve a uniformly expanding on average property in the future (UEF) and past (UEP). Our results can cover random dynamical systems generated by "very dissipative" diffeomorphisms and perturbations of volume preserving surface diffeomorphisms. For example, we can consider a random dynamical system on $\mathbb{T}^2$ generated by perturbations of a pair of non-commuting infinite order toral automorphisms with any arbitrary single diffeomorphism. In this case, we conclude that stationary measures are either atomic or absolutely continuous. We also obtain an orbit classification and equidistribution result.

In this paper, we introduce and study two time-changed variants of the generalized fractional Skellam process. These are obtained by time-changing the generalized fractional Skellam process with an independent L\'evy subordinator with finite moments of any order and its inverse, respectively. We call the introduced processes the time-changed generalized fractional Skellam process-I (TCGFSP-I) and the time-changed generalized fractional Skellam process-II (TCGFSP-II), respectively. The probability generating function, moment generating function, moments, factorial moments, variance, covariance, {\it etc.}, are derived for the TCGFSP-I. We obtain a variant of the law of the iterated logarithm for it and establish its long-range dependence property. Several special cases of the TCGFSP-I are considered, and the associated system of governing differential equations is obtained. Later, some distributional properties and particular cases are discussed for the TCGFSP-II.

We study longest and shortest directed paths in the following natural model of directed random planar maps: the uniform infinite bipolar-oriented triangulation (UIBOT), which is the local limit of uniform bipolar-oriented triangulations around a typical edge. We construct the Busemann function which measures directed distance to $\infty$ along a natural interface in the UIBOT. We show that in the case of longest (resp.\ shortest) directed paths, this Busemann function converges in the scaling limit to a $2/3$-stable L\'evy process (resp.\ a $4/3$-stable L\'evy process). We also prove up-to-constants bounds for directed distances in finite bipolar-oriented triangulations sampled from a Boltzmann distribution, and for size-$n$ cells in the UIBOT. These bounds imply that in a typical subset of the UIBOT with $n$ edges, longest directed path lengths are of order $n^{3/4}$ and shortest directed path lengths are of order $n^{3/8}$. These results give the scaling dimensions for discretizations of the (hypothetical) $\sqrt{4/3}$-directed Liouville quantum gravity metrics. The main external input in our proof is the bijection of Kenyon-Miller-Sheffield-Wilson (2015). We do not use any continuum theory. We expect that our techniques can also be applied to prove similar results for directed distances in other random planar map models and for longest increasing subsequences in pattern-avoiding permutations.

We introduce a general diploid population model with self-fertilization and possible overlapping generations, and study the genealogy of a sample of $n$ genes as the population size $N$ tends to infinity. Unlike traditional approach in coalescent theory which considers the unconditional (annealed) law of the gene genealogies averaged over the population pedigree, here we study the conditional (quenched) law of gene genealogies given the pedigree. We focus on the case of high selfing probability and obtain that this conditional law converges to a random probability measure, given by the random law of a system of coalescing random walks on an exchangeable fragmentation-coalescence process of \cite{berestycki04}. This system contains the system of coalescing random walks on the ancestral recombination graph as a special case, and it sheds new light on the site-frequency spectrum (SFS) of genetic data by specifying how SFS depends on the pedigree. The convergence result is proved by means of a general characterization of weak convergence for random measures on the Skorokhod space with paths taking values in a locally compact Polish space.

This paper extends the asymmetric Kullback-Leibler divergence and symmetric Jensen-Shannon divergence from two probability measures to the case of two sets of probability measures. We establish some fundamental properties of these generalized divergences, including a duality formula and a Pinsker-type inequality. Furthermore, convergence results are derived for both the generalized asymmetric and symmetric divergences, as well as for weak convergence under sublinear expectations.

Pinsker-type inequalities are considered for the weighted total variation distance between probability measures in terms of the R\'enyi divergence powers. They are applied in derivation of transport-entropy inequalities under moment-type conditions.

This paper establishes a probabilistic representation for the solution of the parabolic obstacle problem associated with the normalized $p$-Laplacian. We introduce a zero-sum stochastic tug-of-war game with noise in a space-time cylinder, where one player has the option to stop the game at any time to collect a payoff given by an obstacle function. We prove that the value functions of this game exist, satisfy a dynamic programming principle, and converge uniformly to the unique viscosity solution of the continuous obstacle problem as the step size $\varepsilon$ tends to zero.

We study the recovery of the distribution function $F_X$ of a random variable $X$ that is subject to an independent additive random error $\varepsilon$. To be precise, it is assumed that the target variable $X$ is available only in the form of a blurred surrogate $Y = X + \varepsilon$. The distribution function $F_Y$ then corresponds to the convolution of $F_X$ and $F_\varepsilon$, so that the reconstruction of $F_X$ is some kind of deconvolution problem. Those have a long history in mathematics and various approaches have been proposed in the past. Most of them use integral transforms or matrix algorithms. The present article avoids these tools and is entirely confined to the domain of distribution functions. Our main idea relies on a transformation of a first kind to a second kind integral equation. Thereof, starting with a right-lateral discrete target and error variable, a representation for $F_X$ in terms of available quantities is obtained, which facilitates the unbiased estimation through a $Y$-sample. It turns out that these results even extend to cases in which $X$ is not discrete. Finally, in a general setup, our approach gives rise to an approximation for $F_X$ as a certain Neumann sum. The properties of this sum are briefly examined theoretically and visually. The paper is concluded with a short discussion of operator theoretical aspects and an outlook on further research. Various plots underline our results and illustrate the capabilities of our functions with regard to estimation.

The double Dixie cup problem of D.J. Newman and L. Shepp is a well-known variant of the coupon collector problem, where the object of study is the number of coupons that a collector has to buy in order to complete m sets of all N existing different coupons. In this paper we consider the case where the coupons distribution is a mixture of two different distributions, where the coupons from the first distribution are far rarer than the ones coming from the second. We apply a Poissonization technique, as well as well known results and techniques from our previous work, to derive the asymptotics (leading term) of the expectation of the above random variable as N goes to infinity for large classes of distributions. As it turns out, both distributions contribute to this result. The leading asymptotics of the rising moments of the aforementioned random variable are also discussed. We conclude by generalizing the problem to the case where the family of coupons is a mixture of j subfamilies.

We present an extension of the famous Littlewood-Offord problem when Bernoulli distributions are replaced with discrete log-concave distributions. A variant of the Littlewood-Offord problem for arithmetic progressions, as well as an entropic version, is also discussed. Along the way, we recover and extend a result of Madiman and Woo (2015) on the entropy power inequality for discrete uniform distributions.

Occupation times quantify how long a stochastic process remains in a region, and their single-time statistics are famously given by the arcsine law for Brownian and L\'evy processes. By contrast, two-time occupation statistics, which directly probe temporal correlations and aging, have resisted exact characterization beyond renewal processes. In this Letter we derive exact results for generic one-dimensional jump processes, a central framework for intermittent and discretely sampled dynamics. Using generalized Wiener-Hopf methods, we obtain the joint distribution of occupation time and position, the aged occupation-time law, and the autocorrelation function. In the continuous-time scaling limit, universal features emerge that depend only on the tail of the jump distribution, providing a starting point for exploring aging transport in complex environments.

We show that the heat kernel measures based at the north pole of the spheres $S^{N-1}(\sqrt N)$, with properly scaled radius $\sqrt N$ and adjusted center, converges to a Gaussian measure in $\R^\infty$, and find an explicit formula for this measure.

We study the excess growth rate -- a fundamental logarithmic functional arising in portfolio theory -- from the perspective of information theory. We show that the excess growth rate can be connected to the R\'{e}nyi and cross entropies, the Helmholtz free energy, L. Campbell's measure of average code length and large deviations. Our main results consist of three axiomatic characterization theorems of the excess growth rate, in terms of (i) the relative entropy, (ii) the gap in Jensen's inequality, and (iii) the logarithmic divergence that generalizes the Bregman divergence. Furthermore, we study maximization of the excess growth rate and compare it with the growth optimal portfolio. Our results not only provide theoretical justifications of the significance of the excess growth rate, but also establish new connections between information theory and quantitative finance.