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
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
37 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
20 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
109 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
32 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
63 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
24 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
50 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
17 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
77 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
90 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
26 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
47 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
41 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
54 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
32 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
31 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 ...
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 ...
1
vote
0answers
34 views

How to use Borel-Cantelli specifically to show that the probability of a simple random walk returning to the origin in finite time is 1?

Suppose we have that $X_i$ are iid random variables with $P(X_i =1) = P(X_i = -1) = 1/2$ and that $X_0 = 0$. Then, we define the simple symmetric random walk to be $S_n = \sum_{i=1}^n X_i$. We define ...
4
votes
0answers
48 views

For a simple random walk $S_n$ and for a stopping time $\tau$, what is the intuitive interpretation of $P(\tau < \infty) = 1$?

Suppose we have a simple random walk $S_n$ and we define a stopping time to be $\tau = min\{n: S_n = A \ \text{or} \ S_n = -B\}$. That is, we stop the first time we hit $A$ or $-B$. With this, I have ...
0
votes
1answer
48 views

Expected # of Returns in a Symmetric Simple Random Walk

The problem involves a 1-D symmetric simple random walk starting from the origin. Let $N_{n}$ denote the the number of returns by time n. Show that: $$ E[N_{2n}]=(2n+1) \dbinom{2n}{n} (\frac{1}{2})^{...
0
votes
1answer
30 views

Why is this stopping time the result of intersections instead of unions?

On page 54 of the book "Basic Stochastic Processes" of Brzezniak and Zastawniak, author proposes this example: A coin is tossed repeatdely and you win or lose 1 pound depending on which way it lands. ...
0
votes
0answers
27 views

When do we have finite fourth moment

Let's consider a random walk $S_n=\sum_{i=1}^n{X_i}$ starting from the origin, with the following conditions: finite range, symmetric distribution, irreducibility (with respect to the state space), ...
1
vote
0answers
66 views

Random walk on one dimension (Randam walk on $\mathbb{Z}$)

I have to solve the following situation about Random walk : Let consider random walk in one dimension. Assume that each step we might move forward with probability $p$, and might move backward with ...
0
votes
0answers
21 views

Limit transition probability

I would like to prove the following: Let $p$ be the increment distribution of a discrete time random walk in $\mathbb{Z}^2$ which we assume to be irreducible, symmetric and of finite range, so $$S_n=...
0
votes
1answer
43 views

Showing a d-dimensional symmetric random walk returns infinitely often to a position that it already occupied

I have the following problem on random walks: Consider a $d$-dimensional symmetric random walk which starts at the origin at time $n=0$. Show that the walk has probability $1$ of returning ...
0
votes
3answers
53 views

Prove closed form for $\sum_k (2k)^2\binom{2n}{k+n} $ and $\sum_ k(2k+1)^2\binom{2n+1}{k+n+1}$

The following identities, are true, but I am having trouble proving them: $$ \left\{\begin{array}{lll} \sum_k (2k)^2\binom{2n}{k+n} &=& (2n)2^{2n} \\ \sum_ k(2k+1)^2\binom{2n+1}{k+n+1} &=...
9
votes
0answers
111 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 ...
1
vote
1answer
30 views

Number of walks of length $n$ on $\mathbb{Z}$ times a square

Let $a_n$ denote the number of self-avoiding walks of length $n \in \mathbb{N}$ on $\mathbb{Z}$ times a square, that is $4$ parallel copies of $\mathbb{Z}$ that are sideways connected in parallel ...
0
votes
0answers
45 views

Probability of ever visiting a point in $2$D random walk

At point $A$, the probability of moving up is $q$ and the probability of moving down is $p$. At point $B$, the probability of moving left is $x$, the probability of moving right is $y$ and the ...
2
votes
1answer
74 views

Random walk (Exercise 3.11.39 from Grimmett and Stirzaker)

A particle performs a random walk on the non-negative integers as follows. When at the point $n\ (> 0)$ its next position is uniformly distributed on the set $\{0, 1, 2, \ldots, n + 1\}$. When it ...
1
vote
0answers
52 views

Intersection of two simple random walks

Suppose that $X_n$ and $Y_n$ are independent, symmetric, one-dimensional simple random walks, where $X_0 = 0$ and $Y_0 = N$ for some $N \in \mathbb{N}$ where $N$ is even. I would like to show that the ...
4
votes
2answers
75 views

Stopping time on an asymmetric random walk

Suppose that we are given an asymmetric random walk whose step is defined as $P(\xi_i = 1) = p$ and $P(\xi_i = -1) = 1-p$, where $p >1/2$. The hitting time, $T_x$ is defined as $\inf{\{n : S_n = x\...
2
votes
0answers
44 views

Useful bounds on stopping time for a positive drift random walk

I was studying SPRT (Sequential Probability Ratio Tests) and there was a section (in an online article I was reading) which proved optimality of SPRT using some approximations. Unfortunately, this ...
1
vote
2answers
42 views

Probability of getting destination with closed roads

So the question asks: We want to drive from A to B. See the road map in the figure below. Because of snow, each of the five roads (R1−R5) can be closed with probability $p$, independently of all other ...
1
vote
1answer
33 views

Number of distinct vertices in a random walk on a graph

Let $G$ be a graph on $n$ vertices. Is it possible to calculate the expected number of distinct vertices seen in a simple random walk of length, say, $k < n$? Moreover, how is this affected when $...
1
vote
4answers
97 views

Problem about simple probability

I guess that this will be really simple for you guys, but i have no foundation in probability. Please, help me to find not only the answer but also what i need to learn in order to be able to solve ...
1
vote
0answers
49 views

Random walk with bounds and pauses in 1-d

EDIT: There was a point that I had misunderstood and hence modifying the question slightly. The boundary at $N$ is sticky, not bouncing. The boundary at $1$ is a bouncing boundary. How do we ...
3
votes
1answer
65 views

Proof of semigroup property for family of operators

I'm studying a proof of a large deviations principle and I'm having trouble with a part that is concerned with the semigroup property of a family of operators. Assumptions $(X_t)_{t\geq0}$ is a ...