For questions on random walks, a mathematical formalization of a path that consists of a succession of random steps.

learn more… | top users | synonyms

4
votes
1answer
103 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
15 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 ...
0
votes
1answer
16 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{ ...
1
vote
1answer
68 views

Reaching a level before another for a random walk

Suppose we are given a simple random walk starting in $0$, i.e. $(X_k)_{k\in\mathbb{N}}$ with $P[X_k=+1]=P[X_k=-1]=\frac{1}{2}$. What is the probability of hitting the level $a$ before hitting the ...
0
votes
0answers
13 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
34 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
64 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
33 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 ...
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 ...
4
votes
1answer
469 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
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$, ...
3
votes
2answers
211 views

Exponential ergodicity of biased random walk confined to the positive integer quadrant

I am looking at a discrete-time random walk on $(\mathbb{Z}^{+})^n$, where $\mathbb{Z}^{+}:=\{0,1,2,\dots\}$ and $n\in\mathbb{N}$. At any time, the random walk chooses a uniformly random co-ordinate ...
1
vote
3answers
1k views

Exact probability of collision of two independent random walkers after N steps

Two drunks start together at the origin at $t=0$ and every second they move with equal probability either to the right or to the left, each drunk independently from the other. What is the probability ...
1
vote
0answers
42 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 ...
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 ...
2
votes
1answer
302 views

A Boundary crossing result for discrete brownian bridge

Let $S_n$ be a random walk with gaussian increments with $S_0=0$, i.e. $S_n-S_{n-1}\sim N(0,1), n\geq 1$. Fix $a>0,b\in \mathbb{R}$ and $c<a+bn$. Define the new process $$ ...
0
votes
1answer
359 views

Simple Probability Matrix

Consider a simple model that predicts whether you pass you next test or not based on the result of your previous test. If you pass your previous test, then you have 0.2 chance you will pass your ...
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
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$?
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
1answer
47 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} ...
3
votes
1answer
309 views

Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I ...
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 ...
13
votes
2answers
1k views

Random walk on $n$-cycle

For a graph $G$, let $W$ be the (random) vertex occupied at the first time the random walk has visited every vertex. That is, $W$ is the last new vertex to be visited by the random walk. Prove the ...
3
votes
1answer
318 views

Random walk around circle [duplicate]

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 ...
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 ...
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 ...
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$ ...
0
votes
1answer
48 views

Random-walk in a pentacle (5 nodes)

There are a total of 5 nodes at the edge of a pentagram At each node, you have a 4 choices which will lead you to either a destination node or non-destination node. Assume the decision of path is ...
2
votes
1answer
29 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 ...
7
votes
3answers
605 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
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
56 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 ...
-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) ...
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 ...
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. ...
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: ...