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
4 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
12 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
32 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
58 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
31 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
13 views

Escape probability in difussion 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
68 views
+50

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,...\right\}$ be a simple random walk on the integers ...
0
votes
0answers
20 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 ...
9
votes
1answer
207 views

Probability that multiple random walks are back at the origin

Consider a uniformly chosen random very long vector $A$ with $A_i \in \{-1,1\}$ and a uniformly chosen random vector $B$ of length $n$ (assume $n$ is even) with $B_j \in \{-1,1\}$. For a given $i$, ...
2
votes
0answers
28 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
29 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
41 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
46 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
58 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
26 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
16 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
18 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
72 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
284 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
111 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
26 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
17 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 ...
1
vote
0answers
39 views

Polya's random walk and gambler's ruin: interpretation in higher dimensions

I've read that Polya coined the term "Random Walk." He analyzed the 1-dimension example and proved that the chances of returning to any point on the line is ultimately 100%. This is how one can think ...
11
votes
1answer
270 views

How to combine the four Theorems in order to prove the statement?

I have a question concerning a statement about Random Walks on $\mathbb{Z}$. Let $F$ be a distribution on $\mathbb{Z}$ which has mean $0$ and finite variance. Let $\left\{X_1,X_2,\ldots\right\}$ be an ...
2
votes
3answers
115 views

How often does a one-dimensional lazy random walk end at the origin?

This seems like it's probably a solved problem, but I don't seem to be googling the right keywords. I want to know the probability that a lazy random walk on $\mathbb{Z}$ ends where it started. To be ...
0
votes
0answers
42 views

Stopping times and expectation for the symmetric random walk

Let $X_n : \Omega \to \{ -1, 1 \}$ be a random variable with $P(X = -1) = P(X = 1) = 1/2$, like tossing a coin, and $M_n = \sum_{i=1}^n X_n$. Also let $\tau_m : \Omega \to \mathbb N \cup \{ \infty\}$ ...
0
votes
0answers
27 views

Probability of hitting zero

Suppose time is discrete. $X_{t+1} = X_t + x_t$. $x_t$ is of continuous value, iid with mean zero and finite variance. Let initial condition $X_0>0$, how can I prove that the probability of $X_t$ ...
2
votes
1answer
28 views

Distribution of the norm of a multivariate normal distributed random variable

As a part of a project, I would like to know what the distribution is of the absolute distance people traveled on a particular moment of the day (in comparison to their home). I think it would be best ...
0
votes
0answers
20 views

visiting $n$ distinct sites in a random walk of $n$ steps on $\mathbb{Z}^2$

Consider the symmetric random walk on $\mathbb{Z}^2$. I am looking for references about the number of ways to visit $n$ distinct sites in $n$ steps where I don't count the origin, so visiting $n+1$ ...
3
votes
1answer
32 views

number of loops of length $n$ without crossings in random walk on $\mathbb{Z}^2$

Consider the symmetric random walk on $\mathbb{Z}^2$, where you go in one of the four directions with probability 1/4. We start in 0. My question is whether there are results on counting how many ways ...
1
vote
1answer
30 views

Graph theory and Combinatorics - how many walks?

The question is more combinatorial, but it is based on graph theory. How many walks with length $k$ does an $r$-regular graph with $n$ nodes contain? Well $r$-regular means that all nodes have $r$ ...
1
vote
1answer
55 views

Dirac delta function with a sum as the argument

I'm reading "First steps in random walks" by Klafter and Sokolov, and I don't understand this step involving the Dirac delta function. They want to obtain the probability density of having a walker at ...
4
votes
1answer
54 views

Simple random walk: What is the probability that the hitting time is exactly 2n?

I refer to the random walk $(S_n)_{n \geq 1}$ where $S_n = X_1 + \cdots + X_n$ and $X_i$ are i.i.d random variables taking values $\pm 1$ with equal probability. I want to know how to show that ...
0
votes
0answers
16 views

Random symmetric walk. [duplicate]

So there's this assignment I'm doing. Let p=1/2. I already proved that for a random walk P(X_n=k) = (n over (n+k)/2) * 2^(-n) Now I need to prove that lim n->inf (n^(1/2))P(X_2n=2k)) = 1/pi. Given ...
1
vote
0answers
30 views

Proof of the Ballot Theorem Random Walks

Ballot Theorem: For $b>0$ the number of paths (0,0) to (n,b) that do not revisit the x axis is $\frac{b}{n}\mathbb{P}_{0}(S_n=b)$. MY ATTEMPT Now the first step of this path is to the point ...
4
votes
0answers
50 views

Discrete Time Two sided Gaussian Random Walk : Hitting Time Distribution

I am looking at the hitting time of a two sided Gaussian random walk i.e. $S_{n}=\sum_{i=1}^{n}X_{i}$ where $X_{i}$ are i.i.d normally distributed random variables. The hitting time is ...
-3
votes
1answer
92 views

Variance of a special random walk

I am trying to find the variance of the following special random walk: Suppose that $U=(U_1,U_2,...)$ is a sequence of independent random variables, each taking values $u$ (for up) and $d$ (for down) ...
2
votes
1answer
33 views

Find the probability generating function $G(s)$ of this branching process.

Suppose that $X_n$ is size of the $n$th generation of a branching process started from a single individual, where each individual has a random number of children with probability mass function: ...
0
votes
1answer
47 views

Escape probabilities in a random walk.

So, a lot of theory in symmetric random walks seems to concentrate on 'hitting/stopping times' and things like that. So I started wondering... How would I go about calculating the probability of ...
2
votes
1answer
63 views

Can someone help explain a proof from Feller Vol1 III.5?

One will need a copy of Feller's text (3rd edition) to answer this question. The proof I'm having difficulty with is Theorem 1, pages 84-85. When he discusses the r=1 case, he says ... "To the ...
2
votes
0answers
30 views

Consequence of random walk with positive speed on a graph

Consider a random walk $X(n)$ on a vertex-transitive graph where the random walk has positive speed, i.e., $$ \lim\limits_{n \rightarrow \infty} \frac{d(X(n), X(0))}{n}= \alpha>0$$ almost surely. ...
6
votes
1answer
69 views

A number-theoretic random walk on the integers

Suppose a random walker starts at $S_0 = 2$, and walks according to the following transition probabilities: If the walker is on the $n$th prime number $p_n$, she moves to either $p_n + 1$ or ...
2
votes
0answers
41 views

Why do we use an exponential Martingale for the stopping time of a BIASED random walk?

The following is a passage from the lecture notes: Let a simple random move to the right with probability $p$ and to the left with probability $q = 1 − p$. We want the probability that it hits ...
0
votes
1answer
48 views

Limit of random walk on $\mathbb{Z}$

$$\limsup_{n \to \infty} \frac{S_n}{\sqrt{n}}=+\infty, \quad\liminf_{n \to \infty} \frac{S_n}{\sqrt{n}}=-\infty \quad P\text{-a.s.}$$ Here $S_n$ is a random walk on $\mathbb{Z}$. I managed to show ...
1
vote
1answer
105 views

Probability of absorption of a biased random walk when the starting point has binomial distribution

Consider a random walk $\{0,1, ... , N\}$ with up probability $p$ and down probability of $p-1$ where $p \neq 1/2$. Suppose there are absorbing barriers at $0$ and $N$ and that the starting point, ...
1
vote
0answers
25 views

Easy Question from Application: Estimate for transition probabilities of random walk - finding a coupling

SHORT VERSION: Find appropriate Coupling Suppose we have a random walk on the natural numbers, where we go to the left with probability $p_L \geq \frac{1}{6}$, to the right with probability $p_R\leq ...
3
votes
1answer
49 views

Class of graphs with symmetric random walk

Let $(V,E)$ be a graph and let $X_n$ be a random walk on the graph. At every step, the walker at $x$ jumps to one of the neighbors drawn uniformly at random among all the vertices $y$ such that there ...
1
vote
0answers
35 views

One dimensional Lazy random walk, $O(1/\sqrt{n})$?

Suppose that we have a Lazy 1-dimensional random walk $X_n$ valued in $\mathbb{Z}$, i.e. $$X_n = \sum_{i}^{n} \xi_i\;\;\;\;\;\;\;\;(\xi_i\;\text{iid}) $$ and $$\frac{1}{4}=P(\xi_1= 1)=P(\xi_1 =-1) ...
1
vote
0answers
34 views

A 'mix' of simple and lazy simple random walk

Consider a $\mathbb{Z}$ valued markov chain $X_n$ which evolves as follows. $$P(X_{n+1}=y | X_n) =\begin{cases} \frac{1}{2}, y=X_n+1, X_n-1, |X_n|>K \\ \frac{1}{4}, y = X_n-1 , y= X_n+1, ...
3
votes
3answers
53 views

How to show $M_n = X_n^2-n$ is a martingale?

Let $X_n, n = 0, 1, 2, . . .$ denote an unbiased Normal Random Walk. $X_0 = 10$, and $X_{n+1} = X_n + Y_{n+1}$, with $\{Y_n\}$ are i.i.d. $N(0, 1)$. Then how can I show that: A) $M_n = X_n^2-n$ is a ...