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

learn more… | top users | synonyms

1
vote
0answers
11 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
47 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 ...
2
votes
0answers
71 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
7 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
5 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
62 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
55 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
31 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
42 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
73 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 ...
2
votes
1answer
25 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
23 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
18 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
45 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
73 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
36 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
16 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
112 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
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
0answers
30 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
30 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
44 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
50 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
61 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
30 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
19 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
21 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
286 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
119 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
31 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
18 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
40 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
121 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
43 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
32 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
21 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
59 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
56 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
56 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
35 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
51 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
64 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 ...