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

CLT for Random Walks [on hold]

I am having trouble with the following problem. How do I show that it converges in distribution to a normal gaussian distribution? Along with the following questions of the problem. Click for image
2
votes
0answers
30 views

Hitting probabilities in a random walk on a graph

Consider a random walk $(X_n)$ on the graph below, where we jump from a given vertex to one of its adjacent vertices with equal probability. I want to find: the probability that we hit $A$ before ...
2
votes
2answers
26 views

Divergence of asymmetric not-simple random walk

Consider a (not simple) random walk $S_n = \sum_{k=0}^n X_k$ where X_k are i.i.d and the mean $\overline{X}<0$. Is there is simple proof or a reference showing $P( \lim \limits_{k \to \infty} S_k = ...
0
votes
0answers
48 views

Random walk visiting $k$ distinct points

I have a random walk on $\mathbb{Z}$ with starting point $0$ and with length $n$ and possible steps to right, left or stay where you are, all with the same probabilities. I am interested in exact ...
2
votes
1answer
27 views

Expected number of zero crossings in 3 value random walk

Let's say we have a 1D random walk starting at the origin where we go up $1$ with probability $1/5$, down $1$ with probability $1/5$, and stay put with probability $3/5$. If we walk $n$ steps, what's ...
3
votes
0answers
32 views

$2D$ random walk stopping time

A $2D$ random walk starts at $(X_0, Y_0) = (k, k)$ where $k>0$ is an integer. At each step $(X_{n+1}, Y_{n+1}) = (X_{n}-1, Y_{n})$ or $(X_{n+1}, Y_{n+1}) = (X_{n}, Y_{n}-1)$ with the same ...
2
votes
0answers
32 views

Survival probability of a biased random walker

A random walker moves to $+1$ with probability $p$ and moves to $-1$ with probability $q=1-p$. If he starts at point $m$, what is the probability that he doesn't hit the point zero after $k$ steps, ...
0
votes
1answer
18 views

Probability of maximum of a random walk?

Let us consider a random walk denoted by Sn and let Mn be the maximums of the random walk. Now let us consider that this random walk will end at some point k. SO I am stuck how to prove this equality: ...
1
vote
1answer
23 views

Fluctuations in estimator of $\min\{p,1-p\}$

Let $X_1,\ldots,X_n$ be i.i.d. Bernoulli with some parameter $1/2$. Let $\bar{X}_n = \frac{1}{n} \sum_{i=1}^n X_i$. I am trying to show $$\mathbb{E} \min\{\bar{X}_n,1-\bar{X}_n\} \ge \frac{1}{2} - C ...
3
votes
1answer
40 views

Probability that two random walks on $\mathbb{Z}^2$ meet at the origin

Suppose $X,Y$ are symmetric, independent random walks on the lattice $\mathbb{Z}^2$. I am trying to find the probability: $$\mathbb{P}\big(X_n=Y_n=(0,0)\;\text{for ...
0
votes
0answers
11 views

Gaussian blur over (or random walk in) a surface mesh

Let $V$ be the set of mesh vertices, connected by edges $E$, forming a mesh that represents a surface embedded in $\mathbb{R}^3$. On this mesh a function $f:V\rightarrow\mathbb{R}$ is defined. For ...
2
votes
0answers
30 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
47 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
33 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
24 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
26 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
28 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
40 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} := ...
0
votes
2answers
40 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 ...
2
votes
3answers
28 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 ...
-3
votes
0answers
26 views

Asymmetric Random Walk with $+2$, $+1$ and $-1$ step sizes

Consider a one-dimensional random walk with $3$ kind of moves: with probability $p$ one step of size $l$ to right with probability $p$ one step of size $l$ to left with probability $r$ one step of ...
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
42 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 ...
1
vote
0answers
61 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
29 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 ...
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
34 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
91 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 ...
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
42 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
38 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
15 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
39 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 ...
0
votes
0answers
29 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
14 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
36 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 ...
0
votes
0answers
19 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
45 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
106 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
30 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
60 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
33 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
61 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
22 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, ...
0
votes
0answers
48 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 ...
2
votes
0answers
16 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 ...