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

learn more… | top users | synonyms

10
votes
0answers
126 views

Probability on entering direction of a simple random walk

Let $X(n)$ be a simple random walk on $\Bbb{Z}^2$. Also we define $S_{R} = \inf\{n > 0 : X(n) \notin [-R, R]^2 \} $ : the exit time of the square $[-R, R]^2$, $T_{v} = \inf\{n > 0 : X(n) = ...
10
votes
0answers
161 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$: ...
9
votes
0answers
106 views

probability of completing a self-avoiding chessboard tour

Someone asked a question about self-avoiding random walks, and it made me think of the following: Consider a piece that starts at a corner of an ordinary $8 \times 8$ chessboard. At each turn, it ...
8
votes
0answers
121 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 ...
7
votes
0answers
284 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, ...
5
votes
0answers
96 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
180 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
245 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 ...
4
votes
0answers
42 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
71 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's 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 ...
4
votes
0answers
122 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 ...
4
votes
0answers
41 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
114 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 ...
4
votes
0answers
243 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
75 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: ...
4
votes
0answers
157 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 ...
4
votes
0answers
133 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 ...
4
votes
0answers
133 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 ...
3
votes
0answers
42 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 ...
3
votes
0answers
32 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 ...
3
votes
0answers
66 views

Proving how to reduce a Brownian walk on a plane to a line (2D to 1D)

I have a Brownian motion on a plane and would like to find the time of when it is expected to hit a set of parallel lines, i.e the hitting time. In order to do so, I understand that I can reduce the ...
3
votes
0answers
20 views

The boundedness of a certain sequence of expectations

In Bálint Tóth's paper, "No More Than Three Favourite Sites for Simple Random Walk", while proving one of the many technical lemmas in his theorem's proof, he makes the following claim: suppose for ...
3
votes
0answers
31 views

$S_n \in [-a,a]$ for some $a$ infinitely often

Suppose we have iid r.v.s $X_n \in \mathbb{R}$ with mean $0$ variance $\sigma^2$, I wonder is it true that we have $\exists a>0,$ $$P(S_n \in [-a,a] \text{ infinitely often} )=1,$$ where $S_n ...
3
votes
0answers
29 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? ...
3
votes
0answers
170 views

Maximum difference between 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)$, ...
3
votes
0answers
76 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 ...
3
votes
0answers
81 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 ...
3
votes
0answers
73 views

Simple random walk conditioning on non-return

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0=0$. Let $k$ and $j$ be two positive integers. Let $P_{k,j}$ be the probability that the walker hits the vertex ...
3
votes
0answers
58 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 ...
3
votes
0answers
101 views

Sum of sequence of random variables infinitely often positive

Let $X_1,X_2,\ldots$ be an infinite sequence of independent (but not necessarily identically distributed) random variables with $E(X_i)=0$ for all $i$. Set $S_n=\sum_{i=1}^n X_i$. I want to show that ...
3
votes
0answers
102 views

Expected minimum of a finite random walk.

So I couldn't find any resource for how to calculate the expected minimum of a random walk. Since it is such the minimum of the random variables are actually not independent as they are cumulative ...
3
votes
0answers
36 views

Number of times above a linear boundary for a finite variance random walk

I consider a random walk $(S_n)$ with mean zero and finite variance, and $\epsilon>0$. Is it true that $$ \mathbb{E}\left[\sum_{n=0}^{+\infty} 1_{S_n>n\epsilon}\right] < +\infty \quad ? $$ ...
3
votes
0answers
69 views

Upper bounds on the sum in a Martingale process

My question is related the hitting time of not a random walk, but a more general martingale process. Suppose we start with an arbitrary $x_0=x$ with $0\leq x\leq 1$. We compute $x_{t+1}$ from $x_t$ ...
3
votes
0answers
78 views

Dimension free Concentration bounds for Martingales

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
3
votes
0answers
77 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 ...
2
votes
0answers
32 views

Survival probability of a biased random walker

A random walker moves to $+1$ with probability $p$ and moves to $-1$ with probability $q=1-p$. If he starts at point $m$, what is the probability that he doesn't hit the point zero after $k$ steps, ...
2
votes
0answers
30 views

Three person simultaneous random walk

So let's say you have 3 people walking 100m, from one wall to another. Each move each person independently draws 3 integers, each between -10 and 5 with equal probability. You, as the coordinator, ...
2
votes
0answers
26 views

Is every discrete martingale a time-changed simple random walk?

While going through the book by Revuz and Yor titled 'Continuous Martingales and Brownian Motion', I came accross the notion of time change. In a nutshell, if X is a stochastic process and C is an ...
2
votes
0answers
16 views

Multiplicative Super-martingales

Let $\{X_n\}$ be a stochastic process which is strictly positive, i.e. $X_n > 0$ almost surely for all $n$. It then follows that $\{Z_n = \log(X_n) \}$ is a well-defined stochastic process as ...
2
votes
0answers
44 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 ...
2
votes
0answers
32 views

Return time for two independent one dimensional random walks

Let $X^1$ and $X^{-1}$ be two simple random walk in $\mathbb{Z}$ starting respectively from $1$ and $-1$. Let $\tau$ be the first time one of them reaches the origin, $$\tau = \inf \{ j \geq 0 \, : ...
2
votes
0answers
37 views

Test a law-of-iterated-logarithm-like result, with numerical simulation

I have a non-standard random walk $S_n$ for which the increments are not exactly independent (I could describe it, but it would be a totally different long and complex topic). I expect it to have ...
2
votes
0answers
75 views

Let $\{ X_{n}\} _{n\geq1}$ be IID s.t $\mathbb{E}[X_{i}]=0$ and $|X_{i}|\leq K$. Show $S_{n}$ visits $[-K,K]$ infinitely often.

Let $\left\{ X_{n}\right\} _{n\geq1}$ be a sequence of IID random-variables s.t $\mathbb{E}\left[X_{i}\right]=0$ and $\left|X_{i}\right|\leq K$ . Let $S_{n}=\sum_{i=1}^{n}X_{i}$ , I want to show ...
2
votes
0answers
36 views

Theory of random walk

Let 0 < p < 1 and let $S_n$ be the simple random walk with step probabilities p, 1 − p. In other words $S_n = X_1 + · · · + X_n$ and the {$X_i$} are i.i.d. random variables with distribution ...
2
votes
0answers
63 views

Almost sure convergence of a martingale

I just learned martingales (with no depth) and I am working on the following question. Suppose $S_n$ is a a random walk on the integers and at each step, it increases by 1 with probability $p$ or ...
2
votes
0answers
125 views

Gambler's Ruin with no set target for win

I have been presented with the following probability question: A compulsive gambler is never satisfied. At each stage he wins $€1$ with probability $p$ and loses $€1$ otherwise. Find the probability ...
2
votes
0answers
33 views

An inequality for standard random walk.

How to prove that $\Bbb P_1(\lim\sup_{n\to\infty}\frac{\log \bf{x}(n)}{\log n}\le \frac{1}{2})=1$, with the suggestion that $\bf{x}(n)$ goes to $\infty$ like $\sqrt{n}$. Here $\bf{x}_n$ is the ...
2
votes
0answers
50 views

Excursion of random walk conditioning on return

Consider a simple random walk in one dimension starting from the origin. Let $\epsilon>0$. How to prove that, conditioning on the event that the random walk is at the origin at time $n$, the ...
2
votes
0answers
89 views

Expected distance of a random walk of distance $k$ on the $k$th step

I am trying to sharpen my intuition on some random-walk style results. Suppose we are looking at a random walk on $\mathbb{Z}$ starting at $0$. At the $k$th step, we either walk to the left $k$ ...
2
votes
0answers
63 views

Is the sudden appearance of transient random walks in 3-dimensions a phase transition?

Consider a particle walking uniformly at random on the infinite d-dimensional lattice $\mathbb{Z}^d$. This is symmetric random walk. Symmetric random walk in two dimensions almost always returns to ...