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
32 views

Three person simultaneous random walk

So let's say you have 3 people walking 100m, from one wall to another. Each move each person independently draws 3 integers, each between -10 and 5 with equal probability. You, as the coordinator, ...
4
votes
1answer
51 views

What is the expected number of steps in a random walk from leaf to leaf in a full binary tree?

Let $h \geq 2$ be a natural number. Consider a complete binary tree of height $h$. Say we take a random walk starting from the "leftmost" leaf. What is the expected number of steps before the "...
1
vote
1answer
46 views

(Random Walk) Probability of Returning to Origin

I want to find out the probability that a 1-dimensional asymmetric random walk, which steps to the right with probability $p > \frac{1}{2}$ and to the left with probability $1-p$, ever returns to ...
1
vote
1answer
26 views

Equal distribution only for finite dimensional distributions

Two processes $(X_t)_{t \in T}$, $(Y_t)_{t \in T}$ are known to be equal in distribution if and only if they agree on all finite-dimensional distributions, i.e., for all $t_1$, $t_2$, $\ldots$, $t_n$, ...
2
votes
0answers
28 views

Is every discrete martingale a time-changed simple random walk?

While going through the book by Revuz and Yor titled 'Continuous Martingales and Brownian Motion', I came accross the notion of time change. In a nutshell, if X is a stochastic process and C is an (...
0
votes
1answer
29 views

Recurrence of 0 in a random walk

Assume $\mathcal{S} := \{0, 1, \cdots \}$, $p(0,1)=1$ and $p(n,0)=p(n,n+1)=\frac{1}{2}$ for $n=1,2, \cdots$. Is $0$ recurrent or transient? So, basically this is an irreducible, closed but infinite ...
0
votes
2answers
45 views

Expectation of stopping time on a random walk

Assume $X_1 , X_2 , \cdots$ are i.i.d. with distribution Bernouli$(\frac{1}{2})$, i.e., $P(X_i = 0)=P(X_i=1)=\frac{1}{2}$. Denote $S_0 := 0$, $S_n := \sum\limits_{i=1}^n X_i$, and $\tau_{1000} := inf\{...
0
votes
2answers
43 views

Simple Random Walk - Why are these two events the same?

Let $S = (S_n)_{n \geq 1}$ be a simple random walk. We denote the hitting time of a point $b$ by $\tau_b = \min \{i \geq 1 : S_i \geq b\}$. My text says that the events $\displaystyle\{\max_{k \leq n}...
2
votes
3answers
40 views

Binomial Random Walk

For the random walk with step sizes: $S_i = \begin{cases} &+1 &\text{probability} &p, \\ &-2 &\text{probability} &q=1-p \end{cases}$ Let $T_n = \sum_{i=1}^mS_i$ be the ...
0
votes
1answer
26 views

Probability of one outcome in random walk

This question is really throwing me off: Lets say there's two players, A and B. Each game consists of betting \$1. Gameplay ends when one player has all of the money. Player A starts with \$3, B ...
4
votes
3answers
45 views

A walk on the chessboard with conditions!

A 16 step path is to go from (-4,-4) to (4,4) with each step increasing in either the x-coordinate or the y-coordinate by 1. How many such paths stay outside or on the boundary of the square $-3<x&...
1
vote
0answers
62 views

Probability of the martingale staying non-negative.

Here is a question on martingales (given after third graduate lecture on the subject). Let $X_n$ a martingale with respect to the natural filtration and such that $X_0 = 0$, assume that $\frac{1}{2} ...
1
vote
1answer
31 views

distance from the origin in a simple random walk on $\mathbb Z^2$

let $S_{n}= \sum_{i=1}^{n}X_i$ be a simple random walk on $\mathbb{Z}$, with $S_0 = 0$. $X_i = 1$ with probability $p$ and $X_i = -1$ with probability $1-p$. It can be shown that $$\mathbb{P}(S_n=i\...
0
votes
0answers
7 views

What is the probability of this Markov Jump process remaining in this state?

Suppose you had a time homogeneous Markov jump processed defined by the following transition diagram I'm assuming that this means that the process remains in state $0$ for time $t$ with probability ...
1
vote
1answer
40 views

Simple symmetric random walk on $\mathbb{Z}$

Let $S_n$ be the simple symmetric walk on $\mathbb{Z}$ (prob go forward = prob go backward = $1/2$) and let $N = \inf\{n \geq 0 : S_n = 0\}$ be the hitting time at $0$. Then I would like to verify ...
2
votes
1answer
96 views

Ito integral of average of the square of a Wiener signal?

How do we evaluate the average of the square of a Wiener signal? Standard case: Typically, the signal average is $S(t)=\frac{1}{T}\int_{0}^{T}s(t)dt$, where we can write the integral in Ito form $S(...
1
vote
1answer
11 views

What does the notation $P_{\overline{MM}}(t)$ mean in this context?

The notation $P_{\overline{MM}}(t)$ is used in part (iii) of the following question: I'm unsure of exactly what this notation represents. My guess would be that it represents the probability that a ...
0
votes
0answers
55 views

Probability distribution of maximum of absolute value of a random walk

Suppose that we have a random walk $\{B_t\}_{t\ge0}$. The maximum of $B_t$ is well known: $M_t=\sup_{0\le s\le t} B_s$ has probability $Pr(M_t>x)=2Pr(B_t>x)$. Is there a known result for the ...
2
votes
1answer
39 views

Stability of a dimer on a square grid after $n$ random steps

On a white square grid there are two black cells. Each step consists of each of the cells 'moving' in one of the four directions with equal probability $p_0=1/4$ (a cell can't stay in the same place). ...
0
votes
1answer
16 views

Is the normalized graph laplacian row stochastic?

Let $W$ be the adjacency matrix of a graph $G$, where $w_{ij} \in \{0, 1\}$ for an unweighted graph, or real values otherwise. And let $D$ be the diagonal weight matrix, where $D_{i, i} = \sum_j w_{i, ...
1
vote
1answer
50 views

Lower bound for expectation of absolute sum of Rademacher

Let $\epsilon_i$ be i.i.d. Rademacher random variables (i.e., $\epsilon_i$ takes value $\pm 1$ with equal probability). The upper bound $\mathbb{E} |\sum_{i=1}^n \epsilon_i| \le \sqrt{n}$ follows from ...
1
vote
0answers
36 views

Laplacian in spherical coordinates - brownian motion

Consider the Laplacian equation on the unit sphere, for a vector $f$. $\theta$ is polar angle, and $\phi$ is azimuthal angle. The Laplacian in spherical coordinate is : $$ \Delta f = {1 \over r^2} {\...
0
votes
0answers
15 views

How do you find the expected Cover Time of a graph?

I can only find resources that give an upper bound on the cover time, but not how to find the exact expected cover time of a graph. Somebody told me it's related to the coupon collector problem, but I ...
0
votes
0answers
43 views

Random walk with reflection and skips in linear system

Let's take a case of simple and linear Random walk (0, 1...n) with only one absorbing state n and reflecting state -1, which we can define as: P (move right at state i) = 1/2 and P (moving left at ...
3
votes
1answer
40 views

Random walk on the positive integers with reflecting boundary

Consider a Markov chain $X$ on the positive integers where for each $n$: $$n\longrightarrow 1,\;2,\;3\;\dots \;n,\;n+1$$ with equal probability, and $n\longrightarrow m$ with zero probability if $m>...
0
votes
0answers
21 views

Exercises on the following topics on Markov Chains

We are being taught the following topics in Markov Chains: 1) Markov Chain Monte Carlo: Hard Core model, Counting random q-colourings of a graph 2) Total variation distance for a Simple Symmetric ...
0
votes
1answer
49 views

Leaving time of a set

I want to prove the following result. Let $S_n$ be a symmetric irreducible random walk on the integers (d=dimension). Claim: If $x\in A$ and $P_x(T_A=\infty)>0$ then $\forall \epsilon>0\exists ...
3
votes
3answers
113 views

Random Walk of a drunk man

Problem Statement: From where he stands, one step toward the cliff would send the drunken man over the edge. He takes random steps, either toward or away from the cliff. At any step his probability ...
0
votes
0answers
38 views

Random walk in high dimensional space with stationarity

I have a vector of high dimension ( say 100). When I take a random walk ( i.e add a step value to each components of the vector, the step value being drawn randomly drawn from standard normal ...
0
votes
1answer
62 views

Application of CLT to random walks

Let $X_1,X_2,\ldots$ be an iid sequence such that $P\{X_1 = 1\} = p$, $P\{X_1 = -1\} =p$ and $P\{X_1 = 0\} = 1-2p$. We have that $E[X_1] = 0$ and $E[X_1^2] = 2p$. Define $S_n = \sum_{i=1}^nX_i$ and $...
0
votes
1answer
33 views

Discrete random walk bounded in an interval

Suppose I have a discrete random walk with equal probabilities, and the particle begins at $x=0$. The process goes on indefinitely. What is the probability that the particle will never leave $[-n,n]$, ...
1
vote
0answers
34 views

Product of expectations is a martingale

Consider a probability space $(\Omega, \mathcal{F}, P)$ and random variables $X_0, X_1, \ldots , X_n$ adapted to the filtration $\{\mathcal{F}_t\}_{t\geq0}$. Assume furthermore that each $X_n$ is ...
1
vote
2answers
65 views

Non-symmetric random walk on $\mathbb{Z}^2$

a random walker, walks on a lattice with non-negative coordinates. In each step, if he is in a positive coordinate, say $(a,b)$ where $a,b>0$ he will go to $(a-1,b)$ or $(a,b-1)$ with same ...
0
votes
1answer
25 views

When almost sure limit coincides with L2 limit

Let $S_n$ be a random walk and $\tau$ be a stopping time. Let $\tau$ be a stopping time for the random walk and define $\tau_N := \min \{ \tau, N \}$, which is a bounded stopping time. Assume that I ...
1
vote
1answer
25 views

Bounding the probability of landing at any point for a random walk on a tree

Fix $m\geq 2$ and a vertex $v_0$ in an infinite connected $2m$-regular tree, (in other words, the Cayley graph for the free group on $m$ generators) and consider the random walk on the tree starting ...
0
votes
0answers
30 views

Probability of being within a standard deviation in a modified random walk?

I am only familiar with the very basics of random walks, so I can not judge how trivial my question is. Assume that we have a generalised random walk where now instead of the outcomes being $\{1, -1\}...
0
votes
0answers
51 views

Density function of $\sqrt{(\mathcal{N}_1(\mu,\sigma^2))^2+(\mathcal{N}_2(\mu,\sigma^2))^2}$ (Random walk)

I have 2D random walk and I would like to find out what distance I will travel after 200 steps. So I introduce two random variables $Z^{(200)}_x$ and $Z^{(200)}_y$ which tell me probabilities of my $x$...
2
votes
0answers
19 views

Multiplicative Super-martingales

Let $\{X_n\}$ be a stochastic process which is strictly positive, i.e. $X_n > 0$ almost surely for all $n$. It then follows that $\{Z_n = \log(X_n) \}$ is a well-defined stochastic process as well....
0
votes
2answers
83 views

Number of steps in a 2D random walk return to origin

We have a random walk in 2D. In this many dimensions, we return to the origin with probability $1$. However, the number of steps it takes to do so seems to vary greatly from computer simulations I've ...
0
votes
0answers
92 views

Expected infimum of a 1d random walk

Consider a simple symmetric random walk on $\mathbb{Z}$ starting from $0$, $S_n$. Let $I_n := \inf\{S_0, S_1, S_2, \ldots S_n\}$. Is an explicit formula for $E[I_n]$ known?
0
votes
1answer
28 views

Symmetric Simple Random Walk - Definition Clarification

I'm finding conflicting answers everywhere, including in my own notes. In the phrase "symmetric simple random walk", which part, "symmetric" or "simple" refers to having a probability of $0.5$ to go ...
2
votes
1answer
48 views

Why does infinite expected number of returns to the origin imply a random walk returns to the origin with probability 1?

In proving that a simple symmetric 2-d random walk a.s. returns to the origin, the proofs generally start by showing (*) that the expected number of returns to the origin is infinite, and then use a ...
1
vote
0answers
42 views

Random Walk on a Grid

Consider the $k \times (k+1) \times (k+2)$ grid G. Starting from a point $\vec x = (x_1,x_2,x_3)$, we perform the following random walk. We choose a coordinate $i \in \{1,2,3\}$ uniformly at random ...
3
votes
0answers
68 views

Proving how to reduce a Brownian walk on a plane to a line (2D to 1D)

I have a Brownian motion on a plane and would like to find the time of when it is expected to hit a set of parallel lines, i.e the hitting time. In order to do so, I understand that I can reduce the ...
0
votes
0answers
25 views

Most visited vertex in a random walk with a place dependent drift

Consider the following Markov chain on $\mathbb{Z}$: $$ P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}} $$ Do there exist constants $c,C>0$ such that $$ c\cdot P^t(z,z) \...
1
vote
2answers
55 views

Variation on Vandermonde's identity

How can you show that $$ \binom{2n}{n}^2 = \sum_{m=0}^{n} \binom{2n}{2m} \binom{2m}m \binom{2n-2m}{n-m} $$? I was fooling around with random walks, and apparently both expressions are supposed to be ...
3
votes
1answer
37 views

Let $X_n$ be a one-dimensional random walk with $p \neq 0.5$. Show that $P(\lim_{n \rightarrow \infty} \frac{1}{n} X_n = 0)$ equals $0$.

Let $X_n$ be a one-dimensional random walk on the integers that starts at $0$ (as normally) but has $p \neq \frac{1}{2}$, i.e. so that it moves to its right neighbor with probability $p$ and left ...
1
vote
0answers
42 views

What is the invariance principle of Random Walks?

Several papers I have read allude to the fact that a random walk is invariant; however, I have been unable to find any reference to support this fact. Could anyone explain why random walks are ...
0
votes
0answers
35 views

Why number of positive paths is twice the number of non-negative ones in random walk

In Shiryaev "Probability" text book the author states in paragraph 10 "Random Walk. II. Reflection Principle. Arcsine Law" Hence to verify (9) we need only establish that $2L_{2k}(S_1>0, \...
0
votes
1answer
34 views

Random walk and expected value

Consider a classical symmetric random walk that starts at origin $x=0$ and lasts for $N$ steps. If $x=-1$ is reached, a walk is terminated. What is the expected value of this process? I divided a ...