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

learn more… | top users | synonyms

1
vote
0answers
25 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) ...
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 ...
1
vote
0answers
21 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
57 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 ...
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 ...
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
29 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 ...
2
votes
0answers
66 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
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
32 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
43 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
30 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
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)= ...
1
vote
0answers
49 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, ...
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?
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
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 ...
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 ...
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 = ...
9
votes
3answers
939 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 ...
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 ...
2
votes
1answer
37 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]}$ ...
4
votes
1answer
71 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 ...
-1
votes
2answers
73 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 ...
4
votes
1answer
79 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
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
21 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 ...
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\}$. ...
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 ...
1
vote
0answers
22 views

1-dimensional random walk with stops: prove it converges almost surely

Let $p\in (0,1)$ be fixed, and let $q=1-p$. A frog performs a (discrete time) random walk on the 1-dimensional lattice $\mathbb{Z}$ the following way: The initial position is $X_0=0$. The frog ...
2
votes
0answers
30 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 ...
1
vote
0answers
36 views

Why does $P(Z_{1}\leq x_{1},…,Z_{n}\leq x_{n},M>u) $ equal the following expression?

We consider the following setting: Let $Z_{1},...,Z_{n}$ be iid random variables with distribution function $H_{Z}$ and $u>0$ a constant. We set $M:= \sup_{n\in N} \sum_{k=1}^{n} Z_{k} $. In the ...
0
votes
0answers
68 views

simple random walk problem and its expected value

A man sat in a round table of 10 seats by himself and put his backpack in a seat next to him. In the end, He got drunk and did not remember which seat did he put his bag. He decides to find it. But he ...
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
48 views

Asymmetric Random Walk / Prove that $T:= \inf\{n: X_n = b\}$ is a $\{\mathscr F_n\}_{n \in \mathbb N}$-stopping time

Given random variables $Y_1, Y_2, ... \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
2answers
83 views

What is wrong with this answer to: expected time of return to origin in random walk on edges of a cube

(Quant Job interviews Questions and Answers Q3.22) Suppose we have an ant travelling on edges of a cube going from one vertex to the other. The ant never stops and it takes it one minute to go along ...
0
votes
1answer
51 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
1answer
38 views

Asymmetric Random Walk / Prove $E[X_{T \wedge n}] = (p-q)E[T \wedge n]$

Given random variables $Y_1, Y_2, ... \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
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 = ...