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
42 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
89 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
47 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
71 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
55 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
147 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
44 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
239 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
29 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
79 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
19 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
26 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
38 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
48 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
26 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 ...
8
votes
0answers
121 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
50 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
63 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
170 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
51 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
338 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
26 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
76 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
122 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
44 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
66 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
90 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
45 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
49 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
33 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
240 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
115 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
76 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
32 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
145 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
25 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
86 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
80 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
85 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
96 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
81 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 ...
0
votes
0answers
35 views

Function/algorithm to generate a random walk on a graph

I'm looking for a graph function or an algorithm that can generate a random fluctuating random walk that will eventually converge between the value of y = 0 and y = 1, more or less after a number of ...
0
votes
0answers
60 views

Diffusion Constant of a 1D Random Walk

Brownian motion(Wiener process) is a limit of Random walk. What is the diffusion constant for a Brownian motion that is a limit of a 1D Random Walk, with $\frac{1}{2}$ probability of moving to each ...
2
votes
1answer
81 views

Autocorrelated, discrete, bounded and symmetric random walk with no edge attraction

I need to move over a discrete set of linearly organized.. let's say "Japan steps" $S=\{0,\dots,c\}, c \in \mathbb{N}^*$. My current position is given by $d \in S$. On each time step, I need to draw ...
3
votes
3answers
353 views

Probability that after 10,000 steps (+-1) you'll end up at the origin. How to use Central Limit Theorem?

Starting at the origin and taking one step left or right with equal probability, what is the probability that you'll end up at 0 after 10,000 steps? I figured it'd be ...
8
votes
1answer
193 views

Expected number of times Random Walk crosses 0 line.

Suppose we have a simple random walk: $$ x_t = x_{t-1} + \epsilon_{t} $$ Where $$ \epsilon_{t} = iid\ \mathcal{N} (0,1) $$ Assume that x starts at ...
2
votes
1answer
77 views

Derive diffusion coefficient for heat equation from random walk simulation

I want to simulate the underlying stochastic process of diffusion on a microscopic level and compare the result with the solution of the heat equation. However, I'm not able to match the solution of ...
0
votes
0answers
20 views

What is the measure for a Random Walk?

Let $F$ be a distribution on $\mathbb{Z}$. Let $(X_1,X_2,...)$ be an i.i.d. sequence of random variables with distribution $F$. Then $S_0=0, S_1=X_1, S_2=X_1+X_2,...$ is called the random walk with ...