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
41 views

Non - nearest neighbor random walk in $\mathbb{Z^{2}}$

$\textbf{Problem:}$ let {$X_{n} : n ≥ 0$} be any symmetric random walk on $\mathbb{Z^{2}}$ whose jumps have finite second moment. That is, $X_{0} = 0$ , {$X_{n} − X_{n−1} : n ≥ 1$} are mutually ...
4
votes
1answer
196 views

Random walk on $\mathbb{Z}^d$

Problem Let $\{X_n\}_{n=0}^{\infty}$ be a random walk on $\mathbb{Z}^d$ such that; $X_0=(0,0,\cdots,0)$ and $\{X_n-X_{n-1}\}_{n=1}^{\infty}$ are mutually independent, identitically distributed ...
0
votes
1answer
28 views

Find a asymptotic upper bound for $\sum_{n=N}^{\infty}p_{ii}^{(n)}$ for a asymetric one-dimensional simple random walk

For asymmetric one-dimensional simple random walk, that is $$P(X_n = X_{n-1} + 1) = p = 1 - P(X_n = X_{n-1} - 1)$$ for some $p \ne 1/2$, provide an asymptotic upper bound for ...
0
votes
1answer
22 views

Estimating a point on graph from multiple random values.

I am developing a mobile game app that needs to find a point on a map based on a set of observed values. The app allows users to touch points on a map to the closest proximity of where they think an ...
3
votes
0answers
78 views

Expected minimum of a finite random walk.

So I couldn't find any resource for how to calculate the expected minimum of a random walk. Since it is such the minimum of the random variables are actually not independent as they are cumulative ...
1
vote
0answers
83 views

Hitting time Distribution of a Gaussian Random Walk

I am trying to find out the exponential decay rate of the Probability $Pr(T>n)$ where $T$ is the first hitting time of a gaussian random walk with i.i.d random variables i.e. ...
2
votes
1answer
43 views

Bounds on median of random walks

If $k$ random $n$-step $\pm 1$ walks start at 0, and the $i$th walk ends at position $X_i$, how big is $\text{median}_i \, |X_i|$? Is there a bound along the lines of $\text{P}(\text{median}_i \, ...
1
vote
3answers
344 views

Distribution of the first passage time of a Gaussian random walk

Does anyone know the distribution for the first passage time of a Gaussian random walk i.e. $$ S_n = \sum_{i=1}^n X_i $$ where $X_i$ are iid normally distributed random variables. The first passage ...
3
votes
1answer
85 views

Random walk where increment depend on current position

Consider the following stochastic process, $$b(i+1) = b(i) + \xi_i (b_i),$$ where $\xi_i(b_i) \in \{-1, k \}$ are the independent increments having the following distribution: $$\begin{align} P (\xi ...
0
votes
1answer
88 views

2 dimensional random walk - hit of targets

Consider a random walk in $\mathbb{Z}^2$, $x(j) = x(j-1) + \xi_j$, where the increments are random variables independent and identically distributed with finite support, the expectation $m := ...
2
votes
1answer
144 views

central limit theorem for high dimensional random walk

Consider random walk in $\mathbb{Z}^d$, $d>1$, with $x(t) = x(t-1) + \xi$, where $\xi$ has some probability distribution in $\mathbb{Z}^d$ with finite support, expectation $m = \sum_{v \in ...
4
votes
0answers
227 views

Random walk on $\mathbb{Z}$ with more than two possible steps

Let be $\{X_n\}_{n\in \mathbb{N}}$ random walk on $\mathbb{Z}$. Let be $$P(X_{n+1} = k + a| X_n = k)= p_a$$ for $a\in \mathcal{A} \subset \mathbb{Z}$. Let say that $X_0 = 0$. I am interested in ...
4
votes
1answer
109 views

Drunk problem involving probability of being in a circle.

This is the typical drunk problem wherein the person is confined to moving either to the North, South, East, or West but never diagonally with just one step. A step has a length $L$. What is the ...
1
vote
1answer
604 views

First step analysis on random walk

Let us consider random walk on integers {0,1,...,N} where $P(N,N)=1$,$P(0,1)=1$, $P(N,N-1)=0$ and all other connections have probability $\frac{1}{2}$. Using first step analysis, compute $p_{00}$ for ...
4
votes
1answer
90 views

random walk in a certain environment

Consider the following random walk in one dimension, starting from $r(0)=0$. $$ r(i+1) = r(i) + \xi, $$ where $\xi(i, r(i))$ is an increment with distribution $P(\xi=1) = \frac{c^{r(i)}}{i-r(i)+1}$ ...
1
vote
1answer
59 views

ruin of the gambler with probability to die

Consider a random walk on $\mathbb{Z}$ starting from $i >0$. With probability $p$ it moves to the nearest neighbor on the left, with the same probability it moves to the nearest neighbor on the ...
1
vote
0answers
36 views

Prove equilibrium theorem without irreducibility and aperiodicity

I have to solve the following question: Consider a random walk Markov chain on $S = \{1, 2, \ldots, 100\}$. If the chain is between 2 and 99, it selects one of the adjacent states with equal ...
0
votes
1answer
247 views

Probability for asymmetric random walk

How to express this in equation form(in terms of position(x) and time(N)), like the one for symmetric random walk, $\displaystyle P(x,N) = \frac{N!}{(\frac{N+x}{2})! ...
0
votes
1answer
98 views

random walk with dependent increment

Consider the following sort of random walk. The position of the walker at time $t$ is represented by the random variable $r(t)$, with $r(0) = 0$. The variable satisfies the following equation, $$ ...
5
votes
1answer
247 views

The random walk of two drunks

The problem is such: two drunks start at either end of an alleyway of length n. Apart from at the ends, they each move one step forwards or one step backwards randomly. At the ends of the alley they ...
0
votes
1answer
181 views

Random walk with weighted probabilities

Taking a walk on $\mathbb{N}$, starting at 1, I need to find out how many steps I expect to take before returning to the origin, as a fraction. For each step, I either walk forward, backward, or stay ...
0
votes
2answers
129 views

How Do You Calculate Probabilities of Random Events Occuring in Sequence?

So I have a series: $f(x_{n+1})=x_n \pm t$ and $f(x_0)=W$ What I'd like to calculate is the probability in terms of $t$ and $W$ (assuming they're any constant $W>t$) that any $f(x_q)=0$ for all ...
1
vote
0answers
35 views

Horizontal drift of snowflake

I wonder if the random-walk dynamics of falling snowflakes is understood well enough to estimate the likely sideways drift of a single snowflake falling in a windless environment, from its cloud ...
0
votes
1answer
93 views

Random walk, discrete time, 1D, unequal discrete steps

Can someone point me towards a resource that will help me analyse a 1-d random walk where each step can take 1 of say 6 values with known probabilities. Not a continuous time random walk, time ...
1
vote
0answers
208 views

Random walk - expected distance not from origin

We have an assignment on random walk, but I can't figure out the expected value. The situation is as follows: In the origin there is a hunter that shoots at a duck, but misses. The duck starts at a ...
2
votes
3answers
128 views

Random walk problem in the plane

Let a particle in the plane $R^2$ executes random jumps at discrete times $t= 1, 2, ...$. At each step, the particle jumps from the point it is a distance of lenght one. The angle of any new jump ...
17
votes
1answer
158 views

height of domino tower

Suppose you are building a domino tower using identical pieces of unit length. You place a new domino piece, one at a time, on the top of the tower. However there is a random error in the placement of ...
0
votes
0answers
56 views

Expected hitting time of one barriers

I have learned the skill to deal with Expected hitting time of one of two barriers. Now I have a similar one.The walker starts from x=0 and the barriers are located in x=+n.The walker can move one ...
0
votes
1answer
50 views

Need a candidates for a random-walk, but limited, perturbation.

I have some time-dependent data that I would like to perturb. Just pulling numbers out of a uniform or normal distribution won't suffice. The jump in perturbation from one time to the next should ...
1
vote
1answer
366 views

Random Walk, Recurrence relation

Q: There is a particle that moves on the positive section of the real line with an absorbing barrier at 0. It moves two units to the right with probability p and one unit to the left with q = 1 - p at ...
1
vote
0answers
38 views

New stochastic calculus

I am interested in Kagi and Renko approach and hope I can use it for a random walk process. I searched for it on internet but I couldnt find any basic material to read about it. Can someone please ...
1
vote
0answers
58 views

Why do candlestick plots seem to show a cyclical structure?

One oddity I notice is that if a random or quasi-random data series such as price data is plotted, it is similar to a random walk, but if the same data series is plotted using candlesticks ...
2
votes
0answers
61 views

mean displacement inequality for random walk with drift away from zero

Suppose $X_n$ is a nearest neighbor random walk on the integers with transition probabilities biased towards moving away from zero but with the bias asymptotically vanishing as you move away from ...
4
votes
2answers
139 views

The problem of the drunkard in a valley.

We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. ...
3
votes
1answer
188 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
281 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
66 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
34 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
144 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
35 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
149 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
230 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
118 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
638 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
127 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
106 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
81 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
705 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
56 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
90 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 ...