Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-walk]

For questions on random walks, a mathematical formalization of a path that consists of a succession of random steps.

14
votes
0answers
337 views

Expected range of simple random walk in $\mathbb{Z^2}$

Let $(Y_k)_{k\geq0}$ be a simple random walk process. The range of an $n$-step random walk, $R_n$, is a random variable that characterizes the number of distinct points visited at time $n$: $$R_n=|\{...
12
votes
0answers
2k views

Does the “prime ant” ever backtrack?

A few mathematical questions have come up from the question "The prime ant 🐜" on the Programming Puzzles & Code Golf Stack Exchange. Here is how the prime ant is defined: Initially, we have ...
10
votes
0answers
235 views

A generalization of simple random walk

Suppose $S_n, n\geq 0$ is a martingale on $\mathbb{R}$ such that $S_0=0$ and $|S_{n+1}-S_{n}|\in [\frac{1}{2}, 1]$. Prove that there exists $c,C>0$ s.t. $$ \frac{c}{\sqrt{n}} \leq P( S_1\geq 0,\...
8
votes
0answers
189 views

Brownian Motion in Confined space, any results?

I am searching for work regarding Brownian motion in a confined space, like a sphere or a cylinder, where the wall will serve as reflection boundary. I am wondering if it is possible to derive results ...
8
votes
0answers
497 views

Random matrices, eigenvalue distribution.

I just investigated randn(1024) + 1i*randn(1024), a 1024x1024 complex valued matrix with elements both real part and imaginary part drawn from $\mathcal{N}(\mu = 0, \sigma = 1)$. I was a bit surprised ...
7
votes
0answers
217 views

Question about random walk

Consider $X_1, X_2, X_3$ ... random variables i.i.d. such that $P(X_i=1)=p$ and $P(X_i=-1)=1-p$. Consider the random walk $(S_n)_{n\ge 0} $ with $S_0=0$ and for $n\ge 1 $, $S_n = \displaystyle\sum^{...
7
votes
0answers
340 views

Is there a connection between the 3D random walk constant and the partition function?

In thinking about this question, I took a look at Pólya's random walk constants and was struck by the fact that an expression for the constant for a three-dimensional random walk, $$\frac3{(2\pi)^3}\...
5
votes
0answers
105 views

Potential uses for viewing discrete wavelets constructed by filter banks as hierarchical random walks.

I have some weak memory that some sources I have encountered a long time ago make some connection between random walks and wavelets, but I am quite sure it is not in the same sense. What I was ...
5
votes
0answers
111 views

How to compute the exit probabilities for a random walk? a question concerning a typo on sinai's paper

On Sinai's paper "The Limiting Behavior of a One-Dimensional Random Walk in a Random Medium" (1982) one considers a random walk on $Z^1$ that moves from $x$ to $x + 1$ with probability $p(x)$ and ...
5
votes
0answers
199 views

What is the area covered by a Random walk in a 2D grid?

I am a biologist and applying for a job, for which I need to solve this question. It is an open book test, where the internet and any other resources are fair game. Here's the question - I'm stuck on ...
5
votes
0answers
452 views

Discrete Time Two sided Gaussian Random Walk : Hitting Time Distribution

I am looking at the hitting time of a two sided Gaussian random walk i.e. $S_{n}=\sum_{i=1}^{n}X_{i}$ where $X_{i}$ are i.i.d normally distributed random variables. The hitting time is $\tau=\inf\{n:...
5
votes
0answers
129 views

Self-avoiding random walk on $\mathbb{Z}^2$ getting stuck

Let $W_n$ be a self-avoiding random walk (SAW) on $\mathbb{Z}^2$, starting at the origin. Formally, $W_0=0$ and for $n\ge 0$, $W_{n+1}$ is chosen uniformly from the neighbours of $W_n$ which were not ...
5
votes
0answers
177 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
5
votes
0answers
439 views

Intuition for the optimality of bold play

There is a standard result (I think originally by Dubins and Savage) that if one wants to maximise the probability of winning a certain amount in an unfair game of chance then an optimal strategy is “...
5
votes
0answers
297 views

Where does directed random walk hit the boundary?

I have a problem that I more or less know the answer to, but would really like to see it done in a systematic, rather than ad hoc way. In spite of this, I will pose the question in a very concrete way....
4
votes
0answers
39 views

Deriving Polya’s Random Walk Constants

It is a well known theorem of Pólya that a random walk in 1 or 2 dimensions has a probability of 1 of returning to the origin. However, the probability in the 3-dimensional case is given by a strange ...
4
votes
0answers
160 views

Convergence to Uniform Distribution of a Random Walk on a Finite Group

I am reading the paper Shuffling Cards and Stopping Times by P. Diaconis and D. Aldous (American Math. Monthly, 1986). Context. Let $G$ be a finite group and $Q$ be a probability distribution on $G$....
4
votes
0answers
57 views

Random Walks and the Locus of Partial Sums of the Riemann Zeta Function

It is a relatively well-known fact that Random Walks are a pretty good approximation of the locus of partial sums for the zeta function. For instance let $\zeta_k(s)$ denote the $k^\text{th}$ partial ...
4
votes
0answers
341 views

Asymmetric random walk

Let $(X_i)_{i=1}^n$ be a sequence of i.i.d. random variables with $\Pr(X_i=1)=1-\Pr(X_i=-1)=p$, for some $0\leq p\leq 1$. Let $S_0=0$ and, for $1\le i\le n$, $S_i = X_1+X_2+\cdots+X_i$. Let $\Pi_n$ ...
4
votes
0answers
41 views

Number of paths with 1,2,… crosses over a point $m$ between 0 and $x$ in a random walk of $n$ steps

Suppose we have a random walk starting from origin and ending at $x$ with $n$ steps, where the set of points is integers on the number line and the steps allowed are 'right' and 'left'. We know that ...
4
votes
0answers
97 views

$2D$ random walk stopping time

A $2D$ random walk starts at $(X_0, Y_0) = (k, k)$ where $k>0$ is an integer. At each step $(X_{n+1}, Y_{n+1}) = (X_{n}-1, Y_{n})$ or $(X_{n+1}, Y_{n+1}) = (X_{n}, Y_{n}-1)$ with the same ...
4
votes
0answers
161 views

For a simple random walk $S_n$ and for a stopping time $\tau$, what is the intuitive interpretation of $P(\tau < \infty) = 1$?

Suppose we have a simple random walk $S_n$ and we define a stopping time to be $\tau = min\{n: S_n = A \ \text{or} \ S_n = -B\}$. That is, we stop the first time we hit $A$ or $-B$. With this, I have ...
4
votes
0answers
223 views

Useful bounds on stopping time for a positive drift random walk

I was studying SPRT (Sequential Probability Ratio Tests) and there was a section (in an online article I was reading) which proved optimality of SPRT using some approximations. Unfortunately, this ...
4
votes
0answers
47 views

Random walks with limited number of visits

I'm interested in random walks (esp. their hitting times) such that the number of visits to each state is limited by some parameter $K$. Is there any canonical name for such stochastic processes? ...
4
votes
0answers
52 views

Random walks and their uses

Can anyone provide some motivation behind the use of random walks? I know they're used a lot in computer science, in things like page walk (I think that's what it was called- something like pagerank), ...
4
votes
0answers
183 views

Uniform integrability of the maximum of a random walk with negative drift

Given $S_k^{(n)} = X_1^{(n)} + ... + X_k^{(n)}$ for all $k,n\in\mathbb{N}$, where the $X_i^{(n)}$'s are iid with mean $-\gamma$ for some $\gamma > 0$ and unit variance. Let \begin{equation}M^{(n)...
4
votes
0answers
113 views

Random walk with $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} < \infty$

Consider a random walk started at $S_0=0$, denoted $S_n = \sum_{k=1}^{n}X_k$, where $X_1$, $X_2$... are the i.i.d increments. If we have $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} &...
4
votes
0answers
255 views

Random walk on $\mathbb{Z}$ with more than two possible steps

Let be $\{X_n\}_{n\in \mathbb{N}}$ random walk on $\mathbb{Z}$. Let be $$P(X_{n+1} = k + a| X_n = k)= p_a$$ for $a\in \mathcal{A} \subset \mathbb{Z}$. Let say that $X_0 = 0$. I am interested in ...
4
votes
0answers
815 views

2-dimensional random walk

I have a question which I anticipated to be rather easy initially. After some googling, however, I realized it is actually not that easy. It concerns a 2-dimensional random walk with constant unit ...
4
votes
0answers
171 views

random walk on real line

Suppose I start at $A>0$ and every period I either move a distance $B$ to the right with probability $p$ or a distance $C$ to the left with probability $1-p$. The expected move is positive: $p\...
4
votes
0answers
175 views

Conditional probability and integrating out part of a random walk

Suppose that I have a random walk process defined by $\alpha_{t+1}$ ~ N$(\alpha_t, \omega^2)$. Given $\alpha_t$ and $\alpha_{t+2}$, I understand why the conditional formula for $(\alpha_{t+1}|\alpha_{...
4
votes
0answers
139 views

probability of this event happening

Play $(n+1)t$ rounds of the same coin-tossing game and the coin is fair ($n$ is a fixed natural number). Please help me find the following probability: $P$(the number of rounds of tossing that show ...
4
votes
0answers
187 views

Completeness of random walks in multiple dimensions?

I was reading Artificial Intelligence: Modern Approach (Norvig and Russell), and there was a footnote that really caught my attention. I apologize if the problem is more in the domain of CS than ...
4
votes
0answers
98 views

Diffusion on a graph and its dual

Is there a relation between the diffusion of a random walker on a planar graph and that on the dual of the graph? It seems perhaps intuitive that if the diffusion on the graph is slow (in comparison ...
3
votes
0answers
114 views

Will simple random walk on $n$-cycle converges to Brownian motion on $S^1$?

I know that, by Donsker's theorem, simple random walk on $\mathbb{Z}$ will converge to Brownian motion on $\mathbb{R}$. Here, simple random walk means that the Markov chain with probability from $n$ ...
3
votes
0answers
58 views

Compute limits using central limit theorem

I want to find the limit of expressions such as: $\lim_{n \to \infty} P(\frac{|S_{n}|}{n} \le \epsilon) $. I do not know how to proceed. Using the central limit theorem, I can rewrite the expression: ...
3
votes
0answers
32 views

Martingale ganerated by random walk

Let $(\Omega,\mathcal{F},P)$ be a probability space. Moreover let $\tau_x\colon \Omega \to \Omega$ for $x \in \mathbb{Z}$ be an ergodic group of tranformations that preserves $P$. By ergodic we mean ...
3
votes
0answers
38 views

Giving sense to a sum over an uncountable set of elements which are equal to zero

Let $(X_i)$ be a simple random walk in $\mathbb{Z}$ starting from the origin. Let $\Sigma$ be the set whose elements are $(Y_i)_{i \in \mathbb{N}}$, which are infinite random walk trajectories. ...
3
votes
0answers
174 views

An efficient way to calculate probabilities for Markov chain/Random walks on a graph

Some of you might remember me from previous posts on Markov chains on top of biological data [1,2]. Finally, I managed to understand the basic concept of the procedure after reading it again and again ...
3
votes
0answers
115 views

Markov chains and Random walks on top of biological data

I'm coming from biology's field and thus I have some difficulties in understanding (intuitively?) some of the ideas of that paper. Initially, I posted this question to the StackOverflow, but they ...
3
votes
0answers
36 views

Pushing the Iterated Logarithm Rule to the limits.

Given a standard Brownian motion, the Iterated Logarithm Rule says that with probability one, $$\frac{|w(t)|}{\sqrt{t \log\log t}},\ (1\le t)$$ has $\limsup$ $\sqrt{2}$ as $t \to\infty$. But what is ...
3
votes
0answers
275 views

Autocorrelation function of derivative

I have a question, I am stuck on for quite some time now. Imagine you can choose a two dimensional autocorrelation function $C_V(x,y)$. From this I can create the two dimensional random process $V(x,y)...
3
votes
0answers
133 views

Probability random walk remains bounded

Consider a simple unbiased random walk on the discrete line starting at $0$. Fix a number $n$. As a function of $k$, what is the probability that the walk remains bounded in $\{-n,\ldots,n\}$ for the ...
3
votes
0answers
333 views

Symmetric random walk

The following question is somewhat related to: Asymmetric random walk Let $(X_i)_{i=1}^n$ be a sequence of i.i.d. random variables with $\Pr(X_i=1)=\Pr(X_i=-1)=1/2$. Let $S_0=0$ and, for $1\le i\le ...
3
votes
0answers
750 views

Why are random walks in dimensions 3 or higher transient?

I watched this PBS video a while ago (relevant part here) and have been trying to get my head around the idea of transient walks. The video says that a recurrent random walk is one that is guaranteed ...
3
votes
0answers
94 views

How can I generate a random walk on the unitary group $U(n)$?

I'm interested in generating a random walk on U(n) using a computer: any references on this topic or related / requisite topics would be helpful. Specific suggestions that discuss the problem ...
3
votes
0answers
105 views

A Proof that the distribution becomes unitary after N step 2D lattice random Walk

I am working with random walks and http://mathworld.wolfram.com/RandomWalk2-Dimensional.html says that "Amazingly, it has been proven that on a two-dimensional lattice, a random walk has unity ...
3
votes
0answers
74 views

Predator-Prey Pursuit-Evasion via Random Walks on a Graph

Let $G = (V, E)$ be a connected, undirected graph. We begin by placing $a$ predators and $b$ prey on the graph: each one is placed at a node chosen uniformly at random. Each predator and each prey ...
3
votes
0answers
143 views

Random walk with centered increments

Let $X_1, X_2,\cdots$ be a sequence of independent, identically distributed random variables and $\displaystyle S_n=\sum_{i=1}^{n}X_i$. Then $EX_{1} <0$ if, and only if , $\displaystyle\lim_{n \...
3
votes
0answers
162 views

Hitting probabilities in a random walk on a graph

Consider a random walk $(X_n)$ on the graph below, where we jump from a given vertex to one of its adjacent vertices with equal probability. I want to find: the probability that we hit $A$ before ...