Source author record

Perla Sousi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.CO math.CA math.FA Discrete Mathematics math-ph math.MP

Catalog footprint

Research overview

23works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Chen--Stein Method for the Uncovered Set of Random Walk on $\mathbb Z_n^d$ for $d \ge 3$

Let $X$ be a simple random walk on $\mathbb{Z}_n^d$ with $d\geq 3$ and let $t_{\rm{cov}}$ be the expected cover time. We consider the set of points $\mathcal{U}_α$ of $\mathbb{Z}_n^d$ that have not been visited by the walk by time $αt_{\rm{cov}}$ for $α\in (0,1)$ . It was shown in [MS17] that there exists $α_1(d)\in (0,1)$ such that for all $α>α_1(d)$ the total variation distance between the law of the set $\mathcal{U}_α$ and an i.i.d. sequence of Bernoulli random variables indexed by $\mathbb{Z}_n^d$ with success probability $n^{-αd}$ tends to $0$ as $n \to \infty$ . In [MS17] the constant $α_1(d)$ converges to $1$ as $d\to\infty$ . In this short note using the Chen--Stein method and a concentration result for Markov chains of Lezaud we greatly simplify the proof of [MS17] and find a constant $α_1(d)$ which converges to $3/4$ as $d\to\infty$ .

preprint2021arXiv

Cutoff for Random Walk on Dynamical Erdős--Rényi Graph

We consider dynamical percolation on the complete graph $K_n$ , where each edge refreshes its state at rate $μ\ll 1/n$ , and is then declared open with probability $p = λ/n$ where $λ> 1$ . We study a random walk on this dynamical environment which jumps at rate $1/n$ along every open edge. We show that the mixing time of the full system exhibits cutoff at $\log n/μ$ . We do this by showing that the random walk component mixes faster than the environment process; along the way, we control the time it takes for the walk to become isolated.

preprint2020arXiv

A comparison principle for random walk on dynamical percolation

We consider the model of random walk on dynamical percolation introduced by Peres, Stauffer and Steif (2015). We obtain comparison results for this model for hitting and mixing times and for the spectral-gap and log-Sobolev constant with the corresponding quantities for simple random walk on the underlying graph $G$ , for general graphs. When $G$ is the torus $\mathbb{Z}_n^d$ , we recover the results of Peres et al. and we also extend them to the critical case. We also obtain bounds in the cases where $G$ is a transitive graph of moderate growth and also when it is the hypercube.

preprint2016arXiv

Capacity of the range of random walk on $\mathbb{Z}^4$

We study the scaling limit of the capacity of the range of a simple random walk on the integer lattice in dimension four. We establish a strong law of large numbers and a central limit theorem with a non-gaussian limit. The asymptotic behaviour is analogous to that found by Le Gall in '86 for the volume of the range in dimension two.

preprint2016arXiv

Capacity of the range of random walk on $\mathbb{Z}^d$

We study the capacity of the range of a transient simple random walk on $\mathbb{Z}^d$ . Our main result is a central limit theorem for the capacity of the range for $d\ge 6$ . We present a few open questions in lower dimensions.

preprint2016arXiv

Sensitivity of mixing times in Eulerian digraphs

Let $X$ be a lazy random walk on a graph $G$ . If $G$ is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle $\mathbb{Z}_n$ shows. However, we establish that for Eulerian digraphs, the mixing time is $O(mn)$ , where $m$ is the number of edges and $n$ is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case.

preprint2015arXiv

Random walks colliding before getting trapped

Let $P$ be the transition matrix of a finite, irreducible and reversible Markov chain. We say the continuous time Markov chain $X$ has transition matrix $P$ and speed $λ$ if it jumps at rate $λ$ according to the matrix $P$ . Fix $λ_X,λ_Y,λ_Z\geq 0$ , then let $X,Y$ and $Z$ be independent Markov chains with transition matrix $P$ and speeds $λ_X,λ_Y$ and $λ_Z$ respectively, all started from the stationary distribution. What is the chance that $X$ and $Y$ meet before either of them collides with $Z$ ? For each choice of $λ_X,λ_Y$ and $λ_Z$ with $\max(λ_X,λ_Y)>0$ , we prove a lower bound for this probability which is uniform over all transitive, irreducible and reversible chains. In the case that $λ_X=λ_Y=1$ and $λ_Z=0$ we prove a strengthening of our main theorem using a martingale argument. We provide an example showing the transitivity assumption cannot be removed for general $λ_X,λ_Y$ and $λ_Z$ .

preprint2014arXiv

Intersection and mixing times for reversible chains

Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reversible and lazy chains that the total variation mixing time is always upper bounded by the expected intersection time taken over the worst starting states. For random walks on trees we show the two quantities are equivalent. We obtain an expression for the expected intersection time in terms of the eigenvalues for reversible and transitive chains. For such chains we also show that it is up to constants the geometric mean of n and E[I], where I is the number of intersections up to the uniform mixing time. Finally for random walks on regular graphs we obtain sharp inequalities that relate the expected intersection time to maximum hitting time and mixing time.

preprint2014arXiv

Martingale defocusing and transience of a self-interacting random walk

Suppose that $(X,Y,Z)$ is a random walk in $\mathbb{Z}^3$ that moves in the following way: on the first visit to a vertex only $Z$ changes by $\pm 1$ equally likely, while on later visits to the same vertex $(X,Y)$ performs a two-dimensional random walk step. We show that this walk is transient thus answering a question of Benjamini, Kozma and Schapira. One important ingredient of the proof is a dispersion result for martingales.

preprint2013arXiv

A permuted random walk exits faster

Let $σ$ be a permutation of $\{0,\ldots,n\}$ . We consider the Markov chain $X$ which jumps from $k\neq 0,n$ to $σ(k+1)$ or $σ(k-1)$ , equally likely. When $X$ is at 0 it jumps to either $σ(0)$ or $σ(1)$ equally likely, and when $X$ is at $n$ it jumps to either $σ(n)$ or $σ(n-1)$ , equally likely. We show that the identity permutation maximizes the expected hitting time of n, when the walk starts at 0. More generally, we prove that the hitting time of a random walk on a strongly connected $d$ -directed graph is maximized when the graph is the line $[0,n]\cap\Z$ with $d-2$ self-loops at every vertex and $d-1$ self-loops at 0 and $n$ .

preprint2013arXiv

Dimension of Fractional Brownian motion with variable drift

Let $X$ be a fractional Brownian motion in $\mathbb{R}^d$ . For any Borel function $f:[0,1] \to \mathbb{R}^d$ , we express the Hausdorff dimension of the image and the graph of $X+f$ in terms of $f$ . This is new even for the case of Brownian motion and continuous $f$ , where it was known that this dimension is almost surely constant. The expression involves an adaptation of the parabolic dimension previously used by Taylor and Watson to characterize polarity for the heat equation. In the case when the graph of $f$ is a self-affine McMullen-Bedford carpet, we obtain an explicit formula for the dimension of the graph of $X+f$ in terms of the generating pattern. In particular, we show that it can be strictly bigger than the maximum of the Hausdorff dimension of the graph of $f$ and that of $X$ . Despite the random perturbation, the Minkowski and Hausdorff dimension of the graph of $X+f$ can disagree.

preprint2013arXiv

Mixing times are hitting times of large sets

We consider irreducible reversible discrete time Markov chains on a finite state space. Mixing times and hitting times are fundamental parameters of the chain. We relate them by showing that the mixing time of the lazy chain is equivalent to the maximum over initial states x and large sets A of the hitting time of A starting from x. We also prove that the first time when averaging over two consecutive time steps is close to stationarity is equivalent to the mixing time of the lazy version of the chain.

preprint2013arXiv

Symmetric Rearrangements Around Infinity with Applications to Levy Processes

We prove a new rearrangement inequality for multiple integrals, which partly generalizes a result of Friedberg and Luttinger (1976) and can be interpreted as involving symmetric rearrangements of domains around infinity. As applications, we prove two comparison results for general Levy processes and their symmetric rearrangements. The first application concerns the survival probability of a point particle in a Poisson field of moving traps following independent Levy motions. We show that the survival probability can only increase if the point particle does not move, and the traps and the Levy motions are symmetrically rearranged. This essentially generalizes an isoperimetric inequality of Peres and Sousi (2011) for the Wiener sausage. In the second application, we show that the q-capacity of a Borel measurable set for a Levy process can only decrease if the set and the Levy process are symmetrically rearranged. This result generalizes an inequality obtained by Watanabe (1983) for symmetric Levy processes.

preprint2013arXiv

Total variation cutoff in a tree

We construct a family of trees on which a lazy simple random walk exhibits total variation cutoff. The main idea behind the construction is that hitting times of large sets should be concentrated around their means. For this sequence of trees we compute the mixing time, the relaxation time and the cutoff window.

preprint2013arXiv

Uniformity of the late points of random walk on Z_n^d for d >= 3

Suppose that $X$ is a simple random walk on $\Z_n^d$ for $d \geq 3$ and, for each $t$ , we let $\U(t)$ consist of those $x \in \Z_n^d$ which have not been visited by $X$ by time $t$ . Let $\tcov$ be the expected amount of time that it takes for $X$ to visit every site of $\Z_n^d$ . We show that there exists $0 < α_0(d) \leq α_1(d) < 1$ and a time $t_* = \tcov(1+o(1))$ as $n \to \infty$ such that the following is true. For $α> α_1(d)$ (resp.\ $α< α_0(d)$ ), the total variation distance between the law of $\U(αt_*)$ and the law of i.i.d.\ Bernoulli random variables indexed by $\Z_n^d$ with success probability~ $n^{-αd}$ tends to~ $0$ (resp.\ $1$ ) as $n \to \infty$ . Let $τ_α$ be the first time $t$ that $|\U(t)| = n^{d-αd}$. We also show that the total variation distance between the law of $\U(τ_α)$ and the law of a uniformly chosen set from $\Z_n^d$ with size $n^{d-αd}$ tends to $0$ (resp.\ $1$ ) for $α> α_1(d)$ (resp.\ $α< α_0(d)$ ) as $n \to \infty$ .

preprint2012arXiv

Hunter, Cauchy Rabbit, and Optimal Kakeya Sets

A planar set that contains a unit segment in every direction is called a Kakeya set. We relate these sets to a game of pursuit on a cycle $\Z_n$ . A hunter and a rabbit move on the nodes of $\Z_n$ without seeing each other. At each step, the hunter moves to a neighbouring vertex or stays in place, while the rabbit is free to jump to any node. Adler et al (2003) provide strategies for hunter and rabbit that are optimal up to constant factors and achieve probability of capture in the first $n$ steps of order $1/\log n$ . We show these strategies yield a Kakeya set consisting of $4n$ triangles with minimal area, (up to constant), namely $Θ(1/\log n)$ . As far as we know, this is the first non-iterative construction of a boundary-optimal Kakeya set. Considering the continuum analog of the game yields a construction of a random Kakeya set from two independent standard Brownian motions $\{B(s): s \ge 0\}$ and $\{W(s): s \ge 0\}$ . Let $τ_t:=\min\{s \ge 0: B(s)=t\}$ . Then $X_t=W(τ_t)$ is a Cauchy process, and $K:=\{(a,X_t+at) : a,t \in [0,1]\}$ is a Kakeya set of zero area. The area of the $ε$ -neighborhood of $K$ is as small as possible, i.e., almost surely of order $Θ(1/|\log ε|)$ .

preprint2012arXiv

Minkowski dimension of Brownian motion with drift

We study fractal properties of the image and the graph of Brownian motion in $\R^d$ with an arbitrary c{à}dl{à}g drift $f$ . We prove that the Minkowski (box) dimension of both the image and the graph of $B+f$ over $A\subseteq [0,1]$ are a.s.\ constants. We then show that for all $d\geq 1$ the Minkowski dimension of $(B+f)(A)$ is at least the maximum of the Minkowski dimension of $f(A)$ and that of $B(A)$ . We also prove analogous results for the graph. For linear Brownian motion, if the drift $f$ is continuous and $A=[0,1]$ , then the corresponding inequality for the graph is actually an equality.

preprint2012arXiv

Self-interacting random walks

Let $μ_1,... μ_k$ be $d$ -dimensional probability measures in $\R^d$ with mean 0. At each step we choose one of the measures based on the history of the process and take a step according to that measure. We give conditions for transience of such processes and also construct examples of recurrent processes of this type. In particular, in dimension 3 we give the complete picture: every walk generated by two measures is transient and there exists a recurrent walk generated by three measures.

preprint2012arXiv

The Isolation Time of Poisson Brownian Motions

Let the nodes of a Poisson point process move independently in $\R^d$ according to Brownian motions. We study the isolation time for a target particle that is placed at the origin, namely how long it takes until there is no node of the Poisson point process within distance $r$ of it. In the case when the target particle does not move, we obtain asymptotics for the tail {probability} which are tight up to constants in the exponent in dimension $d\geq 3$ and tight up to logarithmic factors in the exponent for dimensions $d=1,2$ . In the case when the target particle is allowed to move independently of the Poisson point process, we show that the best strategy for the target to avoid isolation is to stay put.

preprint2011arXiv

An isoperimetric inequality for the Wiener sausage

Let $(ξ(s))_{s\geq 0}$ be a standard Brownian motion in $d\geq 1$ dimensions and let $(D_s)_{s \geq 0}$ be a collection of open sets in $\R^d$ . For each $s$ , let $B_s$ be a ball centered at 0 with $\vol(B_s) = \vol(D_s)$. We show that $\E[\vol(\cup_{s \leq t}(ξ(s) + D_s))] \geq \E[\vol(\cup_{s \leq t}(ξ(s) + B_s))]$, for all $t$ . In particular, this implies that the expected volume of the Wiener sausage increases when a drift is added to the Brownian motion.

preprint2010arXiv

Brownian motion with variable drift: 0-1 laws, hitting probabilities and Hausdorff dimension

By the Cameron--Martin theorem, if a function $f$ is in the Dirichlet space $D$ , then $B+f$ has the same a.s. properties as standard Brownian motion, $B$ . In this paper we examine properties of $B+f$ when $f \notin D$ . We start by establishing a general 0-1 law, which in particular implies that for any fixed $f$ , the Hausdorff dimension of the image and the graph of $B+f$ are constants a.s. (This 0-1 law applies to any Lévy process.) Then we show that if the function $f$ is Hölder $(1/2)$ , then $B+f$ is intersection equivalent to $B$ . Moreover, $B+f$ has double points a.s. in dimensions $d\le 3$ , while in $d\ge 4$ it does not. We also give examples of functions which are Hölder with exponent less than $1/2$ , that yield double points in dimensions greater than 4. Finally, we show that for $d \ge 2$ , the Hausdorff dimension of the image of $B+f$ is a.s. at least the maximum of 2 and the dimension of the image of $f$ .

preprint2010arXiv

Collisions of Random Walks

A recurrent graph $G$ has the infinite collision property if two independent random walks on $G$ , started at the same point, collide infinitely often a.s. We give a simple criterion in terms of Green functions for a graph to have this property, and use it to prove that a critical Galton-Watson tree with finite variance conditioned to survive, the incipient infinite cluster in $\Z^d$ with $d \ge 19$ and the uniform spanning tree in $\Z^2$ all have the infinite collision property. For power-law combs and spherically symmetric trees, we determine precisely the phase boundary for the infinite collision property.

preprint2010arXiv

Mobile Geometric Graphs: Detection, Coverage and Percolation

We consider the following dynamic Boolean model introduced by van den Berg, Meester and White (1997). At time 0, let the nodes of the graph be a Poisson point process in R^d with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes if their distance is at most r. We study three features in this model: detection (the time until a target point---fixed or moving---is within distance r from some node of the graph), coverage (the time until all points inside a finite box are detected by the graph), and percolation (the time until a given node belongs to the infinite connected component of the graph). We obtain precise asymptotics for these features by combining ideas from stochastic geometry, coupling and multi-scale analysis.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Perla Sousi

Research overview

Is this your work?

23 publications

Chen--Stein Method for the Uncovered Set of Random Walk on $\mathbb Z_n^d$ for $d \ge 3$

Cutoff for Random Walk on Dynamical Erdős--Rényi Graph

A comparison principle for random walk on dynamical percolation

Capacity of the range of random walk on $\mathbb{Z}^4$

Capacity of the range of random walk on $\mathbb{Z}^d$

Sensitivity of mixing times in Eulerian digraphs

Random walks colliding before getting trapped

Intersection and mixing times for reversible chains

Martingale defocusing and transience of a self-interacting random walk

A permuted random walk exits faster

Dimension of Fractional Brownian motion with variable drift

Mixing times are hitting times of large sets

Symmetric Rearrangements Around Infinity with Applications to Levy Processes

Total variation cutoff in a tree

Uniformity of the late points of random walk on Z_n^d for d >= 3

Hunter, Cauchy Rabbit, and Optimal Kakeya Sets

Minkowski dimension of Brownian motion with drift

Self-interacting random walks

The Isolation Time of Poisson Brownian Motions

An isoperimetric inequality for the Wiener sausage

Brownian motion with variable drift: 0-1 laws, hitting probabilities and Hausdorff dimension

Collisions of Random Walks

Mobile Geometric Graphs: Detection, Coverage and Percolation

See the researcher in context

Building this map preview

Perla Sousi

Research overview

Is this your work?

23 publications

Chen--Stein Method for the Uncovered Set of Random Walk on Znd\mathbb Z_n^dZnd​ for d≥3d \ge 3d≥3

Cutoff for Random Walk on Dynamical Erdős--Rényi Graph

A comparison principle for random walk on dynamical percolation

Capacity of the range of random walk on Z4\mathbb{Z}^4Z4

Capacity of the range of random walk on Zd\mathbb{Z}^dZd

Sensitivity of mixing times in Eulerian digraphs

Random walks colliding before getting trapped

Intersection and mixing times for reversible chains

Martingale defocusing and transience of a self-interacting random walk

A permuted random walk exits faster

Dimension of Fractional Brownian motion with variable drift

Mixing times are hitting times of large sets

Symmetric Rearrangements Around Infinity with Applications to Levy Processes

Total variation cutoff in a tree

Uniformity of the late points of random walk on Z_n^d for d >= 3

Hunter, Cauchy Rabbit, and Optimal Kakeya Sets

Minkowski dimension of Brownian motion with drift

Self-interacting random walks

The Isolation Time of Poisson Brownian Motions

An isoperimetric inequality for the Wiener sausage

Brownian motion with variable drift: 0-1 laws, hitting probabilities and Hausdorff dimension

Collisions of Random Walks

Mobile Geometric Graphs: Detection, Coverage and Percolation

See the researcher in context

Building this map preview

Chen--Stein Method for the Uncovered Set of Random Walk on $\mathbb Z_n^d$ for $d \ge 3$

Capacity of the range of random walk on $\mathbb{Z}^4$

Capacity of the range of random walk on $\mathbb{Z}^d$