28

Here is an argument that proves the conjecture. More generally, it shows that if $X_1,\dots,X_n$ is a "generic" sequence of positive real numbers, and we form a sum by permuting the terms randomly and putting random signs on the terms (uniform distribution over all possibilities), then the probability that all partial sums are positive is given by $P_n$ as ...

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

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 ...

18

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 ...

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 ...

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$.

15

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 ...

14

The fundamental result the completely characterizes recurrent/transient graphs is that a graph is recurrent if and only if the effective resistance of the graph, when considered as an electric network where every edge has resistance one, from some/any vertex to infinity is infinite. This is true also when the degrees are unbounded.
Of course, to use this, ...

answered Dec 13 '11 at 18:28

Ori Gurel-Gurevich

6,39111 gold badge2121 silver badges3636 bronze badges

13

The table in that Mathworld page suggests that $p(d) \rightarrow 0$ as $d \rightarrow \infty$.
That page also gives a formula for $p(d)$ in terms of a definite integral:
$$
p(d) = 1 - \left[ \int_0^\infty I_0(t/d)^d e^{-t} dt \right]^{-1},
$$
where $I_0$ is a "modified Bessel function" with power series
$$
I_0(x) = \sum_{n=0}^\infty \frac{(x/2)^{2n}}{n!^2}
= ...

answered Dec 13 '11 at 6:37

Noam D. Elkies

60.8k1111 gold badges210210 silver badges293293 bronze badges

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 ...

12

Here is a somewhat different way from Johan's of looking at this
problem. At each stage of the walk, choose a number $x$
uniformly from $[0,1]$ and then walk either a distance $x$ to the
right or $1-x$ to the left. This does not affect the probability
of becoming negative since there is still a uniform probability
of taking a step whose length belongs to ...

answered Apr 21 '12 at 17:40

Richard Stanley

34.3k99 gold badges121121 silver badges197197 bronze badges

12

This is not an answer, but rather an explanation of why this question is so difficult.
For positive coprime integers $a,q$, let
$$\pi(x;q,a) = \# \{p \leq x : p \equiv a \pmod{q}\}.$$
For $k \in \mathbb{Z}$, let
$$A_k = \{n \in \mathbb{N} : \pi(n;8,1) - \pi(n;8,5) = k\},$$
and let
$$B_k = \{\pi(n;8,3) - \pi(n;8,7) \in \mathbb{Z} : n \in A_k\}.$$
Then your ...

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

60.8k1111 gold badges210210 silver badges293293 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 ...

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

One quick remark: the result in Doyle and Snell cannot be sharp. Indeed, take any graph and on each vertex add a finite but huge (and larger and larger as you go away from a merked origin vertex) tree to the graph. Obviously this does not change the recurrent/transient nature of the graph, because a random walk will exit any finite trap like this in finite ...

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,39111 gold badge2121 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

For the case $N=3$, this is the random walk on the honeycomb lattice:
(source)
Lemma 2.1 in this paper computes the number of walks of length $2n$ on
the honeycomb lattice
which return to the origin,
so $$g_3(t)=\sum_{n=0}^{\infty}\sum_{k=0}^n \binom{2k}{k}\binom{n}{k}^2 t^{2n}.$$

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 ...

8

At the intuitive level, it would seem that the process should behave as if it had finite memory, and be diffusive in the long term: as soon as $p>0$ I would expect a central limit theorem. Of course the variance of the limit should depend on the value of $p$ and be smaller and smaller as $p\to0$. Now proving that is another story, and questions of that ...

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

#### Related Tags

random-walks × 346pr.probability × 238

stochastic-processes × 68

markov-chains × 44

reference-request × 43

co.combinatorics × 42

graph-theory × 40

gr.group-theory × 24

probability-distributions × 23

geometric-group-theory × 15

st.statistics × 14

brownian-motion × 14

discrete-geometry × 13

mg.metric-geometry × 10

ds.dynamical-systems × 10

ergodic-theory × 7

random-graphs × 7

algorithms × 6

martingales × 6

lie-groups × 5

stochastic-calculus × 5

lattices × 5

stochastic-differential-equations × 5

fa.functional-analysis × 4

asymptotics × 4