Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere

Ronen Eldan

Displaying similar documents to “Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere”

Giant component and vacant set for random walk on a discrete torus

Itai Benjamini, Alain-Sol Sznitman (2008)

Journal of the European Mathematical Society

Similarity:

We consider random walk on a discrete torus $E$ of side-length $N$ , in sufficiently high dimension $d$ . We investigate the percolative properties of the vacant set corresponding to the collection of sites which have not been visited by the walk up to time $u N^{d}$ . We show that when $u$ is chosen small, as $N$ tends to infinity, there is with overwhelming probability a unique connected component in the vacant set which contains segments of length const $log N$ . Moreover, this connected component occupies a...

Random ε-nets and embeddings in $ℓ_{\infty}^{N}$

Y. Gordon, A. E. Litvak, A. Pajor, N. Tomczak-Jaegermann (2007)

Studia Mathematica

Similarity:

We show that, given an n-dimensional normed space X, a sequence of $N = {(8 / ε)}^{2 n}$ independent random vectors ${(X_{i})}_{i = 1}^{N}$ , uniformly distributed in the unit ball of X*, with high probability forms an ε-net for this unit ball. Thus the random linear map $Γ : ℝ \to ℝ^{N}$ defined by $Γ x = {(⟨ x, X_{i} ⟩)}_{i = 1}^{N}$ embeds X in $ℓ_{\infty}^{N}$ with at most 1 + ε norm distortion. In the case X = ℓ₂ⁿ we obtain a random 1+ε-embedding into $ℓ_{\infty}^{N}$ with asymptotically best possible relation between N, n, and ε.

Positivity of integrated random walks

Vladislav Vysotsky (2014)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Take a centered random walk $S_{n}$ and consider the sequence of its partial sums $A_{n} : = \sum_{i = 1}^{n} S_{i}$ . Suppose $S_{1}$ is in the domain of normal attraction of an $α$ -stable law with $1 l t; α \leq 2$ . Assuming that $S_{1}$ is either right-exponential (i.e. $ℙ (S_{1} g t; x | S_{1} g t; 0) = e^{- a x}$ for some $a g t; 0$ and all $x g t; 0$ ) or right-continuous (skip free), we prove that $ℙ {A_{1} g t; 0, \dots, A_{N} g t; 0} \sim C_{α} N^{1 / (2 α) - 1 / 2}$ as $N \to \infty$ , where $C_{α} g t; 0$ depends on the distribution of the walk. We also consider a conditional version of this problem and study positivity of integrated discrete bridges.

Asymptotic behavior of a stochastic combustion growth process

Alejandro Ramírez, Vladas Sidoravicius (2004)

Journal of the European Mathematical Society

Similarity:

We study a continuous time growth process on the $d$ -dimensional hypercubic lattice $𝒵^{d}$ , which admits a phenomenological interpretation as the combustion reaction $A + B \to 2 A$ , where $A$ represents heat particles and $B$ inert particles. This process can be described as an interacting particle system in the following way: at time 0 a simple symmetric continuous time random walk of total jump rate one begins to move from the origin of the hypercubic lattice; then, as soon as any random walk visits a site...

Stable random fields and geometry

Shigeo Takenaka (2010)

Banach Center Publications

Similarity:

Let (M,d) be a metric space with a fixed origin O. P. Lévy defined Brownian motion X(a); a ∈ M as 0. X(O) = 0. 1. X(a) - X(b) is subject to the Gaussian law of mean 0 and variance d(a,b). He gave an example for $M = S^{m}$ , the m-dimensional sphere. Let $Y (B); B \in ℬ (S^{m})$ be the Gaussian random measure on $S^{m}$ , that is, 1. Y(B) is a centered Gaussian system, 2. the variance of Y(B) is equal of μ(B), where μ is the uniform measure on $S^{m}$ , 3. if B₁ ∩ B₂ = ∅ then Y(B₁) is independent of Y(B₂). 4. for $B_{i}$ , i = 1,2,..., $B_{i} \cap B_{j} = \emptyset$ ,...

About the generating function of a left bounded integer-valued random variable

Charles Delorme, Jean-Marc Rinkel (2008)

Bulletin de la Société Mathématique de France

Similarity:

We give a relation between the sign of the mean of an integer-valued, left bounded, random variable $X$ and the number of zeros of $1 - Φ (z)$ inside the unit disk, where $Φ$ is the generating function of $X$ , under some mild conditions

Universality of the asymptotics of the one-sided exit problem for integrated processes

Frank Aurzada, Steffen Dereich (2013)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider the one-sided exit problem – also called one-sided barrier problem – for ( $α$ -fractionally) integrated random walks and Lévy processes. Our main result is that there exists a positive, non-increasing function $α \mapsto θ (α)$ such that the probability that any $α$ -fractionally integrated centered Lévy processes (or random walk) with some finite exponential moment stays below a fixed level until time $T$ behaves as $T^{- θ (α) + o (1)}$ for large $T$ . We also investigate when the fixed level can be replaced by a different...

The spread of a catalytic branching random walk

Philippe Carmona, Yueyun Hu (2014)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider a catalytic branching random walk on $ℤ$ that branches at the origin only. In the supercritical regime we establish a law of large number for the maximal position $M_{n}$ : For some constant $α$ , $\frac{M_{n}}{n} \to α$ almost surely on the set of infinite number of visits of the origin. Then we determine all possible limiting laws for $M_{n} - α n$ as $n$ goes to infinity.

On the Law of Large Numbers for Nonmeasurable Identically Distributed Random Variables

Alexander R. Pruss (2013)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

Let Ω be a countable infinite product $Ω ₁^{ℕ}$ of copies of the same probability space Ω₁, and let Ξₙ be the sequence of the coordinate projection functions from Ω to Ω₁. Let Ψ be a possibly nonmeasurable function from Ω₁ to ℝ, and let Xₙ(ω) = Ψ(Ξₙ(ω)). Then we can think of Xₙ as a sequence of independent but possibly nonmeasurable random variables on Ω. Let Sₙ = X₁ + ⋯ + Xₙ. By the ordinary Strong Law of Large Numbers, we almost surely have $E_{*} [X ₁] \leq l i m i n f S ₙ / n \leq l i m s u p S ₙ / n \leq E * [X ₁]$ , where $E_{*}$ and E* are the lower and upper expectations....

The number of absorbed individuals in branching brownian motion with a barrier

Pascal Maillard (2013)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We study supercritical branching Brownian motion on the real line starting at the origin and with constant drift $c$ . At the point $x g t; 0$ , we add an absorbing barrier, i.e. individuals touching the barrier are instantly killed without producing offspring. It is known that there is a critical drift $c_{0}$ , such that this process becomes extinct almost surely if and only if $c \geq c_{0}$ . In this case, if $Z_{x}$ denotes the number of individuals absorbed at the barrier, we give an asymptotic for $P (Z_{x} = n)$ as $n$ goes to infinity....

Some limit theorems for $m$ -pairwise negative quadrant dependent random variables

Yongfeng Wu, Jiangyan Peng (2018)

Kybernetika

Similarity:

The authors first establish the Marcinkiewicz-Zygmund inequalities with exponent $p$ ( $1 \leq p \leq 2$ ) for $m$ -pairwise negatively quadrant dependent ( $m$ -PNQD) random variables. By means of the inequalities, the authors obtain some limit theorems for arrays of rowwise $m$ -PNQD random variables, which extend and improve the corresponding results in [Y. Meng and Z. Lin (2009)] and [H. S. Sung (2013)]. It is worthy to point out that the open problem of [H. S. Sung, S. Lisawadi, and A. Volodin (2008)] can be...

A Note on the Men'shov-Rademacher Inequality

Witold Bednorz (2006)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

We improve the constants in the Men’shov-Rademacher inequality by showing that for n ≥ 64, $E (s u p_{1 \leq k \leq n} | \sum_{i = 1}^{k} X_{i} | ² \leq 0.11 (6.20 + l o g ₂ n) ²$ for all orthogonal random variables X₁,..., Xₙ such that $\sum_{k = 1}^{n} E | X_{k} | ² = 1$ .

Size of the giant component in a random geometric graph

Ghurumuruhan Ganesan (2013)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

In this paper, we study the size of the giant component $C_{G}$ in the random geometric graph $G = G (n, r_{n}, f)$ of $n$ nodes independently distributed each according to a certain density $f (\cdot)$ in ${[0, 1]}^{2}$ satisfying ${inf}_{x \in {[0, 1]}^{2}} f (x) g t;$ $0$ . If $\frac{c_{1}}{n} \leq r_{n}^{2} \leq c_{2} \frac{log n}{n}$ for some positive constants $c_{1}$ , $c_{2}$ and $n r_{n}^{2} ⟶ \infty$ as $n \to \infty$ , we show that the giant component of $G$ contains at least $n - o (n)$ nodes with probability at least $1 - e^{- β n r_{n}^{2}}$ for all $n$ and for some positive constant $β$ . We also obtain estimates on the diameter and number of the non-giant components of $G$ .

The absolute continuity of the invariant measure of random iterated function systems with overlaps

Balázs Bárány, Tomas Persson (2010)

Fundamenta Mathematicae

Similarity:

We consider iterated function systems on the interval with random perturbation. Let $Y_{ε}$ be uniformly distributed in [1-ε,1+ ε] and let $f_{i} \in C^{1 + α}$ be contractions with fixpoints $a_{i}$ . We consider the iterated function system $Y_{ε} f_{i} + a_{i} (1 - Y_{ε}) ⁿ_{i = 1}$ , where each of the maps is chosen with probability $p_{i}$ . It is shown that the invariant density is in L² and its L² norm does not grow faster than 1/√ε as ε vanishes. The proof relies on defining a piecewise hyperbolic dynamical system on the cube with an SRB-measure whose projection...

Dimension of weakly expanding points for quadratic maps

Samuel Senti (2003)

Bulletin de la Société Mathématique de France

Similarity:

For the real quadratic map $P_{a} (x) = x^{2} + a$ and a given $ϵ > 0$ a point $x$ has good expansion properties if any interval containing $x$ also contains a neighborhood $J$ of $x$ with $P_{a}^{n} |_{J}$ univalent, with bounded distortion and $B (0, ϵ) \subseteq P_{a}^{n} (J)$ for some $n \in ℕ$ . The $ϵ$ -weakly expanding set is the set of points which do not have good expansion properties. Let $α$ denote the negative fixed point and $M$ the first return time of the critical orbit to $[α, - α]$ . We show there is a set $ℛ$ of parameters with positive Lebesgue measure for which the Hausdorff...

Uniform mixing time for random walk on lamplighter graphs

Júlia Komjáthy, Jason Miller, Yuval Peres (2014)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Suppose that $𝒢$ is a finite, connected graph and $X$ is a lazy random walk on $𝒢$ . The lamplighter chain $X^{⋄}$ associated with $X$ is the random walk on the wreath product $𝒢^{⋄} = 𝐙_{2} ≀ 𝒢$ , the graph whose vertices consist of pairs $(\underset{̲}{f}, x)$ where $f$ is a labeling of the vertices of $𝒢$ by elements of $𝐙_{2} = {0, 1}$ and $x$ is a vertex in $𝒢$ . There is an edge between $(\underset{̲}{f}, x)$ and $(\underset{̲}{g}, y)$ in $𝒢^{⋄}$ if and only if $x$ is adjacent to $y$ in $𝒢$ and $f_{z} = g_{z}$ for all $z \neq x, y$ . In each step, $X^{⋄}$ moves from a configuration $(\underset{̲}{f}, x)$ by updating $x$ to $y$ using the transition rule of $X$ and then...

On uniqueness of distribution of a random variable whose independent copies span a subspace in $L_{p}$

S. Astashkin, F. Sukochev, D. Zanin (2015)

Studia Mathematica

Similarity:

Let 1 ≤ p < 2 and let $L_{p} = L_{p} [0, 1]$ be the classical $L_{p}$ -space of all (classes of) p-integrable functions on [0,1]. It is known that a sequence of independent copies of a mean zero random variable $f \in L_{p}$ spans in $L_{p}$ a subspace isomorphic to some Orlicz sequence space $l_{M}$ . We give precise connections between M and f and establish conditions under which the distribution of a random variable $f \in L_{p}$ whose independent copies span $l_{M}$ in $L_{p}$ is essentially unique.

On sum-product representations in $ℤ_{q}$

Mei-Chu Chang (2006)

Journal of the European Mathematical Society

Similarity:

The purpose of this paper is to investigate efficient representations of the residue classes modulo $q$ , by performing sum and product set operations starting from a given subset $A$ of $ℤ_{q}$ . We consider the case of very small sets $A$ and composite $q$ for which not much seemed known (nontrivial results were recently obtained when $q$ is prime or when log $| A | \sim log q$ ). Roughly speaking we show that all residue classes are obtained from a $k$ -fold sum of an $r$ -fold product set of $A$ , where $r ≪ log q$ and $log k ≪ log q$ , provided the...

Supercritical self-avoiding walks are space-filling

Hugo Duminil-Copin, Gady Kozma, Ariel Yadin (2014)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

In this article, we consider the following model of self-avoiding walk: the probability of a self-avoiding trajectory $γ$ between two points on the boundary of a finite subdomain of $ℤ^{d}$ is proportional to $μ^{- length (γ)}$ . When $μ$ is supercritical (i.e. $μ l t; μ_{c}$ where $μ_{c}$ is the connective constant of the lattice), we show that the random trajectory becomes space-filling when taking the scaling limit.

Soft local times and decoupling of random interlacements

Serguei Popov, Augusto Teixeira (2015)

Journal of the European Mathematical Society

Similarity:

In this paper we establish a decoupling feature of the random interlacement process $ℐ^{u} \subset ℤ^{d}$ at level $u$ , $d \geq 3$ . Roughly speaking, we show that observations of $ℐ^{u}$ restricted to two disjoint subsets $A_{1}$ and $A_{2}$ of $ℤ^{d}$ are approximately independent, once we add a sprinkling to the process $ℐ^{u}$ by slightly increasing the parameter $u$ . Our results differ from previous ones in that we allow the mutual distance between the sets $A_{1}$ and $A_{2}$ to be much smaller than their diameters. We then provide an important application...

On families of weakly dependent random variables

Tomasz Łuczak (2011)

Banach Center Publications

Similarity:

Let $ₙ^{(k)}$ be a family of random independent k-element subsets of [n] = 1,2,...,n and let $(ₙ^{(k)}, ℓ) = ₙ^{(k)} (ℓ)$ denote a family of ℓ-element subsets of [n] such that the event that S belongs to $ₙ^{(k)} (ℓ)$ depends only on the edges of $ₙ^{(k)}$ contained in S. Then, the edges of $ₙ^{(k)} (ℓ)$ are ’weakly dependent’, say, the events that two given subsets S and T are in $ₙ^{(k)} (ℓ)$ are independent for vast majority of pairs S and T. In the paper we present some results on the structure of weakly dependent families of subsets obtained in this way. We...