# Tagged Questions

The random-walk tag has no usage guidance.

**4**

votes

**1**answer

144 views

### Connection between degree of growth and return probabilities of random walks on Lie groups

Let $G$ be a finitely generated group of polynomial growth, let $\mu$ be a non-degenerate symmetric probability measure with finite support on $G$, and let $d$ be the degree of growth of $G$. ...

**8**

votes

**0**answers

165 views

### How much do the classes of geodesic metrics and Green metrics on a Gromov hyperbolic group differ?

Background
Let $G$ be a Gromov hyperbolic group. If $G$ acts properly discontinuously and cocompactly on a proper geodesic metric space $X$, then any bijective identification of $G$ with its orbit ...

**3**

votes

**2**answers

250 views

### Nonmonotonicity of expected distance of a random walk

What's the simplest example of a reversible random walk $X_n$ on an infinite vertex-transitive graph such that the expected distance from the origin is not increasing, i.e. there exists $n$ such that:
...

**10**

votes

**3**answers

470 views

### Hitting time for two out of three random walk particles

I'm imagining a simple random walk on $\mathbb{Z}$ with three independent particles (maybe add laziness so they don't jump over each other). Suppose the particles are initially placed at, say, $-10$, $...

**8**

votes

**2**answers

347 views

### Area covered by Brownian motion of 2D disc

I would like to know the expected value for the area covered by a disc of radius $R$ whose center undergoes Brownian motion (diffusion).
Specifically, let $\mathbf{X}_t$ represent a two-dimensional ...

**5**

votes

**2**answers

620 views

### Random walk by simplex vertices

I apologize if this question is well-known, but I was unable to find it mentioned anywhere.
There exists a bug which moves around in $r$-space. The bug begins at the origin of this $r$-space. If the ...

**4**

votes

**0**answers

102 views

### Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height

I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...

**7**

votes

**0**answers

121 views

### Speed on recurrent graphs

Suppose that $G$ is a (locally finite) graph such that the simple random walk on $G$ is recurrent. Does this imply any upper bound on the speed $\mathbb{E}d(X_t,X_0)$ of such random walk?

**4**

votes

**1**answer

662 views

### Expectation of Maximum of Uniform Multinomial Distribution

Suppose we have a uniform multinomial distribution with $k$ buckets, i.e. we put $n$ items uniformly at random in $k$ buckets leading to $n_1, \dots, n_k$ items in each bucket respectively. Let $m = \...

**1**

vote

**2**answers

486 views

### Quadratic variation for discrete Martingale

Is there any analogue of continuous martingale quadratic variation for the discrete case? If so, are there any theorems which characterize simple random walk using quadratic variation - similar to ...

**8**

votes

**1**answer

443 views

### Width of a random convex polygon

Consider a planar (2D) random walk comprised of N steps.
Consider the minimum convex polygon enclosing the N points visited by the random walker.
Assume the definition of the width of a convex polygon ...

**2**

votes

**1**answer

740 views

### Random walk in a circle

Suppose we have a circle of radius $R$ centered in the origin of a $x,y$ cartesian reference frame. A particle starting from the center of the circle is moving with a speed given by:
$$\overrightarrow{...

**0**

votes

**1**answer

95 views

### Joint law for number of visits in transient simple random walk

Consider a simple $1$-dimensional random walk $X_n$.
Let $p$ and $q$ (with $p+q=1$) be the probability of transitions from $n$ to $n+1$ and from $n$ to $n-1$ respectively, and suppose that $p>q$ ...

**4**

votes

**1**answer

105 views

### Estimates for simple random walks in groups of intermediate growth

I'm looking for references for the rate of escape and return probability for a group of intermediate growth.
Let $0<\alpha < 1$. If the volume growth is $\succeq \mathrm{exp}(n^\alpha)$, then (...

**5**

votes

**2**answers

463 views

### Methods to approximate the betweenness centrality on large networks

To calculate the between centrality wiki def:
$g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
of a node in a graph/network;$\sigma_{st}$ is the ...

**5**

votes

**1**answer

328 views

### Random walk with positive uniformly distributed steps

Let $U_1,U_2,\ldots$ be iid random variables distributed uniformly on $[0,1]$. I am interested in the random walk $X_i = \sum_{j \leq i} U_j$. In particular,
What is the expected number of points ...

**1**

vote

**0**answers

87 views

### Discretization model for Dirac equation in higher dimensions

I'm wondering if there are cases of discretization models (in lattices or graphs) that converge toward the non-linear Dirac equations? While there is a paper on the 2-d and 3-d cases http://arxiv.org/...

**4**

votes

**2**answers

314 views

### Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...

**6**

votes

**1**answer

403 views

### Random walk over a function

Let $\{X_n\}_{n\geq 0}$ be a random walk. Let us assume that $\mathbb{E}X_1 =0$ and $\mathbb{E}X_1^2=1$. Let also $\mathbb{E}\exp(c|X_1|)<+\infty$ for some $c>0$ and $X_1$ has a law with ...

**8**

votes

**1**answer

359 views

### Twisted random walks

Suppose the points of two random walks in $\mathbb{R}^2$ are given the
step number (or time) as a third coordinate, so that they become paths in $\mathbb{R}^3$.
Here are several pairs of walks of $n=...

**8**

votes

**1**answer

1k views

### random walk and Brownian motion on Riemannian manifold

As we know, the random walk on $\mathbb{Z}/n$ will converge(in some sense) to the Brownian motion on $\mathbb{R}$ when $n\to\infty$. I would like to know is there some higher dimensional analogy ...

**3**

votes

**1**answer

268 views

### Speed of random walks in groups

I've seen some estimates for the decay in $d$ of the probability a SRW makes a distance $d$ in time $n$, but is there any reference for the "speed" of a random walk in a group? I'm interested mostly ...

**6**

votes

**1**answer

339 views

### Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...

**18**

votes

**2**answers

874 views

### Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and “Reflective” Boundary at Origin

A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...

**6**

votes

**1**answer

397 views

### The number of lattice paths below y=n/m x for gcd(m,n) = 1

The motivation of my question is the recent preprent of Armstrong, Rhoades and Williams http://arxiv.org/abs/1305.7286 on rational Catalan combinatorics.
An important starting point of this paper is ...

**12**

votes

**3**answers

496 views

### An “inchworm-like” random walk on an integer interval

Imagine I place $k$ stones on an infinite one-dimensional integer interval $Z$ s.t. no stone is more than some distance $d$ from any other stone. For example, if $d=1$ and $k = 5$, we might place the ...

**0**

votes

**1**answer

331 views

### Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...

**1**

vote

**1**answer

262 views

### Fundamental inequality of entropy in random walks

I'm looking for a reference for an inequality related to the "fundamental inequality" about entropy and rate of escape of random walks (on the Cayley graph of a group). Namely,
$\textbf{Question}$: ...

**4**

votes

**1**answer

451 views

### Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...

**5**

votes

**1**answer

259 views

### Memory of Uniformly Random Dyck Paths

Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have $S(0)...

**2**

votes

**1**answer

865 views

### Hitting time probability in a Random Walk with possibility to die.

A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. ...

**5**

votes

**1**answer

315 views

### The minimal norm of a shifted stochastic matrix

Hello,
Given a row-stochastic matrix $M$ with singular values $\sigma_{1}\geq\ldots\geq\sigma_{n}$, I am looking for an upper bound on the expression: $\min_{\alpha}\parallel M- \frac{\alpha}{n}J_{n}\...

**4**

votes

**0**answers

608 views

### Random walk on the hypercube

Let $H_N=\{0,1\}^N$ the N-dimensional hypercube. We define the following random walk $X_n$ on $H_N$:
start from a point $x \in H_N$
pick at random an integer $k$ in $[1,N-1]$ and exchange $x(k)$ and ...

**1**

vote

**1**answer

1k views

### asymmetric random walk, hitting time probability

Let's consider an asymmetric Random Walk on $Z$, with transition probabilities $p_{i, i+1}=p$, $~~p_{i, i+1}=q$, $\forall i \in \mathcal{Z}$, $p+q=1$ and $p>q$.
I am interested in the probability ...

**0**

votes

**0**answers

437 views

### Probability density function of the node positions in a random walk after N time slots

Hello, my question basically is how do I find the probability density function of the position of the nodes in a given area after N discrete time slots when the nodes move following the 2D random walk ...

**1**

vote

**1**answer

77 views

### Spanning subgaph with trivial Poisson boundaries

Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some $k$-...

**1**

vote

**1**answer

475 views

### Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...

**14**

votes

**1**answer

712 views

### Distribution of maximum of random walk conditioned to stay positive

I have an $n$ step random walk which starts at zero $X_0 = 0 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$, but the walk is conditioned on the hypothesis that it ...

**12**

votes

**3**answers

483 views

### Estimate on currents in Cayley graphs

Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...

**31**

votes

**1**answer

1k views

### Prime Number Races in 2 Dimensions

Is the mapping $$f: \ \mathbb{N} \rightarrow \mathbb{Z}[i], \ \ \ n \ \mapsto
\sum_{2 < p \leq n \ {\rm prime}} e^{\frac{p-1}{4} \pi i}$$ surjective?
In 1999, when I was an undergraduate student, ...

**0**

votes

**0**answers

105 views

### Theorem Leads for tied-down random walk

scribd.com/doc/87930409/18/Leads-for-tied-down-random-walk [Theorem 3.7, page 38]
Could you explain me the last equality in the proof? I mean this:
$$\frac{2[\sqrt{1 - s^2t^2} - \sqrt{1-t^2}]}{t^2(...

**4**

votes

**1**answer

251 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

309 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

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

**3**

votes

**1**answer

423 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

927 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
$$f_N(t)=\frac{1+2t+2t^2+t^3}{1-Mt-Mt^2+\frac{...

**2**

votes

**1**answer

3k 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 $1/...

**10**

votes

**1**answer

358 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

257 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

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