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
0answers
33 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
115 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 ...
1
vote
0answers
33 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
146 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
145 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
86 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
334 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
102 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
71 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
76 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 ...
3
votes
1answer
428 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
47 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
80 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
140 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
40 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
51 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
74 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
32 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
70 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 ...
2
votes
2answers
74 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
61 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
108 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
68 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
117 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
0answers
146 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
31 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
50 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
126 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
268 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
95 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
2answers
216 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
57 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
425 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
117 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
151 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
52 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
133 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
111 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
45 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} ...
2
votes
1answer
81 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
242 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$, ...
1
vote
1answer
195 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
95 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
87 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 ...
38
votes
1answer
1k 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: $$ ...
0
votes
0answers
120 views

On the second derivative of Wiener process

As we all know, continuous white noise is the derivative, with respect to time, of a Wiener process. My question is that does the second derivative of Wiener process exists? If so, what is it and how ...
2
votes
1answer
97 views

Computation of a mean (random sum)

Let $X_1$, $X_2$, ... be independent and identially distributed positive random variables and define the sum $S_n = X_1 + X_2 + ... + X_n$. Consider the first time $N$ where $S_N \ge b$ with a given ...
2
votes
1answer
80 views

A continuous random walk of length 1

Suppose one starts at origo in in the plane and takes $N$ steps of length $1/N$ in a random direction, what is the distribution of the resulting distance from origo as $N$ approaches infinity? For one ...
1
vote
1answer
68 views

Absorbing state for a collection of random walks

Further to this question; having learned some stuff since I posed it. Consider a collection of random walks $X_i$ which take finite integer values. These evolve as time-inhomogeneous Markov Chains. ...
1
vote
2answers
57 views

Random walk confusion

If a ransom walk is binomial (1/2 probability of going forward, 1/2 backward) why isn;t the variance a) $\sigma=(\frac{n}{4})^.5$ b) instead of $\sigma=(n)^.5$ these sources seem to give ...