For questions on random walks, a mathematical formalization of a path that consists of a succession of random steps.

learn more… | top users | synonyms

1
vote
0answers
15 views

Conditional expected number of visits in symmetric random walk with two absorbing barriers

Consider a symmetric random walk on vertices $\{0,1,2,\ldots,n\}$. Suppose that we are at vertex $1$ initially. At each step, we move left with probability $1/2$ and right with probability $1/2$. We ...
1
vote
0answers
15 views

Conditional probability of a random walk hits position $b$ in $n$ steps

This question comes from my question Modified gambler's ruin problem: quit when going bankruptcy or losing $k$ dollars in all Generally, I know the probability that a random walk hits position $b&...
5
votes
1answer
78 views

Modified gambler's ruin problem: quit when going bankruptcy or losing $k$ dollars in all

In each round, the gambler either wins and earns 1 dollar, or loses 1 dollar. The winning probability in each round is $p<1/2$. The gambler initially has $a$ dollars. He quits the game when he has ...
1
vote
1answer
111 views

States of a Group Ring

Let $G$ be a finite group and $\mathbb{C}G$ its group ring. Now taking the approach of orangeskid, consider the space $\mathbb{C}G$ as a Hilbert space with orthonormal basis $\delta^g$. $G$ acts on ...
1
vote
0answers
24 views

Random walk on a connected graph

I am reading a book and I have a problem understanding why a relation holds. Assume that we have a time-homogeneous random walk on a connected graph $G=(V,E)$. For $o\in V$, the roundtrip from $o$ ...
0
votes
0answers
7 views

Splitting Probability Within a Finite Time [on hold]

Let $\mathcal{X}=\{x_i\}_{i=1}^{N}$ be a subset of $\mathbb{Z}$. For $j\in(1,N)$, what is the probability that the first element of $\mathcal{X}$ encountered by a simple 1D random walk is $x_j$ and ...
1
vote
0answers
14 views

“Return probability” to origin of a variant of the random walk.

Let $\{\epsilon_t\}_{t\ge0}$ be an iid sequence of random variables and let $\lambda>1$. I am interested in the following process: Let $X_0 = 0$ and $$ X_{t+1} = \lambda(X_t+\epsilon_t). $$ This ...
-1
votes
2answers
47 views

What is the probability of random walking ant to be at a position after some finite steps on an infinite grid? [on hold]

Is it even calculable? What if the grid is infinitely dimensional? Lets say that it is a simple random walk, and probability to move to any neighboring position is equal, but other types are also ...
1
vote
0answers
26 views

Area under staircase walk

If I create a random lattice path from $(0,0)$ to $(n,k)$, taking only north or east steps $(1,0)$ or $(0,1)$, with equal probability, the so called staircase walk, what are the moments of the area ...
0
votes
0answers
20 views

Random walk on a segment with infinite time

Given a point particle on a segment $L$ of length $1$, $(L=[0,1])$, assume the particle moving randomly in such a way: $p_{(k+1)}=p_k+\delta_k$ where $p_{k+1}$ is the position on the segment at time $...
1
vote
0answers
23 views

Return probability of a SRW in an even number of steps

I am looking for some references for the following problem. Consider a graph $G$ and a simple continuous time random walk $(X_t)_{t\geqslant 0}$ on this graph. Consider the family of events $(e_t)...
1
vote
1answer
70 views

Exact Expected Value of Random Walk?

i just read in Noga Alon's Book That the exact expected value of a random walk is which was a question in putnam competition... Sn=X1+X2+...Xn Which Xi are independent uniform random in {-1,+1} ...
43
votes
7answers
11k views

Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1

How does one prove that a simple (steps of length $1$ in directions parallel to the axes) symmetric (each possible direction is equally likely) random walk in $1$ or $2$ dimensions returns to the ...
1
vote
2answers
46 views

Probability of $\max_i \{X_i\} = X_0$ where $X_i$ are iid binomial

We have $M$ Binomial random variables, where $X_0 \sim $ Bin$(n,p)$ and $X_i \sim $ Bin$(n,1/2)$. Suppose $p > 1/2$. I'm interested in the probability that $\mathbb{P}(\max \{X_1,\dots,X_M\} \geq ...
0
votes
1answer
18 views

Random walk mean number of visits to state before absorption

This is from Stirzaker's book Random Processes. Suppose we have a simple random walk with probability going "up" p, "down" q. At time 0 it stats at 0, so $$S_0 = 0$$ Now let $u_b $ be the mean ...
0
votes
0answers
18 views

Bernstein-type inequality for simple random walk

Let $(X_n)$ be a sequence of random walks: $P(X_i=1) = P(X_i=-1)=1/2$. Denote $S_n = X_1+...+X_n$. Show that, for $0 < \epsilon \leq 1/4$ $$P\bigg\{\bigg | \frac{S_n}{n} \bigg| \geq \epsilon \bigg\}...
0
votes
1answer
22 views

Continuous random walk

I am reading a book that is talking about continuous random walk. It first starts with defining one dimensional discrete random walk as starting at point 0 and move to either to the right or left at ...
2
votes
2answers
172 views

What are the assumptions for applying Wald's equation with a stopping time

I am trying to understand the assumptions under which I am allowed to apply Wald's equation for a sum of a random number $N$ of random variables $X_n$, $1\leq n\leq N$. There seem to be several ...
1
vote
1answer
19 views

Compute covariance matrix random walk

Consider a random walk on the square lattice $\mathbb{Z}^2$ with diagonal jumps of size $2$, i.e. the jump probabilities are $$P(X_1 = x) = \begin{cases} \frac{1}{4} & \quad \text{if } ...
1
vote
2answers
45 views

Approximation of probability that the walker is at the origin after $2n$ steps

I'm reading Lawler's "Lecture on comtemporary probability". There are $2$ parts in the book that I don't understand: "In order for the walker to be at the origin after $2n$ steps, the walker will ...
0
votes
1answer
35 views

Stopping times of random walk with time dependent absorbing barriers

I have a Bern$(p)$ random walk ($Y_i = 1$ with probability $p$ and Y_i = 0 with $1-p$) with two absorbing boundaries, $A: Y^i \leq t_i$ and $B:Y^i \geq d_i-t_i$. Now, both $d_i$ and $t_i$ are evolving ...
0
votes
1answer
46 views

Three-Dimensional Random Walk

A particle starts at an origin $O$ in three-space. Thinking of point $O$ as the center of a cube 2 units on a side. One move in this walk sends the particle with equal likelihood to one of the eight ...
0
votes
0answers
22 views

Show that $S_n/n$ converges in probabilty but not almost surely - Borel Cantelli

Let $X_n$ be independent random variables with the following distribution: $$ P(X_n=\pm n)=\frac{1}{2(n+1)\log (n+1)}, \;\;\;\; P(X_n=0)=1-\frac{1}{(n+1)\log (n+1)} $$ and let $S_n=\sum_{k=1}^n X_k$....
2
votes
0answers
27 views

'Finding' a normally distributed random variable

Let a random variable $Z$ have a standard normal distribution. Suppose that we start at $0$. We 'walk' right, along the number line, till we reach $a$. We then turn around, walk back, past $0$, till ...
0
votes
0answers
39 views

Integral of non-Gaussian distribution, random walk?

I would like to evaluate $$ F = \frac{\mathbb{E} \left\{\left(\int_0^T x^3(t) dt \right)^2\right\}}{\mathbb{E} \left\{\left(\int_0^T x(t) dt \right)^2 \right\} } \approx \frac{\mathbb{E} \left\{\left(...
1
vote
3answers
37 views

Probability of reaching net 4 heads when tossing coin 8 times

This problem is #19 from the AMC 12 2016A, and goes as follows: Jerry starts at $0$ on the real number line. He tosses a fair coin $8$ times. When he gets heads, he moves $1$ unit in the positive ...
2
votes
0answers
32 views

joint-probability of Langevin equation

I am working on Langevin equations: $\frac{dx}{dt}=u$ $m\frac{du}{dt}= -\gamma u + \theta(t)$ where $\theta(t)$ is delta-correlated in time Gauss-distributed noise with zero-mean $\langle \theta (...
3
votes
0answers
45 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 ...
1
vote
0answers
29 views

The probability that the d-dimensional symetric random walk returns to the origin - is this relatively short proof correct?

Let $p_n$ denote the probability of returning to the origin after n steps. If n is odd, $p_n = 0$. The main insight is that $\sum_{n=0}^{\infty}p_{2n}$ is asymptotically ~ $C \cdot \frac{1}{n^{d/2}}$ ...
2
votes
2answers
29 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
52 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
34 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
33 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
37 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
20 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
29 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 n^...
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 some}\;n\,\big|\,X_0=Y_0=(0,N)\big)$$...
0
votes
0answers
14 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
32 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
49 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
41 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 ...
0
votes
2answers
42 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 n}...
1
vote
1answer
26 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
28 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
29 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
42 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} := inf\{...
2
votes
3answers
33 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
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 ...
0
votes
1answer
27 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
vote
2answers
188 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 ...