The random-walk tag has no wiki summary.

**4**

votes

**1**answer

195 views

### Approximating a hitting time for some state using the stationary distribution?

Provided a random walk on a bounded interval, with step probabilities, $p$ and $q$ and a stationary distribution $\pi$, how "bad" of an approximation is to assume that the hitting time for a position ...

**2**

votes

**1**answer

277 views

### Manhattan distance vs. absorption time on an unbounded integer lattice

Imagine I have unbounded $d$-dimensional integer lattice where I take two vertices, $v_a$ and $v_b$, separated by a fixed Manhattan distance $L$, and I release a random walker at $v_a$ and allow for ...

**4**

votes

**5**answers

394 views

### Spectrum of transition matrix for symmetric random walk

I asked this question previously on math.stackexchange.com, where it had little traction.
Consider the symmetric random walk on $\{0,1,…,n\}$ with transition probabilities $P(j→j±1)=1/2$ for $0 ...

**2**

votes

**1**answer

257 views

### Probability that a “closable” self-avoiding random walk forms a polygon

Consider a self-avoiding random walk on an infinite graph (for concreteness, the grid of 2-dimensional lattice points $\mathbb{Z}^2$), in which on each step, the next position is chosen uniformly at ...

**11**

votes

**2**answers

671 views

### Random walks on Coxeter groups

Let $G_N$ be the group generated by elements $a_1,\ldots,a_N$ subject to the relations $a_i^2=1$ and $(a_ia_j)^3=1$. The growth function of $G_N$ is then
...

**2**

votes

**1**answer

1k views

### Expected Hitting Time for Simple Random Walk from origin to point (x,y) in 2D-Integer-Grid

Consider a simple random walk on the lattice $\mathbb Z^2$ starting at the origin $(0,0)$ where in each step, one of the four adjacent vertices in chosen uniformly at random, i.e. with probability ...

**9**

votes

**1**answer

338 views

### Elephant populations (and Dyck words)

Hello,
I'm relatively new to this forum so apologies if I have tagged my
question incorrectly.
I have been in contact with a wildlife biologist recently concerning
counting elephant populations and ...

**1**

vote

**1**answer

195 views

### Extending Wald's equation to two classes of i.d. random variables?

I try to adopt Wald's equation to a slightly more complex problem. In fact, after a full day, I found some solution now, but it has a confusing argument in the middle. Perhaps somebody can help me at ...

**7**

votes

**1**answer

720 views

### Generating function for Random Walk Hitting Time, taking the wrong root

In a calculation of the hitting time for a Bernoulli random walk we have to calculate the hitting time $\tau(1)=\inf\{n\ge 0:S_n=1\}$ to reach $+1$ and the generating function has the recursion ...

**8**

votes

**2**answers

389 views

### A discrete random walk that avoids previously visited vertices for an exponentially distributed time interval

Imagine a discrete random walk on an infinite one-dimensional lattice where, for every unit interval of time, $(t_1, t_2, ...)$, the walker takes a step with uniform probability to its left or right. ...

**4**

votes

**2**answers

256 views

### How does a quasi-isometry affect Poisson or Martin boundaries?

Take two graphs (of bounded valency) or manifolds (f bounded geometry) $G$ and $G'$. Assume there is a quasi-isometry $f:G \to G'$, and assume the Poisson or Martin boundary of $G$ is known, what may ...

**1**

vote

**1**answer

251 views

### The probability a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice takes more than $N$ steps before trapping itself

What is the probability that a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice is able to take more than $N$ steps, i.e. able to take more than $N$ steps before trapping itself ...

**5**

votes

**0**answers

139 views

### hitting time of a subset

Suppose you have the simple random walk on $L=\mathbb{Z}^n,$ and $A \subset L$ is a subset (in my case, the subset is a union of hyperplanes, so in particular infinite). There is a random variable ...

**5**

votes

**0**answers

611 views

### On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...

**10**

votes

**2**answers

531 views

### Markov chains: invariant measures and explosion

The following seems like such an elementary question, but I didn't get anywhere with it.
Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure ...

**1**

vote

**1**answer

172 views

### Distributions induced by (weighted) random walks on the integer lattice

Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...

**2**

votes

**1**answer

341 views

### MCMC with progressive demollification of delta distributions

Edit: I simplified the example to a canonical case for clarity.
Given an integral $\int_{\Omega}{g(\mathbf{x})}$ with a well-posed integrand $g(\mathbf{x})$ defined on some multidimensional space ...

**2**

votes

**2**answers

427 views

### Simple random walk on the 3-1 tree is recurrent

Hello guys,
There is an infinite tree structure named "the 3-1 tree", denoted by $T_{3-1}$. The tree is constructed as follows:
The origin vertex (which can be referred to as the zeroth level) has ...

**3**

votes

**1**answer

278 views

### Where does directed random walk hit the boundary of a region?

I have a problem that I more or less know the answer to (in an ad hoc way), but would really like to see it done in a systematic way. In spite of this, I will pose the question in quite a concrete ...

**4**

votes

**1**answer

218 views

### Probability of a topologically non-trivial random walk on a finte torus

Hi: this question is regarding the topological properties of random walks on a finite torus.
Consider an unbiased random walk on finite square lattice on a torus of linear dimension $L$. Place a ...

**2**

votes

**2**answers

206 views

### Probability of a Random Walk crossing an increasing function of the standard deviation

Let $(S_n)_{n=0}^{\infty}$ be a random walk with $S_n = \sum_{i=1}^n X_i$, and let the $X_i$ be distributed according to some (bounded) distribution function $F$ with mean $0$ and variance $1$, so ...

**1**

vote

**0**answers

166 views

### A random walk with uniformly distributed steps II

The problem is a improved version of this problem,
A random walk with uniformly distributed steps
Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will ...

**3**

votes

**1**answer

292 views

### Transience of self avoiding random walks on $\mathbb{Z}^d$

I'm finishing up a masters thesis in computer science and want to say a bit in the introduction about self-avoiding walks. My thesis looks at a random process which arose in computer science and my ...

**1**

vote

**2**answers

238 views

### Limit of a rescaled random sum of i.i.d. random variables

Consider a sequence of i.i.d. random variables $(X_i)_{i \in \mathbb N}$ and let $S_n=X_1+\dots+X_n$
For every $\alpha \in ]0,+\infty[$, let $N(\alpha)$ be a discrete random variable on $\mathbb N$, ...

**2**

votes

**1**answer

213 views

### Reference Request: Cover time for simple random walk on nxn torus

I'm putting the finishing touches on my masters thesis and need a reference for the following fact (which my advisor told me):
Let $G$ be the $n\times n$ grid and identify the sides to make it a ...

**20**

votes

**5**answers

2k views

### A random walk with uniformly distributed steps

The following problem has bothered me for a long time.
Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly in the ...

**2**

votes

**0**answers

173 views

### $n$-th return of a random walk on $\Bbb Z^d$

Lets define $f_n = P(X_n =0 , X_k \ne 0, k< n)$ the first return distribution of the random walk $X_n$ on $\mathbb{Z}^d$, and lets go ahead and assume that $f_n \approx n^{-(1+\alpha)}$ for some ...

**1**

vote

**2**answers

219 views

### Gibbs sampling step size

I have some data generated using MCMC methods and in particular Gibbs sampling. I computed the autocorrelation but I'm unsure how to determine how many samples to skip.
I'd like to determine that ...

**0**

votes

**0**answers

230 views

### Random Walk in $\mathbb{R}^n$

Have there been papers dealing with random walks in $\mathbb{R}^n$ that are not on the lattice $\mathbb{Z}^n$? Instead of walking in one of the directions possible in $\mathbb{Z}^n$ with probability ...

**8**

votes

**1**answer

233 views

### Mixing time of unitary Brownian motion

Let $B_t$ be the unitary Brownian motion, i.e. Brownian motion on the unitary group $U(N)$. What is known about the mixing time of $B_t$, that is, how fast does the measure $B_t(\delta_{\{Id\}})$ ...

**2**

votes

**1**answer

626 views

### first passage time, brownian motion

Hi,
If X(t) is Brownian motion in 2D, where X(0) = 0, then we can ask what is the expected time required to first hit a circle of radius R, centered at the origin. This is a First Passage Time ...

**9**

votes

**0**answers

629 views

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

Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of ...

**3**

votes

**1**answer

284 views

### Maximum vertical distance for a lattice path when NSEW steps are allowed

Suppose we have a lattice path in 2D starting at the origin, in which north, south, east, and west steps are allowed. For a given path $L$, let $\max(L)$ be the maximum value of the $y$ coordinate ...

**11**

votes

**5**answers

863 views

### Simple Random Walk on a Locally Finite Graph - when is it recurrent?

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...

**8**

votes

**1**answer

775 views

### Pólya's Random Walk Constants at infinity

Let be the probability that a random walk on a d-D lattice returns to the origin. In 1921, Pólya proved that $p(1)=p(2)=1$
but $p(d)<1$ for $d>2$.
...

**8**

votes

**2**answers

340 views

### Limit shape for fixed-perimeter lattice polygons

Let $P$ be a simple polygon defined by $n$ unit-length segments
connecting lattice points of $\mathbb{Z}^2$.
I have two operations that preserve the perimeter of $P$.
The first is the "pop" of a ...

**2**

votes

**2**answers

512 views

### probability distribution of hitting nodes on a finite graph random walk

Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an ...

**6**

votes

**2**answers

375 views

### Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,
$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
The ...

**4**

votes

**1**answer

346 views

### Decomposition of Haar measure other than Hurwitz's

Hurwitz defined a decomposition of the Haar measure on $SO(n)$ based on Given's rotation. So by left multiplication of Givens rotation one can always bring an orthogonal matrix into the identity. The ...

**3**

votes

**0**answers

164 views

### criterion for deciding whether the product of a sequence of Givens rotations can reach the full special orthogonal group

By Givens' rotation $R(1,2;\theta)$ I mean a matrix which has the
$$\begin{pmatrix} \hphantom{-}\cos \theta &\sin \theta \cr -\sin \theta & \cos \theta \end{pmatrix}$$
$2 \times 2$ block at ...

**-1**

votes

**1**answer

231 views

### Walks that cannot hit the boundary

I've casually proved, as application of some ideas that I am developing, a result that might be of interest in itself. I am completely new in this field and then I would like to ask your help to ...

**12**

votes

**2**answers

581 views

### What is the maximum diameter of $N$ steps of a random walk?

Since probability is quite far away from my daily buisiness, please forgive me if my use of terminology is wrong or the question is too trivial. However, I was not able to find the right keyword to ...

**5**

votes

**0**answers

228 views

### Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...

**1**

vote

**2**answers

728 views

### Probability of first return to starting vertex in Random walk on regular finite graph

Hi, this is related to this earlier question.
Given Random walk on a regular graph $G=(V,E)$. The Random walk is simple so that transition probabilities are $1/\text{deg}(v_i)$, and time is in ...

**1**

vote

**1**answer

324 views

### Comparing hitting probabilities for two different random walks

Let $p$ be a probability in $]0,1[$, and let $(X^p_i)_{i \geq 1}$ be a i.i.d. family
of variables with law $P(X=1)=p, P(X=-\frac{p}{1-p})=1-p$ (so that $E(X)=0$).
Set $S^p_n=\sum_{k=1}^{n} X^p_k$ for ...

**2**

votes

**3**answers

241 views

### How long does it take a Brownian particle to achieve a uniform probability distribution across a space?

Imagine I have a point-like Brownian particle, with diffusion constant $D$, and I place it at some initial coordinate in a cage of known geometry. Assuming the volume $V$ of the cage is "everywhere" ...

**4**

votes

**3**answers

385 views

### Averaging over random walk on binary lattice

I have a function $f$ defined over a bit vector of length $n$. Equivalently, this is a function defined on the set of integers $[0,\ldots,2^n-1]$. I would like to compute the mean or variance or some ...

**2**

votes

**0**answers

135 views

### Reference request for a result on subsets unlikely to be hit by random walks in a group

Suppose we are performing a random walk in a group. More precisely, we have a finite generating set $S$ of a group $G$ and the probability of walking along generator $s$ is given by $\mu(s)$ for some ...

**11**

votes

**1**answer

596 views

### How far can a particle travel from its origin if it exhibits self-avoiding Brownian motion in two-dimensions?

Let's say I have a point-like Brownian particle undergoing two-dimensional diffusion on an infinite plane with the caveat is that the particle can never return to a coordinate that it previously ...

**5**

votes

**0**answers

361 views

### Compute the expected value of the next step of a sorted random walk

Here's what I'm thinking about. If you have a random walk (move +1 or -1 at each step) of some fixed length, then if you're at the maximum of the walk, the next step you take is -1 with probability 1. ...