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

distribution of the length for a random walk on an infinite 2D grid

In connection with the flatland paradox, consider a 2D-random walk $(X_n)$ on $\mathbb{Z}^2$: the four moves of length one to W,E,N, and S are equaly likely at each time. For a fixed number of moves ...
1
vote
1answer
43 views

Integrate bivariate normal distribution over circular region

Context: Need to compute the probability that a 2D Gaussian random walk falls within distance $ d $ of some point $ p $ on the next step. (Assume the covariance $ \Sigma $ is the identity matrix $ I ...
1
vote
2answers
42 views

Random walk on vertices of a cube

If a particle performs a random walk on the vertices of a cube, what is the mean number of steps before it returns to the starting vertex S? What is the mean number of visits to the opposite vertex T ...
1
vote
1answer
36 views

Show a random walk is transient

I was going through some problems related to Markov chains and I got stuck on this bit: We are given a random walk on $Z$, defined by the transition matrix $p_{i,i+1}=p$ and $p_{i,i-1}=1-p$. How to ...
2
votes
0answers
19 views

Biased Asymmetric Random Walk [duplicate]

Consider the random walk $S_n$ given by: $$ S_{n+1}= \left\{ \begin{array}{ll} S_n + 2 & \mbox{w.p } p\\ S_n -1 & \mbox{w.p } 1-p \end{array} \right. $$ Assume that $S_0=n > 0$ ...
0
votes
1answer
41 views

Find E(min(Ta, T-b)) in Simple Random Walk

Let $T_x$ denote the first time a symmetric random walk visits $x$. (The random walk starts at $0$.) Find $\mathsf E(\min(T_a, T_{-b}))$ where $a, b > 0$. Hint: we computed $P(T_a < T_{-b})$ ...
2
votes
0answers
35 views

If two Brownian motion starts and end at the same points, can we say something about there difference?

Let $X$ and $Y$ be two standard Brownian motions with mean $0$ and variance $1$, both started at zero. If we know that \begin{align} X_n &= Y_n, \end{align} for some $n>0$, can we say ...
1
vote
0answers
26 views

Is a linear random walk with jump recurrent?

Let $\lambda_0=10^5$ or any other large integer. Define the recursive "process": $\lambda_t=\text{sample from a Poisson distribution with mean }\lambda_{t-1}$. Is this process recurrent? I mean, after ...
0
votes
1answer
50 views

Approximating a joint pdf using normal density of two independent variables

I know that given these two random variables (which correspond to the $x$ and $y$ coordinates of a random walk after $n$ steps, their joint probability density function can be $approximated$ by a ...
0
votes
1answer
79 views

probability, random walk, Markov chain question

Let $P$ be a transition matrix for a regular Markov chain and let $w$ be it’s equilibrium vector. Show that $w$ has no zero entries.
1
vote
0answers
43 views

Multiple Anihilating Random Walks in a Ring (cycle)

I've been trying to solve this problem for a long time. Problem Let $R$ be a cycle with $2n$ nodes and assume there are $2k$ particles performing a simple random walk in this ring (i.e., they have ...
1
vote
0answers
17 views

Self-Avoiding Walk incorporating diagonals

How many paths are there between $(0,0)$ and $(n,n)$ if you include all eight common cardinal directions: North, East, South, West, Northeast, Northwest, Southeast, and Southwest. The only condition ...
25
votes
2answers
369 views

Random Walk Without Repetitions

Suppose that we simulated a random walk on $\mathbb Z$ starting at $0$. At each step, we transition from position $x$ to position $x-3,\,x-2,\,x-1,\,x+1,\,x+2,$ or $x+3$ with equal probability. If ...
2
votes
1answer
157 views

Probability of asymmetric random walk returning to the origin

Consider the random walk $S_n$ given by $ S_{n+1} = \left\{ \begin{array}{lr} S_n+2 & with & probability & p\\ S_n - 1 & with & probability & 1-p \end{array} ...
0
votes
0answers
36 views

Filtered Probability Space Understanding

Usually in my probability theory class, we define a filtered probability space in the background $\left(\Omega, F, \left\lbrace F_t \right\rbrace P\right)$ and do all of our work on that space. I'm ...
0
votes
1answer
32 views

Exit time of simple random walk on $[-a,b]$

It can be proved using martingales and the optional stopping theorem that the expected exit time of a random walk on $(-a,b)$ beginning at $0$ with $a,b>0$ is $ab$. How can this be shown using a ...
0
votes
0answers
36 views

If there are two different stationary distributions, then there are infinitely many distributions in reducible markov chain

If there are two stationary distributions μ1 and μ2 there are actually infinitely many stationary distributions: (pμ1 + (1 − p)μ2) is also a stationary distribution for any real number 0 ≤ p ≤ 1. How ...
1
vote
0answers
33 views

Reading material on Random Walk on S_n using Transpositions

I am from an engineering background and I wanted to get hold of some very basic reading material on Random Walk on $S_n$ (symmetric group on n letters) using Transpositions. Could someone suggest ...
0
votes
0answers
45 views

Probability distribution for a random walk in arbitrary dimension

I'm trying to find the probability distribution for a random walk on a lattice with lattice constant a in arbitrary dimension d. The rules for my walk is that in each step the walker has to move to an ...
2
votes
0answers
39 views

An inequality for symmetric random walk

I need to show that if $(X_j)$ are symmetric i.i.d. random variables with partial sums $S_n:= \sum_{j=1}^n X_j$, then for all $x \geq 0$ $$P(|S_n| > x) \geq \frac{1}{2} P(\max_{1 \leq j \leq n} ...
0
votes
0answers
33 views

Final step of a random walk proof

I am working through the last bit of a random walk proof to show that a 3-d random walk is transient. The result I am looking for states that: $\frac {1}{2}^{2s} {{2s}\choose{s}} \sum_{j+k\leq{n}} ...
1
vote
0answers
47 views

Expected time of reaching 0 of a simple symmetric random walk

Consider the symmetric, simple random walk on $S = \{0, 1, \ldots , k\}$ for $k \in \mathbb N$. Let $$T = \min \{ n \in \mathbb N_0|X_n = 0\}$$ be the first time where the process reaches $0$ and ...
2
votes
0answers
53 views

2d random walk on the nonnegative quadrant using martingale techniques

I know the basics of (discrete time) martingales, and I'd appreciate any help and suggestions on how to prove the following using martingale techniques. Let $Z_n$, $n\ge 0$ be a random walk on the ...
0
votes
1answer
126 views

Probability that random walkers meet

I was wondering about a question about Random Walks. I came across various papers where the probability of 2 random walkers in 1 dimension and 2 dimension starting at the same point and returning to ...
2
votes
1answer
62 views

Random walks : Hitting and recurrence Times relation

I have trouble understanding that how $$E\left[T_0|X_{0} = 0\right] = 1 + E[H_0|X_0=1] $$ where $T_0 = \inf\{n \geq 1:X_n = 0 \}$ and $H_A =\inf\{ n\geq 0: X_n \in A \}$. In other words $T_0$ is the ...
0
votes
1answer
41 views

How to calculate the correlation coefficient of two independent random walks to demonstrate spurious regression?

I heard of non-stationary time series could result in spurious regression, so I want to know, as sample size goes to infinity, how to calculate the correlation coefficient of two descrete independent ...
0
votes
0answers
31 views

A random walk with an exit

Let's consider a random walk. We start on the tile $n_0$. For our $q$th step, if we're already on the tile $k$ then we have a probability $P_{q,k,p}$ to go to the tile $p$ with $p\in\mathbb{N}$. ...
1
vote
1answer
55 views

Show expectation is finite of an asymmetric walk

Where does this result come from? $$\mathbb{E}\left[\left(\frac{q}{p}\right)^{S_n}\right]\leq \left(\frac{q}{p}\right)^n + \left(\frac{q}{p}\right)^{-n}$$ where $$S_n = \sum_{i=1}^{n}X_i$$ and $0\leq ...
0
votes
1answer
30 views

Series of random numbers on a continuous function

At one point, I read about a function used to generate random numbers that follow a continuous pattern. By this I mean random numbers that as a series is random, but in which items tend to be ...
0
votes
0answers
43 views

Expected number of returns by time n in a symmetric 1-d random walk?

How do we prove that $E(N_{2n})=(2n+1){{2n}\choose{n}}(\frac{1}{2})^{2n}-1$ I started working on it. And I see that $E(N_{2n})=\Sigma_0^n{{2k}\choose{k}}(\frac{1}{2})^{2k}-1$ Therefore the problem ...
1
vote
0answers
33 views

capacity of biased random walk in $\mathbb{Z}^2$

Let $P_{x,y}$ the probability that a random walk starting from $x$ will ever visit $y$. Consider a biased random walk in $\mathbb{Z}^2$. Let $A_k$ be the set of vertices having a distance less than ...
2
votes
1answer
62 views

Random walk : probability of reaching value $i$ without passing by negative value $j$

This is just some question that popped out of nowhere while starting studying random walks, and I don't really know how to approach this. Say I have a random walk that starts at zero, and goes up or ...
0
votes
0answers
31 views

Optimal stopping strategy

I try to solve the following problem : Given a series of random variables : X1,X2,... such that each one can get either -1 or 1 with probability 0.5, give a strategy to maximize the expected value of ...
1
vote
1answer
41 views

Independence of random variables derived from a Random walk

Let $w=(w_x)_{x \in \mathbb Z}$ be i.i.d random variables taking values in $(0,1)$. Let $(X_n)_{n \in \mathbb{N}_0} (\mathbb{N} \cup {0})$ be a Markov chain (more specifically a simple random walk ...
0
votes
0answers
23 views

1-D random walk weighted towards the origin

I would like to model a random walk in one dimension where the walker is attached to the origin by a rubber band, such that the walker's probability of moving toward origin increases with the distance ...
7
votes
0answers
73 views

Probability on entering direction of a simple random walk

Let $X(n)$ be a simple random walk on $\Bbb{Z}^2$. Also we define $S_{R} = \inf\{n > 0 : X(n) \notin [-R, R]^2 \} $ : the exit time of the square $[-R, R]^2$, $T_{v} = \inf\{n > 0 : X(n) = ...
0
votes
1answer
55 views

Why the probability of a sequence is simply the multiplication?

In studying the random walk in one dimension I had a doubt on basic probability. The point is the following: we consider a random walk with $N$ steps consiting of $n_1$ steps to the right and $n_2$ ...
9
votes
0answers
121 views

Expected range of simple random walk in $\mathbb{Z^2}$

Let $(Y_k)_{k\geq0}$ be a simple random walk process. The range of an $n$-step random walk, $R_n$, is a random variable that characterizes the number of distinct points visited at time $n$: ...
0
votes
0answers
71 views

The characteristic function for the random walk

I want to determine the characteristic function of the probability distribution of a random walk. The probability distribution of a random walk is: ...
1
vote
1answer
115 views

Expectation and Variance of random walks

Consider random walks of fixed length (e.g. $5$) starting at node $u$ in an undirected and connected graph with $N$ vertices. If a node $k$ has $N_k$ edges, the probability of the walk reaching any of ...
0
votes
1answer
18 views

$\sqrt{n}$ in scaled random walk

In a reference, it is stated that $W^{(n)}(t)=\frac {1}{\sqrt{n}}M_{nt}$ with : $W^{(n)}(t)$ as scaled random walk and $M_{nt}=\sum_{j=1}^{nt}X_j$. Where does $\sqrt{n}$ come from? Would you ...
0
votes
1answer
44 views

Probability - Random Walk Type Problem

Suppose two teams play a series of games, each producing a winner and a loser, until one time has won two more games than the other. Let G be the number of games played until this happens. Assuming ...
0
votes
0answers
33 views

diffusion- stuck

In a round room of radius R, a large number of coins N of diameter d are randomly dispersed upon the floor. A ladybird starts from the centre of the room, crawling at speed v. Suppose that every time ...
0
votes
0answers
36 views

Random Walks - $n$ particles on a $n-clique$

We take $n$ particles and put them on $v$, a vertex in $n$-size Clique $G$, where each vertex has a loop to itself. Each particle does a Random Walk on the clique and the $n$ Random Walks are ...
4
votes
1answer
54 views

Random walk with finite expected stopping time

Let's say each $X_i$ is a simple random variable taking on values 1 or -1 with probability $1/2$ each. Then $S_n = \sum_{i=1}^{n} X_i$ is a random walk. Set $T = \min \{n\in\mathbb{N} \, : \, S_n = ...
0
votes
0answers
12 views

compare hitting time of two random walks with reset action

Let $s^i_k = s^i_{k-1} + x^i_k$ with $s^i_0 = 0$ for $i=1,2$. Additional constraint on $s^i_k$ is that $s^i_k$ cannot be negative, i.e., $s^i_k$ is reset to be zero whenever it becomes negative. The ...
1
vote
0answers
17 views

a problem on random walk and maximu of its summation

Suppose $X_n$ is random walk with $P(X_n=1)=1-P(X_n=-1)=p=1-q$. $M_n=\max_{1\le i\le n} S_i$, $Y_n=M_n-S_n, T_a=\min\{S_n=a\}$. Find $P(\max_{0\le k\le T_a} Y_k <y).$
2
votes
1answer
44 views

$E(S_T^2)\not=E (\sum_{i=1}^T \sigma_i^2) $ when $E|T|<\infty$

I am currently learning random walk and come across a problem concerning stopping time. The question asks to give an example that $X_1,X_2,...$ independent r.v. with mean $0$ and variance ...
1
vote
1answer
29 views

Why random walk sample path seen as if it is continuous-time stochastic process?

Random walk is a discrete-time stochastic process. In many references, instead of using dots to draw its sample path, why does random walk use line-styled graph as if it is a continuous-time ...
3
votes
2answers
52 views

Random walk on a tree

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that ...