26 votes

A comprehensive list of random walk inequalities?

There I will list the inequalities and asymptotic theorems on random walks, that are currently known to me: Notation that will be used in the list: $\{X_n\}_{n = 1}^\infty$ are i.i.d. random variables....
Chain Markov's user avatar
  • 2,618
19 votes
Accepted

Does a random walk on a surface visit uniformly?

This problem was first considered and solved by Sunada, see his 1983 paper Mean-value theorems and ergodicity of certain geodesic random walks. Alas, the authors of the quoted arxiv paper were not ...
R W's user avatar
  • 16.6k
16 votes
Accepted

Optimal search puzzle

You can solve the problem via dynamic programming. For $n\in\{1,\dots,t\}$, let $V(n)$ be the minimum expected number of steps starting from $n$. Then $V(1)=0$ and otherwise $$V(n) = 1+\min\left(\...
RobPratt's user avatar
  • 5,159
16 votes

Optimal search puzzle

Because using the random operator destroys any potential gain from a previous subtraction, the optimal strategy must look like the one stated in the question. The solution of @RobPratt showed that ...
Karl Fabian's user avatar
  • 1,546
13 votes

A random walk on an infinite graph is recurrent iff ...?

This is a huge subject, but the best introductory reference remains: Doyle, Peter G.; Snell, J.Laurie, Random walks and electric networks, The Carus Mathematical Monographs, 22. Washington, D. C.: ...
Igor Rivin's user avatar
  • 95.6k
13 votes
Accepted

Random Walks on high dimensional spaces

Let $X_1,X_2,\dots$ be iid random vectors each uniformly distributed on $S^{d-1}$. Let $S_n:=\sum_1^n X_i$. By the symmetry, $EX_1=0$. Also, $1=|X_1|^2=\sum_{j=1}^d X_{1j}^2$, where $X_1=(X_{11},\dots,...
Iosif Pinelis's user avatar
12 votes
Accepted

The mean square distance of a random walk from the origin

Let us divide the (time) interval $[0,n]$ into $n/t$ subintervals of length $t$. Let us call the $k$th interval good, if, during that interval, the random walk spends time at least $t/5$ to the left ...
Serguei Popov's user avatar
12 votes

How many random walk steps until the path self-intersects?

Here are some computational insights. I ran $N = 10^k$ simulations for $3 \leq k \leq 12$. For $N = 10^9$ I recorded some explicit instances and recorded which pairs intersected, as opposed to just ...
Greg Hurst's user avatar
12 votes
Accepted

Expected number of games until bust

Let $x$ be the expected time to get to \$0, starting from \$1. What's the expected time to get to \$0, starting from \$2? It's $2x$. That's because to get from \$2 to \$0, we first need to get from \$...
James Martin's user avatar
  • 3,787
10 votes
Accepted

Random walk to stay in an interval forever

Yes. Indeed, if $s = \sum_{i \geq 1} t_i^2 <1$, then $$ \mathbb{P}[ \ \ \forall n, \sum_{i=1}^n X_i \in [-1,1] \ \ ] \geq 1-s > 0. $$ To see this, note that $M_n = |\sum_{i=1}^n X_i|$ is a ...
js21's user avatar
  • 7,199
10 votes
Accepted

Number of self avoiding paths on a grid graph?

UPD: the answer below is in fact completely wrong - it deals with counting walks $\gamma$ weighted by $\mu^{-\text{length}(\gamma)}$. It is clear that without restricting or penalizing for the lengths ...
Kostya_I's user avatar
  • 8,642
9 votes
Accepted

Growing a chain of unit-area triangles: Fills the plane?

Here is a sketch of the "cheapest" way I know how to prove something like that. Filling in the details may still be a bit lengthy but should be essentially routine. To set things up, let's write $X$ ...
Martin Hairer's user avatar
9 votes

Random walk on infinite graph

You haven't defined what "the lazy random walk" is. Since you refer to the vertex degrees, I presume that you mean that the transition probabilities are $$ p(x,y) = \begin{cases} \frac12 \;, ...
R W's user avatar
  • 16.6k
9 votes
Accepted

Average and max. hitting time to a specific vertex

Notation: Let $G=(V,E)$ be an undirected simple graph of $n$ nodes. If $\tau_x$ is the (random) time it takes the walk to reach the node $x$, then write $H(v,x)=E_v(\tau_x)$. Denote $H_{\max}(x):=\...
Yuval Peres's user avatar
8 votes

Is there a differentiable random walk?

Actually if all you are concerned with is the smoothness of the sample path, the smoothness of a Gaussian process is completely characterized by its covariance function. The following result provides ...
Henry.L's user avatar
  • 7,951
8 votes

Annihilating random walkers

With a "physicist approach", I would write down the following equation for $f(x,t)$ that should represent the "density" of walker around $x$ at time $t$: $$\partial_t f =\Delta f -\alpha f^2 +\delta_0 ...
RaphaelB4's user avatar
  • 4,296
8 votes

A comprehensive list of random walk inequalities?

This is a large subject, but the following books are an excellent starting point; each of them has been cited thousands of times. Chow, Yuan Shih, and Henry Teicher, 2012. Probability theory: ...
Yuval Peres's user avatar
8 votes

How long for Brownian motion to "fill-out" a torus in d-dimensions?

It looks like the $d$-dimensional case is easier generally than the $d=2$ case according to the excerpt below from this paper (see page three). ...the two-dimensional model is also more difficult ...
Josiah Park's user avatar
  • 3,177
8 votes
Accepted

How long for Brownian motion to "fill-out" a torus in d-dimensions?

A very general answer, in dimension $d\geq 3$, is in the following paper of Dembo, Peres and Rosen https://projecteuclid.org/euclid.ejp/1464037588: for compact $d$-dimensional manifolds, $$C_\...
ofer zeitouni's user avatar
8 votes
Accepted

Hitting probability of a line

As Timothy Budd has commented above, the limiting distribution is hyperbolic secant distribution. Here is a proof. By the reflection principle, the random walk in question can be substituted with one ...
sweehong's user avatar
  • 320
8 votes

Random pseudo-walk of Poisson variables

The situation given above is like a queueing process in discrete time with constant service time and Poissonian arrivals. Call $D_t$ the number of objects added between times $t+1$. Then $(N_t)_{t \ge ...
Christophe Leuridan's user avatar
7 votes
Accepted

Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4

For the record, this question is answered in a pair of papers: Gábor V. Nagy, A combinatorial proof of Shapiroʼs Catalan convolution, In Advances in Applied Mathematics, Volume 49, Issues 3–5, 2012, ...
Robin Houston's user avatar
7 votes
Accepted

How many times does a simple symmetric random walk of length n return to the origin?

All these questions are answered in paragraph 6 of Chapter III of Volume 1 of "An Introduction to Probability Theory and its Applications" by Feller. In particular: (1) $p=1/2$ is indeed the "right" ...
Serguei Popov's user avatar
7 votes

Random walk to stay in an interval forever

The crucial requirement is that $\sum_{i=0}^\infty t_i^2 < \infty$. See Kolmogorov's two-series theorem and also the more general Kolmogorov's three-series theorem.
Ori Gurel-Gurevich's user avatar
7 votes
Accepted

Spiral lattice random walk

It seems to me that this random walk is recurrent. Denote $Y_n=\|X_n\|$, where $(X_n, n\geq 0)$ is your "spiral" walk. Then, as $x\to \infty$, my calculations imply that $$ \mathbb{E}(Y_{n+1}-Y_n\mid ...
Serguei Popov's user avatar
7 votes

Particularities about the honeycomb lattice for the computation of connectivity constant

What fails for other lattices is that there seems to be no parafermionic observable with properties as nice as for hexagonal lattice; specifically, there is no analog of Lemma 1. In the definition of ...
Kostya_I's user avatar
  • 8,642
7 votes
Accepted

Random spanning trees probability problem

Here is a proof that the variance of $d_T(v)$ does not exceed $\frac14(\deg v-1)$. For every edge $e\in E$ take a variable $x_e$ and consider the polynomial $$P:=\sum_T \prod_{e\in T} x_e,$$ where the ...
Fedor Petrov's user avatar
7 votes

counting fixed-area closed walks on square 2d lattice

This is a difficult question, and the answer depends on what exactly do you want to know. If you want to know asymptotics for $A$ fixed, then the answer is known for $A=0$ and I would guess it's the ...
Igor Pak's user avatar
  • 16.3k
7 votes
Accepted

Diameter bound for graphs: spectral and random walk versions

The conjectured inequality is false in General. Proof: Let $\ell=\lfloor n^{1/2}/2 \rfloor$ and let $G_1,G_2,\dots,G_\ell$ be disjoint cliques of size $\ell$. Let $K$ be a clique on $n-\ell^2 >n/...
Yuval Peres's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible