The random-walk tag has no usage guidance.

**12**

votes

**1**answer

594 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

**0**answers

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

**2**

votes

**2**answers

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

**4**

votes

**1**answer

101 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

313 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

63 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

56 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}$ ...

**4**

votes

**0**answers

120 views

### Decay to stationarity in a random walk on the hypercube

Let $\mu$ be a probability distribution on $\mathbb F_2^n$. Consider the random walk $X_0,X_1,\ldots$ defined by
$$\begin{aligned} X_0 &= 0\\X_{i+1}&=X_i + Z,\end{aligned}$$
where $Z\sim \mu$ ...

**6**

votes

**2**answers

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

**3**

votes

**0**answers

58 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

249 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

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

**3**

votes

**1**answer

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

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

414 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

97 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

25 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

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

**2**

votes

**1**answer

174 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

123 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

85 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

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

**0**

votes

**0**answers

143 views

### Shortest distance on a combinatorial chess board

Consider a random $n\times n$ combinatorial $0/1$ square matrix over field $\Bbb F$ of rank $r$ with every row distinct and every column distinct as a chess board.
Definition of combinatorial ...

**2**

votes

**1**answer

99 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

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

**4**

votes

**1**answer

149 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

164 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

337 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

165 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

68 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

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

**2**

votes

**2**answers

181 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

72 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

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

**7**

votes

**2**answers

262 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

124 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

175 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

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

**1**

vote

**0**answers

36 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

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

**9**

votes

**1**answer

355 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

349 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

**2**answers

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

**1**

vote

**1**answer

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

**2**

votes

**1**answer

177 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

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

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

**2**

votes

**1**answer

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

**7**

votes

**5**answers

856 views

### Reference requested: Random walk on groups

I am looking for a good reference to learn about random walks on groups (either finite groups or Lie groups). Ideally, I would like a reference for general theory of random walks on groups that is ...