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
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
132 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
67 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
137 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
50 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
78 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
35 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
48 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
64 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
53 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
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
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
125 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
40 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
30 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
56 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
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 ...
0
votes
1answer
59 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
49 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 ...
2
votes
1answer
56 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 $S_t=∑_{...
2
votes
0answers
34 views

An inequality for standard random walk.

How to prove that $\Bbb P_1(\lim\sup_{n\to\infty}\frac{\log \bf{x}(n)}{\log n}\le \frac{1}{2})=1$, with the suggestion that $\bf{x}(n)$ goes to $\infty$ like $\sqrt{n}$. Here $\bf{x}_n$ is the ...
1
vote
1answer
81 views

Random walk in a graph

This is a question about random walk from vertex $s$ in a graph (can be directed), which is defined in the following manner: The random variable $X_0$ (whose possible values is the set of vertices) ...
1
vote
0answers
81 views

Wald's Identity for non-i.i.d. Case

I am looking for Wald's Identity for non-i.i.d. case as discussed in the following links: https://en.wikipedia.org/wiki/Wald%27s_equation What are the assumptions for applying Wald's equation ...
3
votes
2answers
51 views

Random Walk UpperBound

enter image description hereIs it possible to prove that for any symmetric Random Walk the absolute value of its partial sum $S_n$ never exceeds $\sqrt{2 \pi n}+\sqrt{\pi / 2}$ ? I run some ...
0
votes
0answers
22 views

Transience of random walks starting from each of the sites which have been already visited

Consider a simple random walk on $\mathbb{Z}^d$, $d \geq 3$, which starts from the origin. As $d \geq 3$, there is a positive probability that the random walk never visits the origin again. Now, let ...
0
votes
0answers
17 views

Discounted stochastic linear regulator problem with a transversality condition: I think I have a solution, need proof

Consider a sequence of i.i.d. random variables $ \left\{ {{\varepsilon _t}}\right\}_{t = 1}^\infty $ with $E\left( {{\varepsilon _t}} \right) = 0 $ and $ E \left( {\varepsilon _t^2} \right) = {\...
0
votes
1answer
26 views

Calculating infinite sum from a random walk in 1-dimension

Consider the random walk on $\mathbb{Z}$ with 1-step transition probabilities $p_{i,j} = \frac{1}{2}$ iff $|i - j| = 1$. Then the probability that the first time that the chain returns from $i$ to $i$ ...
1
vote
0answers
15 views

How does one reconcile the fact that a random walk is non-mean reverting with Polyas recurrence theorem?

In particular, Polyas theorem says that in 2 or 1 dimension the symmetric random walk is recurrent so that it has probability 1 of returning to zero. Yet, I have read that random walks are known as ...
3
votes
0answers
36 views

$S_n \in [-a,a]$ for some $a$ infinitely often

Suppose we have iid r.v.s $X_n \in \mathbb{R}$ with mean $0$ variance $\sigma^2$, I wonder is it true that we have $\exists a>0,$ $$P(S_n \in [-a,a] \text{ infinitely often} )=1,$$ where $S_n =\...
0
votes
0answers
34 views

Continuation of random walks

I have trouble understanding the following identity: $\mathbb{E}[e^{i\theta\cdot T_t}]=\sum_{j\geq 0}{e^{-t}\frac{t^j}{j!}\mathbb{E}[e^{i\theta\cdot S_j}]}$. I see that somehow it uses the following ...
0
votes
1answer
36 views

What's the difference between a white noise process, IID process and random walk?

Just need some clarification between these concepts. Is an IID with mean zero white noise process? Also is random walk a summation of white noise process?
1
vote
1answer
149 views

What is the relationship between eigenvector and computing PageRank?

I read several papers about PageRank and didn't get stuck in understanding the idea of PageRank because it is simple, but I got stuck in computing PageRank, those papers talk about some mathematical ...
1
vote
0answers
39 views

Symmetric random walk about $y=2$.

Consider a simple (symmetric) random walk $p=q=\frac{1}{2}$ and $(X_n)_{n\geq 0}$ with $X_0 = 0$. Using the reflection principle, find the probability that $X_{12} = -4$ and $X_1 < 2$, $X_2 < 2$,...
2
votes
1answer
69 views

What is a good/extensive undergraduate level reference on random walks?

Random walks on graphs, expected times for different things, gambler's ruin. I seem to either stumble on some pretty advanced texts about group representation theory or texts that briefly mention it ...
1
vote
1answer
57 views

Random walk - Markov chain

I have a problem.If we start at place $0$ and the probability to go right is $p$ and the probability to go left $q$. I need to calculate the probability after 100 steps that the maximum place when we ...
2
votes
1answer
39 views

A Game of Random Walk plus Combinatorics

1 Original and reasons for this game This game is actually changed from Geoffrey and David's Book [1] (section 11.2, page 445) and its accompanying solution manual [2]. The book gives the result ...
0
votes
0answers
44 views

Brownian motion determining probability of success for binomial experiment

Suppose you have some particle that moves according to brownian motion in one dimension (x), in discrete time steps. Suppose you have, for each position x, a probability P(x), which specifies the ...
4
votes
0answers
71 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
1
vote
0answers
62 views

Random walk evaluated by a Poisson process

I found the following proposition and I want to prove it. Let $S_n$ be a discrete-time random walk with increment distribution p and $N_t$ be a Poisson process with parameter $1$.Then the process $...