The random-walk tag has no usage guidance.

**0**

votes

**1**answer

72 views

### Exact formula for computing n-step transition probability of random walks with self-transitions

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...

**0**

votes

**0**answers

27 views

### Basic Definition and Notations in RWRE [on hold]

From the definition of Zeitouni's lecture notes on RWRE: $(V, E)$ is a special graph, and $N_v:= \{k \in V: (v,k) \in E\}$ is the neighborhood of $v \in V$. $\Omega = \prod_{v \in V} M_1(N_v)$ ...

**3**

votes

**0**answers

50 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

**1**answer

150 views

### Number of walks on integer lattice with self-edge at zero

Consider the graph with vertices $V=\mathbb Z$ and edges
$$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$
that is,
the usual integer lattice with a self-edge at zero.
For some fixed parameters $a,b,n\in\...

**1**

vote

**1**answer

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

**7**

votes

**0**answers

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

**14**

votes

**1**answer

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

**3**

votes

**2**answers

163 views

### The necessary sufficient condition for recurrence of a Markovian random walk

Suppose $\sigma_{1},\sigma_{2},...$are i.i.d random variables.$S_{0}=0$. Define $S_{n}=S_{0}+\sum_{i=1}^{n}\sigma_{i}$, then ${S_{n}}$ is a Markovian random walk.
I want to figure out the necessary ...

**1**

vote

**0**answers

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

**3**

votes

**1**answer

148 views

### Range of random walk

I have a random walk on $\mathbb{Z}$ with starting point $0$ and with length $n$ and possible steps to right, left or stay where you are, all with the same probabilities. I am interested in exact ...

**1**

vote

**0**answers

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

**4**

votes

**0**answers

192 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

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

**6**

votes

**1**answer

325 views

### Liouville property - a very basic question

Let $\mathbb{F}_2$ be the free group on two generators. By a result of Kaimanovich and Vershik, for each measure $\mu$ on $\mathbb{F}_2$ such that the support of $\mu$ generates $\mathbb{F}_2$, we ...

**2**

votes

**0**answers

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

**1**

vote

**1**answer

60 views

### Choose uniformly from fixed-length paths in $[0,n]\cap\mathbb{Z}$ with fixed start and end

Let $X_k$ be a symmetric (discrete time) random walk on $\mathbb{Z}$ and let $m,n\in\mathbb{N}$. I want to chose uniformly from the paths of $X_k$, which
start at $0$
stay in $[0,n]\cap\mathbb{Z}$ ...

**7**

votes

**2**answers

200 views

### Robustly recurrent random walk

Is there a probability measure $\mu$ on $\mathbb{Z}$ such that, for every $0 < \alpha \leq 1$ and every finitely supported (¹) probability measure $\nu$ on $\mathbb{Z}$, it holds that the $\alpha \...

**4**

votes

**0**answers

66 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) \...

**12**

votes

**0**answers

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

**0**

votes

**0**answers

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

**3**

votes

**1**answer

179 views

### Expected visits to the origin by a symmetric random walk on the integers

Consider the first $2n$ steps of a simple random walk on the integers, starting at the origin. A simple binomial argument shows that regardless of $n$, the origin gets visited the most (in expectation)...

**1**

vote

**0**answers

46 views

### Expected number of forward jumps to reach a given quantile of a rv [closed]

I'm a noob in randomized algorithm and ran into a problem(definitely not home work. I'm doing a self study out of my interest with help of my friends. I'm pursuing research career in a machine ...

**4**

votes

**4**answers

423 views

### Order of magnitude of the hitting time of a random walk

Consider the random walk on $\mathbb R$ with $X_0 = a >0$ and
$$X_{n+1} = X_n + U_n,$$
where $U_0, U_1, U_2,\ldots $ is an i.i.d. sequence of uniform random numbers in $[-1,1]$.
How does the ...

**2**

votes

**1**answer

101 views

### Random Walk 2D with dependent weights [closed]

I have spent a lot of time trying to solve this problem but have had no luck so far! Any help would be highly appreciated!
Suppose I have a 3x3 grid as shown below.
(3,1) (3,2) (3,3)
(2,1) (2,2) (...

**0**

votes

**0**answers

26 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

**1**answer

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

**3**

votes

**1**answer

185 views

### How many times does a simple symmetric random walk of length n return to the origin?

Consider the simple symmetric random walk on the integers starting from
the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as
$$ w:= \omega_0 \omega_1 \ldots \...

**0**

votes

**1**answer

126 views

### Transition probabilities for the symmetric random walk on the integers

I found that most references for the symmetric random walk on the integers are for the discrete time case, i.e. the ones that gives us explicit transition probabilities. Now, I am looking at a random ...

**0**

votes

**1**answer

86 views

### Weak convergence of process

Background:
I am trying to compute the weak limit of the following model from mathematical biology that is supposed to exist:
Let $$L(f)(\eta)= \sum_{x \in \mathbb{Z}}\frac{1}{2}\left(1_{\eta(x+1) \...

**0**

votes

**1**answer

161 views

### Mixing time of lazy random walk on the directed cycle $C_n$

Briefly: A hint (if this is easy), reference or derivation would be of great help.
The question
Let $C_n$ be the directed cycle with loops in each of its $n$ vertices, and consider the random walk ...

**2**

votes

**1**answer

101 views

### Resources to study self-avoiding walks

What would the best resources be for someone who wants to study self-avoiding walks from a mathematical standpoint?
I'm talking about seminal/important papers, good textbooks perhaps, things of that ...

**5**

votes

**1**answer

504 views

### Stopping time of two dimensional random walk

Let $U_n=\sum_{i=1}^n X_i,V_n=\sum_{i=1}^n Y_i$, $n\geq 1$, be a two-dimensional random walk with i.i.d. increments $(X_n, Y_n)$, where $X_n, Y_n$ are discrete random variables with joint pmf $P_{X,Y}$...

**4**

votes

**1**answer

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

**1**

vote

**1**answer

165 views

### Does walk on $Z^d$ with steps $(\pm 1,\pm1,\ldots,\pm 1)$ return to origin?

If the steps are iid uniform as in the title, is the return probability known? Is it positive? Answers, comments, references welcome. Clearly each of these steps is not equivalent to $d$ steps of type ...

**9**

votes

**2**answers

349 views

### Adaptive version of the Azuma–Hoeffding inequality

The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition:
$$|X_k - X_{k-1}| \leq c_k$$
Then:
$$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...

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

**4**

votes

**1**answer

169 views

### Random walk with continuously distributed steps on [-1,1]

A simple random walk $S_n = X_1 +\cdots +X_n$, where $P(X_i = 1) = p \not = 0.5$ and $P(X_i=-1)= q \triangleq 1-p$, admits the following probability
$$P(S_n \textrm{ reaches } a \textrm{ before} -b) =...

**3**

votes

**0**answers

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

**1**

vote

**1**answer

470 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 $\gamma_2(...

**2**

votes

**2**answers

187 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

**2**answers

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

**1**

vote

**1**answer

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

**8**

votes

**2**answers

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

**1**

vote

**1**answer

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

**5**

votes

**2**answers

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

**8**

votes

**1**answer

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

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

**4**

votes

**3**answers

303 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)$,
$m_n=\min(S_1,S_2,\...

**9**

votes

**1**answer

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

**5**

votes

**1**answer

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