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

learn more… | top users | synonyms

3
votes
1answer
259 views

What is the probability a random walk hits x before it hits y?

This problem was motivated by my bitcoin trading and recalling some of my math education back in the day. I thought I'd ask people who know this much better than I... Suppose there is a continuous, ...
1
vote
0answers
394 views

2-dimensional random walk

I have a question which I anticipated to be rather easy initially. After some googling, however, I realized it is actually not that easy. It concerns a 2-dimensional random walk with constant unit ...
4
votes
0answers
74 views

random walk on real line

Suppose I start at $A>0$ and every period I either move a distance $B$ to the right with probability $p$ or a distance $C$ to the left with probability $1-p$. The expected move is positive: ...
3
votes
0answers
36 views

Number of times above a linear boundary for a finite variance random walk

I consider a random walk $(S_n)$ with mean zero and finite variance, and $\epsilon>0$. Is it true that $$ \mathbb{E}\left[\sum_{n=0}^{+\infty} 1_{S_n>n\epsilon}\right] < +\infty \quad ? $$ ...
6
votes
1answer
201 views

Colored path in a randomly colored grid

A friend of mine asked this question a while ago which I couldn't find any appropriate answer for it. I'd appreciate any comment or help. If one colors each unit square with black/white of an $m ...
2
votes
0answers
39 views

Using Lyapunov's CLT for a project

I'm trying to model the location of a drunkard who starts at $x=0$ and moves towards $x=20$ with probability $0.6$ and to the left with $0.4$, when $x=20$ he moves in either direction with probability ...
7
votes
1answer
155 views

Two people are looking for each other. Is it faster for both to actively search, or for one to search while the other stays still?

Choose among two actors randomly and place the chosen actor at the origin. Place the other actor in the unit circle uniformly at random. Both actors move at the same speed. Both actors are said to ...
0
votes
1answer
341 views

Reflected Simple Random Walk

Suppose $W = (W_{n})_{n\geq0}$ is a symmetric random walk on $\mathbb{Z}$ with $SRW(\frac{1}{2})$. Define $\hat{W_{n}} = (\hat{W}_{n})_{n\geq0}$ by $\hat{W_{n}} := |W_{n}|$. Show that for $y \gt 0$: ...
1
vote
2answers
156 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 ...
1
vote
1answer
1k views

Meaning of root mean square distance in random walk

This is a question about a simple random walk problem where we want to measure the average distance from the start in various experiments of N steps each. If d is distance moved during one such ...
0
votes
1answer
170 views

Strong Law of Large numbers, prove expression is Standard Normal

Question: "Let $X_{1},X_{2},\cdots$ be a sequence of independent random variables such that $X_{n}$ is binomial with parameters $2n-1$ and $p=\frac{1}{2}$. If $$Y_{n} = \frac{2(X_{1}+X_{2}+\cdots ...
1
vote
0answers
180 views

A matrix-multiplication random walk

Let $x \in \mathbb{R}^n$. Consider an $n\times n$ matrix $A$. Suppose we're interested in how $||A^nx||$ grows with $n$, the answer (excluding pathological cases) is that it scales exponentially with ...
2
votes
1answer
84 views

How to model a stochastic process, continuous in stepsize, which converges against a simple random walk?

I want to compute the probability distribution for a stochastic process with discrete number of steps, where each real value has a nonvanishing probability to be the next stepsize. And I want to ...
5
votes
1answer
1k views

Expected number of steps in a random walk with a boundary

Let's say I am trying to climb a flight of $N$ stairs. Each time I want to take a step, I flip a fair coin. Heads means I take a step up; tails means I take a step down. If I'm at the bottom of the ...
3
votes
0answers
65 views

Upper bounds on the sum in a Martingale process

My question is related the hitting time of not a random walk, but a more general martingale process. Suppose we start with an arbitrary $x_0=x$ with $0\leq x\leq 1$. We compute $x_{t+1}$ from $x_t$ ...
0
votes
1answer
119 views

First-passage probability with absorbing boundary at origin (No Laplace)

I have the following problem which I would like to solve without using Laplace transform. Can you possibly help or provide pointers? What is the first-passage probability, and mean first-passage time ...
2
votes
0answers
147 views

Finding functions where the increase over a random interval is Poisson distributed

I'm trying to construct a type of function $f(t_1, t_2)$ that counts the number of deterministically simulated Poisson events between two points in time. We can use a single valued function ...
1
vote
2answers
50 views

Computing the sum of a Catalan sequence— Random-walk motivated

How would one go about computing the following?: $$\sum_{n=0}^\infty (.5)^{2n+1} \cdot \frac{{2n}\choose{n}}{n+1}$$ The motivation is that this gives the probability that a random walk on a number ...
1
vote
1answer
69 views

Proving that the eigenvectors of this class of matrices are the binomial coefficients

So I'm trying to figure out the behavior of this system: you have $N$ coins, and every step, you choose one of the coins randomly and flip them. Now we imagine a bazillion of these systems. We call ...
1
vote
0answers
81 views

Markov Chain Problem

I have been stuck on this question for days and really need some help. There are two methods, A and B, to finish a work. Method A succeeds with probability 1/3, but if it fails one tries method B ...
3
votes
1answer
37 views

Bounding the number of visits for each site of a random walk by a sequence

Recently, I asked if, for each $k>1$, a transient random walk visits each site less than $k$ times a.s.. You can find the question here: Visits from a transient random walker on the integers This ...
2
votes
1answer
84 views

Visits from a transient random walker on the integers

Consider a random walk $\{S_n\}$ on $\mathbb{Z}$ with forward probability $p>\frac12$. It is known for such a transient RW that each site is a.s. visited only finitely many times. However, is it ...
3
votes
2answers
93 views

Random walk on one-dimensional lattice - understanding the expression $pe^{i\theta} + qe^{-i\theta}$

I've started reading the book - First Steps in Random Walks and in the very first example in Chapter 1 they talk about a random walk on a one-dimensional lattice. If we consider a particle starting ...
1
vote
2answers
69 views

For a Gaussian Random walk where $x_n$ is the sum of $n$ normal random variables, what is $P(x_1 >0, x_2 >0)$?

I know that the events $x_1 >0$ and $x_2 >0$ are not independent, but I can't think of a way to find a conditional probability so I can solve this. Thanks!
0
votes
1answer
140 views

Recurrence for dependent random walks.

Let $\{X_i\}_{i\in\mathbb{N}}$ be a sequence of random variables taking values in $\{\pm e_1,\pm e_2\}$, where $\{e_1,e_2\}$ is the standard basis of $\mathbb{R}^2$. If $\{X_i\}$ are i.i.d. ...
2
votes
1answer
135 views

Martingales of random walk

Let $S_n$ be a random walk process defined by $$S_n=X_1+\dots+X_n$$ with $X_i \sim N(\mu,\sigma^2)$ and $X_i$ are i.i.d. I'm trying to prove that the quantity $(S_n-n\mu)^2-n\sigma^2$ is a ...
5
votes
2answers
181 views

How can we directly see that the number of random walks starting and ending at the origin is ${n\choose n/2}^2$?

In an infinite two-dimensional square-shaped grid, we define four directions, north, south, east, west. We thus have $4^n$ random walks of length $n$. If we end where we started, for every north step ...
7
votes
1answer
175 views

Recurrence of a certain class of $2$-$d$ random walks

As is well known, a symmetric random walk on $\mathbb{Z}^d$ (the lattice of $d$ dimensional vectors with integer components) is recurrent if and only if $d=1,2$. In particular it is transient for ...
2
votes
0answers
46 views

Sums of independent random variables

I was unsuccessful in deriving a good estimate of the distance below. Let $(X_{n})_{n \geqslant 1}$ be a sequence of i.i.d. random variables, and let $(\varepsilon_{n})_{n\geqslant 1}$ be a sequence ...
1
vote
0answers
75 views

Random Walk in confined region and loop configurations

Suppose I take a random walk on a 2 dimensional square lattice, but this lattice plane has a finite size, e.g. Dx*Dy. I can not cross the boundary, my step length is the lattice cell size, I either go ...
0
votes
1answer
182 views

Solving a differential equation (Lattice Laplacian)

Suppose that $ p_n(t) $ is the probability of finding n particle at a time t. And the dynamics of the particle is described by this equation : $$ \frac{d}{dt} p_n(t) = \lambda \Delta p_n(t) $$ ...
12
votes
1answer
313 views

Random walks and diffusion limits

Imagine a long and narrow cylinder of radius r and a point particle that moves in the region bounded by the cylinder. The motion is specified as follows: starting at a point on the inner wall of the ...
3
votes
3answers
104 views

A fly on a triangle?

A fly is on the vertex of a triangle. It can move left with probability $\frac 12$ and right with probability $\frac 12$. What is the expected number of moves till it reaches its starting point? ...
1
vote
1answer
223 views

Symmetric random walk and Borel-Cantelli

Let $(X_n)$ be a sequence of i.i.d. r.v. such that $\mathbb{P}(X_n=1)=\mathbb{P}(X_n=-1)=\frac{1}{2}$ Also let $$S_n= \sum_{k=1}^{n} X_k$$ I am asked to show, using Borel–Cantelli lemma, that ...
1
vote
2answers
264 views

Calculating expected value of random walk with one stop value.

I know that for a random walk with two stop values, the expected value of the number of steps needed is $ab$ where the stop values are $-a$ and $b$ and the initial position is at 0. What about for ...
1
vote
2answers
77 views

Random Walk with Edges

The setup for the specific problem that led to this question is as follows: You are playing a game at a casino and have \$10,000; The bank has \$2,000. You are making \$1,000 bets, with a equal ...
2
votes
1answer
952 views

Expected time for winning in biased Gambler's Ruin

Consider the random walk $X_0, X_1, X_2, \ldots$ on state space $S=\{0,1,\ldots,n\}$ with absorbing states $A=\{0,n\}$, and with $P(i,i+1)=p$ and $P(i,i-1)=q$ for all $i \in S \setminus A$, where ...
1
vote
0answers
158 views

Bayesian random walk

Suppose that, at first, I am trying to estimate the mean and standard deviation of some data that I assume to be normally distributed. My prior is gaussian with mean $\mu_0$ and variance $\sigma^2_0$. ...
0
votes
3answers
199 views

Probability of having X more heads than tails for N tosses.

Giving a a fair coin, and tossing it N times, in how many possible outcomes would there be a point wherein there were more heads than tails tossed, ie, net heads.
1
vote
1answer
54 views

Concerning the distribution of a random variable of a random walk that doesn't make any sense to me

Let $\Omega = \{w = (x_1, \dots, x_N) | \; x_i \in \{-1, 1\}\}, \;X_k(w) = x_k, \;S_n(w) = \sum_{k=1}^n X_k(w), \; S_0(w) = 0.$ After having proven a few theorems about $S_n$, in our lecture about ...
1
vote
0answers
135 views

Brownian motion, rate of large events

Given the most simple brownian motion: $$ \dot x(t) = \sigma \eta(t)$$ where $\langle \eta(t)\eta(t')\rangle=\delta(t-t')$, I define as large event in a time-frame $\tau$ a portion of the trace ...
1
vote
0answers
165 views

Stopping time and martingale for random walks

Let $X_0=0, X_1, X_2,\dots, X_N$ be i.i.d. random variables, with Gaussian distribution $\cal N (0,1)$. For $k=0,\dots, N, S_k=\sum_{i=1}^k X_i$ and $\tau=\min\{k:S_k^2\geq N-k\}$. So $\tau$ is a ...
1
vote
0answers
54 views

Random walk - proving limits exist

Consider the random walk $\{X_k\}_{k\geq0}$ on $\mathbb{Z}$ with transition probabilities $$\begin{cases} p_{i,i-1} = p_{-1} &> 0 \\ p_{i,i+1} = p_{1} &> 0 \\ p_{i,i+2} = p_{2} ...
4
votes
2answers
1k views

Random walk on a cube

Start a random walk on a vertex of a cube, with equal probability going along the three edges that you can see (to another vertex). what is the expected number of steps to reach the opposite vertex ...
2
votes
1answer
95 views

What is the probability that the robot steps on the bomb?

Suppose a robot is initially placed at $0$ on the number line, and is programmed to take steps of integer length in the positive direction between $1$ and $k$, inclusive, where $k$ is a positive ...
2
votes
3answers
325 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ with $p_1$, ...
4
votes
1answer
408 views

Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I ...
2
votes
0answers
114 views

random walk with possibility to freeze

Consider a Random Walk on a one-dimensional lattice. The walker starts moving at time $0$ from $x=0$. At every step, the walker moves to the right with probability $p$, to the left with probability ...
2
votes
1answer
111 views

law of large number modified statement

The weak law of large number states that, given $Y_n = \sum_{k=1}^{n} X_k$, where $X_k$ are random variables independent and identically distributed with finite expectation $\mu$, $$ \forall ...
48
votes
1answer
2k views

Identity for simple 1D random walk

The question is to find a purely probabilistic proof of the following identity, valid for every integer $n\geqslant1$, where $(S_n)_{n\geqslant0}$ denotes a standard simple random walk: $$ ...