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....
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 ...
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(\...
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 ...
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.: ...
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,...
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 ...
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 ...
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 \$...
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 ...
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 ...
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$ ...
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 \;, ...
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):=\...
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 ...
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 ...
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: ...
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 ...
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_\...
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 ...
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 ...
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, ...
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" ...
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.
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 ...
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 ...
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 ...
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 ...
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/...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
random-walks × 511pr.probability × 355
stochastic-processes × 121
reference-request × 65
co.combinatorics × 61
markov-chains × 60
graph-theory × 59
probability-distributions × 38
gr.group-theory × 26
brownian-motion × 26
st.statistics × 18
geometric-group-theory × 18
discrete-geometry × 14
ds.dynamical-systems × 13
random-graphs × 12
mg.metric-geometry × 11
ergodic-theory × 10
martingales × 10
asymptotics × 9
random-matrices × 9
linear-algebra × 7
algorithms × 7
stochastic-differential-equations × 7
spectral-graph-theory × 7
trees × 7