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

learn more… | top users | synonyms

0
votes
0answers
23 views

Explicit formula for return probability of simple random walk

Is there an explicit formula for the probability that a simple symmetric random walk on $\mathbb{Z}$ starting from $1$ will not hit $0$ before time $t$?
2
votes
0answers
22 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 \, : ...
0
votes
0answers
15 views

Expectation of a stopping time on an asymmetric random walk

Let $X_1, X_2, \cdots$ be i.i.d. such that $P(X_i=1)=p , P(X_i=-1)=1-p$. Denote $\tau_a = inf \; \{ n \ge 1 : S_n = a \}$ for any integer $a$, where $\tau_a = \infty$ if $S_n \neq a$ for all $n \ge ...
1
vote
0answers
27 views

Reflection principle for simple random walk

Let $(X_n)$ be a sequence of independent random variables, such that $P(X_i=1) = P(X_i=-1) = 1/2$. Then, the reflection principle states that for all $a > 0$, $$P(\max_{1\leq k\leq n} S_k \geq a) ...
2
votes
0answers
67 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 ...
0
votes
2answers
36 views

Root mean square distance explanation…

We know that $D_{rms}=\sqrt N$ where $N$ is the number of steps taken by the random walker. Now,consider a situation where a random walker walks $2$ steps in positive direction in the first two ...
0
votes
1answer
21 views

symmetrical random walk P[M(n)=k]

On a symmetrical random walk, I am trying to deduce P[$M_{n}$ = k] = $(\frac{1}2)^n$ ${n \choose \frac{n+k}2}$ where n is the total number of steps and ${n \choose \frac{n+k}2}$ is the number ...
2
votes
1answer
24 views

An example of a reducible random walk on groups?

Random walk on group is defined in the following way as a Markov chain. A theorem says the uniform distribution is stationary for all random walk on groups. If the random walk is ...
1
vote
0answers
23 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 ...
3
votes
1answer
59 views

Numerical evidence of law of iterated logarithm (random walk)

The law of iterated logarithm states that for a random walk $$S_n = X_1 + X_2 + ... X_n$$ with $X_i$ independent random variables such that $P(X_i = 1) = P(X_i = 1) = 1/2$, we have $$\limsup_{n ...
0
votes
1answer
35 views

calculate mean and variance from multivariate probability-generating function in random walks

Suppose in a biased random walk, $r(i,n)$ is the probability that a particle appears at position $i$ at time $n$. The corresponding probability generating function is $$ R(z,s)=\sum_{n=0}^\infty ...
0
votes
0answers
30 views

heuristic for expected number of visits random walk

What is the heuristic argument that explains why, on $\mathbb{Z}^d$, $d \geq 3$, the expected number of visits of a random walk starting from the origin at $x$ is of order $$ O(|x|^{2-d})? $$
0
votes
1answer
38 views

The expected range covered by a random walk

The question that I have been struggling with lately is: If we have a one-dimensional random walk of length $n$ (consisting of $n$ steps) with discrete steps $1$ and $-1$, with probabilities of ...
0
votes
0answers
30 views

Number of ways a dice can roll every side equally many times for the first time after x rolls

This problem is best viewed as a walk on a $d$-dimensional integer lattice with integer steps corresponding to various results of a dice roll. For a normal 6-sided dice, these would be ...
0
votes
0answers
33 views

3d symmetric random walk passes infinitely through any particular line

I'm trying to solve problem 27 from Chapter XIV An Introduction to Probability Theory Volume I by William Feller, ...
1
vote
2answers
32 views

Random Walk Definition

I have just begun studying this script about Random Walks, but I'm having trouble with a definition that is given there right at the beginning (page 10). We're looking at Random Walks on the square ...
1
vote
1answer
44 views

Random Walk Stopping Time 2

Let $(X_1,X_2,...)$ be i.i.d random variables, with $P(X_t=1)=P(X_t=-1)=1/2$. Then $S_t= \frac{1}{t}\sum_{i=1}^{t}X_i $ is a zero mean random walk. Let $\tau$ be the stopping time corresponding to ...
0
votes
2answers
31 views

Random Walk Stopping Time

Let $(X_1,X_2,...)$ be i.i.d random variables, with $P(X_t=1)=P(X_t=-1)=1/2$. Then $S_t= \frac{1}{t}\sum_{i=1}^{t}X_i $ is a zero mean random walk. Let $\tau$ be the stopping time corresponding to ...
2
votes
1answer
26 views

Probability that a biased asymmetric random walk reaches the origin

I am working on the following problem for my probability class and I am a little stuck: A particle moves at each step two units to the right or one unit to the left, with corresponding ...
0
votes
0answers
20 views

Expected value of a random walk given value at previous time

I have a homework question dealing with random walks. One part of the question required me to find the probabilities $p$ and $q$ such that $$E[M_1] = M_0$$ which I achieved. Having found these, the ...
0
votes
0answers
19 views

Random process theory: probability distribution of height vs summits

Imagine I have a matrix of height values ($z$), e.g. a surface height topography. This surface is a random process: randomly rough isotropic surface with Gaussian distribution. What is the difference ...
1
vote
0answers
51 views

Expected value of sum of heights of books in a shelf with limited width

This question has arisen from a previous post: Statistical problem: how many books of different widths fit it into a self of a limited certain width? Let's assume that there are $N$ types of books, ...
-1
votes
2answers
74 views

Show $E[T] < \infty$ by finding an upper bound for $P(T=k)$

Given random variables $X_1, X_2, \ldots \stackrel{iid}{\sim} P(X_i = 1) = p = 1 - q = 1 - P(X_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in ...
1
vote
1answer
48 views

Understanding Random Walk

I have a trouble understanding the random walk, where $/xi_1,...,/xi_n$ is iid integer valued rv with the probability mass function $f(x)$. I want to get the expression $p(x,y) = f(y-x)$. $p(x,y)= ...
2
votes
2answers
49 views

Random walk on a square

Problem: Given a square $ABCD$, $AB$ being an horizontal vertex, we start at $A$. With each step, we move to another corner: horizontally with a probability $p$ vertically with a probability $q$ to ...
0
votes
0answers
27 views

Resources to study self-avoiding walks

What would the best resources be (books, papers, OCW) for someone who wants to study self-avoiding walks from a mathematical standpoint?
0
votes
0answers
32 views

Markov Chains - Random Walk

Let $X_n$ be the distance from his desired path of our drunken man. At each step he is moving right or left with probabilities $p$ and $1− p$. Given that $p\neq 1-p \neq 0.5$ 1)Calculate the ...
1
vote
1answer
41 views

Question about a Symmetric random walk, Problem 4.1.1 in Durrett

I am working on the following problem: Let $X_1, X_2, \dots \in \mathbb{R}$ be i.i.d. with a distribution that is symmetric about $0$ and nondegenerate, i.e. $P(X_i=0)<1$. Show that $-\infty = ...
0
votes
0answers
18 views

Probability a random walk hits zero at specified time set

Let $X_n \in \lbrace -1, 0, 1 \rbrace$ be sequence of i.i.d random variables taking $-1$ or $1$ with equal probability, and $0$ some positive probability. $S_n = \sum_{i = 1}^{n} X_i$ is a random ...
9
votes
3answers
940 views

Random solving of a Rubik cube .

After playing a little with a Rubik cube I thought of the following problem : Suppose we start with a solved Rubik cube (a general one , with $n^3$ cubes) . Then we choose one of the moves , each ...
2
votes
1answer
37 views

Probability a random walk eventually crosses a square root boundary

Let $\lbrace X_n, n \geq 1 \rbrace$ be i.i.d random variables taking values in $\lbrace -1, 1 \rbrace$, and \begin{align*} S_n = \sum_{i = 1}^{n} X_i \end{align*} be a random walk. Let $f$ be a ...
0
votes
1answer
403 views

Simple Probability Matrix

Question: Consider a simple model that predicts whether you pass your next test or not based on the result of your previous test. If you pass your previous test, then you have 0.2 chance you will ...
4
votes
2answers
88 views

How to show $M_n = X_n^2-n$ is a martingale?

Let $X_n, n = 0, 1, 2, . . .$ denote an unbiased Normal Random Walk. $X_0 = 10$, and $X_{n+1} = X_n + Y_{n+1}$, with $\{Y_n\}$ are i.i.d. $N(0, 1)$. Then how can I show that: A) $M_n = X_n^2-n$ is a ...
2
votes
1answer
39 views

Upper bound for random walk to show stopping time is bounded

I have a simple symmetric random walk (SSRW), and a stopping time: $\tau=\inf\{ n \geq 0 ~:~ |S_n|=N\}$. I am showing that $\newcommand{\ee}[1]{\mathbb{E}[#1]}$ $\newcommand{\pp}[1]{\mathbb{P}[#1]}$ ...
1
vote
0answers
26 views

Simple random walk on the $N$-cycle

I am considering the following example: In my lecture notes we noted that "the functions $(\phi_j)_j$ form a basis". I think they refer to the space $\mathbb{C}^G$ where $G$ is the above ...
4
votes
1answer
72 views

Simple Random Walk: Hitting time of 1 is a.s. finite

Let $X_i, i \geq 0$ be i.i.d. random variables with $P[X_i=1]=P[X_i=-1]=1/2$ and consider $S_n = X_1 + \dotsc + X_n$ for $n \geq 1$, $S_0=0$, the symmetric simple random walk on $\mathbb{Z}$. Let ...
1
vote
1answer
53 views

Average distance from origin in a random walk on the integer number line

In a random integer walk along a number line (each step 0.5 probability of moving right and 0.5 probability of moving left), what is the average distance from the origin during the walk? Other ...
4
votes
1answer
81 views

Show that $P(T \le n + N \mid \mathscr F_n) > \epsilon$ where T is a stopping time

Given random variables $Y_1, Y_2, \ldots \stackrel{iid}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in ...
0
votes
1answer
67 views

Symmetric Random Walk / Prove $S = \inf\{n : X_n = 7\}$ and $T = 10^{12} \wedge S$ are $\{\mathscr F_n^Y\}$-stopping times.

Given a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in \mathbb N}, \mathbb P)$ where $\mathscr F_n = \mathscr F_n^Y$, let $Y_1, Y_2, ...$ be iid random variables w/ $P(Y_n = ...
4
votes
1answer
102 views

Probability distribution for 1-dimensional random walk with pauses

The problem could be stated as follows : we have some random walker in an unbounded 1-dimensional lattice, such that there is a 50% chance the walker doesn't move at all, a 25 % chance the walker ...
3
votes
0answers
83 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 ...
0
votes
0answers
21 views

Random walk that can die and which is conditioned on not to die

Let $S_t$ be a symmetric random walk on $\mathbb{Z}$ with some jump distribution $Q(x,y) = Q(0,y-x)$ and $S_0=0$. Let $P_n(\epsilon)$ be the probability that the random walk will reach a distance at ...
3
votes
2answers
58 views

Does a random walk with infinite mean ever converge to anything?

Suppose we have a random walk on the real line whose step sizes have finite variance. We know that, when viewed as a function and suitably rescaled, this random walk will converge to a Brownian ...
0
votes
0answers
23 views

Expected position in a random walk with probabilities in various directions

A child makes a random walk on a square lattice of lattice constant $a$ taking a step in north, east, south or west directions with probabilities $0.225,0.255,0.245$ and $0.245$, respectively. After a ...
40
votes
7answers
10k views

Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1

How does one prove that a simple (steps of length $1$ in directions parallel to the axes) symmetric (each possible direction is equally likely) random walk in $1$ or $2$ dimensions returns to the ...
1
vote
1answer
111 views

Asymmetric Random Walk / Prove that $E[T:= \inf\{n: X_n = b\}] < \infty$

Given random variables $Y_1, Y_2, \ldots \stackrel{iid}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in ...
0
votes
1answer
46 views

Symmetric Random Walk / Find $E[X_S]$ and $E[X_T]$

Given a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in \mathbb N}, \mathbb P)$ where $\mathscr F_n = \mathscr F_n^Y$, let $Y_1, Y_2, ...$ be iid random variables w/ $P(Y_n = ...
0
votes
1answer
52 views

Asymmetric Random Walk / Prove $E[T] = \frac{b}{p-q}$ / How do I use hint?

Given random variables $Y_1, Y_2, \ldots \stackrel{\mathrm{iid}}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr ...
0
votes
0answers
44 views

Simple random walk in $\mathbb{Z}^3$

I have the following combinatorial problem. I want to find the probability that a SRW $(X_n)_n$ in $\mathbb{Z}^3$ returns to $0$. So let's consider $2n$ steps. Then we can go in $3$ different ...
0
votes
0answers
75 views

Mean absorption time, two absorbing states

I have a transition matrix $$ P = \begin{Vmatrix} 1 & 0 & 0 &0\\ .3& 0 &.7& 0\\ 0& .1 & 0 & .9 \\ 0& 0 & 0 &1 \end{Vmatrix}$$ on states $\{0,1,2,3\}$. ...