Questions tagged [random-walk]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Two random walks hitting time

given two continuous time random walks $X_0$, $X_1$ on $\mathbb{Z}$ which Start in 0 and 1 respectively, have jumping times which are $\exp(2)$ distributed and we define $\tau = \inf\{ t: X_0(t)= X_1(...
-2
votes
1answer
20 views

How does one decompose the Π matrix from the cointegration relationship? [closed]

The $2 \times 2$ matrix $\Pi$ is \begin{bmatrix}-0.5&-1.0\\-0.25&-0.5\end{bmatrix} where $\Pi = \alpha \beta’$. The result is $\begin{bmatrix}-0.5 \\ -0.25 \end{bmatrix}$ for $\alpha$ ...
1
vote
0answers
33 views

simple walk on $\mathbb{Z}$

Consider the simple random walk $(X_n)_{n \in \mathbb{N}}$ starting from $X_0 = 0$. Consider $\varepsilon>0$, show that, for all $\delta>0$, $$ \lim _{n \rightarrow \infty} \mathbb{P}\left(\frac{...
1
vote
0answers
17 views

Random walk with absorbing barriers: total probability of absorpion

Consider a random walk that moves up by 1 unit with probability $p$ and down by one unit with probability $1-p$. It starts at $0$ and there is one absorbing bareer at $-2$. How can I calculate the ...
3
votes
1answer
46 views

Why does Polya's random walk theorem for $d>3$ follow from $d=3$?

Im reading this paper in the Direct counting argument section(I'm only interested in this method of proof) and it is said that once we have proven $d=3$, the $d>3$ case follows as a generalisation ...
1
vote
0answers
46 views

A random walk on a circle with $n$ points. What is the probability that the walk will end at point $i$ ? ($0 \le i \le n-1$) [duplicate]

$n>1$ points numbered $0,1,2,...,n-1$ are placed on a circle. A random walker starts his journey at point $0$ and at each step, he steps randomly on the circle to one of the two closest points. For ...
3
votes
1answer
62 views

Explanation of Durrett example 5.2.13

I am referring to Durrett's " Probability Theory and Examples". I am not including everything that's in the example as given in the book but only the relevant part for which I need ...
2
votes
0answers
69 views

Whats the chance that upon randomly adding $\pm1$ to a number, it eventually reaches $0$

Start with an integer $k$. Then at each step either add or substract $1$ randomly, if after some amount of steps you get the number $0$ the process terminates. What's the probability that the process ...
0
votes
0answers
21 views

Puzzle -- Does transformation from multiplicative random walk to additive change its properties?

Suppose we have the following stochastic process: $$x_t=(1+\gamma)x_t, \ \ \ with \ \ 1/2 \ \ probability$$ $$x_t=(1-\gamma)x_t, \ \ \ with \ \ 1/2 \ \ probability$$ where $\gamma$ is some constant ...
1
vote
0answers
40 views

Understanding a definition from a French paper

I want to understand a very special case of the following situation. The following is from the paper "Simplicité de spectres de Lyapunov et propriété d'isolation spectrale pour une famille d'...
4
votes
2answers
65 views

How can I obtain or sample a random Rubiks Cube shuffle?

I was thinking of how to obtain a random shuffle of the Rubik's cube with uniform probability. Simply trying a randomly generated sequence of turns will not necessarily produce a uniform distribution ...
2
votes
0answers
27 views

Intuitive explanation of the transience of symmetric random walks

We know that the symmetric random walk on $\mathbb{Z}^d, \, d \geq 3$ is transient. However, if we looked at each coordinate separately, we would see a lazy symmetric random walks on $\mathbb{Z}$, ...
3
votes
0answers
31 views

Ornstein-Uhlenbeck Bridge as a Random Walk Limit (The Urn Game)

An urn contains $N$ red balls and $N$ black balls. Consider the game in which you sequentially draw balls from the urn: a) with replacement; b) without replacement, until the $2N$ balls are all drawn; ...
1
vote
1answer
24 views

Combinatorical Counting of Non-negative Simple Random Walks

Given a simple random walk $S_n = \sum_{i=0}^n X_i$, where $X_0=0$ and $X_{i>0} \in \{-1,1\}$, the count of positive walks (for which $\forall i>0 : S_i > 0 $) that end in $u > 0$ (i.e. $...
1
vote
0answers
37 views

Mean minimum distance of a random walk for a certain number of steps to a given point in space

Given there is a 3D random walk starting at the origin $\vec{0}$. For simplicity, lets assume a lattice, where the walker randomly goes exactly one unit per step in one of the coordinate directions. ...
0
votes
0answers
33 views

Brownian motion as a limit of random walk

In Stein and Shakarchi's functional analysis, We recall the random walk in $\mathbb{R}^d$...is given by a sequence $\{s_n\}_{n=1}^\infty$ where $$s_n = s_n(x) = \sum_{k=1}^n \tau_k(x),$$ with $s_n(x) ...
1
vote
0answers
37 views

Random walk of $k$ particles on a $n$-dimensional hypercube

I would appreciate your help with the following, if possible. Consider an $n$-dimensional hypercube where nodes are connected by an edge if they differ in a single bit. There are $k=poly(n)$ particles,...
0
votes
1answer
58 views

Distribution of stopping time for biased random walk using martingales.

Let $X_1,X_2,..,X_n,...,$ be i.i.d. random variables with distribution $P(X_i=1)=p$ and $P(X_i=-1)=q$, $q<p$. Given $S_n=\sum_{i=1}^n X_i$ with $S_0=0$, $a,b$ positive integers and $T=\inf\{n\in\...
2
votes
1answer
76 views

Let $S_n$ be a simple symmetric random walk. Show that $P(S_1S_2...S_{2n} \neq 0) = P(S_{2n} = 0)$

Let $S_n$ be a simple symmetric random walk. Show that $P(S_1S_2...S_{2n} \neq 0) = P(S_{2n} = 0)$ I'm not sure how to approach this. A hint would be greatly appreciated!
5
votes
2answers
153 views

Is the expectation of the supremum of a random walk with negative drift finite?

Let $(\xi_n)_{n\in\mathbb N}$ be iid random variables with negative mean, let $S_n=\sum_{k=1}^n\xi_k$, and let $M=\sup_{n\ge 0}S_n$. Is it true that if the $\xi_n$ are nice (say, finite variance), ...
0
votes
0answers
13 views

A random step in the $2D$ plane

Suppose we start in the Cartesian plane with coordinates $(x, y)$ such that $x^2 + y^2 < 1$ (lies in the unit circle). There are $2$ variations to my question: A step is defined as picking a ...
0
votes
1answer
21 views

Ratio of unique co-ordinates visited to total co-ordinate visited in a random walk.

For a random walk in integer valued order pair coordinate, if a particle/agent moves randomly right/left/up/down one unit with equal probability, what is the ratio of unique coordinate visited to ...
2
votes
2answers
76 views

Expected value of steps taken to hit +1 on a 1D integer random walk given you start from zero?

I am trying to calculate the expected number of steps taken on a 1-dimensional random walk (starting from zero) to reach +1. So far my approach has been to use recursive expectation (first step ...
0
votes
0answers
9 views

Binary brancing process extinction with different starting population

Given individual gives birth to 2 individuals they die with the probability p and individual gives birth to 0 individuals then dies with the probability 1-p. For this process, I know that p < 0.5 ...
1
vote
0answers
34 views

Random walk with stopping time

$T_n=\Sigma_{j=1}^n Y_j$ is a symmetric simple random walk with $P(Y_j=1)=\frac{1}{2}, P(Y_j=-1)=\frac{1}{2}$ and $T_0=0$. Define $M=\mbox{min}\{i:|T_i|=n\}$. We are require to find $\mathbb{E}(M)$ ...
4
votes
1answer
75 views

Going from 30 to 100 in a coin flip game.

The question is this: Say you're playing a coin flip game, where you start with 30 dollars. If you flip heads, you win 1. If you get tails, you lose 1. You keep playing until you either run out of ...
0
votes
1answer
69 views

Probability of reaching state $b$ before $-a$

We define the lazy random walk $S_n$ on $\mathbb{Z}$ which goes left with probability $\frac{1}{2}$, right with probability $\frac{1}{4}$, and stay in place with probability $\frac{1}{4}$. Assume that ...
3
votes
1answer
66 views

Symmetric random walk on the integers

I found an exercise in a paper by Anupam Gupta, Sahil Singla that i couldn't solve, sadly my knowledge in Markov processes is pretty limited. The exercise is the following: Suppose we have a symmetric ...
0
votes
0answers
7 views

[dis]similarity between samples of a probability distribution and its noisy version

Consider a probability distribution $\mathbb{P}(.)$ which takes into account $k$ prior samples. Suppose $x_t$ is a random sample from this distribution: $$ x_t \sim \mathbb{P}(x_{t-1}, ..., x_{t-k}) $$...
0
votes
1answer
44 views

Random walk 1D with a single bound

Consider a one dimensional random walk, where we have a bound at 0 and no upper bound. Also consider that we start at point: 1. My question is how many steps will it on average take to reach zero. If ...
0
votes
1answer
52 views

If you flip a coin to choose the direction you move along a number line, what is the probability you finish at a given position [closed]

Say you have a counter on a number line, you flip a coin n times. If it's heads you move left, if it's tails you move right what is the probability you land on a given number m and what is the ...
0
votes
1answer
40 views

Probability of the first time that a chain on $\mathbb{Z}$ hits a state.

Consider the following Markov chain on $\mathbb{Z}$ with transition probabilities given by $p(i,j)=1/2$ if $j=-1$, $p(i,j)=1/2$ if $j=i+1$ and $0$ otherwise. I want to find the probability $\mathbb{P}...
0
votes
1answer
51 views

Does a simple symmetric random walk on $\mathbb{Z^{2}}$ reach each vertex?

First of all I am very very new to random walks and markov chains in general. I proved that this is true for the random walk on integers. There I used recurrence relation to prove this. However I also ...
1
vote
1answer
53 views

Calculate the diffusion coefficient from a random walk with stay.

I am working on a problem involving a random walk inspired by protein motion in biological cells. It is assumed that motion in time is a stochastic process. In this case, the simple 1D random walk ...
4
votes
1answer
89 views

Random walks on symmetric groups

Let $S_n$ be the symmetric group on $n$ elements. Now, we pick a random transpositions to generate random walks on $S_n$ (also assume the probability of picking each transposition is equal of course). ...
24
votes
1answer
385 views

Average swaps needed for a random bubble sort algorithm

Suppose we have $n$ elements in a random permutation (each permutation has equal probability initially). While the elements are not fully sorted, we swap two adjacent elements at random (e.g. the ...
1
vote
0answers
76 views

Consider a random walk on an integer lattice. Show that $E[Y_1]=E[Y_2]$

Consider a random walk on the integer lattice of the positive quadrant in two dimensions. If at any step the process is at $(m,n)$, it moves at the next step to $(m+1,n)$ or $(m,n+1)$ with probability ...
2
votes
0answers
94 views

The distribution of visit times to the arc of absorbing DTMC

Consider there is an absorbing DTMC $X_n$ and it has $m$ absorbing states and $n$ nonabsorbing states. My question is if the $X_n$ starts from a transient state $s$ and ends in a specific absorbing ...
0
votes
0answers
11 views

symmetric random walk with two bounds, stop within n steps

As graph showed, it is a 1-dim symmetric random walk with two stopping points +a and -b. My question is what is the probability of stopping (either hit +a or -b) within n steps. We can assume $n\geq ...
1
vote
0answers
20 views

Can the symmetry of this run-distribution be established without recourse to its explicit formula?

Consider all possible arrangements of the sequence $S_k=(\underbrace{1,1,...,1}_{k},\underbrace{2,2,...,2}_{k}),$ where $k\ge 1.$ There's a neat proof, using indicators and linearity of expectation, ...
0
votes
2answers
77 views

Probability of $X_{n+1}=x$ in a random walk

I have the following problem regarding random walks: Given a simple random walk $\{ X_n : n=0,1,2,\dots \} $ in $\mathbb{Z}$ and $p+q=1$ show that $$P(X_{n+1}=x) = p P(X_n = x-1 ) + qP(X_n = x+1 )$$ I ...
1
vote
0answers
30 views

biased simple random walk and optional stopping theorem

Suppose we have a biased simple random walk $S_K=X_1+\dots+X_k$ on integers which begins at $0$, where $X_l$s are i.d.d random variables such that $P(X=1)=p=1-P(X=-1)>1/2$. It's easy to check $EX=p-...
0
votes
1answer
32 views

One-dimension random walk expected exit time

There is a pawn in $x=0$ at $t=0$. At $t'=t+1$ the pawn moves to $x+1$ or $x-1$ with probabilities $p$, $1-p$. What is the mean time to escape from the boundaries $-k$, $+n$, where $k,n\in \mathbb N$, ...
0
votes
0answers
23 views

Two dimensional symmetric random walk

Suppose we begin at $(x,y)$ within a square $0 \leq x \leq 7, 0 \leq y \leq 7,$ What's the probability of moving out of square within $n$ steps? I am not familiar with the symmetric random walk. I ...
1
vote
2answers
64 views

Box A has m balls, box B has n balls. Draw one ball randomly from one box. What is the expectation of remaining balls when one box is empty?

There are $m$ balls in box A and $n$ balls in box B. For every time, you draw a ball from either box with equal probability. (i.e. 1/2) You stop drawing when there is an empty box (i.e. you stop as ...
5
votes
2answers
109 views

Weighted summation of symmetric Bernoulli RV. Characteristic function inequality

Let $$S_n = \sum_{k=1}^n \frac{X_k}{\sqrt{k}}$$ where $X_1, X_2, \ldots$ are iid symmetric Bernoullis with parameter $\frac{1}{2}$: $$X_k = \begin{cases} 1 &p=\frac{1}{2}\\ -1 &p=\frac{1}{2} \...
0
votes
0answers
36 views

Probability distribution of n dimensional random walk

In an n dimensional lattice, what is the probability density function for $\sum_{i=1}^{M} X_i$, where $X_i$ is the random variable consisting of all the basis vectors and their negatives, with ...
0
votes
0answers
17 views

Combinatorial identities for random walk/gambler's ruin variation

For a biased or unbiased random walk where $$P(X_k = 1) = p \quad\text{and}\quad P(X_k = -1) = 1-p$$ we have that the number of paths of $N$ steps to position $m$ is the combinatorial identity $$G(N, ...
0
votes
0answers
35 views

Two points random walk

How can I build an algorithm which creates a random walk but subject to the constraint that I give the initial and final positions. How can I do it? Let's say I meet a drunk guy on the street. I know ...
0
votes
0answers
57 views

Biased random walk: Probability of hitting a value before some specified time.

Question. Suppose we have iid random variables $\{X_k\}_{k\geq 1}$ where $$P(X_k = 1) = \frac{2}{3} \quad\text{and}\quad P(X_k = -1) = \frac{1}{3}.$$ We have the random walk $\{S_t\}_{t \geq 1}$ where ...

1
2 3 4 5
41