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
19 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
31 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
38 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
50 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
20 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 ...
0
votes
0answers
27 views

2D-Classical staggering drunk or random walk problem [closed]

Suppose a drunk is standing on a street corner when he decides to go for a walk to sober up. Assume that there is an equal problability of his going north, east, south or west as he reaches each ...
3
votes
0answers
30 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
43 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 ...
0
votes
0answers
14 views

Proof of “changes of sign” in one-dimensional random walk model [Feller's section 3.5, page 84]

Consider the one-dimensional random walk of a particle. We shall denote the individual steps by $X_1, X_2, \cdots$ with $X_i = \pm 1$ and the positions by $S_1, S_2, \cdots$ with $S_i = X_1 + X_2 + ...
3
votes
1answer
52 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
26 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 ...
3
votes
3answers
401 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$ ...
0
votes
0answers
11 views

Writing a proof that a certain algorithm generates the correct transition matrix for a quantum walk?

Regarding quantum walks, I have a transition matrix $M$ and a particle vector $P$ and I have determined that the elements of $M$ have to be positioned in a certain way so that the position of the ...
0
votes
0answers
34 views

Expected number of steps in a random graph walk

Suppose I have a directed graph $D(V, A)$ where the edges have weights on them. Let's notate the weight function $w: A \rightarrow [0, 1]$. If $f, t \in V$ and $a \in A$ such that $a = (f, t)$ then ...
3
votes
1answer
61 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 < ...
4
votes
1answer
73 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
66 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 ...
0
votes
0answers
16 views

Random Walk Prediction on a grid using markov chain

We have a m*n Grid and n no of robots in that grid which would perform a random walk simultaneously.Each robot can move in 4 direction specifically Up, Left, Down, Right. After x steps the random ...
0
votes
0answers
24 views

Mean absolute value of random walk with drift

Ok, so the mean absolute value for a random walk, $X(t)=\sum\limits_{i=1}^t\epsilon_i$, is given by: $\sigma\sqrt{\dfrac{2t}{\pi}}$ ...a result from the folded normal distribution. BUT, I am ...
1
vote
0answers
28 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
25 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
32 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
44 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 ...
0
votes
0answers
27 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
61 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
30 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
40 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
17 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
27 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
57 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
37 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
53 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
22 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
27 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
179 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
19 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 ...
1
vote
0answers
97 views

Upper bound for mean hitting time of two-dimensional random walk

Let $U_n=\sum_{i=1}^n X_i,V_n=\sum_{i=1}^n Y_i$, $n\geq 1$, be a two-dimensional random walk with iid increments $(X_n, Y_n)$, where $X_n, Y_n$ are discrete random variables with joint pmf ...
0
votes
0answers
18 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
18 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
45 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
18 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
17 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
1answer
53 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
58 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
44 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
59 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
200 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
30 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
78 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
77 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 ...