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

learn more… | top users | synonyms

2
votes
1answer
30 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
42 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
44 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})? $$
-1
votes
1answer
51 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
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 ...
0
votes
0answers
37 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
36 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, ...
2
votes
2answers
37 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
55 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
42 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
66 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
22 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
25 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 ...
0
votes
1answer
50 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
53 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
30 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
54 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
37 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
28 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
46 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 = ...
10
votes
3answers
1k 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
45 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
33 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
53 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
115 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
65 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
85 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
94 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
28 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
70 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
47 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
130 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
113 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
28 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
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 ...
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 ...
1
vote
1answer
127 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
61 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
133 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
66 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
46 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
54 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
73 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 = ...
0
votes
1answer
32 views

Computing the expected number of steps of a random walk

I have a Markov chain with probability $p_{ij}$ to transition from state $i$ to state $j\, (p_{01} = 1)$. How can I calculate the expected number of steps it takes to go from one state to another?
1
vote
1answer
47 views

random walk and calculating the probability of paths

Consider a random walk $(X_n)_{n≥0}$ with $p = 0.7$, starting from $X_0 = 3$. Find the probability that $X_{10} = 5$, but $X_n ≥ 1$ for $n = 0, . . . , 10.$. Essentially what I got from the ...
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 ...
0
votes
2answers
52 views

Recurrent random walk

Let $S_n=S_0+\sum_{i=0}^n{X_i}$ be a random walk with increment distribution $p$ and n-th step distribution $p_n(x)=\mathbb{P}[S_n=x\mid S_0=0]$. We say that a random walk is recurrent if ...
3
votes
3answers
64 views

Random Walk And Stochastic-Processes

Assume that $P(X_i = 1) =1/2, P(X_i =-1)= 1/4,\text{ and }P(X_i = 0)=1/4$. Consider the random walk starting at 1 given by $$S_n = 1 + X_1 + X_2 + \cdots + X_n$$ where $X_1,X_2, ...$ are i.i.d. ...
1
vote
0answers
39 views

Expected number of vertex-pairs without any simple path in between

Consider a random undirected graph $G(n, p)$, with $n$ vertices and each edge is added independently with probability $p$. The goal is to find the expected number of vertex-pairs without any simple ...
1
vote
1answer
38 views

Show that a martingale is not $L^1$ convergent

Consider the symmetric random walk $S_n$ on $\mathbb{Z}$. The process $Z_n=\exp(uS_n-n \ \log(\cosh(u)))$ for $u\in \mathbb{R}$ is a positive martingale with $E(Z_n)=1$ for all $n\geq 1$. $Z_n$ is ...