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

learn more… | top users | synonyms

5
votes
1answer
269 views

Walks of Even Length on a Bipartite Graph

Given a random walk on a simple $d$-regular bipartite graph $G$. The adjacency matrix $A'$ of $G$ may be split into blocks $$ A'=\pmatrix{ 0 &A^T\\ A&0 }, $$ The propagation operator $M=A'/d$ ...
4
votes
1answer
504 views

Covariance of Brownian-motion-like processes

We know that $\operatorname{Cov}(B_s,B_t)=\min(s,t)$ if $B_t$ is Brownian motion. What is $\operatorname{Cov}(B_{f(s)},B_{f(t)})$ for some injective $f$? How can I write $B_{f(t)}$ in an Ito ...
0
votes
0answers
86 views

Expected time spent in $i$, assymetric random walk on $\mathbb{Z}$

This is exercise 1.7.4 in Norris' Markov Chains textbook. I'm having difficulty calculating a simple looking expectation. Let $(X_n)_{n\geq0}$ be a simple random walk on $\mathbb{Z}$ with transition ...
0
votes
1answer
417 views

Relationship between a stationary distribution for a random walk and the hitting time at some position

In a previous question of mine, I asked for the probability distribution of an agent taking a biased walk on the positive integers (with a reflecting boundary at the origin): Probability distribution ...
8
votes
6answers
348 views

simplify summation of factorial (random walk)

I suspect that the expression $$\sum_{n=0}^N \frac{(N-2n)^2}{n!(N-n)!}$$ simplifies to $$\frac{2^N}{(N-1)!}$$ But I cannot find the intermediate steps. Can someone give me a hint how I can deduce ...
3
votes
1answer
108 views

Proof of random work property given the absolute value of variables

This hints that $E(|S_n|)\,\!$, the expected translation distance after ''n'' steps, should be of the order of $\sqrt n$. In fact, $$\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac ...
3
votes
3answers
141 views

Introduction to Markov Random Fields

I'm looking for a gentle introduction to this topic. The material I've found so far is substantially related to physics, and requires some background in such field. Is there anything more general and ...
0
votes
1answer
212 views

mean reverting random walks

I need a set of stochastic processes $x_i(t)$ with the following characteristics: At each time $t$, the jump of each variable can be just $+s$ or $-s$; The processes have to be mean reverting, so ...
5
votes
1answer
593 views

Probability distribution for the position of a biased random walker on the positive integers

I initialize a biased one-dimensional random walk on the positive integers at the origin, $x = 0$, which also serves as a reflecting boundary blocking steps onto the negative integers. Let's say that ...
2
votes
1answer
255 views

Random walk with 3 possible steps

I have i.i.d. random variables with following distribution: $$ P(\xi_i =1) = p_1, \ P(\xi_i = 0) = p_0, \ P(\xi_i = -1) = p_{-1}; \quad S_n = \sum^n_{i=1}\xi_i.$$ I am interested in probability of ...
3
votes
1answer
30 views

Infinite number of 1D-random walkers

Place exactly one random walker at each integer in $\Bbb Z$ and define $Y_n$ as the number of these who are at the origin at time n. Show that $0<\displaystyle\lim_{n\to\infty}P\{Y_n=0\}<1$ and ...
2
votes
0answers
118 views

Spectrum of Transition Matrix for Random Walk

Consider the symmetric random walk on $\{0, 1, \dots, n\}$ with transition probabilities $P(j \to j \pm 1) = 1/2$ for $1 \le j \le n-1$ and $P(0 \to 0) = P(0 \to 1) = P(n \to n) = P(n \to n-1) = 1/2$. ...
1
vote
1answer
166 views

Increasing entropy of random walk in regular graph

Let $P$ be a transition matrix of a random walk in an undirected regular graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by $$H(\pi)=-\sum_{v \in ...
0
votes
1answer
2k views

Probability distribution of a Hitting Time in simple random walk

In order to solve a puzzle in correspondence with a friend, I am using a simple random walk hitting time calculation based upon the reflection principle as it is expressed in this University of ...
2
votes
0answers
109 views

Equilibrium distributions for a finite urn scheme

Given an urn with $n$ (fixed) balls that can be red or black, and given two parameters $0 < p, \, q < 1$, keep doing the following: Flip a $p$-coin. If heads come up, remove a black ball or ...
1
vote
2answers
292 views

A question about random walk in 1 dimension

For a simple random walk problem in 1 D, the expected position of the particle in $n$ step is $E(X_n)=n(p-q)$ so the distance from origin should be $=E(X_n)$ but according to Mean distance from ...
0
votes
1answer
206 views

Recurrent, strongly aperiodic random walk

Assume $(X_n)_{n\geq1} \subseteq \mathbb {Z}$ and $(Y_n)_{n\geq 1} \subseteq \mathbb {Z}$ to be iid, $X_i \sim Y_i$ and such that $S_n=\sum_{i=1}^n(X_i-Y_i)$ is a strongly aperiodic, recurrent random ...
10
votes
1answer
405 views

Is there an intuitive way to see this property of random walks?

For an $n$-step symmetric simple random walk (start at origin 0 and each step 1 unit towards left or right with equal probability,) an interesting fact is that the probability that you stop exactly at ...
1
vote
1answer
67 views

Absorbing time in $0$ of a simple left-drifted Markov chain on non-negative integers

Let $M$ denote the Markov chain on states $\{0, 1, 2, ...\}$ with absorbing state $0$. For $i \geq 1$, let the transition probabilities be $p$ for $(i, i-1)$ and $1-p$ for $(i, i+1)$. Further, assume ...
1
vote
1answer
35 views

Off-lattice Brownian bridges in R^3

Start at a point $(0,0,z_0)$ and take $n$ steps of unit length in a random direction (for each step) in $\mathbb{R}^3$. Let such a walk be valid if the position of the last step, and only the last ...
3
votes
2answers
185 views

Mixing time for a random walk on an interval

I take a random walk on a bounded one-dimensional interval of length $N$, with possible walker positions $1$ through $N$. If I start at position $1$, how many steps should it take before my walker is ...
0
votes
2answers
303 views

How to check that a sequence of numbers is random? [duplicate]

I have a sequence of numbers like 1,7,22,45,12,96,21,45,65,36,85,14,51,16,18,17,16....65... IS there any formula to check whether the sequence is random or not ? In my case odd numbers are ...
0
votes
0answers
40 views

Find for a given distribution a random walk

Let $\{Z_i\}$ be i.i.d. $\mathbb{R}^d$ valued random variables. Then we define $S_n:=\sum_{i=1}^n Z_i$ and call the process $\{ S_n\}$ random walk on $\mathbb{R^d}$. Let $\mu$ be a distribution on ...
5
votes
1answer
102 views

What's the easiest way to show that a random walk can go arbitrarily far?

Let's consider the simplest situation. On the one dimensional line of integers, and we starts from the origin. Each time we either move left or right (at the same probability) for 1 unit. How do I ...
8
votes
1answer
155 views

How long until everyone has been in the lead?

Earlier, I asked a question about a series of competitions: A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I'm looking ...
8
votes
1answer
192 views

First player to win k matches

A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I'm looking for a probabilistic description of the outcome when looking at ...
2
votes
0answers
131 views

Repeated reflection

This is a problem from Feller's book introduction to probability theory and its application, Vol 1, Chap 3 problem 3. Let $a$ and $b$ be positive, and $-b <c<a$. Prove the number of paths to ...
0
votes
3answers
177 views

Probability of landing on a particular point in an infinite 1D random walk

$50\%$ of the time you walk right one unit, and $n$ units to the left o.w. The probability in question is ever landing one unit to the right of where you start at (as your number of moves goes to ...
1
vote
0answers
90 views

Martingale with reflecting barrier

I am not very familiar with the theory of martingales or random walks, perhaps someone could point me in the right direction or give me some help with the following problem. Consider a random ...
23
votes
2answers
542 views

Random walk: police catching the thief

This is a problem about the meeting time of several independent random walks on the lattice $\mathbb{Z}^1$: Suppose there is a thief at the origin 0 and $N$ policemen at the point 2. The thief and ...
12
votes
3answers
278 views

Select a new value from last $N$ values; how long until the last $N$ are all the same?

Say first we have N distinct numbers in a line, like 1,2,3,...,N, in each round, we choose a ...
0
votes
1answer
392 views

Why is a random walk a time-homogeneous Markov process?

Why is a random walk on $\mathbb{R}^d$ (see below) a time-homogeneous Markov process? Specifically, why does it satisfy requirement #2 of definition 17.3 that the map ...
2
votes
1answer
605 views

Random Walk Expected Number of Visits

I'm having a bit of trouble with a question involving a random walk with five vertices. The graph is shown below. The problem I can't figure out reads: Suppose a walker starts in vertex C. What ...
3
votes
2answers
293 views

Boundary conditions on asymmetric random walk recursion formula

A random walker moves at each step two units to the right or one unit to the left, with corresponding probabilities $p$ and $q = 1-p$. The allowed range is $[-A, B]$ and the starting position is $0$. ...
6
votes
2answers
865 views

A question on calculating probabilities for the random walk

I am currently working on a high school project revolving around the 'Cliff Hanger Problem' taken from ”Fifty Challenging Problems in Probability with Solutions” by Frederick Mosteller. The problem ...
2
votes
1answer
256 views

Random walk on finite graph

I know that the stationary distribution of a random walk on the graph is given by, (degree of the node)/($2\times$ total number of links in graph). My question is, how do we get this solution?
3
votes
2answers
335 views

Drunk person walking in 1D desert

Given $f(x)$, a strictly positive monotonically decreasing sequence, converging to 0. How to check whether a one dimensional random walk with stepsize $f(n)$ in random direction at the $n$-th step, ...
3
votes
2answers
435 views

one-dimensional random walk

Consider a one-dimensional random walk whose steps are $+2$ and $-1$ with probabilities $p$ and $1-p$ respectively, starting from $0$ and in the interval {$-n$, $n$}. The walk ends at $-n$ or $n$ or ...
3
votes
2answers
282 views

Random walk and its expectation

Let $S_n=X_1+X_2+...+X_n$, where $X_i=1$ with probability $p$ and $X_i=-1$ with probability $q=1-p$, for all $i$ and independently of each other. Assume that $S_0=0$ and $0<p<\frac{1}{2}$. ...
2
votes
3answers
180 views

Derivation of Wiener process first passage times using probability generating function?

I would like to find the distribution of first passage times in a simple Wiener process using the idea of probability generating functions. Thus there will be, at certain point, a limiting step to go ...
4
votes
1answer
191 views

The probability of a “double supremum” of random variable

Let $X_1,X_2,X_3,\ldots$ be IID r.v. with \begin{equation} P(X_i<-1)=0 \end{equation} \begin{equation} P(X_i<0)>0 \end{equation} \begin{equation} P(X_i>0)>0. \end{equation} Define ...
2
votes
0answers
312 views

Probability distribution of a self avoiding walk

Preliminary: Consider a walk on the lattice $\mathbb{Z}_d$ lattice of length $N$. In a normal random walk, if we let $N$ get large the end position has a probability distribution (PDF) that looks ...
1
vote
1answer
179 views

Wiener process question

When I look up the definition of 'Wiener process' at Wikipedia, it tells me: $W(0) = 0$ and $W(t) - W(s) \sim N(0, t-s)$. When I try to simulate this in matlab, I get different results when I define ...
3
votes
1answer
108 views

what is the behaviour of moving dot with 50% chance to go left or right?

If a dot is moving (from zero) left or right, by one, with 50% chance to go left or right - is it going to go to the +inf or -inf when it has infinite moves?
3
votes
1answer
146 views

A difference equation related to RW on Hypercube

I am trying to solve the following recurrent relation $$ T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0 $$ Where $0\leq n\leq m$ and $m$ is a fixed integer. I have ...
0
votes
1answer
815 views

Stopping time and random walk: Proof that Stopping time of reaching a certain value is finite a.s. [duplicate]

Possible Duplicate: Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1 This is a basic question but I was wondering if there was a simple proof (I ...
0
votes
1answer
96 views

A random walk on $\mathbb{Z}$ with a twist

I am trying to decide whether the following random walk is recurrent or not. Intuitively, I think it is - but I am not familiar with techniques of proving it. My random walk is the following: on each ...
1
vote
1answer
204 views

Variation of a simple random walk

Consider the following problem. A particle takes discrete steps $\sigma_1, \sigma_2, \sigma_3, \ldots, \sigma_n$ which take on values $+1$ or $-1$. However, $P(\sigma_i = +1) = p$ if $i$ is odd and ...
4
votes
1answer
344 views

Circular random walk

Suppose we have a circumference divided in N arcs of the same length. A particle can move on the circumference jumping from an arc to the adjacent, with probability $P_{k \to k-1}=P_{k\to ...
0
votes
1answer
172 views

A problem about the expectation of maximum rise up for a random walk.

Give such a random walk moving on the x-axis: Start from $x_0=0$; After the $i^{th}$ step, the location is $x_i$. The length for the $i^{th}$ step $x_i-x_{i-1}$ is a uniformly generated real number ...