The random-walk tag has no usage guidance.

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

**1**

vote

**1**answer

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

**20**

votes

**0**answers

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

**12**

votes

**0**answers

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

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

**8**

votes

**0**answers

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

**7**

votes

**0**answers

56 views

### Distribution of the stopping time of an autoregressive sequence

Consider $e_t$ be i.i.d. uniformly chosen from $\pm 1$. Let $\eta$ be a small positive constant. What is the distribution of $T$ such that $\eta^{0.5} (1+\eta)^T W_T$ first hits $\pm 1$, in which
$$
...

**7**

votes

**0**answers

142 views

### Winding number of a random walk on the square lattice before hitting the origin

Let us consider a simple random walk on $\mathbb{Z}^2$ started at $(x,0)$ and killed upon hitting the origin. Define the total winding number $w_x$ around the origin to be the (signed) number of ...

**7**

votes

**0**answers

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

**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?

**5**

votes

**0**answers

69 views

### Most visited vertex in a random walk with place dependent drift

Consider the following Markov chain on $\mathbb{Z}$:
$$
P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}}
$$
Do there exist constants $c,C>0$ such that
$$
c\cdot P^t(z,z) \...

**5**

votes

**0**answers

157 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 $T(...

**5**

votes

**0**answers

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

**5**

votes

**0**answers

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

**5**

votes

**0**answers

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

**4**

votes

**0**answers

108 views

### Hierarchical (Recursive) Random Walk Model

Consider the following hierarchical (recursive) random walk model.
For the first level $\ell=1$, let $\{X_t^{(\ell)}\}_{t=1}^{T}$ be a (discrete) random walk.
For the next level $\ell=2$, we ...

**4**

votes

**0**answers

59 views

### Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?

In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...

**4**

votes

**0**answers

193 views

### Self-adjusting random walk

Let $X_t$ be a random process such that
\begin{eqnarray}
X_1 &=& 0\\
X_t &=& X_{t-1} + \left\{\begin{array}{ll}
A_t, & X_{t-1} \geq 0\\
B_t, & X_{t-1} < 0
\end{array}\...

**4**

votes

**0**answers

237 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)$, ...

**4**

votes

**0**answers

118 views

### 1d random walk probability of previous n positions

I have the following question.
(May be it is very simple, but I cannot find the answer).
Suppose I have a 1d random walk on integer numbers with equal pobabilities of unit step in either direction (...

**4**

votes

**0**answers

158 views

### Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

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

**4**

votes

**0**answers

420 views

### Monotonic properties of harmonic functions on graphs

I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...

**3**

votes

**0**answers

73 views

### What is the influence of unreliable comparisons on the results of sorting

Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...

**3**

votes

**0**answers

69 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 G$)?...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

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

**2**

votes

**0**answers

72 views

### Question about martin boundaries of random walks induced on transient subgroups

Suppose $\Gamma$ is a discrete, finitely generated, non-amenable group, and
consider a random walk given by a measure $\mu$.
Assume the measure is symmetric, finitely generated, and the support of
$\...

**2**

votes

**0**answers

60 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 (0,\...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

287 views

### Cover time for a biased random walk on an 'N'-dimensional integer lattice

Imagine that I have a random walk on an $N$-dimensional integer lattice, $Z^N$, of finite dimensions, $(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some ...

**2**

votes

**0**answers

288 views

### Self-avoiding Walk with next-nearest neighbors

Background
I study polymer physics and am doing experiments testing the model outlined in this paper. Basically, the polymers fall into an integer number of pits, and we create a partition function ...

**1**

vote

**0**answers

37 views

### Probability for a SRW to be at some place in an even number of steps

I am looking for some references for the following problem.
Consider a graph $G$ and a simple continuous time random walk $(X_t)_{t\geqslant 0}$ on this graph. Consider the family of events $(e_t)...

**1**

vote

**0**answers

35 views

### Expression for Joint-PDF of Langevin equation?

How to derive exact or approximate analytical expression for time-dependent joint-PDF (velocity-coordinate PDF) for Langevin equations of Brownian motion?
Langevin equations is:
$\dot{x}=v$
$\dot{...

**1**

vote

**0**answers

71 views

### Diagonal of Green's Function

I am looking to numerically calulate the diagonal of Green's function. I am interested in Green's functions of elliptic PDEs and in those that arise from stochastic processes (discrete and continuous)....

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**0**

votes

**0**answers

21 views

### Multi-particle random walks

Define a multi-particle "breeding" random walk $\mathcal{W_p}$ in $d$ dimensions, for $p \in (0,1)$ as follows:
The state of $\mathcal{W_p}$ at integer time $t\geq 0$ consists of the pair
$(k, x)$ ...

**0**

votes

**0**answers

20 views

### Large-$t$ expected distance from origin in non-trapping, self-avoiding random walks

Consider two variants on Self-(vertex-)Avoiding Random Walks on $\Bbb{Z}^2$:
(A) "Legal" steps consist of any step not ending on a vertex previously visited, and the probabilities of each of the 1, 2,...

**0**

votes

**0**answers

28 views

### Unidirectional continuous path discrete time random walk

Is there any material available to study on unidirectional continuous path discrete time random walk on a line interval.
To say "unidirectional continuous path discrete time random walk on a line ...

**0**

votes

**0**answers

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

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

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

**-1**

votes

**0**answers

58 views

### Random walk on d-dimensional torus

I am reading the following paper: http://arxiv.org/pdf/1602.03849v2.pdf
I will explain the general setup below.
Let $x\in X=\mathbb{T}^d$, where $\mathbb{T}^d$ is the d dimensional torus. Let $\rho$ ...