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
0answers
43 views

Excursion of random walk conditioning on return

Consider a simple random walk in one dimension starting from the origin. Let $\epsilon>0$. How to prove that, conditioning on the event that the random walk is at the origin at time $n$, the ...
2
votes
1answer
62 views

Comparing hitting probabilities vs comparing mean hitting times of a random walk on a graph

I am trying to understand random walks on graphs and whether an intuition that I have can be made rigorous mathematically, and whether it is also true. Let $G$ be a finite, connected undirected graph ...
1
vote
0answers
29 views

Prove that uniform distribution on a set of vertices $V$ is stationary if the graph is regular.

I was going through Random walks on graphs: A survey It was stated that: Uniform distribution on a set of vertices $V$ is stationary if the graph is regular. Can anyone give me some hints to ...
2
votes
1answer
31 views

Inequality for General random walks

Let $S_n=(S_n^1,...,S_n^d)$ be a random walk with distribution $p(y,z):=\mathbb{P}\{S_{n+1}=z\mid S_n =y\}=p(z-y)$. Then $\mathbb{P}\{S_{2n}=0\}\geq(\mathbb{P}\{S_2=0\})^n\geq p(x)^{2n}\forall x\in ...
0
votes
0answers
26 views

Infinite expected number of visits with Green function

The random walk Green function is defined by $G(x,1) = \sum_{n\in \mathbb{N}_0} P(S_n = x)$, with $x\in\mathbb{Z}^d$. $G(x,1)$ equals the expected number of visits to $x$. Now I want to prove that ...
1
vote
2answers
78 views

Showing stopping is finite almost surely

Consider a discrete random walk taking values +1 or -1 with probabilities p and q, respectively. Let $S_n = \sum_{k=1}^{n}X_k$. Let $[-A,B]$ be an interval, $A,B \geq 1$. Now define $$\tau =\min(n:n ...
1
vote
2answers
28 views

Clarification on Two-player Gambler's Ruin variant.

I looked around and found many questions related to two-player variants of Gambler's Ruin but could not find what I had in mind. I needed clarification on a certain step while deriving the expression. ...
0
votes
0answers
40 views

Hitting probabilities for random walk with +m/-n steps

Random walk theory in the real axis: a frog starts at k initially, and in each move, it moves either by distance m to the right (from i to i+m) or by n to the left(from i to i-n), where k,m,n are ...
2
votes
0answers
75 views

Expected distance of a random walk of distance $k$ on the $k$th step

I am trying to sharpen my intuition on some random-walk style results. Suppose we are looking at a random walk on $\mathbb{Z}$ starting at $0$. At the $k$th step, we either walk to the left $k$ ...
1
vote
0answers
44 views

2-dimensional random walk experiment

Question: Consider a board covered by square tiles(like a chess set only of a size of your choosing) and colored like a chess set. Two "people" are placed in different areas of the board and ...
3
votes
1answer
48 views

Step in computation of the expected cover time for the simple random walk on a discrete circle

I'm having a little trouble understanding part of an example in Lawler's Intro to Stochastic Processes ("Simple Random Walk on a Circle" example on page 32). The problem is the following: Suppose ...
0
votes
0answers
41 views

Can a Random Walk algorithm be considered a computational intelligence algorithm?

I am implementing different computational intelligence algorithms from the local search area. These are Hill Climbing and Simulated annealing. Also I am implementing another algorithm with a mere ...
0
votes
1answer
87 views

Probability Generating Function of a Stopping Time, Random Walk

Let $\{S_k\}_{k\geq0}$, $S_0=0$ be a symmetric simple random walk. For an integer $n\geq1$, let $\tau_n=min\{k\geq1:S_k\notin(-n,n)\}$ be the first time k such that $S_k$ leaves the region $(-n,n)$, ...
0
votes
0answers
26 views

Limit of Covariance and Correlation of Random Walk

Let $S_n=X_1+...+X_n$, $n\geq1$ be a random walk, where $EX_k=\mu$ and $Var(X_k)=\sigma^2$, $0<\sigma^2<\infty$. a)Find the covariance $Cov(S_n,S_m)$ and the correlation coefficient ...
7
votes
1answer
218 views

Last vertex visited by the symmetric random walk on a discrete circle

$n$ cats form a circle, indexed from $0$ to $n-1$. At first, there is a ball at the cat $0$. We throw a coin with the probability of $p$ heads up. If the coin is heads up, we pass the ball clockwise, ...
3
votes
0answers
26 views

Random walks with limited number of visits

I'm interested in random walks (esp. their hitting times) such that the number of visits to each state is limited by some parameter $K$. Is there any canonical name for such stochastic processes? ...
3
votes
0answers
69 views

Random walks intuition [closed]

I came across the reflection principle and this explanation at Is there an intuitive way to see this property of random walks? However, I can't understand the reasoning in the answer about mirroring ...
2
votes
1answer
17 views

Formula for the analytical computation of Eigenvalues for random walks of order one and two on regular lattices

I have a question with respect to random walk penalties in statistics. In Bayesian statistics an adequate prior for modeling a $n$-dimensional random vector $\boldsymbol{x}$ as a random walk of order ...
0
votes
1answer
25 views

Calculating the Variance of a Pure Random Walk

I am trying to calculate the first two moments of the random walk below: $y_t$=$y_0$+$\sum_{j=1} ^t u_j$ Mean: E[$y_t$]=$y_0$ Variance: E[$y_t ^2$]=t$\sigma^2$ I understand how to obtain the 1st ...
0
votes
0answers
34 views

When is a lazy random walk matrix positive definite?

There are a number of nice results about when the graph Laplacian is positive definite and positive semi definite. However, I can't seem to find any analagous results for random walk matrices, and was ...
0
votes
0answers
47 views

An exercise about random walk introducing to wiener process

I learn stochastic process by myself and currently, doing an exercise about random walk. Suppose a random walk $\eta(t,s)$, (1) $\eta(0,s) = 0$; (2) $\eta(t,s)$ is defined on a set of sample point ...
0
votes
0answers
24 views

How to model time changing random variables

Lets say I have a random variable $X(t)$ which describes some unit of motion of a living organism and $X(t)$ is itself a timeseries since this unit of motion changes in time. I would like to be able ...
6
votes
0answers
106 views

A generalization of simple random walk

Suppose $S_n, n\geq 0$ is a martingale on $\mathbb{R}$ such that $S_0=0$ and $|S_{n+1}-S_{n}|\in [\frac{1}{2}, 1]$. Prove that there exists $c,C>0$ s.t. $$ \frac{c}{\sqrt{n}} \leq P( S_1\geq ...
1
vote
0answers
48 views

Biased Random Walk with Variable Probability

Consider a random walk in which the probability to move forward in time $t$ is $p_t$ and the probability to move backward is $q_t=1-p_t$ with $p_t<q_t$ with $p_t<p_{t+1}$ and $q_t>q_{t+1}$. ...
2
votes
0answers
61 views

Is the sudden appearance of transient random walks in 3-dimensions a phase transition?

Consider a particle walking uniformly at random on the infinite d-dimensional lattice $\mathbb{Z}^d$. This is symmetric random walk. Symmetric random walk in two dimensions almost always returns to ...
3
votes
0answers
161 views

Maximum difference between tails in absolute value

I toss a fair coin $n$ times. Some notation: $S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$. $M_n=\max(S_1,S_2,\dots,S_n)$, ...
2
votes
0answers
50 views

Survival probability of 1D Random Walker [duplicate]

For a 1 D random walk on $Z$ axis, starting at $z=0$, equal probability to go to right or left, what is the probability that during the first k steps the walker's position remains $z\leq m$? This is ...
8
votes
1answer
333 views

Expected travel of random walk in arbitrary game with multiple payouts

As explained here, the average distance or 'travel' of a random walk with $N$ coin tosses approaches: $$\sqrt{\dfrac{2N}{\pi}}$$ What a beautiful result - who would've thought $\pi$ was involved! ...
0
votes
0answers
11 views

Limiting Behavior of Zero Mean Random Walk [duplicate]

Suppose $\{ X_t \}$ is a sequence of i.i.d. random variables, with support $\{-1,1\}$ and distribution $P(1)=P(-1)=1/2$. Thus, $S_t = \sum_{s=1}^{t} X_s$ is a zero mean random walk and $$-\infty = ...
0
votes
1answer
20 views

Random Walk Limit Behavior

Suppose $\{ X_t \}$ is a sequence of i.i.d. random variables, with support $\{-1,1\}$ and distribution $P(1)=P(-1)=1/2$. Thus, $S_t = \sum_{s=1}^{t} X_s$ is a zero mean random walk. Also, $S_t$ is a ...
0
votes
0answers
75 views

Probability that the nunber of ties in $2n$ coinflips is $k$

A fair coin is flipped $2n$ times. If the number of "heads" and the number of "tails" coincide, a tie is reached. What is the probability $p_k$, that the number of ties occuring is exactly $k$, ...
2
votes
1answer
105 views

Probability, that a sequence of $n$ coin-flips contains $k$ changes of the lead

A fair coin is flipped $n$ times. What is the probability $p_k$, that the lead between "heads" and "tails" changes exactly $k$ times ? For example, the sequence $$HHTTTHH$$ contains two changes ...
1
vote
1answer
43 views

How to prove that $\Bbb{P}(X_{4l} = 0) \leq c_l (2d)^{-2l}$ for some constant $c_l$?

Let $(X_n)$ be a simple random walk on $\Bbb{Z}^d$ starting at $0$. (The dimension $d$ will vary, but I will suppress the dependence on $d$ for brevity.) I encountered a statement which claims that ...
0
votes
1answer
62 views

probability distribution for each step in a drunkards walk

Imagine a typical drunkards walk (2D) made of steps $\ell$ each of length $L$ in any direction. I was told that the probability distribution of each step can be written as a Dirac delta like this ...
0
votes
2answers
83 views

Limit of an absorbing random walk. (Limit of power of real symmetric matrix)

I have a problem that comes from absorbing random walks on a connected undirected graph $G$ with two types of nodes, absorbing nodes and free nodes. We randomly pick a node to start, once the random ...
1
vote
1answer
43 views

Obtaining a $3$-dimensional simple random walk from a $d$-dimensional simple random walk with $d>3$.

Suppose $S_n$ is a $d$-dimensional random walk with $d>3$. Let $T_n=(S_n^{(1)},S_n^{(2)},S_n^{(3)})$, that is, we obtain $T_n$ by looking only at the first three coordinates of $S_n$. It is clear ...
0
votes
1answer
42 views

Hitting times of a biased continuous time random walk

Let $X_{s \geq 0}$ be a continuous time random walk on $\mathbb{Z}$, i.e. waiting times between jumps are exponentially distributed with mean one. The random walk is biased: $\mathbb{P}(X_s\text{ ...
0
votes
0answers
22 views

Two-dimensional random walk in force field

I have a random walk in two dimensions with a force field. $\vec{x}_{\tau+1} = \vec{x}_\tau + \vec{F}(\vec{x}_\tau)$, where $\vec{x}$ is the position and $\vec{F}(\vec{x}) = ...
-1
votes
1answer
205 views

Conditional Gambler ruin problem

A gambler repeatedly plays a game where in each round, he wins a dollar with probability 1/3 and loses a dollar with probability 2/3. His strategy is “quit when he is ahead by 2 dollars”, though some ...
1
vote
1answer
96 views

Expected Value of a Mosquito

A mosquito is walking at random on the nonnegative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
3
votes
0answers
66 views

What is the area covered by a Random walk in a 2D grid?

I am a biologist and applying for a job, for which I need to solve this question. It is an open book test, where the internet and any other resources are fair game. Here's the question - I'm stuck on ...
0
votes
0answers
25 views

Escape probability in diffusion and random walk

I know that in one and two dimension the probability of a random walker to not come back to the origin is zero and in three dimension it is non zero. Is this fact true for diffusion in one, two and ...
4
votes
1answer
134 views

Normalized hit times of a simple RW converge in distribution to hit times of standard Brownian Motion

I would appreciate some hints or guidance towards solving the following exercise: Let $\left\{ S\left(j\right)\thinspace:\thinspace j=0,1,\ldots\right\}$ be a simple random walk on the ...
0
votes
0answers
23 views

Probability of random walk visit in nonameanable graphs

Consider a vertex-transitive nonameanable graph. Consider a site $x$ having a graph distance $d$ from the origin and let $X(n)$ be a random walk starting from $x$. Is there a general upper bound as a ...
2
votes
0answers
62 views

Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...
-1
votes
1answer
59 views

Mean Squared Displacement of Biased Random Walk [closed]

If $x_t=x_{t-1}+\mathcal{N}(\mu,\sigma)$ and $x_0=0$ what's the value of $\langle x_t^2\rangle$?
1
vote
0answers
69 views

Expected distance of biased 1d random walk with 0 drift

There were many question about biased 1d random walks earlier, but as far as I can tell none of these are directly related. Let $p,q>0$ such that $p+q=1$. Let $X_0=0$ and $X_{i+1} = X_i+1$ with ...
3
votes
1answer
70 views

Expected number of return for a random walk on a graph

Let $G$ be a simple, connected undirected graph of order $n$ and vertex set $\{v_1,\ldots,v_n\}$ and let $P = (p_{i,j})$ be a $n \times n$ matrix where $$p_{i,j} = \left\{ \begin{array}{ll} ...
1
vote
1answer
67 views

Why does symmetry happen in reset-based random walks?

Studying the basic concepts about random walks / brownian motion, and based on the idea of a Möbius-based walk in Wolfram's website, I wanted to try my own version of it in Python to compare it with ...
3
votes
0answers
61 views

Random matrices, eigenvalue distribution.

I just investigated randn(1024) + 1i*randn(1024), a 1024x1024 complex valued matrix with elements both real part and imaginary part drawn from $\mathcal{N}(\mu = 0, \sigma = 1)$. I was a bit surprised ...