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
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
52 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
49 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
31 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
29 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
68 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
47 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
112 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
46 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
86 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
48 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
43 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
50 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
69 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
43 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 ...
1
vote
0answers
42 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
67 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
139 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
76 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
40 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
35 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
44 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$....
1
vote
0answers
89 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
57 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
26 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 ...
2
votes
0answers
37 views

Test a law-of-iterated-logarithm-like result, with numerical simulation

I have a non-standard random walk $S_n$ for which the increments are not exactly independent (I could describe it, but it would be a totally different long and complex topic). I expect it to have ...
4
votes
1answer
73 views

Numerical evidence of law of iterated logarithm (random walk)

The law of iterated logarithm states that for a random walk $$S_n = X_1 + X_2 + ... X_n$$ with $X_i$ independent random variables such that $P(X_i = 1) = P(X_i = 1) = 1/2$, we have $$\limsup_{n \...
2
votes
1answer
32 views

An example of a reducible random walk on groups?

Random walk on group is defined in the following way as a Markov chain. A theorem says the uniform distribution is stationary for all random walk on groups. If the random walk is ...
0
votes
1answer
42 views

calculate mean and variance from multivariate probability-generating function in random walks

Suppose in a biased random walk, $r(i,n)$ is the probability that a particle appears at position $i$ at time $n$. The corresponding probability generating function is $$ R(z,s)=\sum_{n=0}^\infty \...
0
votes
0answers
53 views

heuristic for expected number of visits random walk

What is the heuristic argument that explains why, on $\mathbb{Z}^d$, $d \geq 3$, the expected number of visits of a random walk starting from the origin at $x$ is of order $$ O(|x|^{2-d})? $$
-1
votes
1answer
56 views

The expected range covered by a random walk

The question that I have been struggling with lately is: If we have a one-dimensional random walk of length $n$ (consisting of $n$ steps) with discrete steps $1$ and $-1$, with probabilities of ...
2
votes
0answers
76 views

Let $\{ X_{n}\} _{n\geq1}$ be IID s.t $\mathbb{E}[X_{i}]=0$ and $|X_{i}|\leq K$. Show $S_{n}$ visits $[-K,K]$ infinitely often.

Let $\left\{ X_{n}\right\} _{n\geq1}$ be a sequence of IID random-variables s.t $\mathbb{E}\left[X_{i}\right]=0$ and $\left|X_{i}\right|\leq K$ . Let $S_{n}=\sum_{i=1}^{n}X_{i}$ , I want to show ...
0
votes
0answers
37 views

Number of ways a dice can roll every side equally many times for the first time after x rolls

This problem is best viewed as a walk on a $d$-dimensional integer lattice with integer steps corresponding to various results of a dice roll. For a normal 6-sided dice, these would be (1,0,0),(-1,0,0)...
0
votes
0answers
38 views

3d symmetric random walk passes infinitely through any particular line

I'm trying to solve problem 27 from Chapter XIV An Introduction to Probability Theory Volume I by William Feller, http://ruangbacafmipa.staff.ub.ac.id/files/2012/02/An-Introduction-to-probability-...
2
votes
2answers
40 views

Random Walk Definition

I have just begun studying this script about Random Walks, but I'm having trouble with a definition that is given there right at the beginning (page 10). We're looking at Random Walks on the square ...
1
vote
1answer
58 views

Random Walk Stopping Time 2

Let $(X_1,X_2,...)$ be i.i.d random variables, with $P(X_t=1)=P(X_t=-1)=1/2$. Then $S_t= \frac{1}{t}\sum_{i=1}^{t}X_i $ is a zero mean random walk. Let $\tau$ be the stopping time corresponding to ...
0
votes
2answers
44 views

Random Walk Stopping Time

Let $(X_1,X_2,...)$ be i.i.d random variables, with $P(X_t=1)=P(X_t=-1)=1/2$. Then $S_t= \frac{1}{t}\sum_{i=1}^{t}X_i $ is a zero mean random walk. Let $\tau$ be the stopping time corresponding to ...
2
votes
1answer
73 views

Probability that a biased asymmetric random walk reaches the origin

I am working on the following problem for my probability class and I am a little stuck: A particle moves at each step two units to the right or one unit to the left, with corresponding ...
0
votes
0answers
22 views

Expected value of a random walk given value at previous time

I have a homework question dealing with random walks. One part of the question required me to find the probabilities $p$ and $q$ such that $$E[M_1] = M_0$$ which I achieved. Having found these, the ...