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
2answers
29 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
1answer
26 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 ...
-3
votes
0answers
22 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 ...
2
votes
3answers
25 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
24 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 ...
1
vote
1answer
25 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 ...
-1
votes
0answers
18 views

What is the distribution of the random walk? [closed]

Suppose $s(0),s(1),\ldots,s(t)$ forms a simple random walk. What is the distribution of $\dfrac{s(t)}{\sqrt{t}}$ where $t$ is any time related variable. Does this question tend towards the central ...
1
vote
2answers
175 views

1-d random walk probability bound calculation problem

I'm recently reading the paper about digital fountain code "LT Codes" by M. Luby. There is a statement seems simple with the author "The probability a random walk of length $k$ deviates form its mean ...
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
55 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
25 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
6 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
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 ...
2
votes
1answer
81 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 ...
0
votes
0answers
25 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} ...
1
vote
1answer
30 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 ...
-1
votes
0answers
14 views

probability őf a particle s(t) when t=0

In a symmetric random walk of particle s(t) what is the probability that the particle will return to origin at t=0 i.e P(S(t)=0)?
9
votes
0answers
106 views

probability of completing a self-avoiding chessboard tour

Someone asked a question about self-avoiding random walks, and it made me think of the following: Consider a piece that starts at a corner of an ordinary $8 \times 8$ chessboard. At each turn, it ...
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
0answers
37 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 ...
1
vote
1answer
561 views

Simple Probability Matrix

Question: Consider a simple model that predicts whether you pass your next test or not based on the result of your previous test. If you pass your previous test, then you have 0.2 chance you will ...
0
votes
1answer
14 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
32 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
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
41 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 ...
1
vote
1answer
978 views

Expected hitting time of one of two barriers

In the webpage "hitting time of one of two barriers", the probability that a non symmetric random walk hits one of two barriers is computed. The walker starts from $x=0$ and the barriers are located ...
3
votes
1answer
33 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
18 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
41 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 ...
-1
votes
0answers
25 views

How have these probabilities been derived (using 'symmetry')?

I'm looking at the following section of my lecture notes, where it is discussing the probability that a simple random walk, which starts at the state $X_{0}=0$, will return to the origin. I ...
3
votes
3answers
104 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
1answer
58 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
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
30 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
59 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 ...
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
1answer
24 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 ...
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 ...
0
votes
2answers
62 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 ...
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 ...
0
votes
0answers
89 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?
2
votes
1answer
38 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
38 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
63 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
47 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
35 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 ...
0
votes
1answer
34 views

Create a transition table

I am trying to create a transition table for a markov chain but I have difficulties. Consider a game, where each player (of two, lets call them A and B) has a fixed given probability of scoring 3 ...