The random-walk tag has no usage guidance.

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

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

**4**

votes

**0**answers

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

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

**2**

votes

**1**answer

258 views

### Does random walk have more concentration surrounding the origin?

Consider a simple random walk $S_n$ on one dimension, starting at $0$. In this case, $S_n$ fluctuates between $-\infty$ and $\infty$, but intuition says that it might stay more often in an interval ...

**8**

votes

**1**answer

135 views

### Finite-index iff positive density?

Let $G$ be a finitely generated group and $S$ a symmetric generating set. Define density (lower density, say) with respect to the sequence of balls $S^n$.
Is it true that a subgroup of $G$ has ...

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

**5**

votes

**2**answers

1k views

### Random walk to stay in an interval forever

Consider a random walk on the real time, starting from $0$. But this time assume that we can decide, for each step $i$, a step size $t_i>0$ to the left or the right with equal probabilities.
To ...

**5**

votes

**2**answers

172 views

### A follow up question to: Number of walks on integer lattice with self-edge at zero

Let $a(n)$ be the number of lattice paths in ${\mathbb{Z}^2}$ of length $n$ which start at the origin $(0,0)$ and end up at $(n,0)$ and have only up-steps $U:(i,j) \to (i + 1,j + 1)$, down-steps $D:(...

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

**6**

votes

**1**answer

109 views

### Basic Definition and Notations in RWRE

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

**0**

votes

**1**answer

90 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\}$...

**4**

votes

**1**answer

213 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\...

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

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

**3**

votes

**1**answer

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

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

**3**

votes

**2**answers

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

**6**

votes

**1**answer

330 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

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

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

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

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

**3**

votes

**1**answer

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

**7**

votes

**2**answers

201 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 \...

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

**2**

votes

**1**answer

111 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

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

**3**

votes

**1**answer

212 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

128 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

175 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

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

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

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

**4**

votes

**4**answers

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

**5**

votes

**1**answer

174 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

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

**2**

votes

**2**answers

190 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

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

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

**8**

votes

**2**answers

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

**6**

votes

**2**answers

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

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

**4**

votes

**3**answers

305 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,\...

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

**9**

votes

**1**answer

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

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

**2**

votes

**1**answer

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