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
29 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)= P(...
1
vote
0answers
55 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
55 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
38 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
31 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 walk....
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
48 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
35 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
58 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
129 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
66 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
87 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
99 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
73 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 motion....
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
141 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\}$. I'...
4
votes
1answer
120 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
30 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
137 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
69 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
142 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
70 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 F_n\}...
0
votes
1answer
52 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
56 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
79 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 = ...
1
vote
1answer
38 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
49 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
66 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
54 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 $\mathbb{P}[...
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
40 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 $...
0
votes
0answers
16 views

Bound on Poisson process

In a proof of a theorem I have the following situation: $N_t$ is a Poisson random variable with parameter $t$. From a corollary we get the following result: Let $X_1,X_2,\dots$ be independent, ...
1
vote
0answers
132 views

What is the probability a random walk crosses a line before another?

Let $n \geq 0$, $X_n$ be a random walk, where $X_{n+1} = X_n + 1$ with probability $p$, and $X_{n+1} = X_n - 1$ with probability $1-p$. $X_0 = 0$ Let $l_n, r_n$ be a sequence of integers, where for ...
1
vote
1answer
47 views

Applications of Random Walks for undergraduate students

Students are asking for applications of discrete random walks in "real life" problems. By real life they mean financial applications and industry. We have two more weeks on this subjects and I'm ...
1
vote
0answers
46 views

Triangular inequality for n-th step distributions

Assume that $p_n$ is the $n$-th step distribution of a random walk with state space $\mathbb{Z}^d$, i.e. $p_n(x,y)=\mathbb{P}(S_{n+1}=y\mid S_0=x)$, where $S_n=S_0+\sum_{i=1}^nX_i$ with $X_i$'s i.i.d. ...
2
votes
0answers
126 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 ...
0
votes
1answer
41 views

Number of random walk paths crossing horizontal line

I have series of binomial variables $\xi_1, \xi_2, \dots, \xi_n$ which form a random walk. Variables can be $\pm 1$ with probability $\frac{1}{2}$ and we define $S_n = \sum_{i=1}^n \xi_i$. We start ...
1
vote
0answers
31 views

Eigenvector/value of a biased random walk with a sink and a wall

Suppose you have a one dimensional random walk, with a wall at $S=0$ and a sink at $S=n$. The walk is biased so the odds of moving down vs moving up are $b:1$. More concretely, the transition graph is:...
0
votes
0answers
26 views

Expected steps for ant on a cube, [duplicate]

There is an ant on a vertex of the cube, he's trying to get to the opposite vertex, what's the expected steps for it to take before reaching the opposite vertex? Ant can move in any directions along ...
2
votes
0answers
58 views

Expected number of steps for a random walk- robot

A robot is located at the top-left corner of a m x n grid The robot is trying to reach the bottom-right corner of the grid, he can move randomly in any of the directions: up, down, left, right. ...
0
votes
1answer
74 views

Properties of a random walk [closed]

First of all, I know nothing about Markov chains, and I'd like to prove the following without using the theory around them. Let $(M_{n})_{n\geq 1}$ be a random walk over $\mathbb{Z}$, starting at $...
0
votes
0answers
30 views

Mean absolute distance for a symmetric random walk

I have found that the mean absolute distance for a symmetric random walk after n steps can be computed using this product: What can be deduced from this? For example how can variance be computed ...
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 ...