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

learn more… | top users | synonyms

0
votes
0answers
37 views

Random walk on an infinite resistive lattice

I have been referring to a paper http://arxiv.org/abs/physics/0405135 to determine the effective resistance using random walks for an infinite square resistive lattice Though the author seems to ...
0
votes
0answers
74 views

proving null recurrence of random walk (Markov chain)

How would I prove that the zero state of a random walk with a positive probability of staying in the same state is null recurrent. (sorry if this isn't a random walk and just a Markov chain.) eg. ...
2
votes
0answers
55 views

Random Walk Return Probabilities – Is there an intuition to understand them?

Every mathematician is familiar with the result (due to Pólya) that for a random walk in a $d$-dimensional lattice, the probability $p(d)$ for returning to the origin eventually is $1$ if $d=1,2$, but ...
2
votes
2answers
49 views

Generate random sample with three-state Markov chain

I have a Markov chain with the transition matrix $$\pmatrix{0 & 0.7 & 0.3 \\ 0.8 & 0 & 0.2 \\ 0.6 & 0.4 & 0}$$ and I would like to generate a random sequence between the three ...
0
votes
1answer
18 views

Please explain $E[S_{min(n,T)} ]= E [S_{0}]=0$

If $S_{n}$ is a simple random walk i.e $X_{k}= +/- 1$ with prob = 0.5 T = inf {n > = 0 |$S_{n}$ = 1} is a stopping time. T is finite almost surely. .Explain $E[S_{min(n,T)} ]= E [S_{0}]=0$ I know ...
0
votes
0answers
47 views

Reversing a random walk on a hypergraph

I'm looking for resources (books, papers, etc) that will suggest how to reverse random walks on an invariant directed hypergraph. If you're curious, more details are below. In my problem, I allow a ...
2
votes
2answers
124 views

Urn Problem - black and white balls, infinite trials.

Imagine that there are 10 black balls and 20 white balls in an urn. Two balls are removed at random from the urn. The second ball removed is recolored, such that it matches the color of the first ...
2
votes
0answers
51 views

A random walk on the unit distance graph in $\mathbb{R}^n$

Define a graph $G_n$ whose vertices are the points in $\mathbb{R}^n$ with an edge connecting any two points that are one unit apart. Such a graph is called the unit distance graph in $\mathbb{R}^n$. ...
2
votes
0answers
62 views

Random walk with $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} < \infty$

Consider a random walk started at $S_0=0$, denoted $S_n = \sum_{k=1}^{n}X_k$, where $X_1$, $X_2$... are the i.i.d increments. If we have $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} ...
1
vote
0answers
33 views

Expectation of a Random Walk

I am researching Random Walks and trying to find how to get their expectations. I have studied Markov chains before. I have found one way of getting the expected number of steps to reach a state by ...
1
vote
0answers
31 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
190 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
26 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
0answers
32 views

random walk differential equation

Was reading about random walks and I am learning differential equations and I thought combining them. Because I am just learning about these topics and want to know more, I will use the simplest ...
0
votes
1answer
20 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
62 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 ...
0
votes
0answers
58 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
35 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
2answers
269 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
76 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
67 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
102 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
71 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
100 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
377 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
81 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
51 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
28 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
60 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
191 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
77 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
195 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
106 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
113 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
60 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
181 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
119 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
144 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
49 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
262 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
35 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
51 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
121 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
161 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
247 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 ?