The random-walk tag has no usage guidance.

**2**

votes

**2**answers

123 views

### Bound that random walk stays within with constant probability?

For one-dimensional random walk, it is well-known that if the walk goes for $n$ steps, with constant probability it ends within $\pm\sqrt{n}$.
What is the bound, in terms of $n$, such that if the ...

**1**

vote

**1**answer

108 views

### Two types of random walkers on square lattice

Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index ...

**1**

vote

**2**answers

66 views

### Position likelihood in a 2D graph [closed]

I am looking for general principles or specific answers to this generic example.
Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...

**7**

votes

**2**answers

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

**5**

votes

**2**answers

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

**0**

votes

**1**answer

97 views

### Discrete random walk with uniformly distributed transition p, set initially

I've been working on a discrete version of the "unreliable friend" distribution. It would seem that what I've come up with is equivalent to the following random walk:
Choose $p$ from $U(0,1)$
Start ...

**4**

votes

**3**answers

256 views

### Maximum difference between heads and tails in absolute value

I toss a fair coin $n$ times. Some notation:
$S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$.
$M_n=\max(S_1,S_2,\dots,S_n)$,
...

**1**

vote

**1**answer

114 views

### A deterministic and explicitly described walk which is like random ones

Consider a sequence $(X_i)_{i = 1}^{\infty}$ which every $X_i$ is $-1$, $0$ or $+1$ and lets define $Y_n = X_1+ \cdots + X_n$. We say the sequence $(X_i)_{i = 1}^{\infty}$ a Good Sequence if $Y_n \neq ...

**9**

votes

**1**answer

327 views

### Lattice random walk under gravity

Suppose a random walk on $\mathbb{Z}^2$ takes a step left or right with
probability $\frac{1}{4}$, but up with probability $\frac{1}{2} p$
and down with probability $\frac{1}{2} (1-p)$, where $p \in ...

**3**

votes

**0**answers

62 views

### Is the family of probabilities generated by a random walk on a finitely generated amenable group asymptotically invariant?

Is the family of probabilities $\mu^n$ (convolution) generated by a random walk $\mu$ on a finitely generated amenable group $G$ asymptotically invariant ($\|g\mu^n-\mu\|_{L^1}\to 0$ for any $g\in ...

**2**

votes

**1**answer

153 views

### Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...

**3**

votes

**0**answers

158 views

### Uniform sub-linearity of sub-additive functions on groups

Suppose $G$ is a finitely generated group and suppose $f: G \to \mathbb{R}$ is subadditive function, that is: $f(g_1\circ g_2) \leq f(g_1) + f(g_2)$. One example of such $f$ is the word length in some ...

**2**

votes

**1**answer

68 views

### More precise statement about lower bounds on the cover time of general graphs

Uriel Feige has shown in 1995 in his paper "A Tight Lower Bound on the Cover Time for Random Walks on Graphs", the following result:
For any graph $G$ on $n$ vertices, and any starting vertex $u$ ...

**0**

votes

**0**answers

66 views

### Markov chains on a polyhedron

A modification of a question from Gerard Letac (1976): A m-sided q-adjacent-faced polyhedron has one of its faces "up." Each round, the polyhedron rolls so that any of the adjacent faces is now up. ...

**2**

votes

**0**answers

42 views

### probabilistic interpretation of a finite difference scheme

Let me start with some simple background.
Consider the heat equation :
$
\frac{\partial p}{ \partial t} = \frac{1}{2} \frac{\partial^2 p}{\partial y^2} \quad \mbox{in} \quad \mathbb{R}\times ...

**1**

vote

**1**answer

158 views

### Arc Sine law for Random Walk conditioned to non-absorption or not?

Let $S_n$ be simple symmetric Random walk on the integers in $[-N,N]$ with states $N$ and $-N$ absorbing. Let $\tau$ be the time to absorption when $S_0 = 0$.
Is the $E(S^{2}_{n}| \tau \geq n)$ ...

**1**

vote

**0**answers

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

**2**

votes

**1**answer

166 views

### Random walk on a sphere along latitude-longitude grid

Suppose a sphere is partitioned by a latitude-longitude grid, with
grid quadrilaterals $\Delta \times \Delta$.
All grid nodes have degree $4$, while the North & South poles have
degree $2 \pi / ...

**1**

vote

**0**answers

105 views

### Horizontal vs Vertical sides Exit from a Rectangle for simple symmetric Random Walk on $\textbf{Z}^{2}$

Consider simple symmetric random walk, $X_{n} = (X_{n}^{(1)}, X_{n}^{(2)})$ with $X_0= (0,0)$, on the 2 dimensional integer lattice, $\textbf{Z}^{2}$.
Let $T_{M}, T_{N}$ be the smallest $n$ such ...

**4**

votes

**2**answers

222 views

### First collision time of $n$ random walkers on a cycle

My question is somehow related to the one here First Collision Time for k Random Walkers on a Torus but, unfortunately, the answer does not cover my concern.
My problem is: consider $n$ walkers on ...

**3**

votes

**1**answer

120 views

### General ballot theorem

I am looking for a version of the Ballot Theorem for general step distributions. Specifically, let $X_1,X_2,\ldots$ be i.i.d. real random variables with some distribution. Let $S_n = S_1 + \cdots + ...

**6**

votes

**2**answers

233 views

### A variant of random walk

Standard random walk assumes a sequence of iid RVs $\{X_i\}_{i\geq 0}$ and studied the distribution of $S_n=\sum_{i=0}^n X_i$.
Here, I am wondering whether there is some work on
$T_n=\sum_{i=0}^n ...

**10**

votes

**0**answers

171 views

### Self-avoiding random walks that always turn

I am wondering if the statistics of self-avoiding random lattice-walks
on $\mathbb{Z}^2$
that turn left or right at each step (i.e., they cannot continue the
direction of the preceding step) have been ...

**2**

votes

**1**answer

206 views

### Hitting probabilities for conditioned oriented random walk monotonic?

Consider an oriented random walk on $\mathbb Z^2$ (i.e. only steps $\rightarrow$ and $\uparrow$ with equal probability.) Say we let the walk go $2m$ steps then start guessing sites at distance $2m$ ...

**6**

votes

**2**answers

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

**19**

votes

**0**answers

526 views

### Time for Langton's ant to cover a “square” torus

Langton's ant is a cellular automaton running as follows:
Squares on a plane are colored variously either black or white. We
arbitrarily identify one square as the "ant". The ant can travel ...

**9**

votes

**5**answers

824 views

### Combinatorial\Probabilistic Proof of Stirling's Approximation

Stirling's approximation is the following well-known asymptotic result:
$$n! \approx \left(\frac{n}{e}\right)^n \sqrt{2 \pi n}$$
This result has several analytical proofs, for example via Laplace's ...

**14**

votes

**1**answer

789 views

### In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?

This question is a variation of the return to the origin problem.
Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = ...

**1**

vote

**1**answer

325 views

### The probability that a 2d continuous time random walk avoids the origin

I am trying to find a reference of a proof of a continuous time version of a result of Dvoretzky and Erdos from their paper "Some problems on random walk in space" that says the probability ...

**0**

votes

**1**answer

74 views

### Stationary distribution of random walk alias solving uncountably many linear equations [closed]

Let us have interval $I = (i_1,i_2)$, function $f_1 : I \mapsto I$, function $f_2 : I \mapsto I$.
Let $x_0$, $x_1$, $x_2$, ... be series of random variables from interval $I$ denoting random walk. ...

**7**

votes

**0**answers

182 views

### Asymmetric random walk on the line with barriers

The most commonly considered random walk on the line takes one step left or right with equal probability until a barrier is reached (if there are any barriers).
More generally, suppose we fix any ...

**0**

votes

**1**answer

266 views

### Integration of independent Brownian motions

I am wondering if the following integral of stochastic Brownian motions has an analytical solution?
$$
\int_{0}^{t}e^{\nu \tilde{V}_{\tau} - \frac{1}{2}\nu^{2}\tau}d\tilde{W}_{\tau}
$$
where ...

**0**

votes

**1**answer

105 views

### Do constrained random walks converge weakly to the Wiener measure on the space of constrained paths (that corresponds to the heat equation)?

Let $U$ be an open subset of $\mathbb{R}^n$ such that
$\partial \overline{U}$, the boundary of $\overline{U}$ is ''nice''
(for simplicity you can assume piecewise smooth). I also want to allow the ...

**2**

votes

**1**answer

148 views

### Maximizer of random walk with very small drift

This is an extended question based on
Large deviations for maximizer of random walk with drift.
Let $$S_k = X_1 + \ldots + X_k,$$ where $X_i$ are i.i.d. with mean $-\mu < 0$ and unit variance. ...

**5**

votes

**1**answer

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

**1**

vote

**1**answer

128 views

### Large deviations for maximizer of random walk with drift

Is it easy to write down the large deviations rate for the maximizer of a random walk with negative drift?
Let $X_i$ be the (iid, mean $-\mu$, variance $\sigma$, arbitrarily nice tails) jumps of a ...

**6**

votes

**3**answers

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

**1**

vote

**2**answers

172 views

### Speed and absence of non-constant bounded harmonic functions

For a (symmetric) random walks on countable groups generated by $\mu$, there is a "brute-force computation" argument of Avez (1974) that shows that if the entropy $h_\mu$ is trivial then there are no ...

**5**

votes

**1**answer

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

**2**

votes

**1**answer

215 views

### Random walks with exponential decreasing steps

Let $g$ be the golden number (or another algebraic integer in $(0,1)$ that fullfills an equation with coefficients $\pm 1$). Consider the random walk on $\mathbb{R}$ starting with $0$ and walking ...

**2**

votes

**0**answers

65 views

### Controlling fluctuations in a Markov chain

For $N>0$, consider the Markov chain $x_n$ on $\{0,1/N,...,1\}$ that moves up by $1/N$ at rate $(c-x_n/2)N$ and down by $1/N$ at rate $(c+x_n/2)N$. As $N\rightarrow\infty$ sample paths approach ...

**1**

vote

**0**answers

35 views

### Is there an effective algorithm for finding “minimal discovery times” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it.
Define the discovery time as the expected time to first reach a vertex by
random walk from a uniform start. Are there ...

**3**

votes

**0**answers

90 views

### hitting time of the first quadrant for a 2-d random walk

Suppose $(S_n)_{n=1}^{\infty}$ is a simple random walk in $\mathbb{R}^2$. Let $\tau_{(a,b)}$ be the hitting of the first quadrant when $S_0 = (a,b)$. Is there a way to compute or estimate the ...

**10**

votes

**3**answers

575 views

### Square filling self avoiding walk

I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and ...

**2**

votes

**2**answers

251 views

### Distribution of a random walk on a directed line

Is there a closed formula for the distribution of $x_t$ in the following random process, describing a random walk on a directed line?
$x_0 = n$
$x_t$ is a uniformly random integer between 1 and ...

**10**

votes

**1**answer

287 views

### Trapping a particle

A particle starts a brownian walk in the middle of a long tunnel in the plane, at one end of the tunnel is a region Y of given area A.
Does the shape of region Y affect average time for the particle ...

**1**

vote

**1**answer

349 views

### Brownian motion of every point in the plane

Suppose every point in the plane undergoes brownian motion for a time t. What is the probability n particles ended up at 0? For n finite, countable or uncountable?
What proportion of the plane does ...

**4**

votes

**0**answers

215 views

### Why is the density function of a sum of many iid random variables (i.e., the Gaussian) self-dual?

In the usual proof of the central limit theorem via characteristic functions, we note that if $X_1, \dots, X_n$ are independent and identically distributed, with probability density function $f(x)$, ...

**1**

vote

**1**answer

114 views

### N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...

**17**

votes

**1**answer

506 views

### Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...