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
2answers
52 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
35 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
41 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
31 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
50 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
107 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
60 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
81 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
92 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
27 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
68 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
116 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
35 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
70 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
125 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
58 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
128 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
64 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
51 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
71 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
30 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
46 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
61 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
49 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
62 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
38 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
15 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
130 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
46 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
122 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
37 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
26 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 ...
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 ...
1
vote
0answers
51 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. ...
1
vote
1answer
70 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
27 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 ...
0
votes
1answer
58 views

Help with a random walk problem.

Let $\xi_1,\xi_2,...$ be a sequence of random variables such that $\xi_i=-1$ or $\xi_i=1$ for $i=1,2,...$. Let $x(n)$ be the position of a random walk at time $n$, i.e. $x(n)=\xi_1+\xi_2+...+\xi_n$. ...
2
votes
1answer
48 views

Why is this true with random walks?

Let $S_n=\sum_n{X_n}$ a random walk with $P[X=1]=p=1-P[X=-1]$. Prove that for any $k \in Z$ $P[\cup_{n \geq1} \{S_n\geq k\}]= (P[\cup_{n \geq1} \{S_n\geq 1\}])^k$ I do not understand why is this ...
1
vote
1answer
51 views

Help with a symmetric random walk problems

Given a simple symmetric random walk $X_1,X_2,…,X_n,…$ where $X_t,t=1,2,…$ are i.i.d random variables distributed according to $\Bbb P(X_t=1)=1/2$ and $\Bbb P(X_t=-1)=1/2$. Define partial sum ...