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
22 views

Problem about Random walk and Stopping time.

Here is an example in "Probability with Martingales" My questions are: (1)Does equation (a) hold for $T=\infty$? (2)The equation:$$\mathbb{E}M_T^\theta=1=\mathbb{E}[(sech \theta)^Te ...
0
votes
0answers
24 views

Maximum of a Gaussian random walk with non-identical steps

Consider a sequence of independent normal random variable $X_1,...,X_n$ with (negative) means $\mu_1,...,\mu_n$ and standard deviation $\sigma_1,...,\sigma_n$. Define \begin{equation} S_k = ...
0
votes
1answer
21 views

Random walks on connected finite graphs

On a finite connected graph if a random walked is choosing the next vertex uniformly at random from among the edges of its current vertex, then it looks quite obvious to me that given an infinite walk ...
0
votes
1answer
81 views

Why is the expected average displacement of a random walk of N steps not $\sqrt N$?

Let $D_N$ be the expected average of the displacement of a random walk on $\mathbb Z$ from the origin, where $N$ is the number of steps, each of which is either $-1$ or $1$. We take the definition of ...
1
vote
0answers
15 views

Comparing hitting time of two random walks

There are two random walks, $S^t_i=S^{t-1}_i+ X_i^t$ for $i=1,2$, $X^t_i$ i.i.d they have boundaries $h_1$ and $h_2$ respectively. I'm wondering if it's possible to calculate the probability that one ...
1
vote
1answer
37 views

Invariant mesure of a reflected random walk

Let $(X_n), n \geq 0$ be a Reflected Random Walk defined by: $X_0 = 0$ and: $ X_{n+1}=\max( 0 , X_n + \xi )$ $\xi $ is a random variable such that $P(\xi=a)=\theta$ and $P(\xi=-b)=1-\theta$ for a ...
1
vote
0answers
23 views

Conditional return time of simple random walk

Consider a simple random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0 = 0$. The probability to jump to the right neighbour is $p \geq \frac{1}{2}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, ...
0
votes
0answers
30 views

Reflected random walk

Suppose that $X_n$ is a reflected (in 0) random walk with parameter $\theta$. So $X_{n+1}-X_n = 1$ with probability $\theta$ , and -1 with probability $1-\theta$ when $X_n \geq 1$, if $X_n=0$ then ...
7
votes
1answer
44 views

Random walk on cubic lattice

Suppose at every point of the cubic grid in n dimensions is a particle, and at every timestep every particle moves at random to one of its 2n neighbours. As time goes to infinity, what is the ...
0
votes
2answers
36 views

Non-Probabilistic Argument for Divergence of the Simple Random Walk

The simple random walk is one starting at $0$ with steps of $-1$ and $1$ with equal probability. Is there a proof not involving (too much) probability - preferably number-theoretic - of why this walk ...
0
votes
0answers
28 views

Exact probability distribution for hitting time of simple random walk

Consider simple random walk on the line starting from the site $y \in \mathbb{N}$. With probability $p$ the walker moves to the right and with probability $1-p$ to the left. Call $\tau$ the first time ...
1
vote
0answers
58 views

Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
0
votes
1answer
29 views

Distributions of local times of a single excursion of 1D random walk

Consider Simple Random Walk in one dimensions, starting from $x \in \mathbb{Z}^+$. The walker jumps to the right with probability $p$ and to the left with probability $1-p$. Assume $p \leq ...
1
vote
1answer
39 views

Random walks with finite chance of escape

In a recent answer I gave a combinatorial interpretation for the sum $\sum_{n=1} \binom{2n}{n}\frac{4^{-n}}{n+1}=1$: namely, that it corresponded to the probability of all outcomes adding to $1$. A ...
2
votes
2answers
50 views

Limit value of a product martingale

This question came from a problem i was solving for self-study. I'll state the problem first: Let $Y_n \sim \mathcal N(0,\sigma^2)$ be independent normally distributed variables, $X_n = ...
0
votes
0answers
31 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
53 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 ...
3
votes
1answer
63 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
30 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
61 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
30 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
40 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 ...
3
votes
0answers
25 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
25 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
24 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 ...
0
votes
0answers
23 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
52 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 ...
2
votes
1answer
63 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 ...
5
votes
1answer
104 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
41 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 ...
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
1answer
28 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 ...
4
votes
0answers
71 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
34 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
70 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
42 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
32 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
73 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
63 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
68 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 ...
3
votes
0answers
43 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
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 ...
0
votes
0answers
45 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
85 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
43 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
448 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
15 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 ...