Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
0 answers
129 views

Speed on recurrent graphs

Suppose that $G$ is a (locally finite) graph such that the simple random walk on $G$ is recurrent. Does this imply any upper bound on the speed $\mathbb{E}d(X_t,X_0)$ of such random walk?
Marcin Kotowski's user avatar
6 votes
2 answers
2k views

Random walk to stay in an interval forever

Consider a random walk on the real time, starting from $0$. But this time assume that we can decide, for each step $i$, a step size $t_i>0$ to the left or the right with equal probabilities. To ...
maomao's user avatar
  • 492
6 votes
2 answers
234 views

Recurrence of Poisson binomial distributed random walk

Let $X_n$ be the outcome of a Bernoulli trial where the probability of getting 1 is $p_n$ and the probability of getting 0 is $1-p_n$, and let $S_n = \sum_{i=1}^n \left(X_i - \textrm{E} X_i \right)$. ...
user45947's user avatar
  • 955
6 votes
3 answers
2k views

Number of self avoiding paths on a grid graph?

Let $G$ be an $n \times n$ grid graph. Is there anything known about the asymptotic growth rate of the number of self avoiding paths from $(0,0)$ to $(n,b)$ (from the lower left corner to some ...
Elle Najt's user avatar
  • 1,432
6 votes
2 answers
2k views

Distribution of $\max_{n \ge 0} S_n$, random walk

Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
Zhu's user avatar
  • 61
6 votes
3 answers
921 views

Probability that a self-avoiding walk on $\mathbb{Z}^3$ closes to a polygon

The probability that a random walk on $\mathbb{Z}^3$ returns to the origin is about 34%. This is (part of) Pólya's theorem. I have been looking for an analogous (numerical) result for the probability ...
Joseph O'Rourke's user avatar
6 votes
3 answers
404 views

Parameterized simple asymmetric random walk

Let $ t>0 $, and we look at the random walk $S_{n}=\sum_{i=1}^{n}X_{n}$ on $\mathbb{Z}$ with $S_0=0$ where $$ \mathbb{P}\left(X_{n}=1\right) =\frac{1}{2}\left(1+\frac{1}{n^{t}}\right) $$ $$ \...
Jeremiah's user avatar
6 votes
1 answer
427 views

Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
fawadria's user avatar
6 votes
1 answer
822 views

Random walk with positive uniformly distributed steps

Let $U_1,U_2,\ldots$ be iid random variables distributed uniformly on $[0,1]$. I am interested in the random walk $X_i = \sum_{j \leq i} U_j$. In particular, What is the expected number of points ...
Yuval Filmus's user avatar
  • 1,886
6 votes
2 answers
408 views

Random walk in a convex body or convex polytope

Let $\Delta$ be a convex body (i.e. a compact convex subset) or a convex polytope in $\mathbb{R}^n$. Let $x$ be a point inside $\Delta$ and consider a (uniform) random walk starting at $x$ inside $\...
Kiu's user avatar
  • 883
6 votes
2 answers
405 views

Nonmonotonicity of expected distance of a random walk

What's the simplest example of a reversible random walk $X_n$ on an infinite vertex-transitive graph such that the expected distance from the origin is not increasing, i.e. there exists $n$ such that: ...
Michal Kotowski's user avatar
6 votes
2 answers
419 views

Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The ...
Han Xiao's user avatar
  • 111
6 votes
1 answer
284 views

Random walk with decreasing steps

I have a random walk $$R(t)= \sum_{n<t} X_n,$$ with $X_n \sim U(-\tfrac{1}{n^\alpha}, \tfrac{1}{n^\alpha}),$ where $X_n$ are independant and $\alpha >0$. I think that someone must have studied ...
Sia-TeX's user avatar
  • 95
6 votes
1 answer
346 views

Random walks on infinite directed regular graphs

Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps). Assume that $\Gamma$ is bi-regular, that is ...
Joël's user avatar
  • 25.7k
6 votes
1 answer
208 views

Origin of the term "connective constant"

Let $G$ be a vertex-transitive locally finite graph and $c_n$ the number of self-avoiding walks in $G$ starting from some fixed vertex $v_0$. One can easily see that $c_{m+n} \leq c_m c_n$ and hence ...
Salini Mendisi's user avatar
6 votes
1 answer
225 views

Random walks: How many times does the largest component change?

My understanding is that for an unbiased random walk (starting at the origin) on $\mathbb R$ with $N$ steps that the expected number of sign changes is $O(\sqrt N)$. For a biased walk I believe the ...
Daron's user avatar
  • 1,761
6 votes
1 answer
145 views

Uniform upper bounds for the return probability of random walks on $ \mathbb{R}$

Let $\mu$ be a probability measure with finite support on integers or the real line with the property that $\mu( 0) \le p$ for a fixed $0<p <1$. Let $S_n$ denote the random walk starting at $0$,...
Keivan Karai's user avatar
  • 6,064
6 votes
1 answer
542 views

Liouville property - a very basic question

Let $\mathbb{F}_2$ be the free group on two generators. By a result of Kaimanovich and Vershik, for each measure $\mu$ on $\mathbb{F}_2$ such that the support of $\mu$ generates $\mathbb{F}_2$, we ...
Kate Juschenko's user avatar
6 votes
1 answer
615 views

Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...
ARG's user avatar
  • 4,342
6 votes
1 answer
337 views

Probabilistic problem on random spanning trees

Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
Penelope Benenati's user avatar
6 votes
1 answer
169 views

Basic Definition and Notations in RWRE

From the definition of Zeitouni's lecture notes on RWRE: $(V, E)$ is a special graph, and $N_v:= \{k \in V: (v,k) \in E\}$ is the neighborhood of $v \in V$. $\Omega = \prod_{v \in V} M_1(N_v)$ ...
odakimki's user avatar
6 votes
1 answer
1k views

Properties of a finite random walk

Consider the simplest random walk - $X_0 = 0$ and from there on (i.i.d), $X_i=X_{i-1}+1$ with probability $p$ or $X_{i-1}-1$ otherwise. Let $Y_N$ be the highest point $X$ have reached on the first $N$...
R B's user avatar
  • 608
6 votes
2 answers
607 views

Optimally directing switches for a random walk

If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want? Formal statement More specifically, ...
aorq's user avatar
  • 4,934
6 votes
2 answers
477 views

Tail sigma-algebra of a branching random walk

I am looking for any known results about the tail sigma-algebra of a branching random walk. To be specific, let $T$ be the nodes of an infinite binary tree rooted at $r \in T$. Let $\{X_t\})_{t \in T}$...
Vladimir's user avatar
  • 1,210
6 votes
0 answers
190 views

Random Up-walk on Young's Lattice

Starting from the empty partition, $\varnothing$, follow a random up-walk of length $n$ on Young's Lattice, where an edge's transition probability is 1/updegree. For a particular partition, $\lambda$, ...
Math Helper's user avatar
6 votes
0 answers
180 views

Distribution of the stopping time of an autoregressive sequence

Consider $e_t$ being i.i.d. uniformly chosen from $\pm 1$. Let $\eta$ be a small positive constant. What is the distribution of $T$ such that $\eta^{0.5} (1+\eta)^T W_T$ first hits $\pm 1$, in which $$...
Minkov's user avatar
  • 1,117
6 votes
0 answers
460 views

Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
Jeff Burdges's user avatar
5 votes
3 answers
552 views

Winning game probability

At each round of a game with two players Alice and Bob, Alice can win with a fixed probability $a$ and Bob can win a fixed probability $b$, such that $a+b < 1$, otherwise there is a draw. The game ...
heartwork's user avatar
  • 385
5 votes
1 answer
681 views

Harmonic Crystal using Random Walk

Me and my advisor were looking for a specific proof of the disorder in $2d$ harmonic crystals. We could not find a paper or a textbook with it, so I thought trying my luck here. Basically, it is a ...
Amir Sagiv's user avatar
  • 3,544
5 votes
5 answers
901 views

Spectrum of transition matrix for symmetric random walk

I asked this question previously on math.stackexchange.com, where it had little traction. Consider the symmetric random walk on $\{0,1,…,n\}$ with transition probabilities $P(j→j±1)=1/2$ for $0 &...
Hans Engler's user avatar
5 votes
1 answer
6k views

Expected Hitting Time for Simple Random Walk from origin to point (x,y) in 2D-Integer-Grid

Consider a simple random walk on the lattice $\mathbb Z^2$ starting at the origin $(0,0)$ where in each step, one of the four adjacent vertices in chosen uniformly at random, i.e. with probability $1/...
carnage's user avatar
  • 53
5 votes
2 answers
907 views

Methods to approximate the betweenness centrality on large networks

To calculate the between centrality wiki def: $g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$ of a node in a graph/network;$\sigma_{st}$ is the ...
Vass's user avatar
  • 197
5 votes
2 answers
237 views

A follow up question to: Number of walks on integer lattice with self-edge at zero

Let $a(n)$ be the number of lattice paths in ${\mathbb{Z}^2}$ of length $n$ which start at the origin $(0,0)$ and end up at $(n,0)$ and have only up-steps $U:(i,j) \to (i + 1,j + 1)$, down-steps $D:(...
Johann Cigler's user avatar
5 votes
2 answers
804 views

Random walk by simplex vertices

I apologize if this question is well-known, but I was unable to find it mentioned anywhere. There exists a bug which moves around in $r$-space. The bug begins at the origin of this $r$-space. If the ...
Dylan Pizzo's user avatar
5 votes
1 answer
737 views

Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...
ARG's user avatar
  • 4,342
5 votes
2 answers
999 views

Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in $\lbrace -1, \frac{1-p}{p} \...
Ewan Delanoy's user avatar
5 votes
2 answers
333 views

Is random walk drift rational?

(Question mildly edited for clarity by request of Matt F.) If $G$ is a finitely presented group, let $|\cdot|$ denote the word metric with respect to a finite set of generators. Suppose $\nu$ is a ...
Anthony Quas's user avatar
  • 22.5k
5 votes
4 answers
362 views

Concentration of closed random walks

Consider a random walk $S_n=\sum_{i=1}^n X_i$ where $P(X_i=+1)=P(X_i=-1)=1/2$ with $n$ large. By Chernoff's bound we know that, for example, $\sum_{i=1}^{n/2} X_i=O(\sqrt{n})$ with high probability. ...
Sam Spiro's user avatar
  • 470
5 votes
2 answers
344 views

Divergence of Green function of random walks at spectral radius

Let $P=(p(x,y))_{x, y\in N}$ be the transition matrix over countable states $N$. Consider the generating Green function $G(x, y|t)=\sum_{0}^{\infty} p^n(x, y) t^n$, where $p^n(x,y)$ is the $(x,y)$-...
stephen's user avatar
  • 609
5 votes
1 answer
1k views

Self Avoiding Walk Enumerations

Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...
Alex R.'s user avatar
  • 4,902
5 votes
1 answer
263 views

Random walk with continuously distributed steps on [-1,1]

A simple random walk $S_n = X_1 +\cdots +X_n$, where $P(X_i = 1) = p \not = 0.5$ and $P(X_i=-1)= q \triangleq 1-p$, admits the following probability $$P(S_n \textrm{ reaches } a \textrm{ before} -b) =...
mikew's user avatar
  • 108
5 votes
1 answer
212 views

Second Skorokhod embedding in high dimensions

The first Skorokhod embedding theorem says that any random variable $X$ with $\mathbb E X=0$ and $\mathbb E X^2<\infty $ can be written as $X=B_{\tau }$ where $B$ is a Brownian motion and $\tau$ is ...
Dor's user avatar
  • 723
5 votes
1 answer
300 views

Random walk on $\mathbb{Z}^2$ going forward with probability $p$

Consider a random walk on $\mathbb{Z}^2$ which goes forward (i.e. takes a step in the same direction as the last step) with probability $p$ and turns right and left with probability $\frac{1-p}{2}$ ...
Frederik Ravn Klausen's user avatar
5 votes
1 answer
111 views

Expected time of distinguishability of a series of Poisson processes bounded by each other

Consider a system of $n$ "bounded" Poisson processes over the integers, $X_1, \ldots X_n$, all incrementing at rate $\lambda$. Initially all the processes begin at $0$. The process $X_i$ is inactive ...
aellab's user avatar
  • 133
5 votes
1 answer
2k views

Stopping time of two dimensional random walk

Let $U_n=\sum_{i=1}^n X_i,V_n=\sum_{i=1}^n Y_i$, $n\geq 1$, be a two-dimensional random walk with i.i.d. increments $(X_n, Y_n)$, where $X_n, Y_n$ are discrete random variables with joint pmf $P_{X,Y}$...
Kasper's user avatar
  • 93
5 votes
1 answer
105 views

Asymptotic expansion for the number of self-avoiding random walks

This question is cross-posted from https://math.stackexchange.com/questions/4580314/asymptotic-expansion-for-the-number-of-self-avoiding-random-walks. Let $c_n$ be the number of self-avoiding random ...
Testcase's user avatar
  • 541
5 votes
1 answer
239 views

What is the pdf of Laplace distribution conditioned on a plane? How can I sample from it?

Our goal is to sample from the Laplace distribution conditioned on a linear subspace. Here are the details of this problem. Let $$p(x) \propto \exp(-\|x\|_1/\sigma)$$ be the pdf of the Laplace ...
BOYI's user avatar
  • 53
5 votes
2 answers
347 views

A coupon collector-ish question

Imagine we are in the coupon collector setting: every time step we get independently one coupon out of $n$ coupons uniformly at random. However, unlike the coupon collector problem, we stop the at the ...
DeepC's user avatar
  • 63
5 votes
1 answer
283 views

Random walk on the hypercube with deleted edges

Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a ...
RandomWalker's user avatar
5 votes
1 answer
509 views

Scaling of First-passage times for Random Walk on integer lattices

Consider simple symmetric random walk $S_{n} = (S_{n}^{(1)},\dots, S_{n}^{(d)})$ on the d-dimensional integer lattice with starting point the origin. Let $\tau_{N}$ be the first time $S_{n}$ exits ...
John Lotos's user avatar

1 2
3
4 5
11