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

learn more… | top users | synonyms

0
votes
0answers
26 views

1-dimensional random walk with barrier

Let $X$ be a random walk on $\mathbb{Z}_{\ge 0}$ starting at $0$, with step size 1, and there is a barrier at 0 so that if one tries to move to -1 it stays at 0 (non-reflecting). If we fix the number ...
2
votes
1answer
49 views

Lattice Path Spaces.

It is well known that the number of paths from $(0,0)$ to $(n,k)$ in $\mathbb{N^2}$ with the set of steps $\{(1,0),(0,1)\}$ is ${n+k \choose k}$. This is the minimum number of steps needed to get to ...
1
vote
1answer
23 views

DTMC random walk [closed]

For a discrete Markov chain random walk with p < 0.5 with state space S= {0,1,2..} What is the stationary distribution? I could use any help. Thank you
3
votes
1answer
57 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
1
vote
1answer
29 views

Random walk on free group on two elements

Let $F_2$ be the free group on two elements, generated by $\{a, b\}$. We perform a random walk on $F_2$, starting at the identity element $e$ and uniformly at random selecting one of ...
1
vote
1answer
59 views

Proving a property of hitting times of a simple random walk on $\mathbb{Z}$

I'm reading the course notes of a probability course about martingales currently and I'm trying to solve some of the exercises, however I'm very much stuck with the following exercise: Let $\left\{ ...
0
votes
1answer
23 views

Are random walk variations Markov-Chains?

Let $S_{n}:= S_0 + \sum_{i=1}^{n}X_i$ be a simple random walk, $X_i$ are independent random variables with $P[X_i=1] = p, P[X_i = -1] = 1-p$. Let $M_n:=\max\{S_0, \dots, S_n\}$. The task at hand is ...
0
votes
0answers
37 views

Probability of Stopping Time Taking specific value - Random Walk 1d

We are considering a simple random walk $(X_n)_{n\in\mathbb{N}}$ starting at $X_0=0$ with $X_n=\sum_{i=1}^nY_i$ where $Y_i$ are iid and $\mathbb{P}(Y_i=1)=\mathbb{P}(Y_i=-1)=\frac{1}{2}$. We want to ...
0
votes
1answer
30 views

1D biased random walk - is the event of infinte many returns a tail event?

I am considering a biased random walk: $X_1,X_2,\dots$ iid with $\mathbb{P}(X_1=1)=p$ and $\mathbb{P}(X_1=-1)=1-p$ with $p\in[0,1]\backslash\{1/2\}$, $S_n=X_1+\dots+X_n$. In this setting I want to ...
3
votes
0answers
23 views

Self-avoiding random walk on $\mathbb{Z}^2$ getting stuck

Let $W_n$ be a self-avoiding random walk (SAW) on $\mathbb{Z}^2$, starting at the origin. Formally, $W_0=0$ and for $n\ge 0$, $W_{n+1}$ is chosen uniformly from the neighbours of $W_n$ which were not ...
0
votes
1answer
17 views

Writing down the transition matrix of a discrete Markov chain

Please consider the following scenario: One person is walking along a discrete circle induced by $\mathbb{Z}/n\mathbb{Z}$ In each round we roll a dice with $w\in\left\{2,\ldots n\right\}$ sides If ...
0
votes
1answer
20 views

Simple Random Walk probability of first visit

Consider a particle that moves according to a simple random walk. Denote by $X_n$ the position of the particle immediately after step $n$. Assume that $X_0 = 0$ and that, at each step, the ...
1
vote
2answers
165 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 ...
0
votes
0answers
22 views

Weighted random walk in 1-dimension

Suppose we have random walker on a line, he can only stay on sites which are, say, a distance $a$ from each other. At each step he can go left or right. Every time he steps on a site, makes the ...
3
votes
0answers
59 views

Sum of sequence of random variables infinitely often positive

Let $X_1,X_2,\ldots$ be an infinite sequence of independent (but not necessarily identically distributed) random variables with $E(X_i)=0$ for all $i$. Set $S_n=\sum_{i=1}^n X_i$. I want to show that ...
0
votes
0answers
46 views

Stationary distribution for random walks on directed graph

There is an equation (Eq. (2)) in reference by Lovasz and Winkler about the stationary distribution of a random walk on directed graphs that I would like to find references for where the equation is ...
3
votes
3answers
106 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 ...
2
votes
1answer
54 views

Random walk around circle

For one of the exercises of my homework I need to answer the following question, but I am not sure how I should apply gamblers ruin theory to solve this problem (it is stated as a hint, not that I ...
2
votes
3answers
215 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ with $p_1$, ...
5
votes
1answer
97 views

Probability of random walk returning to 0

Given a symmetric 1-dimensional random walk starting at 0 -- what is the probability of the walk returning $k$ times to 0 after $2N$ steps? I know that the total number of paths it can take is ...
2
votes
0answers
39 views

Hitting time of a maximum of random walk converges to that of Brownian motion

Suppose $S_n$ is a simple random walk; formally, $S_n=\sum_{i=1}^n X_i$ for $X_i\sim\mathcal{U}(-1,1)$, i.i.d.. Denote by $M_n$ the maximum of the random walk on $n$ steps; formally, $M_n=\max_{0\le ...
3
votes
1answer
27 views

Randomly moving about a lattice, probability that I return to my original location?

I thought of this question when I was walking aimlessly around my neighborhood. Here's my question: My house is on an infinite lattice of points: say my house is at $(0,0)$. I start walking north (it ...
12
votes
1answer
253 views

Random walks and diffusion limits

Imagine a long and narrow cylinder of radius r and a point particle that moves in the region bounded by the cylinder. The motion is specified as follows: starting at a point on the inner wall of the ...
2
votes
3answers
116 views

Random walk problem in the plane

Let a particle in the plane $R^2$ executes random jumps at discrete times $t= 1, 2, ...$. At each step, the particle jumps from the point it is a distance of lenght one. The angle of any new jump ...
4
votes
0answers
64 views

Uniform integrability of the maximum of a random walk with negative drift

Given $S_k^{(n)} = X_1^{(n)} + ... + X_k^{(n)}$ for all $k,n\in\mathbb{N}$, where the $X_i^{(n)}$'s are iid with mean $-\gamma$ for some $\gamma > 0$ and unit variance. Let ...
0
votes
0answers
29 views

Estimation of random walk maximum and minimum positions

I am trying to prove that, if a simple and symmetric random walk $S$ starts at $S_0 = 0$ and finishes at $S_n = N$ with $N > 0$, then if there is a maximum $M > N$ and a minimum $B < 0$ (both ...
2
votes
2answers
69 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
39 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
31 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
64 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
46 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
61 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
56 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
55 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 ...
1
vote
2answers
79 views

1-d random walk probability bound calculation problem

I'm recently reading the paper about digital fountain code "LT Codes" by M. Luby. There is a statement seems simple with the author "The probability a random walk of length $k$ deviates form its mean ...
3
votes
0answers
42 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 ...
0
votes
0answers
40 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 + ...
2
votes
1answer
58 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 ...
3
votes
1answer
78 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
42 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
443 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
14 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
40 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 ...
1
vote
2answers
241 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 ...
3
votes
1answer
66 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
86 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
0answers
33 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 ...
0
votes
1answer
50 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 ...
1
vote
1answer
39 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
38 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$ ...