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
1answer
35 views

Random walk question

here is the problem that I have been trying to do: N+1 plates are laid out around a circular dining table, and a hot cake is passed between them in the manner of a symmetric random walk: each time it ...
5
votes
1answer
24 views

counting combinations of {+1, -1} with constraints

I'm trying to count the number of ways of arranging a sequence of length $N+2L$ made of "$+1$" and "$-1$", with the following two conditions: 1) the total has to sum to $N$ 2) no partial sum is ...
2
votes
2answers
42 views

Random sequence of $0$'s and $1$'s - what is the average 'in a row' succession

Let's say we create a sequence from coin tossing. Heads will be signified as $0$ and tails as $1$ Let's define $R$ as a successive elements(in the given sequence) of the same value. for example we ...
1
vote
1answer
31 views

Proof that random walk visits zero infinitely many times

Since the Green function $G(x,1)=\sum\limits_{n\in \mathbb{N}_0}P(S_n=x), x\in\mathbb{Z}^d$ gives the expected number of visits to $x$ in a random walk, I'm asked to prove the following: I have to ...
1
vote
2answers
26 views

One dimension symmetric random walk

We have person that starts at $x=0$ and at every step he goes left with probability $0.5$ and right with probability $0.5$. What is the probability he will arrive at $x=3$ at some time? I got ...
0
votes
4answers
95 views

Random walk on a finite square grid: probability of given position after 15 or 3600 moves

An ant is walking on the squares of a 5x5 grid - it starts in the center square. Each second, it will choose (with equal probability) to do one of the following: Move north one square Move south ...
3
votes
1answer
97 views

Expected time to get from bottom left to top right in a square

Consider a two dimensional random walk starting at the bottom left hand corner of an $n$ by $n$ square. At each step you take one step up, down, left or right distance $1$. Each choice has equal and ...
1
vote
0answers
13 views

Simple random walk conditioning on non-return

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0=0$. Let $P_{k,j}$ be the probability that the walker hits the point $k$ without returning to the origin in ...
2
votes
1answer
51 views

Intuition in Random walk

Suppose $X_i$ are i.i.d. r.v. $S_n=X_1+\cdots+X_n$ is random walk. Why $\mathcal{F}_n =\sigma(X_1,\cdots,X_n)$ are called the information known at time n? I think We only know the measurability of ...
1
vote
1answer
96 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
30 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
29 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
105 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 ...
2
votes
0answers
17 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
39 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
28 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
34 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
49 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
42 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
34 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
59 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
44 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
54 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
32 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
59 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
70 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
31 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
67 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
41 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
41 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
26 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
33 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
25 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
25 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
61 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
56 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
82 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
109 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
45 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
33 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
29 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
74 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
42 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
34 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
84 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
54 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
68 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 ...