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

learn more… | top users | synonyms

2
votes
2answers
81 views

Random walk on tree

You begin at a root node that has 2 children. Each of those two children have two more children, and each of those children have two final children (i.e., there are 15 nodes in the graph). How do I ...
0
votes
0answers
58 views

Random looking Gray Codes or Hamiltonian Cycles on Hypercubes

Cyclic Gray codes come in many flavors and correspond 1-1 to Hamiltonian cycles on hypercubes. I would like to find a type that looks like a random walk on the hypercube. In a sense this is an ...
2
votes
0answers
49 views

Recurrence for a random walk question

Let $X_i$'s be iid and define $X_1+\ldots+X_n=S_n$. I was trying to show that if $S_n$ is recurrent, then $S_{2n}$ is also recurrent. Assume these walks are in $\mathbb{R}^d$. Using Chung-Fuchs ...
1
vote
2answers
157 views

Power series convergence of random walk transition matrix

I would like to find out if $$ \sum_{t=0}^\infty P^t = \left( I- P \right)^{-1} ~,$$ where $P = D^{-1}W ~ $ is a random walk transition matrix. $W$ is a matrix describing weights in a graph and ...
1
vote
1answer
84 views

{Probability}: choosing keys from a pool without replacement

The OP is trying to understand the following question. The OP understand that if you can always write out the term $$P(X=k) \implies (1-\frac{1}{N})(1-\frac{1}{N-1})\cdots(1-\frac{1}{N-k+1}),$$ ...
0
votes
1answer
95 views

Expected number of steps and probability

I have a problem that I am not quite sure how to solve using my elementary knowledge of probability. My question is this: suppose a friend and I are playing a game. We both start at 0 points, and ...
0
votes
1answer
62 views

Probability: deviation from the mean

I am having trouble to understand the following. If $S_n=X_1+X_2+......+X_n$, where X_1,X_2 are Bernouli (p). I don't understand this. So you get an intermediate point Constant* sqrt(n). To the ...
1
vote
1answer
125 views

rate of convergence of absorbing markov chain

Let $G$ be a biconnected and non-bipartite graph. I can simulate a random walk on this graph with a markov chain. The stochastic matrix is $M = AD^{-1}$, where $A$ is the adjacency matrix of $G$ and ...
5
votes
0answers
72 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
2
votes
1answer
66 views

Infinite series containing binomial coefficients

I've encountered the following series: $$\sum_{t=1}^\infty {1 \over 2^{t}}\, {{\large t} \choose {\large{t + x \over 2}}}$$ Is this series even convergent? I'm really lacking knowledge on series ...
4
votes
1answer
130 views

Function of a uniformly distributed continuous random variable

Basically, I'd like to add $n$ random vectors in a 2 dimensional space of unit length and of angle $\theta$ relative to a global axis. The probability density function of the angle $\theta$ is a ...
1
vote
1answer
90 views

Explanation on one-dimensional random walk in Feller's book

Consider the random walk on the integer number line, $\mathbb{Z}$, which starts at 0 and at each step moves $+1$ or $−1$ with equal probability. The probability for the event that "the first return to ...
7
votes
3answers
604 views

Probability a random walk is back at the origin

I have a symmetric random walk that starts at the origin. With probability $1/6$ it goes right by one and with probability $1/6$ it goes left by one. With probability $4/6$ it stays put. After $n$ ...
4
votes
1answer
86 views

Solving a recurrence for a random walk revisited

I previously asked about the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < ...
5
votes
1answer
111 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
1
vote
2answers
870 views

Simulating Diffusion/Wiener Process with Random Walk

I hope this is the right section for this kind of questions. I am trying to simulate, with MATLAB, a diffusion model starting from a Random Walk. I am using a Random Walk with information increment ...
1
vote
0answers
48 views

Random walk on a graph

For a random walk say from point $x$ to $y$ on a graph, How is the probability of a Random walker reaching point $y$ before returning to $x$ related to the expected of the number of visits to point ...
1
vote
1answer
64 views

Reaching a level before another for a random walk

Suppose we are given a simple random walk starting in $0$, i.e. $(X_k)_{k\in\mathbb{N}}$ with $P[X_k=+1]=P[X_k=-1]=\frac{1}{2}$. What is the probability of hitting the level $a$ before hitting the ...
2
votes
0answers
49 views

The number of paths, which touches or crosses the abscissa

If $S_n$ is a random walk s.t. $S_0=1$. $S_n=X_1+X_2+...+X_n$ for $n\ge 1$ and for any $i\in N$ $P[X_i=1]=P[X_i=-1]=1/2$ for $r\ge 1$ calculate the number of paths from time $0$ to $2n-1$ ...
0
votes
1answer
113 views

Probability of random walk traversal

Consider a random walk on an connected, non-bipartite, undirected graph G. Show that, in the long run, the walk will traverse each edge with equal probability. Note: The walk can traverse each edge ...
2
votes
0answers
76 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
52 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
20 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 ...
2
votes
2answers
167 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
57 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
69 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 \} ...
2
votes
0answers
53 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
42 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
198 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
28 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
1answer
22 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
83 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 ...
1
vote
0answers
86 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
45 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
3answers
378 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
93 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
95 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
156 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
236 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 ...
4
votes
1answer
113 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
637 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
91 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
62 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
36 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
1answer
267 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
114 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
249 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
213 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
134 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
35 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 ...