Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-walk]

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

1
vote
0answers
18 views

Limit expectation of $\mathbb{E}\min(\sigma_{2n}, 2n)$ for stopping times of a random walk

Let us consider $X_1, X_2, \ldots$ as a random walk, such that $\mathbb{P}(X = 1) =p$, $ \mathbb{P}(X = -1) = q$ and $p > q$. Further, define a stopping moment as $$\sigma_{2n}= \left\{\begin{...
0
votes
0answers
34 views

Range of one-dimensional random walks

How many lattice paths in $\mathbb{Z}$ of length $n$ with steps in $\{-1,0,+1\}$ visit $m$ distinct points? Notice that this is just the number of lattice paths $P$ such that $\max P - \min P + 1 = m$...
2
votes
1answer
27 views

Existence of separators for biased random walk.

Let us consider a biased random walk in $\mathbf{Z}$ whose step-lengths satisfy $\mathbf{P}(\xi = +1) = p > \mathbf{P}(\xi = -1) = q$ (with $p+q = 1$). A value $k \in \mathbf{Z}$ is a "separator" ...
2
votes
1answer
72 views

Question about a random walk

Let $(X_i)_i$ be a sequence of i.i.d. random variables such that $\Pr(X_i=1)=1-\Pr(X_i=-1)=p$, and assume that $p<1/2$. Define the random walk $S_i = \sum_{j=1}^iX_i$. Then, is it true to claim ...
0
votes
1answer
20 views

show map $f$ satisfies $f(\omega_1)=f(\omega_2)$ for $w_1\ne\omega_2$ iff $f(\omega_1)$ is a dyadic rational in $(0,1)$

$\Omega=\{0,1\}^\infty$ $A=\{\omega:\omega=(\omega_n)_{n\ge{1}}\in\Omega\}$ $f:A\longrightarrow(0,1)$ where, $f(\omega)=\underset{n\ge{1}}{\sum}2^{-n}\mathbb{I}_{\{\omega_n=1\}}\in(0,1)$ (doubt) Why ...
0
votes
0answers
53 views

Showing $\mathbb{E}S_{\tau}^2=\mathbb{E}\tau$.

Suppose that $x_1, x_2,...x_n$ are independent copies of random variable $x$ having distribution $$P(x=1)=P(x=-1)=\frac{1}{2}.$$ In addition, suppose that $\mathcal{D}=\mathcal{D}_{x_1,...,x_k}(k=1,......
0
votes
0answers
33 views

Proving that sequence is a martingale

Suppose that $x_1, x_2,...,x_n$ are independent copies of random variable $x$ having distribution $$P(x=1)=p, \text{ } P(x=-1)=q,$$ where $p+q=1$. In addition, suppose that $\mathcal{D}_k=\mathcal{D}_{...
0
votes
0answers
25 views

Expected number of steps for a bug to reach position $N$ [duplicate]

A bug starts at time $0$ at position $0$. At each step, the bug either moves to the right by $1$ step $(+1)$ with probability $1/2$, or returns to the origin with probability $1/2$. What is the ...
1
vote
2answers
28 views

Count conditional probability of winning a game

In a certain game of tennis, Alice has a 60% probability to win any given point against Bob. The player who gets to 4 points first wins the game, and points cannot end in a tie. What is Alice's ...
0
votes
1answer
21 views

Higher Dimensional Random Walks

I've read on a paper that, in the two dimensional case, if you start from the origin and take steps of length one in an arbitrary direction (uniformely on the unit sphere $S^1$), the expected distance ...
0
votes
0answers
44 views

Random walk. Finding probability

There are two players. First one has 3 coins and second one has 5 coins. Probability that first one wins the game (second player gives one coin to the first player) is $P(x_1=1)=\frac{2}{3}$ and ...
0
votes
1answer
41 views

Random walk. Finding probabilities $P_{2k,4}$ and $P_{2k,8}$

Suppose that $x_1, x_2,...$ are independent copies of random variable $\xi$ having distribution $P(x=1)=P(x=-1)=\frac{1}{2}.$ Let $S_0=0$, $S_k=x_1+x_2+...+x_k$, $k \geq1.$ Let $P_{2k,2n}$ be the ...
0
votes
1answer
14 views

Product of random variable and characteristic function

So I was reading about simple random walks and came across this: Suppose $(X_{n})_{n=0}^{N}$ is a sequence of i.i.ds adapted to a filtration $(\mathcal{F}_{n})_{n=0}^{N}$ with $E(X_{n})=0$ for all $n$...
0
votes
1answer
43 views

Random walk. Finding probabilities

Suppose that $x_1, x_2,...$ are independent copies of random variable $\xi$ having distribution $P(x=1)=P(x=-1)=\frac{1}{2}.$ Let $S_0=0$, $S_k=x_1+x_2+...+x_k$, $k \geq1,$ and $a,b$ be non negative ...
0
votes
2answers
57 views

Random walk. Finding a distribution

Suppose that $\xi_1, \xi_2,..$ are independent copies of random variable $\xi$ having distribution $$\mathbb{P}(\xi=1)=\frac{1}{3}, \text{ } \mathbb{P(\xi=-1)=\frac{2}{3}}.$$ Define: $S_0=0$, $...
1
vote
0answers
38 views

A probabilistic attempt to solve Riemann Hypothesis using Mertens function.

I know that the following statement: For every $\epsilon>0$ $$M(N)=O(N^{0.5+\epsilon})$$ is equivalent to Riemann Hypothesis (Where $M(N)$ is Mertens function). As Mertens function behaves somehow ...
3
votes
1answer
43 views

Probability of reaching a maximum in a random walk

Let's define a random walk in the following way $$S_0 = 0, S_n = \sum_{i=1}^{n} \epsilon_i,$$ where: $$\epsilon_i = \pm 1.$$ Moreover $$P(\epsilon_i = - 1) = P(\epsilon_i = + 1) = \frac{1}{2}.$$ ...
1
vote
1answer
40 views

Express the set of all paths with infinite $1$'s using set theoretical representation and elements of another set

Define the collection $\mathscr{A}$ of subsets of $\Omega=\{0,1\}^{\infty}$ as $$\mathscr{A}=\{S\times\Omega:S\subseteq\{0,1\}^{l},l\ge1\}$$ Let all infinite length paths be denoted by $$\omega=(\...
0
votes
1answer
40 views

given a set closed under finite complementation and union; disprove closeness under countable union and intersection

The collection $\mathscr{A}$ of subsets of $\Omega=\{0,1\}^{\infty}$ is given by $$\mathscr{A}=\{S\times\Omega:S\subseteq\{0,1\}^{l},l\ge1\}$$ Then, $\mathscr{A}$ is closed under complementation, ...
0
votes
0answers
27 views

A proper definition of recurrent event in probability

I am having hard time understanding the definition of a recurrent event in probability context. At our lecture it was defined as follows: Let $X^{[i,n]} = \{X_i, \ldots, X_n\}$ be a random sequence....
0
votes
0answers
28 views

$A_i=S_i\times\Omega ,S_i\subseteq\{0,1\}^{n_i} ,n_i\ge1$, $i=1,2$; show $A_1\cup A_2$ and $A_1\cap A_2$ are of the same form

[Random walk with the actual infinite sample space, $\Omega=\{0,1\}^{\mathbb{N}}$] If $A_1=S_1\times\Omega$ and $A_2=S_2\times\Omega$ where $S_i\subseteq\{0,1\}^{n_i}$ for some $n_i\ge1$, $i=1,2$, ...
1
vote
0answers
17 views

Uncountable Sample Space (Reference)

I need reference on handling uncountably infinite sample spaces in probability considerations . To be more specific , I wish to investigate random walks with the following as a starting point : any ...
2
votes
1answer
108 views

Simple Markov Chain Walk - Expected position after $k$ steps

I am given the following Markov chain and would like to estimate my expected position after $k$ iterations. The chain is in $\mathbb{Z}$. I start at position $1$, with probability $q_1$, I stay at ...
1
vote
1answer
42 views

time between transitions in continous time discrete state Markov process

Problem Statement: I want to compute the time between transitions in a birth-death model. As a simple example, consider that individuals are born with rate $\lambda$ and they die at rate $\sigma n$. ...
0
votes
1answer
23 views

Is there any relation between random walk and eigen-vectors of adjacency matrix other than the first one in graph?

I want to know more about what the relation is between random walk and eigen-vectors of adjacency matrix of graph. I know that the first eigen-vector of adjacency matrix is related to the stationary ...
0
votes
0answers
23 views

Circumventing Potentially Illegal Substitutions in Generating Functions

This question comes from trying to solve the following problem from Probability: An Introduction by Grimmett and Welsh. (b) In a two-dimensional random walk, a particle can be at any of the points $...
-1
votes
1answer
26 views

Asymptotic growth of translation in random walk.

Let's consider a random walk with translation $$F(N)=\sum_{n=1}^{N}X(n)$$ Where $X(n)$ is a random variable distribiuted independently and equal to $0$ or $1$. What is asymptotic growth of $F(N)$? i....
1
vote
0answers
36 views

How to show that q-coloring graph is ergodic

Informal: I want to show that a q-coloring of graph $G$ is ergodic (i.e. strongly connected and aperiodic) Formally: For a given graph $G(V,E)$ where $|V|=n$ with maximum degree $\Delta\geq1$. Also, ...
1
vote
0answers
37 views

2D Random Walk Hitting Time

Suppose there is a grid $[1,N]^2$. A person standing at some initial point $(x_0,y_0)$ walk randomly within the grid. At each location, he/she walks to a neighboring location with equal probability (e....
0
votes
0answers
11 views

Random Walk on a number line and further cases

i) A monkey is sitting on 0 on the real line in period 0. In every period t ∈ {0, 1, 2, . . .} it moves 1 to the right with probability p and 1 to the left with probability 1−p, where p ∈ 1 2 , 1 . ...
2
votes
0answers
67 views

The rook and the bishop are moving independently on the chessboard starting at the same corner

The rook and the bishop are moving independently on the chessboard starting at the same corner. What is the average number of steps until they meet again in the same corner, if we know that the bishop ...
0
votes
0answers
25 views

Proof that if you take enough steps of equal magnitude on a plane, you'll always end up at the starting point

Is the claim in the title true? If yes, is the following sufficient to justify it intuitively? Assume for simplicity that the steps are performed with magnitude 1 in a Cartesian plane. To construct a ...
0
votes
0answers
19 views

Number of times a constrained, discrete random walk changes value

I have two infinitely long series, $X$ and $Y$, and a constant, $n$. Each element in $Y$ is either $+1$ or $-1$, with equal probability. $X$ changes as follows: $$X_i = max(-n, min(n, X_{i-1} + Y_{i-...
1
vote
0answers
108 views

What is the mixing time of a random walk of a rook

Let $G(V,E)$ be the following graph: The vertex set $V$ is a $n\times n$ grid, and two vertices are connected $(E)$ if they lie on either the same row or the same column. This is the rook's graph: It ...
0
votes
1answer
61 views

Show that a symmetric random walk with hit any number with probability 1

I'm supposed to show this with martingale convergence thm. I have tried setting up one barrier at a fixed $n$. And the martingale convergence says it will converges to a random variable almost surely. ...
0
votes
0answers
29 views

Eigenvalues of Markov chain

Suppose I have a Markov matrix M of even dimension representing a random walk: $$\left(\begin{matrix} 0 & p & 0 & \dots & 0 & q \\ q & 0 & p & \dots & 0 & 0 \\...
2
votes
3answers
177 views

Probability that random walk will reach state $k$ for the first time on step $n$

We have a random walk which starts in state $0$. At each step, a coin is tossed with probability of heads: $P(H)=p$. If we get a heads, we go to the next higher integer state and on tails, we go to ...
0
votes
0answers
22 views

Residence times of the telegraph process?

The telegraph process is a two state stochastic process defined by the master equation $$ \dot{\pi}_0(t) = \tau^{-1} \pi_1(t) - \sigma^{-1} \pi_0(t) $$ $$ \dot{\pi}_1(t) = \sigma^{-1} \pi_0(t) - \...
1
vote
0answers
24 views

Integrating the path of a random walk

Suppose I've got a random walk up and down in one dimension. It starts at $S_0=k>0$ and makes a move at every integer time $t$. So: $$S_t=k+\sum_{i=1}^t X_i$$ Each move ($X_i$) has mean 0 and the ...
0
votes
0answers
18 views

Number of returns simple random walk $\mathbb{Z}^d$

I am interested to know the precise numerical value of the expected number of returns to the origin of a simple random walk on $\mathbb{Z}^d$, when $d \geq 3$. Does anyone know where I can find such a ...
1
vote
0answers
58 views

Compound Binomial - Exponential process

Problem: I have a sum of $N$ random variables $X_i$, where $N$ is distributed according to a binomial distribution and the $X_i$ are independent and identically distributed according to an ...
1
vote
1answer
46 views

Simple random walk in 1D with possibility to stand still

Let $\{\xi_i\}$ be i.i.d. with $\mathbb{P}(\xi_i=1) = \mathbb{P}(\xi_i=-1) = \frac{3}{8}$ and $\mathbb{P}(\xi_i = 0) = \frac{1}{4}$. Let $S_0=0$ and for $n\geq 1$ let $S_n = \xi_1+\ldots+\xi_n$. For $...
1
vote
1answer
24 views

Enumerating first arrivals to the opposite corner of $N$-cube

Number of walks from $(0,0,\dots, 0)$ to $(1,1,\dots, 1)$ along the $N$-cube's edges is enumerated by $\sinh^N$ and loops from a vertex to itself by $\cosh^N$ so why isn't the first arrivals to the ...
0
votes
0answers
10 views

Simple Random Walk Recurrence

I am attempting to understand the below theorem. I understand every thing up to the last equality "where the last equation follows...". Could someone explain how that equality follows? I understand ...
2
votes
0answers
47 views

Random walk on $\{0,1,…,k\}$, find the average gain in 10 000 steps

I have the following problem which I can't seem to figure out. The problem is as follows. Consider simple random walk on {0, 1, ... , k} with reflecting boundaries at 0 and k, that is, random ...
1
vote
0answers
29 views

Repeatedly multiplying by numbers taken from a uniform distribution

Motivation: In a software project I know well, for testing purposes, the evolution of a particular price is simulated by repeatedly multiplying by a random number picked between $0.995$ and $1.005$. ...
1
vote
0answers
21 views

The problem is about the expection of the exitpoint distance for the symmetric random walk.

Let $\nu(x)$ be a symmetric probability measure with respect to the origin on $x\in[-1,1]$ such that $\nu(\{0\})\neq 1$. Consider a random walk started at $S_0=0$, denoted $S_n=X_1+\cdots+X_n$, where ...
0
votes
1answer
22 views

Variance of the Wiener Increment

I have a Wiener process $W(t)$, which is a normally distributed random variable with mean $\langle W(t)\rangle = \mu = 0$ and variance $\langle W(t)^2\rangle = \sigma^2 = t$. The angled brackets $\...
1
vote
1answer
45 views

Martingale of random walk and stopping time

Let $\{S_n\}$ be a symmetric random walk such that $S_0 = a$ for some $0 < a < K$. Let $T$ be the stopping time when the walk reaches $0$ or $K$. Show $$M_n = \sum_{i = 0}^n S_i - \frac{1}{3}...
0
votes
0answers
14 views

Third Absolute Moment of a Simple Random Walk

This might be a very basic question. Let $S_n$ denote a simple random walk at time $n$, i.e. $S_n = \sum_{i=1}^n X_i$ , where $X_1,\ldots,X_n$ are i.i.d. Rademacher with $\mathbb{P}(X_1=1) = \mathbb{P}...