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
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
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 ...
0
votes
2answers
68 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
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?
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
43 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
40 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
66 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
52 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 ...
1
vote
0answers
41 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
30 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
33 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
42 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} ...
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
25 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 ...
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
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 ...
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
50 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
72 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 = ...
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
32 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
95 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
63 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 ...
3
votes
0answers
42 views

Randomized Chess [duplicate]

In chess, a rook can move either horizontally within its row (left or right) or vertically within its column (up or down) any number of squares. In an $8\times 8$ chess board, imagine a rook that ...
0
votes
1answer
57 views

Equality for transient Markov chains

Let $S_n$ be a transient, irreducible random walk starting from $0$. Then I want to prove that $$\sum_{n\geq0}{p_n(0,x)}=P_0[S_n=x\text{ for some }n\geq0]\sum_{n\geq0}{p_n(0,0)}$$ where $p_n$ is the ...
0
votes
0answers
38 views

Average number of steps to return to the origin of a random walk on a 2-d lattice.

Suppose I have a random walker on a 2-d square lattice with periodic boundary conditions with equal probability of going in any of the four directions. The walk ends when the walker reaches the point ...
0
votes
0answers
21 views

Harmonic function on 3-dimensional lamplighter group

Can anyone give an example of a non-constant bounded harmonic function on the Lamplighter group $\mathbb{Z}_2 \wr \ \mathbb{Z}^3$? This function should exist, because the random walk on this group has ...
2
votes
1answer
32 views

Conditional expectation of a random walk given that it is positive

Let $\{\xi_k\}$ is a sequence of iid random variables with $E(\xi_1)=0$ and $E(\xi_1)^2=\sigma^2<\infty$. Define the random walk $Y_n=\sum_{k=1}^n \xi_k$. Is it necessarily true that the ...
2
votes
1answer
65 views

Birth-death Process/Extinction

Random processes in Continuous time. Given that $\beta = \frac{4}{5}*\mu$ I have calculated that the birth rate $= 0.4$ and the death rate $= 0.5$. If the initial population $X(0)=6$, how many events ...
3
votes
1answer
123 views

Simple random walk on $\mathbb Z^d$ and its generator

I'm still trying to figure out definitions and properties of random walks on $\mathbb Z^d$. My goal is to work up to understanding some large deviation principles for the local times of such random ...
3
votes
1answer
75 views

Number of 'walks' which stay above 0.

Consider a set of distinct $n$ numbers where $a_i \in \mathbb{R} $ and $$\sum_{i=1}^{n} a_i = 0$$ A walk is defined to be the sum of the numbers, so that the $k$th position is the partial sum to $k$. ...
0
votes
0answers
37 views

Explicit formula for return probability of simple random walk

Is there an explicit formula for the probability that a simple symmetric random walk on $\mathbb{Z}$ starting from $1$ will not hit $0$ before time $t$?
2
votes
0answers
32 views

Return time for two independent one dimensional random walks

Let $X^1$ and $X^{-1}$ be two simple random walk in $\mathbb{Z}$ starting respectively from $1$ and $-1$. Let $\tau$ be the first time one of them reaches the origin, $$\tau = \inf \{ j \geq 0 \, : ...
0
votes
0answers
39 views

Expectation of a stopping time on an asymmetric random walk

Let $X_1, X_2, \cdots$ be i.i.d. such that $P(X_i=1)=p , P(X_i=-1)=1-p$. Denote $\tau_a = inf \; \{ n \ge 1 : S_n = a \}$ for any integer $a$, where $\tau_a = \infty$ if $S_n \neq a$ for all $n \ge ...
1
vote
0answers
74 views

Reflection principle for simple random walk

Let $(X_n)$ be a sequence of independent random variables, such that $P(X_i=1) = P(X_i=-1) = 1/2$. Then, the reflection principle states that for all $a > 0$, $$P(\max_{1\leq k\leq n} S_k \geq a) ...
0
votes
2answers
50 views

Root mean square distance explanation

We know that $D_{rms}=\sqrt N$ where $N$ is the number of steps taken by the random walker. Now,consider a situation where a random walker walks $2$ steps in positive direction in the first two ...
0
votes
1answer
25 views

symmetrical random walk P[M(n)=k]

On a symmetrical random walk, I am trying to deduce P[$M_{n}$ = k] = $(\frac{1}2)^n$ ${n \choose \frac{n+k}2}$ where n is the total number of steps and ${n \choose \frac{n+k}2}$ is the number ...