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
1answer
119 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
203 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
72 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
30 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
66 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
39 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
33 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
62 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
110 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
227 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
24 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 ...
28
votes
2answers
458 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 we ...
2
votes
1answer
693 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
65 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
112 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
50 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
1answer
45 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 some?...
0
votes
0answers
93 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
61 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
37 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
105 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
83 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
194 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
68 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
132 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
48 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
62 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
52 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
81 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
34 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 $k$...
2
votes
1answer
98 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
64 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
47 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 ...
10
votes
0answers
136 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) = v\}$...
0
votes
1answer
63 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$ ...
10
votes
0answers
162 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$: $$R_n=|\{...
1
vote
1answer
204 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
30 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
121 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 ...
4
votes
1answer
91 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 = 1\}...
1
vote
0answers
21 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
48 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 $\sigma_i^...
1
vote
1answer
46 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
67 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 ...
1
vote
0answers
117 views

Maximum of *Absolute Value* of a Random Walk

Suppose that $S_{n}$ is a simple random walk started from $S_{0}=0$. Denote $M_{n}^{*}$ to be the maximum absolute value of the walk in the first $n$ steps, i.e., $M_{n}^{*}=\max_{k\leq n}\left|S_{k}\...
1
vote
1answer
31 views

Let $S_n$ be a Simple Random Walk. What is $E[S_m|S_n]$ if $m < n$?

Let $S_n = W_1 + ... + W_n$ be a simple random walk with $W_i$ IID and $P[W_i = 1] = P[W_i = -1] = 1/2$. Find $E[S_m | S_n]$ when (a) $m > n$ and (b) $m < n$. For part (a), I get the answer of $...
1
vote
4answers
149 views

Expected number of steps

I play a game as follows. A bucket contains four red balls and three green balls. At each step, a ball is chosen at random from the bucket, with each of the balls there being equally likely to be ...
2
votes
2answers
130 views

Bounding profits of gambler by Azuma Inequality

A gambler plays the following game: In each round, he can pay any $0 < p < 1$ dollars, and win 1 dollar with probability p (independently). Show that the probability that the gambler's net gain ...
0
votes
1answer
253 views

Random Surfer as a Markov Chain

Consider a random surfer who begins at a web page (a node of the web graph) and executes a random walk on the Web as follows. At each time step, the surfer proceeds from his current page A to a ...
0
votes
1answer
144 views

Deducing results about continuous time random walks from the corresponding discrete time result

Is there any standard way to prove results about continuous time random walks from the corresponding results for discrete time random walks? Specifically, my problem is that I was reading Lawler and ...