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
73 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
65 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
95 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
215 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 ...
0
votes
0answers
60 views

Conditional expectation of random walking

Let $Y_1,Y_2,...$ be independent random variable such that $VarY_i = \sigma^2$ and $EY_i = \mu_i$. Let $$S_{n+1} = \sum_{j=1}^{n} Y_j$$ Find $E(S_{n+1}| S_n,...,S_1)$. My attempt: We have: ...
4
votes
1answer
97 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
320 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
80 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
50 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
26 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
0answers
56 views

Absorption probability in 1D RW with asymmetric step sizes, $ x<0 $

What is the probability of absorption at $ 0 $, as a function of position $ x $, for a 1D random walk (on $ \mathbb{Z} $) with asymmetric step sizes? For example, suppose that you can take two steps ...
0
votes
1answer
166 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
73 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
187 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
96 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
102 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
32 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
57 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
172 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
118 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
141 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
45 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
48 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
250 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
34 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
49 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
51 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
118 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
147 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
239 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 ...
0
votes
0answers
14 views

why $d$-dimensional symmetric random walk is not recurrent for $d \geq 3$

I want to understand why $d$-dimensional symmetric random walk is not recurrent for $d \geq 3$. I am not finding any good resource for this. Can someone help here ?
4
votes
0answers
62 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
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
111 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
32 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
120 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
85 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
298 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
94 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
67 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
73 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
412 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 ...
0
votes
0answers
26 views

Why must a stochastic process be at least second order in terms of differential equations?

A first order differential equation in $q(t)$ has a unique path through each possible value of $q(0)$. This is opposed to a stochastic process (e.g. random walk), where any place might be "hopped ...
0
votes
0answers
65 views

Identities in proving the arcsine law

In the course of proving the Arcsine Law for 1-dimensional random walk, there appear two combinatorial identities: (We are always considering a simple symmetric random walk of length $2n$) 1. ...
3
votes
0answers
45 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
75 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
139 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
36 views

Computing the sum of a Catalyn 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
48 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 ...