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
0 answers
32 views

Simple random walk, Martingales, stopping time

Suppose $S_n = X_1 + \dots + X_n $ is a simple random walk starting at 0. For any K, let $$T = \min \{n: | S_n| =K\}. $$ $\bullet$ Explain why for every j, $$ \mathbb{P}\{T \leq j +K | T > j\} \geq ...
Win_odd Dhamnekar's user avatar
0 votes
0 answers
19 views

Will this metropolis chain always converge?

Let $G(V, E)$ be a graph and $\pi$ be a probability distribution on V. Denote by $J$ the transition matrix of the simple random walk on $G$. Let $P$ be the transition matrix of the Metropolis chain ...
spatial's user avatar
  • 180
1 vote
2 answers
88 views

How to get asymptotic approximations for complex summations like $S_n = \sum\limits_{i=0}^n {n \choose i}^2 {2(n-i)\choose (n-i)}$

I asked a question about this summation (in the process of proving that a 3-d random walk is transient): $$S_n = \sum\limits_{i=0}^n {n \choose i}^2 {2(n-i)\choose (n-i)}$$ in this post: Summation ...
Rohit Pandey's user avatar
  • 6,581
1 vote
0 answers
15 views

Question: Concerning Simplifying Random Walk from 2D to 1D

I have a question that has been confusing me. For a 1D random walk in the x-direction I was told that the multinomial coefficient is given by: $$C(N,k_x) = \frac{N!}{k_x!(N-k_x)!} \tag{1}$$ In Eq. 1, ...
djf321's user avatar
  • 11
-1 votes
0 answers
18 views

Random walk in higher dimensions [closed]

Let $A_n = \sum_{i=1}^{n} X_i$ be a random walk in $\mathbb R$. What does a random walk in $\mathbb R^3$ intuitively mean and how can it be formulated mathematically in terms of 3 one-dimensional ...
Kevin's user avatar
  • 57
-1 votes
0 answers
21 views

Donsker's theorem for multivariate Brownian motion [closed]

Let $B = (B^1, \dots, B^n)$ be an $n$-dimensional Brownian motion (i.e. $B = (B_t)_{t \geq 0} \in \Omega \rightarrow (\mathbb{R}^n)^{[0,\infty)})$. Do we have something as Donsker's theorem to show ...
Kevin's user avatar
  • 57
0 votes
1 answer
65 views

Probability that a 3-d random walk will return to the origin in $2n$ steps (Ross approach)

In example 4.18 of the book Introduction to Probability Models by Sheldon Ross (10th edition), he shows that the probability a symmetric 1-d random talk will come back to the origin in $2n$ steps to ...
Rohit Pandey's user avatar
  • 6,581
0 votes
0 answers
21 views

Optional stopping time of a simple symmetric random walk on the square lattice

Let $S_n$ be a simple symmetric random walk on the square lattice $\mathbb{Z}^2$ with $S_0=(0,0)$. That is, the walker starts from the origin and at each step independently, she steps one unit to East,...
veganwithabeef's user avatar
3 votes
0 answers
50 views

Geometric Distribution in Simple Random Walk

My question is related to this question here. This says that if $S_{n}$ is a simple random walk (with steps $+1$ or $-1$ with probability $p$ and $q$ respectively) started at $S_{0}=1$, and if $T=\min\...
Blitzkrieg's user avatar
0 votes
0 answers
51 views

A random walk problem where the probability of movement depends on itself

Given a function $f$ with a range between $[0,1]$, and a point $x$ that walks randomly on the number line, initially at the zero point of the number line. $x$ will move $1$ unit to the left or right, ...
c_cpp_a's user avatar
  • 37
3 votes
0 answers
93 views

Analyzing A Random Process

Consider the following random process. For some $m \in \mathbb{N}$, we have a set of $m+1$ items $I = \{i_1,\ldots,i_{m+1}\}$. In every time $t \in \mathbb{N}$, there is a set of items $S_t \subseteq ...
John's user avatar
  • 93
0 votes
0 answers
22 views

Conditional Expectation of random walk square $E^{F_n}X_{n+1}^2$

$X_n$ is simple random walk It seems like $E^{F_n}[X_{n+1}^2]=X_n^2+1$ And $E^{F_n}[X_{n+1}^4]=X_n^4+6X_n^2+1$ I think the first expression is due to $X_n^2$ being positve But how does it reach the ...
dodo's user avatar
  • 718
0 votes
0 answers
46 views

Expected steps between any 2 nodes in a random walk on an undirected line graph

I have a question from class that is as follows: Consider random walk on a graph G = (V, E). Suppose that you are at a node u ∈ V. Given a node w different from u, what is the expectation for the ...
wildpygmy's user avatar
0 votes
0 answers
38 views

Number of counterexamples which prove that the squared distance from the origin of a simple random walk on $\mathbb{Z}^2$is not Markovian

Notations Let $\{X_n\}_{n\in\mathbb{N}}$ and $\{Y_n\}_{n\in\mathbb{N}}$ be two simple random walks on the integers $\mathbb{Z}$. So the process $\{(X_n,Y_n)\}_{n\in\mathbb{N}}$ is a random walk on $\...
Luca Onnis's user avatar
0 votes
0 answers
57 views

Final steps of Lovász derivation of the hitting time between two nodes in a random walk

I'm trying to understand thoroughly the proof of the Lovász's formula to calculate the hitting time $H(s, t)$ between two nodes $s$ and $t$ in a random walk on a graph. At page 13 it gets to the ...
Felipe's user avatar
  • 75
0 votes
0 answers
27 views

Probability 2 Random Walkers get back to original spot and have never met

Was working on this problem wherein two random walkers starting at $0$ and $4$ respectively take ten steps (either $+1$ steps or $-1$ steps with equal likelihood). What is the probability that they ...
Bertrand Einstein IV's user avatar
0 votes
0 answers
22 views

Starting point of random walk does not affect conditional probability

Let $S_n = \sum^n_0 X_k$ be random walk (with steps not necessarily of probability $\frac 12$). I want to show that $$ P(\text{hitting $2$ | hitting $1$ $\cap$ $S_0=0$}) = P(\text{hitting $2$ | ...
Kilkik's user avatar
  • 1,787
1 vote
0 answers
28 views

Hitting times for a random walk on a square

Let $ABCD$ be a square and {$X_t, t \in \mathbb{N}$} a discrete random walk on this square (i.e the state space is {$A,B,C,D$}). Let $$\tau_D := \min\{ t\geq0 : X_t = D \}$$ and $$\tau_C := \min\{ t\...
Daileon108's user avatar
0 votes
0 answers
46 views

Proving a Property of a Random Walk

Consider a process $X_t$, given by $X_0 = 1$ and $X_t = X_{t-1} + B_t$ where \begin{align} B_t = \left\{ \begin{array}{lr} 1, \ \ \text{with probability } \frac{p}{2} \\ 0, \ \ \...
spooleey's user avatar
  • 422
0 votes
1 answer
41 views

Coin game 1D Random Walk

You play a game with a coin. You may place a bet, if Heads if flipped then you receive your bet plus the same in winnings. If tails is flipped, then you lose your bet. You have \$ 10 and you want to ...
quantrader23's user avatar
1 vote
1 answer
66 views

Proof of the spectral formula for the expected number of steps in a random walk

In a paper by Lovász (see reference at the end), there is the derivation of a spectral formula for the hitting time, which is the expected number of steps to get to a node t, starting at s, in a ...
Felipe's user avatar
  • 75
2 votes
1 answer
59 views

How to prove this combinatorics problem in asymmetric random walk

How to show that these two numbers are equal? i.e. $$\sum_{n=0}^\infty\binom{2n}{n}p^n q^n = \frac{1}{1-2q}$$ This is how this equation is derived: Suppose we have a simple random walk $\{R_n, n\geq ...
Bill Wan's user avatar
2 votes
1 answer
71 views

expected hitting time with a moving boundary

Let $X_i$'s be independent $\text{Bernoulli}\left(\frac{1}{2}\right)$ random variables and $$S_n=\sum_{k=1}^nX_i$$ We define $\tau=\inf\{n\geq 2: S_n>\frac{n+1}{2}\}$. I want to compute $\mathbb{E}(...
Probability student's user avatar
1 vote
1 answer
42 views

Random walk probability question: An urn contains $n$ white and $n$ black balls without replacement.

An urn contains $n$ white and $n$ black balls. We draw them one by one without replacement. We pay $£ 1$ for any black ball drawn but receive $£ 1$ for any white one. Denote by $X_i$ our money after ...
veganwithabeef's user avatar
0 votes
1 answer
37 views

How to solve these equations? (from 10.12.c, D. Williams, Probability with Martingales)

In Sec. 10.12 (hitting times of simple random works), eq. (c) (page 103) of Probability with Martingales (D. Williams 1991), the author said: For (any) $\theta\in \mathbb{R}$, let $\alpha:=\mathrm{...
Mingzhou Liu's user avatar
1 vote
1 answer
36 views

Convergence of a Random Walk with a Reflecting Wall to a Steady Distribution

Considering a random walk where, at each step, a person can move either left or right with a step size of 1 and an equal probability of 0.5 for each direction. However, there's a unique feature: a ...
david's user avatar
  • 543
0 votes
0 answers
18 views

How does the probability density function decay off for a 2D random walk with shrinking step size $f(n) = \frac{1}{n}$

Consider a 2D random walk with the magnitude of the nth step fixed by the function $f(n) = \frac{1}{n}$ and the direction being random. I know that the root mean square comes out to be, \begin{...
Prem's user avatar
  • 195
0 votes
2 answers
39 views

Counting discrete space, discrete time random walks that are always strictly positive.

Let $ \Theta \ge 1 $ and $n \ge 1 $ be integers. Consider integer sequences of length $n$ composed of entries each one running independently over the range ${\mathfrak R}_\Theta:=\left\{-\Theta,-\...
Przemo's user avatar
  • 11k
1 vote
0 answers
21 views

How to estimate the lower bound of probability of return time in a random walk in $\mathbb{R}^d$?

Consider simple random walk in $\mathbb{R}^d$, let $\sigma=\inf\{t>0:X_t=0\}$ be the return time. How to estimate the asymptotic lower bound of $P(\sigma=2k)$ given $X_0=0$? I've got the upper ...
Strayer7999's user avatar
2 votes
1 answer
42 views

Does the distribution of T converge to a normal distribution despite not satisfying the Lyapunov condition?

For a sequence of independent and identically distributed (i.i.d) random variables $S_i$ where $i = 1, 2, \dots, n$. Each $S_i$ can take values (-1, 1) with probability $\left(\frac{1}{2}, \frac{1}{2}\...
david's user avatar
  • 543
0 votes
0 answers
39 views

Probability of going broke before reaching target with positive expected value.

In an interview today, I was given a hypothetical situation in which I can bet on the outcome of a biased coin (0.6H, 0.4T). I can bet £1 at a time; if I win i get my stake back and an extra £1, ...
Sylith's user avatar
  • 111
0 votes
1 answer
57 views

Random walk, after many many steps, contradictory with law of large number?

Assume a random walk, start at 0, step size Gaussian N(1,σ²). After many many steps (i.e. n=1,000,000), the translation distance is N(n, nσ²). Here is my confusion: N(n, nσ²) means the probabilty of ...
Jing Zhang's user avatar
1 vote
2 answers
80 views

Formula for Laplace transform of the jump probability in a continuous time random walk

I am trying to understand the basics of continuous time random walks, and this formula has no explanation as far as I can find: $$\hat{p}_{n}(s) = \hat{\rho}(s)^n\cdot\frac{1-\hat{\rho}(s)}{s}$$ Where ...
Remeraze's user avatar
0 votes
0 answers
18 views

Are there functions that look random but have an easy to calculate integral or sum, preferably closed form?

Discrete or continuous. Would prefer a discrete function f(t) that takes on the values -1, 1 for integer t. Let's say F(t) is the sum from f(0) to f(t). Preferably F(t) should look like an example of ...
Justin Tang's user avatar
0 votes
0 answers
19 views

Markov chains: interarrival time and hitting times

Suppose that $(X_{n})_{n\in\mathbb{N}}$ is a Markov Chain with state space $S$ and $A\subseteq S$ and define: $$ T_{S} := \text{min}\{{n\geq0:X_{n}\in A }\} $$ As the hitting time to hit the set $A$. ...
René Quijada's user avatar
2 votes
1 answer
77 views

Convergence of Distribution for a Modified Sequence of IID Random Variables

I have a sequence of IID random variables $S_i$ where $i = 1, 2, \dots, n$. Each $S_i$ can take values (-1, 1) with probability $\left(\frac{1}{2}, \frac{1}{2}\right)$. As we know, the distribution of ...
david's user avatar
  • 543
2 votes
2 answers
145 views

The conditional expectation in Gambler’s ruin

Consider the random walk $X_0, X_1, X_2, \ldots$ on state space $S=\{0,1,\ldots,N\}$ with absorbing states $A=\{0,N\}$, and with $P(i,i+1)=p$ and $P(i,i-1)=q$ for all $i \in S \setminus A$, where $p+q=...
user250236's user avatar
2 votes
0 answers
50 views

Null recurrence of a Random Walk in a Random Environment

Let $W_0^+,W_1^+,...$ i.i.d random variables on $[0,1]$ and $W_0^-:=1-W_0^+,...$. Suppose that X, given W, is a random walk on $\mathcal{N}_0$ with transition probabilities $p_i(x,x+1)=W_i^+$, $p_i(x,...
Enrico's user avatar
  • 525
1 vote
0 answers
64 views

Electric Network and Random Walk: determine effective conductance

Suppose we have a network on $\mathcal{Z}^d$ with unit resistors between neighbouring points. Let $X$ be a simple symmetric random walk on $\mathcal{Z}^d$. I would like to prove that for any two ...
Enrico's user avatar
  • 525
0 votes
1 answer
124 views

How to prove that a Markov chain is transient?

I have a Markov chain $\{Y_n: n\geqslant 0\}$ where the $Y_n$ are integer-valued. The probability of going from any state $i$ to its right (i.e., from state $i$ to state $i+1$) is $p$, and the ...
probstudent's user avatar
0 votes
1 answer
39 views

Question about the Thue-Morse Sequence and its relation with the Fabius function

Recently, I made the following question Integrating the Fabius function $q(x)=\int_0^x F(u)\ du$ trying to make a function that would behave like a continuous smooth version of a Random walk by ...
Joako's user avatar
  • 1,264
1 vote
1 answer
59 views

Integrating the Fabius function $q(x) = \int_0^x F(u) du$

There are any formulas for the integral of the Fabius function? Context_____________ After reading the following question: Smooth functions that resemble random walks, I started thinking about some ...
Joako's user avatar
  • 1,264
0 votes
0 answers
138 views

What is the difference between a Gaussian random walk and a Gauss-Markov process?

My understanding is as follows: A Gaussian random walk is a Markov process $X_0,X_1,\ldots$, where $X_0$ has a Gaussian probability density function (PDF) and for $n=1,2,\ldots$, given $X_{n-1}=x_{n-...
W. Zhu's user avatar
  • 1,317
0 votes
0 answers
34 views

Distribution of hitting times for a Brownian Motion with two absorbing barriers and step size equal to 1

In the question " What is this lognormal-like distribution? ", ck1987pd stated the formula for the probability distribution of hitting times for a Brownian Motion, starting at $0$ with ...
JHickey's user avatar
3 votes
2 answers
99 views

Gambler's ruin in the limit (only stopping rule ruin)

Imagine a classical Gambler's ruin with winning probability p and losing probability q = 1-p. You start at 1\$ and lose once you reach 0\$. The only stopping rule is that the game is over when the ...
romanowski's user avatar
3 votes
0 answers
22 views

Does this simple branching random walk on $\mathbb Z$ satisfy a central limit theorem?

Consider the following simple branching random walk on $\mathbb Z$ in discrete time: At stage 0, we start with one token at the site 0. At each time step, we randomly, independently split each token ...
Good Boy's user avatar
  • 2,200
0 votes
0 answers
29 views

How is called a stationnary stochastic process consisting in Poissonian jumps between Gaussian random variables?

I have a (physical) signal $x(t)$ that is well described by a random process consisting in constant values $x_i$ during random times $\tau_i$. The time intervals $\tau_i$ between jumps are ...
Gipfeli's user avatar
  • 21
0 votes
0 answers
28 views

Entropy increase of a random walk on the sphere

Let $X_0$ be some vector on the unit sphere of $\mathbb{R}^n$ and let $\rho_0$ be the distribution of its entries, $$ \rho_0(z) = \frac{1}{n} \sum_i \delta\left(z-X_0^{i}\right) $$ Assume that $n$ is ...
Juan Giral's user avatar
0 votes
0 answers
21 views

How many times does a random walk starting at vertex v return to v before first visiting vertex to u

Suppose we have a simple random walk on a graph, or possibly more generally a reversible Markov chain, that begins at vertex v and continues until vertex u is first reached. What is the expected ...
Markovian8261's user avatar
0 votes
0 answers
27 views

Proportion of time a sum of Gaussians is above 0

I am stuck with the following problem. For any $k\geq 1$, let $N_k$ be a standard Gaussian, and $X_k:=\sum_{j=1}^kN_j$. I would need to prove the following: $$\lim_{k\rightarrow \infty} \frac{1}{k}\...
Math Enjoyer's user avatar

1
2 3 4 5
48