Questions tagged [random-walk]
A stochastic process that describes a path arising from a succession of random steps.
228
questions
0
votes
2answers
48 views
Is random walk with drift is random?
I see everywhere in the web that lag-plot or acf are used to see if a time serie is random. If there is no structure in the lag plot then the data are random, and if autocorrelation = 0 then data is ...
1
vote
0answers
26 views
What is the distribution of the time-to-ruin for a gambler's ruin problem that allows “pauper bets”?
In another question on this site I have derived the distribution for the time-to-ruin in the gambler's ruin problem where the wealth of the gambler follows a discrete-time random walk. In this ...
1
vote
0answers
16 views
How to invert a random walk [closed]
I have a random walk dynamic parameterized in a function let's say $f(x)$ e given a $x_0$ I can retrieve a curve of this initial value after several simulations. But I need to "invert" this ...
2
votes
1answer
22 views
Are there good examples of martingale processes that are not simple random walks?
Are there non-trivial examples of martingale processes that aren't simple random walks?
I'm trying to better understand the difference between martingales and simple random walks. They look pretty ...
2
votes
0answers
77 views
Fast uniform sampling of walks from directed graph
Given a directed graph $G=(V, E)$ my goal is to sample a set of walks $W\subset\mathcal{W}$ where $\mathcal{W}$ is the set of all walks in $G$. I want each walk to be sampled with the uniform ...
4
votes
1answer
36 views
What is the distribution of time's to ruin in the gambler's ruin problem (random walk)?
In a gambler's ruin problem, where the gambler starts with a fixed amount of wealth. What is the distribution of times to ruin. That is, if each bet has a fixed payout.
As I understand it, this is a ...
0
votes
1answer
36 views
MCMC: Rejecting samples outside the prior support?
I wish to implement a MCMC procedure for a posterior density which has non-trivial prior support. To clarify, this means that the parameter space has certain regions (i.e., combinations of parameters) ...
1
vote
0answers
29 views
Is CPU utilization a predictable time series? [closed]
I've been wondering whether metrics about CPU and resource utilization is a time series which can be predicted or rather a random walk which I cannot learn from. Can recognizing a pattern in the data ...
3
votes
1answer
31 views
Explain formally how expected time to hit 0 from two is the sum of the expected time to hit 1 from 2 and 0 from 1
I have a symmetric random walk on the integers with probability $p$ and $q$ of going up and down respectively started at $X_0 = 2$.
Let
$$
T^0 = \min\{ n > 0: X_n = 0\}, T^1 = \min\{ n > 0: X_n =...
3
votes
2answers
58 views
Appropriate distribution for simulating a random walk between two known points, with known min/max values
I have a 1-D random walker. It starts at a value of x at time t=0. It ends with a value of y ...
1
vote
1answer
37 views
Why iterations of Gibbs sampling for a bivariate Gaussian distribution can be seen as random walk?
In Section 4.4 of the excellent technical report Probabilistic Inference using Markov Chain Monte Carlo Methods, the author tries to analyze the performance of Gibbs and Metropolis algorithm with ...
2
votes
2answers
53 views
Random Walk why is $E[X_{t}] = \mu t$
Question
A Random Walk can be defined as follows. $Z_t$ ($t=1,2,3,\ldots$) is a noise term with a Normal$(\mu,\sigma^2)$ distribution. Define $X_0=0$ and
$$X_t = X_{t-1}+Z_t$$
for $t=1,2,3,\ldots.$
I ...
0
votes
1answer
25 views
How do we define the kernel to calculate the acceptance ratio for Metropolis-Hastings Markov Chain Monte Carlo?
I am having a lot of difficulty understanding how to apply the algorithm to a real scenario.
The part that confuses me is that we are looking for a target distribution (the real distribution of our ...
3
votes
1answer
56 views
distribution of maximum random walk distance
Related to this question.
Suppose I flip a fair coin $N$ times and keep track of the difference between the total number of heads and tails as I am doing it. At the end of the $N$ coin flips, I have ...
2
votes
1answer
40 views
If $y_t$ and $x_t$ are cointegrated, then are $y_t$ and $x_{t-d}$ also cointegrated?
Assume that $x_t, y_t$ are $I(1)$ series which have a common stochastic trend $u_t = u_{t-1}+e_t$. Particularly, consider the following DGP
\begin{align}
y_t&=\alpha_y+u_t+a_t \tag{1} \\
\end{...
1
vote
1answer
19 views
Random walk variance in R less than expected
I am trying to prove via some Monte Carlo simulation that the variance of a random walk equals $t*σ^2$ in R. I am running the following code, 180 times, to find the variance of 180 different random ...
3
votes
2answers
77 views
Which one is more likely to be random walk?
Consider the two series in the chart below: $walkA$ and $walkB$.
They are based on the same steps, although the steps come in a different order.
Indeed, $stepsA$ and $stepsB$ have identical sample ...
0
votes
1answer
38 views
Can a ARIMA(0,0,0) model be stationary?
I have a time series of a stock and use its log differenced daily returns. I have conducted an ADF test for a presence of unit roots, a KPSS test as well and both confirms stationarity in the time ...
0
votes
0answers
26 views
Random walk and variance [duplicate]
If yt is pure random walk the variance Var(yt-yt-k) will (increase, decrease or remains constant) as lag k increases?
0
votes
0answers
31 views
Random walks and Pearson's correlation
One well known problem in time series analysis is spurious correlation when time series are non-stationary (and non-cointegrated). Given random walks of the form $R_i=R_{i-1}+\epsilon_i$, with $\...
0
votes
0answers
10 views
Method for predicting the probability of encountering variably-sized and distanced objects in a 2D random walk
I am working on an archaeological research problem (how people discover new resources on a landscape) and need some assistance on where to look or terms to research for a particular simulation I'm ...
1
vote
0answers
12 views
Same results for RandomWalk and Snowball sampling algorithms
I am trying to find the best sampling algorithm to obtain a sampled graph that exhibits the same distribution compared to the original graph. The metric I am using at the moment is PageRank.
The ...
1
vote
1answer
83 views
Random walk with drift and trend
I am currently having a problem regarding the process,
so this was the equation
$$Y_t = \alpha + Y_{t-1} + \beta t + \epsilon_t$$
where, $\epsilon_t \sim WN(0, \sigma^2)$
I was calculating the $E(y)$ ...
1
vote
0answers
32 views
Probability Assigned to Distance between Two People Random Walking in a Room [closed]
In a scenario where there are two people in the rooms next to each other randomly walking in a room I want to know if we can compute PDF of distance between the two people. So the way I tried to ...
1
vote
0answers
30 views
A Skip Free Negative Random Walk
Suppose $\{X_{n}|n\geq 1\}$ is independent, identically distributed distribuited. Define $S_{0}=X_{0}=1$ and for $n\geq 1$
$$S_{n}=X_{0}+X_{1}+\cdots+X_{n}.$$
For $n\geq 1$ the distribution of $X_{n}$ ...
0
votes
0answers
56 views
what is the expected value of the dot product of two vectors
I have a little question, but I don't know that well how to answer it. I have a random walker with position vector $\vec{r} = \sum_{i=1}^N \vec{r}_i$, where i is the random walker's step. Every vector ...
4
votes
0answers
47 views
What correlation structure is necessary to ensure a random walk is almost surely bounded?
Say I have a stochastic process $\{X_t\}_{t \in \mathbb{N}}$ such that their cumulative sum $\{S_t\}_{t \in \mathbb{N}}$ is a random walk process:
$$
S_t = \sum_{i = 1}^t X_i
$$
If each $X_t$ is i.i.d ...
2
votes
1answer
71 views
Convergence of random walk in $R^2$ to the Brownian motion on circle
We know that the random walk generated in $R^1$ can converge weakly in distribution to the Brownian motion in $R^1$. Could anybody provide a mathematical proof, how a random walk generated in $R^2$ ...
0
votes
0answers
66 views
Random Walk in $R^2$ vs Brownian motion in $R^2$
By central limit theorem, random walk in $R^1$ converges in distribution to the Brownian motion in $R^1$.
For defining a 2D random walk, is there any difference between :
a) If we decompose a 2D ...
5
votes
1answer
224 views
Variance of a 2D random walk
let define a 2D random walk by
$$
\sum_i A_i X_i
$$
where $A=[\cos(\theta)\ \sin(\theta)]^T$, $\theta$ is a random variable in the range $[0,2\pi]$ and $X$ is a scalar random variable between $[-1,1]$....
0
votes
0answers
9 views
Variance Ratio test for 3-D random walks
The variance ratio test proposed by Lo and MacKinlay (1988) is used to detect 1-D random-walk-like-behaviour. 1-D works great for time-series data, but I'd like to adapt this test for imaging data to ...
0
votes
0answers
43 views
Test for correlated vs uncorrelated increments in random walks
Is there a test that can distinguish the strictest form of the random walk,
$$P_{t}=P_{t-1}+\varepsilon_{t}, \varepsilon_{t} \sim \mathrm{IID}\left(0, \sigma^{2}\right)$$
where each step is assumed to ...
0
votes
0answers
7 views
Autocorrelation test robust to heteroskedasticity
I'm testing the random walk hypothesises 1 and 3. I'm done with the first hypothesis but am struggling with the test distribution of the third one.
I'm using the autocorrelationstest. For the first ...
1
vote
2answers
55 views
Confused about stationarity and ARIMA processes
So I am quite confused about stationarity in ARIMA processes. For example, a Random Walk is an ARIMA process with order (1,0,0). Does this mean that a Random walk is stationary?
Stationarity implies ...
0
votes
0answers
19 views
Is it possible to produce two [random] graphs that always pass each other
My question is whether it is possible to create two graphs that go up one point or fall one point at a time [e.g. every minute] in a random walk, and they will pass over each other for sure all the ...
2
votes
1answer
45 views
Random walking with high synthetic correlation
My question is if there is a way to create two graphs that move one point up or down at a time in a random walk, and there will be a high [synthetic] correlation between them [example: 0.8 in Pearson'...
1
vote
1answer
212 views
Metropolis-Hastings exercise with Cauchy and normal distributions [self-study]
I have the following exercise to solve and would appreciate some help.
Consider a linear regression model $y = X\beta + \varepsilon$, where $y = (y_1,...,y_T)'$, $X = (x_1,...,x_T)$, $x_t$ is a single ...
0
votes
0answers
16 views
Expected number of steps for 1D circular random walk with jumps
Consider a simple 1D random walk with 50/50 probability to go left or right. The expected number of steps to reach a barrier at position $a$ or $b$ steps away is given here.
If this random walk is ...
0
votes
1answer
31 views
I must solve this question on random walk, but I don't know where to start or how to do it (I need a hint)
Let $\{y_t: t=1,2,\dots \}$ follow a random walk, as in: $y_t=y_{t-1}+e_t$, with $y_0=0$. Show that Corr$(y_t,y_{t+h} )=\sqrt{t ⁄ (t+h)}$, for $t\ge 1$, $h>0$.
0
votes
0answers
12 views
What is an I(k) random walk process?
Local linear trend - I(2) process: An extension of the random walk trend is obtained by including a stochastic drift component µt+1 = µt + βt + ηt, βt+1 = βt + ζt, ζt ∼ NID(0,σ2 ζ), (3) where the ...
1
vote
0answers
88 views
Does the unconditional mean of a non stationary ARMA process exists?
Assume that we are dealing with an $ARMA(1,1)$ model:
$$
y_{t} = \theta y_{t-1} + \epsilon_{t} + \alpha \epsilon_{t-1}
$$
where $$ \epsilon_{t} \sim WN(0, \sigma^{2})
$$
Then, we can rewrite the model ...
1
vote
0answers
9 views
Dynamic confidence intervals for Bernoulli trails
Let $\dots, X_i, \dots\sim B(p)$ be iid. Bernoulli random variables with mean $p$,
then we know from Chernoff bounds that $\Pr[\left|1-\frac{1}{np}\sum_{i=1}^n X_i\right|>\epsilon]\le2\exp(-\...
0
votes
2answers
49 views
If two random walk patterns follow each other, is it still considered a random walk?
I am wondering if these two lines, F1 and F2, representing time series, would still be considered "random walk", once the relationship between the two was discovered? Could this relationship ever even ...
0
votes
1answer
19 views
How to implement a survival function PDF?
I'm trying to generate a set of points whose separations are given by a Lévy flight. A source that I have (Peebles 1993) says that the process goes as
Starting from a [point] in space, place the ...
3
votes
2answers
44 views
Variance of Marginals of Continuous Random Walk Conditioned on Future Value
Consider the $N$ i.i.d. values
$$ X_i \sim \mathcal{N}(0, \sigma^2) $$
such that
$$ Z_i = \sum_{j=1}^i X_j $$
I am interested in the distribution
$$ f(X_i | Z_N = z) $$
Mean
Under the condition,...
0
votes
1answer
165 views
what is the difference between GCN and random walk
Anyone could explain to me what is the difference between graph convolutional network (GCN) and random walk? or they are the same?
Any further explanation will be much appreciated.
1
vote
0answers
30 views
Expected HIGH and LOW of a random walk?
Given the random walk $s_n$
$$s_n=\sum x_i, \space\space\space x_i \text{ iid, }\space\space x_i \sim N[0,\sigma]$$
what are the expected highest/lowest values of the walk after $n$ steps?
$$H_n=E[...
1
vote
0answers
22 views
Ornstein-Uhlenbeck process inside boundaries
I have some simulation of the Ornstein-Uhlenbeck process:
...
0
votes
1answer
65 views
How can I prove the simple random walk is a Markov process?
I know a simple random walk is defined as $X_t=X_{t-1}+w_t$, but how can I modify this equation is show it is a Markov process?
6
votes
2answers
2k views
Prove that a simple random walk is a martingale
Note that $a$ has a mean of 0.
My approach:
$$X_t=X_{t-1}+a_t$$
$$E[X_{t+1}\mid X_1 + \dots+X_{t-1}]$$
$$=E[X_{t-1}+2a\mid X_1 + \dots+X_{t-1}]$$
$$=E[X_{t-1}\mid X_1 + \dots+X_{t-1}]+E[2a\mid X_1 + ...