Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks
140
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $xi_1,xi_2,ldots$ be a sequence of independent copies of a random vector in $mathbb R^d$ having an absolutely continuous distribution. Consider a random walk $S_i:=xi_1+cdots+xi_i$, and let $C_{n,d}:=text{conv}(0,S_1,S_2,ldots,S_n)$ be the convex hull of the first $n+1$ points it has visited. The polytope $C_{n,d}$ is called $k$-neighborly if for every indices $0leq i_0 <cdots < i_kleq n$ the convex hull of the $k+1$ points $S_{i_0},ldots, S_{i_k}$ is a $k$-dimensional face of $C_{n,d}$. We study the probability that $C_{n,d}$ is $k$-neighborly in various high-dimensional asymptotic regimes, i.e. when $n$, $d$, and possibly also $k$ diverge to $infty$. There is an explicit formula for the expected number of $k$-dimensional faces of $C_{n,d}$ which involves Stirling numbers of both kinds. Motivated by this formula, we introduce a distribution, called the Lah distribution, and study its properties. In particular, we provide a combinatorial interpretation of the Lah distribution in terms of random compositions and records, and explicitly compute its factorial moments. Limit theorems which we prove for the Lah distribution imply neighborliness properties of $C_{n,d}$. This yields a new class of random polytopes exhibiting phase transitions parallel to those discovered by Vershik and Sporyshev, Donoho and Tanner for random projections of regular simplices and crosspolytopes.
rate research
Read More
Let $X_1,ldots,X_n$ be independent random points that are distributed according to a probability measure on $mathbb{R}^d$ and let $P_n$ be the random convex hull generated by $X_1,ldots,X_n$ ($ngeq d+1$). Natural classes of probability distributions are characterized for which, by means of Blaschke-Petkantschin formulae from integral geometry, one can show that the mean facet number of $P_n$ is strictly monotonically increasing in $n$.
We consider the convex hull of the perturbed point process comprised of $n$ i.i.d. points, each distributed as the sum of a uniform point on the unit sphere $S^{d-1}$ and a uniform point in the $d$-dimensional ball centered at the origin and of radius $n^{alpha}, alpha in (-infty, infty)$. This model, inspired by the smoothed complexity analysis introduced in computational geometry cite{DGGT,ST}, is a perturbation of the classical random polytope. We show that the perturbed point process, after rescaling, converges in the scaling limit to one of five Poisson point processes according to whether $alpha$ belongs to one of five regimes. The intensity measure of the limit Poisson point process undergoes a transition at the values $alpha = frac{-2} {d -1}$ and $alpha = frac{2} {d + 1}$ and it gives rise to four rescalings for the $k$-face functional on perturbed data. These rescalings are used to establish explicit expectation asymptotics for the number of $k$-dimensional faces of the convex hull of either perturbed binomial or Poisson data. In the case of Poisson input, we establish explicit variance asymptotics and a central limit theorem for the number of $k$-dimensional faces. Finally it is shown that the rescaled boundary of the convex hull of the perturbed point process converges to the boundary of a parabolic hull process.
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $( u {bf d})^{-1}log n pm (log n)^{1/2+o(1)}$, where $ u$ and ${bf d}$ are the speed of random walk and dimension of harmonic measure on a ${rm Poisson}(lambda)$-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.
Consider a system of coalescing random walks where each individual performs random walk over a finite graph G, or (more generally) evolves according to some reversible Markov chain generator Q. Let C be the first time at which all walkers have coalesced into a single cluster. C is closely related to the consensus time of the voter model for this G or Q. We prove that the expected value of C is at most a constant multiple of the largest hitting time of an element in the state space. This solves a problem posed by Aldous and Fill and gives sharp bounds in many examples, including all vertex-transitive graphs. We also obtain results on the expected time until only k>1 clusters remain. Our proof tools include a new exponential inequality for the meeting time of a reversible Markov chain and a deterministic trajectory, which we believe to be of independent interest.
This paper presents a new algorithm for the convex hull problem, which is based on a reduction to a combinatorial decision problem POLYTOPE-COMPLETENESS-COMBINATORIAL, which in turn can be solved by a simplicial homology computation. Like other convex hull algorithms, our algorithm is polynomial (in the size of input plus output) for simplicial or simple input. We show that the ``no-case of POLYTOPE-COMPLETENESS-COMBINATORIAL has a certificate that can be checked in polynomial time (if integrity of the input is guaranteed).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
