26

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.
$\{S_n\}$ is the random walk ($S_n = \Sigma_{k = 1}^n X_k$)
$\nu(t) = \max\{n \in \mathbb{N}_0 | S_n < t \}$ - the corresponding renewal process (well ...

24

The quantity $R_n$ is asymptotic to ${4\over \pi}(n\log n)^2$, see "Cover times for Brownian motion and random walks in two dimensions" by Dembo, Peres, Rosen and Zeitouni. This was previously conjectured by Aldous.

20

Let $E_n$ denote the probability of the first return after $n$ steps, and let $P_n$ denote the probability of return after $n$ steps (but not necessarily the first return). Note that $E_n=P_n=0$ if $n$ is odd.
We are interested in $E= E(p)= \sum_{n=1}^{\infty} E_n$. Now note that for $n\ge 1$
$$
P_n = E_n + \sum_{k=1}^{n-1} E_k P_{n-k},
$$
from ...

19

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 aware of this. Any assumptions on curvature and dimension are not necessary - it is just enough to assume that the manifold is compact. As it has been pointed out ...

17

The position of the dog relative to the human is a Markov chain, which is symmetric by inspection (there are three cases to consider: interior squares, "edge squares," and "corner squares"). This Markov chain splits up into two irreducible ergodic components corresponding to even and odd squares. Finally, any symmetric, irreducible, ergodic Markov chain has ...

16

I'll expand a bit on my comment. There are $n^2$ $3 \times 3$ tiles. From each, there are two directions you can follow the path. As you move along the path in one direction, you hit a new tile, a previously visited tile, or the edge of the region. The path only gets longer if it encounters a new tile and the tile has one of the patterns connecting it to ...

15

Presumably (though I don't have references handy) the behaviour of a quasiregular tiling in ${\mathbb Z}^d$ is essentially the same as that of ${\mathbb Z}^d$ itself. Essentially this should depend on the fact that the number of sites within $r$ steps of your starting point grows as $r^d$.

13

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,X_{1d})$. Since the $X_{1j}$'s are exchangeable and $1=E|X_1|^2=\sum_{j=1}^d EX_{1j}^2$, we conclude that $EX_{1j}^2=\frac1d$ for all $j$. Also, for any ...

answered Jan 11 '19 at 13:45

Iosif Pinelis

62.6k44 gold badges6060 silver badges117117 bronze badges

12

Suppose the particles start at integers $x,y,z$ with $x \leq y \leq z$
and $x \equiv y \equiv z \bmod 2$ (so they can actually hit rather than
pass through each other). Then if I did this right the expected
hitting time $f(x,y,z)$ is given simply by
$$
f(x,y,z) = (z-y) (y-x).
$$
For example, for $(x,y,z) = (-10,0,10)$ the expected stopping time
is exactly $...

answered Feb 3 '14 at 6:35

Noam D. Elkies

69.1k1212 gold badges247247 silver badges331331 bronze badges

12

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 of $x_k-\sqrt{t}$ and at least $t/5$ to the right of $x_k+\sqrt{t}$ (here, $x_k=X_{kn/t}$ is the position of the walk in the beginning of the $k$th time interval)...

12

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.: The Mathematical Association of America. Distr. by John Wiley & Sons, New York etc. XIII, 159 p. £ 22.00 (1984). ZBL0583.60065.
They present quite a few ...

answered Oct 22 '17 at 16:02

Igor Rivin

92.8k1111 gold badges134134 silver badges329329 bronze badges

12

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 the lengths. For all other runs, I simply summed the results.
First and foremost here's a summary of the runs:
$$
\begin{array}{ |l|l|l|l| }
\hline
N & \...

11

The special case when the $X_i$'s are +1 or -1 with equal probabilities is called Bernoulli Convolution, see the nice survey by Peres, Schlag and Solomyak: SIXTY YEARS OF BERNOULLI CONVOLUTIONS.

answered Apr 18 '15 at 12:59

Ori Gurel-Gurevich

6,53111 gold badge2222 silver badges3636 bronze badges

10

The answer is the same for random walks and for Brownian motion.
If you project a $3$-dimensional Brownian motion perpendicular to $x=y=z$, you get a $2$-dimensional Brownian motion. The projection of the set where $x\lt y\lt z$ is a wedge of angle $\frac{\pi}{3}$. Your question is whether the first exit time from a $\frac{\pi}{3}$ wedge has finite expected ...

10

If you want to derive the Functional CLT for this process from Donsker's theorem, you have to add a couple of small ingredients.
Donsker's applies to random walks with i.i.d. steps. Yours is not quite of that kind. Two consecutive steps are not i.i.d: (i)one imposes a direction restriction on another; (ii) also if you color the vertices of the lattice in ...

10

The object you look at is called the Gaussian Free Field (on your graph, with zero boundary
conditions) in dimension $2$. There is a lot known about it. For some pointers see the Wiki page
http://en.wikipedia.org/wiki/Gaussian_free_field, my lecture notes
http://www.wisdom.weizmann.ac.il/~zeitouni/notesGauss.pdf and Sznitman's lecture notes
https://www....

10

According to the general theory any irreducible finite state space Markov chain has a unique stationary measure, and the empirical frequencies along a.e. sample path converge to this measure. The chain you consider is what is called the simple random walk on the constructed graph (the transition probabilities are equidistributed among neighbors), and its ...

10

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 nonnegative submartingale, so that Doob's martingale inequality yields
$$
\mathbb{P}[ \max_{1 \leq j \leq n} M_j > 1 ] \leq \mathbb{E}[M_n^2] = \sum_{i=1}^n t_i^...

9

Let $X_t$ be the number of points in $[0,t]$. Then, $X_t$ is a renewal process. Let $m(t) = E[X_t]$. Then renewal theorem says
$$
m(t+h) -m(t) \stackrel{t \to \infty}{\longrightarrow} \frac{h}{\mu}
$$
where $\mu = E[U_1]$ is the expected increment.
With $\mu = 1/2$ and $h = 1$ in this case, one gets $2$ for the limit.

9

The result is not true for a general sequence of probabilities $p_n$. For example, if $p_n=1/n^2$ then $\sum_n p_n <\infty$ and therefore by the Borel-Cantelli lemma, almost surely $X_k=0$ (and therefore $X_k-EX_k=-p_k$) for all but a finite number of $k$'s. In particular, $S_n$ will converge almost surely to some random limit so will not be recurrent.

9

This inequality cannot be true. Let us rewrite it in the more common form
$$P(R_n\ge x)\le e^{-x^2/2} \tag{1}
$$
for $x\ge0$, where $R_n:=S_n/b_n$, $S_n:=\sum_1^n c_iB_i$, $b_n:=\sqrt{\sum_1^n c_i^2}$.
Let $n=2$, $c_1=1$, and $c_2=aI\{B_1=-1\}$, where $I\{\cdot\}$ denotes the indicator function, $a>0$ is large enough so that $\frac{-1+a}{\sqrt{1+a^2}}&...

9

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 of the walks, the number of walks will grow exponentially with the volume (i. e., as $\eta^{N^2}$ for some $\eta>1$). In fact, in this paper it is shown ...

9

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$ for the space of oriented non-degenerate area $1$ triangles, so $\tau \in X$ is a pair $(v_1,v_2)$ with $v_i \in \mathbf{R}^2$ and $|v_1 \wedge v_2| = 2$. I then ...

9

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 \;, & \text{if}\; x=y \;,\\
\frac1{2\,\mathbf{deg}\,x } \;, & \text{if}\; x,y\;\text{are neighbours} \;.
\end{cases}
$$
What you are asking about is known ...

8

As Lucia pointed out in a comment, by solving the hitting probability recursions for the Markov chain, you get that the distribution of the maximum is geometric; for $k=0,1,2,\dots$,
$$
\mathbb{P}(M=k)=\left(\frac{p}{1-p}\right)^k\left(1-\frac{p}{1-p}\right),
$$
or equivalently
$$
\mathbb{P}(M\geq k)=\left(\frac{p}{1-p}\right)^k.
$$
There's actually a ...

8

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 an insight into this issue.
In this aspect we can discuss smoothness with probability one, and the sample path smoothness in this sense is relatively clear in ...

8

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 $$
with $\partial_t f =\Delta f+\delta_0$ is the diffusion equation with source at $0$ and $\alpha f^2$ the collisions term which is the density of two walker ...

8

We can get an upper bound of $15.52$ by considering just the cases of interesction of next-to-consecutive steps, which we call quick intersections.
Let $\alpha$ be the angle between step $AB$ and step $BC$, and let $u=\alpha/\pi$. So $u$ is (initially) uniformly distributed between $0$ and $1$. Then, as Gerhard Paseman and Bill Bradley determined, the ...

8

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: independence, interchangeability, martingales. Springer.
Petrov, V.V., (1976, 2012). Sums of independent random variables (Vol. 82). Springer
Ledoux, Michel, and ...

8

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 than its
higher-dimensional counterparts. This is because dimension two is critical for
the walk, resulting in strong correlations. To illustrate the ...

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

#### Related Tags

random-walks × 428pr.probability × 296

stochastic-processes × 88

reference-request × 55

co.combinatorics × 51

markov-chains × 49

graph-theory × 47

probability-distributions × 32

gr.group-theory × 24

brownian-motion × 21

st.statistics × 16

geometric-group-theory × 16

discrete-geometry × 13

ds.dynamical-systems × 12

mg.metric-geometry × 11

martingales × 10

ergodic-theory × 9

random-matrices × 8

random-graphs × 8

asymptotics × 7

algorithms × 6

stochastic-differential-equations × 6

spectral-graph-theory × 6

fa.functional-analysis × 5

linear-algebra × 5