Mixing
Number of reversals of direction to return in random walk
$begingroup$
I am wondering if there are some studies about the number of reversals of direction to return to the starting point in random walk (either symmetric or non-symmetric), for example, its distribution and expectation etc.
probability-theory random-walk
edited Jan 28 at 21:37
Did
249k23226466
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
$endgroup$
add a comment |
$begingroup$
I am wondering if there are some studies about the number of reversals of direction to return to the starting point in random walk (either symmetric or non-symmetric), for example, its distribution and expectation etc.
probability-theory random-walk
edited Jan 28 at 21:37
Did
249k23226466
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
$endgroup$
1
$begingroup$
I guess you are interested in a 1D discrete random walk?
$endgroup$
– Fabian
Mar 8 '11 at 21:26
1
$begingroup$
Are you fixing the length or stopping the walk the first time it returns to the origin or what? What precisely is the random variable you're interested in?
$endgroup$
– Qiaochu Yuan
Mar 8 '11 at 21:26
$begingroup$
@Qiaochu: I am stopping the walk the first time it returns to the origin, if it started there too. The random variable I am considering is: the number of reverses of direction.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
$begingroup$
@Fabian, yes, 1D discrete random walk.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
add a comment |
$begingroup$
I am wondering if there are some studies about the number of reversals of direction to return to the starting point in random walk (either symmetric or non-symmetric), for example, its distribution and expectation etc.
probability-theory random-walk
edited Jan 28 at 21:37
Did
249k23226466
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
$endgroup$
I am wondering if there are some studies about the number of reversals of direction to return to the starting point in random walk (either symmetric or non-symmetric), for example, its distribution and expectation etc.
probability-theory random-walk
probability-theory random-walk
edited Jan 28 at 21:37
Did
249k23226466
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
edited Jan 28 at 21:37
Did
249k23226466
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
edited Jan 28 at 21:37
Did
249k23226466
edited Jan 28 at 21:37
Did
249k23226466
edited Jan 28 at 21:37
Did
249k23226466
249k23226466
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
asked Mar 8 '11 at 21:17
Qiang LiQiang Li
1,82222639
1,82222639
1
$begingroup$
I guess you are interested in a 1D discrete random walk?
$endgroup$
– Fabian
Mar 8 '11 at 21:26
1
$begingroup$
Are you fixing the length or stopping the walk the first time it returns to the origin or what? What precisely is the random variable you're interested in?
$endgroup$
– Qiaochu Yuan
Mar 8 '11 at 21:26
$begingroup$
@Qiaochu: I am stopping the walk the first time it returns to the origin, if it started there too. The random variable I am considering is: the number of reverses of direction.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
$begingroup$
@Fabian, yes, 1D discrete random walk.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
add a comment |
1
$begingroup$
I guess you are interested in a 1D discrete random walk?
$endgroup$
– Fabian
Mar 8 '11 at 21:26
1
$begingroup$
Are you fixing the length or stopping the walk the first time it returns to the origin or what? What precisely is the random variable you're interested in?
$endgroup$
– Qiaochu Yuan
Mar 8 '11 at 21:26
$begingroup$
@Qiaochu: I am stopping the walk the first time it returns to the origin, if it started there too. The random variable I am considering is: the number of reverses of direction.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
$begingroup$
@Fabian, yes, 1D discrete random walk.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
1
1
$begingroup$
I guess you are interested in a 1D discrete random walk?
$endgroup$
– Fabian
Mar 8 '11 at 21:26
$begingroup$
I guess you are interested in a 1D discrete random walk?
$endgroup$
– Fabian
Mar 8 '11 at 21:26
1
1
$begingroup$
Are you fixing the length or stopping the walk the first time it returns to the origin or what? What precisely is the random variable you're interested in?
$endgroup$
– Qiaochu Yuan
Mar 8 '11 at 21:26
$begingroup$
Are you fixing the length or stopping the walk the first time it returns to the origin or what? What precisely is the random variable you're interested in?
$endgroup$
– Qiaochu Yuan
Mar 8 '11 at 21:26
$begingroup$
@Qiaochu: I am stopping the walk the first time it returns to the origin, if it started there too. The random variable I am considering is: the number of reverses of direction.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
$begingroup$
@Qiaochu: I am stopping the walk the first time it returns to the origin, if it started there too. The random variable I am considering is: the number of reverses of direction.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
$begingroup$
@Fabian, yes, 1D discrete random walk.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
$begingroup$
@Fabian, yes, 1D discrete random walk.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
In the symmetric case, one assumes that $X_0=0$ and that $X_n=Y_1+cdots+Y_n$ for $nge1$, where $(Y_n)_{nge1}$ is i.i.d. Bernoulli and centered. For $nge1$, let $R_n$ denote the number of reversals of $(X_k)_{0le kle n}$. Then $R_1=0$ and $R_n=U_2+cdots+U_n$ where $U_k=[Y_kY_{k-1}=-1]$.
The conditional expectation of $R_{n+1}$ with respect to the $sigma$-algebra $F_n=sigma(X_k;0le kle n)$ is $R_n+P(Y_nY_{n+1}=-1|F_n)=R_n+frac12$, hence $M_n=2R_n-n$ defines a martingale $(M_n)_{nge1}$ starting from $M_1=-1$.
In particular, for every uniformly integrable stopping time such as the first hitting time $T_h$ of the set ${0,h}$ with $hge1$ by $(X_n)_n$, $E(M_{T_h})=-1$, hence
$$
2E(R_{T_h})=E(T_h)-1.
$$
When $hto+infty$, $T_h$ converges to the first return time $T$ to $0$ and $T$ is not integrable hence $R_T$ is not integrable.
In the asymmetric case, assume that $P(Y_n=+1)=p$ and $P(Y_n=-1)=1-p$ for a given $p$ in $(0,1)$. If $pnefrac12$, $(X_n)_n$ has a positive probability to never hit $0$ again, in which case the total number of reversals of its path is almost surely infinite, hence not integrable.
One way to save the day is to assume that $p<frac12$ (for example) and to condition on the event $[X_1=1]$. Write $P^+$ for this conditioned probability measure and $E^+$ for the expectation with respect to $P^+$. Then the first return time $T$ to $0$ is (at last!) integrable for $P^+$ and $R_Tle T-1$ hence $R_T$ is integrable for $P^+$.
To compute the value of $E^+(R_T)$, one can mimick the argument given in the symmetric case to show that the formula
$$
M_n=2R_n-n-(1-2p)X_{n-1}
$$
defines a martingale $(M_n)_{nge1}$ with respect to $P^+$, starting from $M_1=-1$. Since $X_{T-1}=+1$ almost surely for $P^+$, this yields
$$
2E^+(R_{T})=E^+(T)-2p,
$$
and it remains to compute $E^+(T)$. This can be done by the usual first-step decomposition: on $[Y_2=-1]$, $T=2$, and on $[Y_2=+1]$, $T=T'+T''$ for two independent copies of $T$. Hence $E^+(T)=2(1-p)+2E^+(T)p$, which yields the value of $E^+(T)$. Finally the mean number of reversals is
$$
E^+(R_T)=frac{1-2p(1-p)}{1-2p}.
$$
answered Mar 9 '11 at 0:00
DidDid
249k23226466
$endgroup$
$begingroup$
Nice answer! Wish I could vote it up again.
$endgroup$
– user940
Mar 9 '11 at 13:25
$begingroup$
@Basj $$U_k=mathbf 1_{A_k}qquad A_k={Y_kY_{k-1}=-1}$$ Yes, $Y_kY_{k-1}=-1$ means exactly that a reversal occurs.
$endgroup$
– Did
Jan 28 at 21:35
$begingroup$
(Deleted and reposted comment because it was incomplete): What do you mean by $U_k=[Y_kY_{k-1}=-1]$? It seems $Y_kY_{k-1}=-1$ doesn't mean $X_k$ has a reversal, it only means two consecutive Bernoulli r.v. $Y_k$ have different values, but this doesn't imply the cumulative sum $X_k$ has a reversal, isn't it right?
$endgroup$
– Basj
Jan 28 at 21:38
$begingroup$
@Basj Please see comment above.
$endgroup$
– Did
Jan 28 at 21:39
$begingroup$
Ohh I see. I was looking for "sign change" (i.e. $X_k geq 0$ and $X_{k+1} < 0$), and I thought "reversal" would be a synonym, but it's not... My bad! Do you know if there is a good question about proving that there is an infinite number of sign changes for a random walk (symmetric Bernoulli case) @Did?
$endgroup$
– Basj
Jan 28 at 21:41
|
show 2 more comments
$begingroup$
For the symmetric random walk with $X_0=0$ and conditioned on $X_{2n}=0$, the average number of reversals should be $n$. Each outcome is a random ordering of $n$ plus signs and $n$ minus signs. A reversal takes place at any of the $2n-1$ time points from $1$ to $2n-1$, when the neighboring signs are opposite. Given the sign of one neighbor, the chance that the other neighbor has an opposite sign is ${nover 2n-1}$. Adding up over the time points shows that the average number of sign changes is $n$.
The original question however is about the average number of reversals up to the first return $T$ to the origin. The argument above can be modified to show that, for $n>1$,
$$E(mbox{reversals} | T=2n) = n - 1 = T/2-1,$$ so that the expected number of reversals is infinite.
$endgroup$
2
$begingroup$
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $frac{2}{3}$ so 1 is both the median and the mode.
$endgroup$
– Henry
Mar 9 '11 at 1:06
$begingroup$
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach.
$endgroup$
– cardinal
Mar 18 '11 at 14:58
$begingroup$
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $sum_{n=1}^{infty}2/4^n = 2/3$
$endgroup$
– Henry
Mar 18 '11 at 17:58
$begingroup$
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event ${X_2 geq X_1}$ for i.i.d. $mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $mathbb{P}(X_2 geq X_1) = frac{1}{2}(1+mathbb{P}(X_2 = X_1)) = frac{2}{3}$.
$endgroup$
– cardinal
Mar 19 '11 at 4:26
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f25836%2fnumber-of-reversals-of-direction-to-return-in-random-walk%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In the symmetric case, one assumes that $X_0=0$ and that $X_n=Y_1+cdots+Y_n$ for $nge1$, where $(Y_n)_{nge1}$ is i.i.d. Bernoulli and centered. For $nge1$, let $R_n$ denote the number of reversals of $(X_k)_{0le kle n}$. Then $R_1=0$ and $R_n=U_2+cdots+U_n$ where $U_k=[Y_kY_{k-1}=-1]$.
The conditional expectation of $R_{n+1}$ with respect to the $sigma$-algebra $F_n=sigma(X_k;0le kle n)$ is $R_n+P(Y_nY_{n+1}=-1|F_n)=R_n+frac12$, hence $M_n=2R_n-n$ defines a martingale $(M_n)_{nge1}$ starting from $M_1=-1$.
In particular, for every uniformly integrable stopping time such as the first hitting time $T_h$ of the set ${0,h}$ with $hge1$ by $(X_n)_n$, $E(M_{T_h})=-1$, hence
$$
2E(R_{T_h})=E(T_h)-1.
$$
When $hto+infty$, $T_h$ converges to the first return time $T$ to $0$ and $T$ is not integrable hence $R_T$ is not integrable.
In the asymmetric case, assume that $P(Y_n=+1)=p$ and $P(Y_n=-1)=1-p$ for a given $p$ in $(0,1)$. If $pnefrac12$, $(X_n)_n$ has a positive probability to never hit $0$ again, in which case the total number of reversals of its path is almost surely infinite, hence not integrable.
One way to save the day is to assume that $p<frac12$ (for example) and to condition on the event $[X_1=1]$. Write $P^+$ for this conditioned probability measure and $E^+$ for the expectation with respect to $P^+$. Then the first return time $T$ to $0$ is (at last!) integrable for $P^+$ and $R_Tle T-1$ hence $R_T$ is integrable for $P^+$.
To compute the value of $E^+(R_T)$, one can mimick the argument given in the symmetric case to show that the formula
$$
M_n=2R_n-n-(1-2p)X_{n-1}
$$
defines a martingale $(M_n)_{nge1}$ with respect to $P^+$, starting from $M_1=-1$. Since $X_{T-1}=+1$ almost surely for $P^+$, this yields
$$
2E^+(R_{T})=E^+(T)-2p,
$$
and it remains to compute $E^+(T)$. This can be done by the usual first-step decomposition: on $[Y_2=-1]$, $T=2$, and on $[Y_2=+1]$, $T=T'+T''$ for two independent copies of $T$. Hence $E^+(T)=2(1-p)+2E^+(T)p$, which yields the value of $E^+(T)$. Finally the mean number of reversals is
$$
E^+(R_T)=frac{1-2p(1-p)}{1-2p}.
$$
answered Mar 9 '11 at 0:00
DidDid
249k23226466
$endgroup$
$begingroup$
Nice answer! Wish I could vote it up again.
$endgroup$
– user940
Mar 9 '11 at 13:25
$begingroup$
@Basj $$U_k=mathbf 1_{A_k}qquad A_k={Y_kY_{k-1}=-1}$$ Yes, $Y_kY_{k-1}=-1$ means exactly that a reversal occurs.
$endgroup$
– Did
Jan 28 at 21:35
$begingroup$
(Deleted and reposted comment because it was incomplete): What do you mean by $U_k=[Y_kY_{k-1}=-1]$? It seems $Y_kY_{k-1}=-1$ doesn't mean $X_k$ has a reversal, it only means two consecutive Bernoulli r.v. $Y_k$ have different values, but this doesn't imply the cumulative sum $X_k$ has a reversal, isn't it right?
$endgroup$
– Basj
Jan 28 at 21:38
$begingroup$
@Basj Please see comment above.
$endgroup$
– Did
Jan 28 at 21:39
$begingroup$
Ohh I see. I was looking for "sign change" (i.e. $X_k geq 0$ and $X_{k+1} < 0$), and I thought "reversal" would be a synonym, but it's not... My bad! Do you know if there is a good question about proving that there is an infinite number of sign changes for a random walk (symmetric Bernoulli case) @Did?
$endgroup$
– Basj
Jan 28 at 21:41
|
show 2 more comments
$begingroup$
In the symmetric case, one assumes that $X_0=0$ and that $X_n=Y_1+cdots+Y_n$ for $nge1$, where $(Y_n)_{nge1}$ is i.i.d. Bernoulli and centered. For $nge1$, let $R_n$ denote the number of reversals of $(X_k)_{0le kle n}$. Then $R_1=0$ and $R_n=U_2+cdots+U_n$ where $U_k=[Y_kY_{k-1}=-1]$.
The conditional expectation of $R_{n+1}$ with respect to the $sigma$-algebra $F_n=sigma(X_k;0le kle n)$ is $R_n+P(Y_nY_{n+1}=-1|F_n)=R_n+frac12$, hence $M_n=2R_n-n$ defines a martingale $(M_n)_{nge1}$ starting from $M_1=-1$.
In particular, for every uniformly integrable stopping time such as the first hitting time $T_h$ of the set ${0,h}$ with $hge1$ by $(X_n)_n$, $E(M_{T_h})=-1$, hence
$$
2E(R_{T_h})=E(T_h)-1.
$$
When $hto+infty$, $T_h$ converges to the first return time $T$ to $0$ and $T$ is not integrable hence $R_T$ is not integrable.
In the asymmetric case, assume that $P(Y_n=+1)=p$ and $P(Y_n=-1)=1-p$ for a given $p$ in $(0,1)$. If $pnefrac12$, $(X_n)_n$ has a positive probability to never hit $0$ again, in which case the total number of reversals of its path is almost surely infinite, hence not integrable.
One way to save the day is to assume that $p<frac12$ (for example) and to condition on the event $[X_1=1]$. Write $P^+$ for this conditioned probability measure and $E^+$ for the expectation with respect to $P^+$. Then the first return time $T$ to $0$ is (at last!) integrable for $P^+$ and $R_Tle T-1$ hence $R_T$ is integrable for $P^+$.
To compute the value of $E^+(R_T)$, one can mimick the argument given in the symmetric case to show that the formula
$$
M_n=2R_n-n-(1-2p)X_{n-1}
$$
defines a martingale $(M_n)_{nge1}$ with respect to $P^+$, starting from $M_1=-1$. Since $X_{T-1}=+1$ almost surely for $P^+$, this yields
$$
2E^+(R_{T})=E^+(T)-2p,
$$
and it remains to compute $E^+(T)$. This can be done by the usual first-step decomposition: on $[Y_2=-1]$, $T=2$, and on $[Y_2=+1]$, $T=T'+T''$ for two independent copies of $T$. Hence $E^+(T)=2(1-p)+2E^+(T)p$, which yields the value of $E^+(T)$. Finally the mean number of reversals is
$$
E^+(R_T)=frac{1-2p(1-p)}{1-2p}.
$$
answered Mar 9 '11 at 0:00
DidDid
249k23226466
$endgroup$
$begingroup$
Nice answer! Wish I could vote it up again.
$endgroup$
– user940
Mar 9 '11 at 13:25
$begingroup$
@Basj $$U_k=mathbf 1_{A_k}qquad A_k={Y_kY_{k-1}=-1}$$ Yes, $Y_kY_{k-1}=-1$ means exactly that a reversal occurs.
$endgroup$
– Did
Jan 28 at 21:35
$begingroup$
(Deleted and reposted comment because it was incomplete): What do you mean by $U_k=[Y_kY_{k-1}=-1]$? It seems $Y_kY_{k-1}=-1$ doesn't mean $X_k$ has a reversal, it only means two consecutive Bernoulli r.v. $Y_k$ have different values, but this doesn't imply the cumulative sum $X_k$ has a reversal, isn't it right?
$endgroup$
– Basj
Jan 28 at 21:38
$begingroup$
@Basj Please see comment above.
$endgroup$
– Did
Jan 28 at 21:39
$begingroup$
Ohh I see. I was looking for "sign change" (i.e. $X_k geq 0$ and $X_{k+1} < 0$), and I thought "reversal" would be a synonym, but it's not... My bad! Do you know if there is a good question about proving that there is an infinite number of sign changes for a random walk (symmetric Bernoulli case) @Did?
$endgroup$
– Basj
Jan 28 at 21:41
|
show 2 more comments
$begingroup$
In the symmetric case, one assumes that $X_0=0$ and that $X_n=Y_1+cdots+Y_n$ for $nge1$, where $(Y_n)_{nge1}$ is i.i.d. Bernoulli and centered. For $nge1$, let $R_n$ denote the number of reversals of $(X_k)_{0le kle n}$. Then $R_1=0$ and $R_n=U_2+cdots+U_n$ where $U_k=[Y_kY_{k-1}=-1]$.
The conditional expectation of $R_{n+1}$ with respect to the $sigma$-algebra $F_n=sigma(X_k;0le kle n)$ is $R_n+P(Y_nY_{n+1}=-1|F_n)=R_n+frac12$, hence $M_n=2R_n-n$ defines a martingale $(M_n)_{nge1}$ starting from $M_1=-1$.
In particular, for every uniformly integrable stopping time such as the first hitting time $T_h$ of the set ${0,h}$ with $hge1$ by $(X_n)_n$, $E(M_{T_h})=-1$, hence
$$
2E(R_{T_h})=E(T_h)-1.
$$
When $hto+infty$, $T_h$ converges to the first return time $T$ to $0$ and $T$ is not integrable hence $R_T$ is not integrable.
In the asymmetric case, assume that $P(Y_n=+1)=p$ and $P(Y_n=-1)=1-p$ for a given $p$ in $(0,1)$. If $pnefrac12$, $(X_n)_n$ has a positive probability to never hit $0$ again, in which case the total number of reversals of its path is almost surely infinite, hence not integrable.
One way to save the day is to assume that $p<frac12$ (for example) and to condition on the event $[X_1=1]$. Write $P^+$ for this conditioned probability measure and $E^+$ for the expectation with respect to $P^+$. Then the first return time $T$ to $0$ is (at last!) integrable for $P^+$ and $R_Tle T-1$ hence $R_T$ is integrable for $P^+$.
To compute the value of $E^+(R_T)$, one can mimick the argument given in the symmetric case to show that the formula
$$
M_n=2R_n-n-(1-2p)X_{n-1}
$$
defines a martingale $(M_n)_{nge1}$ with respect to $P^+$, starting from $M_1=-1$. Since $X_{T-1}=+1$ almost surely for $P^+$, this yields
$$
2E^+(R_{T})=E^+(T)-2p,
$$
and it remains to compute $E^+(T)$. This can be done by the usual first-step decomposition: on $[Y_2=-1]$, $T=2$, and on $[Y_2=+1]$, $T=T'+T''$ for two independent copies of $T$. Hence $E^+(T)=2(1-p)+2E^+(T)p$, which yields the value of $E^+(T)$. Finally the mean number of reversals is
$$
E^+(R_T)=frac{1-2p(1-p)}{1-2p}.
$$
answered Mar 9 '11 at 0:00
DidDid
249k23226466
$endgroup$
In the symmetric case, one assumes that $X_0=0$ and that $X_n=Y_1+cdots+Y_n$ for $nge1$, where $(Y_n)_{nge1}$ is i.i.d. Bernoulli and centered. For $nge1$, let $R_n$ denote the number of reversals of $(X_k)_{0le kle n}$. Then $R_1=0$ and $R_n=U_2+cdots+U_n$ where $U_k=[Y_kY_{k-1}=-1]$.
The conditional expectation of $R_{n+1}$ with respect to the $sigma$-algebra $F_n=sigma(X_k;0le kle n)$ is $R_n+P(Y_nY_{n+1}=-1|F_n)=R_n+frac12$, hence $M_n=2R_n-n$ defines a martingale $(M_n)_{nge1}$ starting from $M_1=-1$.
In particular, for every uniformly integrable stopping time such as the first hitting time $T_h$ of the set ${0,h}$ with $hge1$ by $(X_n)_n$, $E(M_{T_h})=-1$, hence
$$
2E(R_{T_h})=E(T_h)-1.
$$
When $hto+infty$, $T_h$ converges to the first return time $T$ to $0$ and $T$ is not integrable hence $R_T$ is not integrable.
In the asymmetric case, assume that $P(Y_n=+1)=p$ and $P(Y_n=-1)=1-p$ for a given $p$ in $(0,1)$. If $pnefrac12$, $(X_n)_n$ has a positive probability to never hit $0$ again, in which case the total number of reversals of its path is almost surely infinite, hence not integrable.
One way to save the day is to assume that $p<frac12$ (for example) and to condition on the event $[X_1=1]$. Write $P^+$ for this conditioned probability measure and $E^+$ for the expectation with respect to $P^+$. Then the first return time $T$ to $0$ is (at last!) integrable for $P^+$ and $R_Tle T-1$ hence $R_T$ is integrable for $P^+$.
To compute the value of $E^+(R_T)$, one can mimick the argument given in the symmetric case to show that the formula
$$
M_n=2R_n-n-(1-2p)X_{n-1}
$$
defines a martingale $(M_n)_{nge1}$ with respect to $P^+$, starting from $M_1=-1$. Since $X_{T-1}=+1$ almost surely for $P^+$, this yields
$$
2E^+(R_{T})=E^+(T)-2p,
$$
and it remains to compute $E^+(T)$. This can be done by the usual first-step decomposition: on $[Y_2=-1]$, $T=2$, and on $[Y_2=+1]$, $T=T'+T''$ for two independent copies of $T$. Hence $E^+(T)=2(1-p)+2E^+(T)p$, which yields the value of $E^+(T)$. Finally the mean number of reversals is
$$
E^+(R_T)=frac{1-2p(1-p)}{1-2p}.
$$
answered Mar 9 '11 at 0:00
DidDid
249k23226466
edited Mar 9 '11 at 13:42
answered Mar 9 '11 at 0:00
DidDid
249k23226466
answered Mar 9 '11 at 0:00
DidDid
249k23226466
answered Mar 9 '11 at 0:00
DidDid
249k23226466
249k23226466
$begingroup$
Nice answer! Wish I could vote it up again.
$endgroup$
– user940
Mar 9 '11 at 13:25
$begingroup$
@Basj $$U_k=mathbf 1_{A_k}qquad A_k={Y_kY_{k-1}=-1}$$ Yes, $Y_kY_{k-1}=-1$ means exactly that a reversal occurs.
$endgroup$
– Did
Jan 28 at 21:35
$begingroup$
(Deleted and reposted comment because it was incomplete): What do you mean by $U_k=[Y_kY_{k-1}=-1]$? It seems $Y_kY_{k-1}=-1$ doesn't mean $X_k$ has a reversal, it only means two consecutive Bernoulli r.v. $Y_k$ have different values, but this doesn't imply the cumulative sum $X_k$ has a reversal, isn't it right?
$endgroup$
– Basj
Jan 28 at 21:38
$begingroup$
@Basj Please see comment above.
$endgroup$
– Did
Jan 28 at 21:39
$begingroup$
Ohh I see. I was looking for "sign change" (i.e. $X_k geq 0$ and $X_{k+1} < 0$), and I thought "reversal" would be a synonym, but it's not... My bad! Do you know if there is a good question about proving that there is an infinite number of sign changes for a random walk (symmetric Bernoulli case) @Did?
$endgroup$
– Basj
Jan 28 at 21:41
|
show 2 more comments
$begingroup$
Nice answer! Wish I could vote it up again.
$endgroup$
– user940
Mar 9 '11 at 13:25
$begingroup$
@Basj $$U_k=mathbf 1_{A_k}qquad A_k={Y_kY_{k-1}=-1}$$ Yes, $Y_kY_{k-1}=-1$ means exactly that a reversal occurs.
$endgroup$
– Did
Jan 28 at 21:35
$begingroup$
(Deleted and reposted comment because it was incomplete): What do you mean by $U_k=[Y_kY_{k-1}=-1]$? It seems $Y_kY_{k-1}=-1$ doesn't mean $X_k$ has a reversal, it only means two consecutive Bernoulli r.v. $Y_k$ have different values, but this doesn't imply the cumulative sum $X_k$ has a reversal, isn't it right?
$endgroup$
– Basj
Jan 28 at 21:38
$begingroup$
@Basj Please see comment above.
$endgroup$
– Did
Jan 28 at 21:39
$begingroup$
Ohh I see. I was looking for "sign change" (i.e. $X_k geq 0$ and $X_{k+1} < 0$), and I thought "reversal" would be a synonym, but it's not... My bad! Do you know if there is a good question about proving that there is an infinite number of sign changes for a random walk (symmetric Bernoulli case) @Did?
$endgroup$
– Basj
Jan 28 at 21:41
$begingroup$
Nice answer! Wish I could vote it up again.
$endgroup$
– user940
Mar 9 '11 at 13:25
$begingroup$
Nice answer! Wish I could vote it up again.
$endgroup$
– user940
Mar 9 '11 at 13:25
$begingroup$
@Basj $$U_k=mathbf 1_{A_k}qquad A_k={Y_kY_{k-1}=-1}$$ Yes, $Y_kY_{k-1}=-1$ means exactly that a reversal occurs.
$endgroup$
– Did
Jan 28 at 21:35
$begingroup$
@Basj $$U_k=mathbf 1_{A_k}qquad A_k={Y_kY_{k-1}=-1}$$ Yes, $Y_kY_{k-1}=-1$ means exactly that a reversal occurs.
$endgroup$
– Did
Jan 28 at 21:35
$begingroup$
(Deleted and reposted comment because it was incomplete): What do you mean by $U_k=[Y_kY_{k-1}=-1]$? It seems $Y_kY_{k-1}=-1$ doesn't mean $X_k$ has a reversal, it only means two consecutive Bernoulli r.v. $Y_k$ have different values, but this doesn't imply the cumulative sum $X_k$ has a reversal, isn't it right?
$endgroup$
– Basj
Jan 28 at 21:38
$begingroup$
(Deleted and reposted comment because it was incomplete): What do you mean by $U_k=[Y_kY_{k-1}=-1]$? It seems $Y_kY_{k-1}=-1$ doesn't mean $X_k$ has a reversal, it only means two consecutive Bernoulli r.v. $Y_k$ have different values, but this doesn't imply the cumulative sum $X_k$ has a reversal, isn't it right?
$endgroup$
– Basj
Jan 28 at 21:38
$begingroup$
@Basj Please see comment above.
$endgroup$
– Did
Jan 28 at 21:39
$begingroup$
@Basj Please see comment above.
$endgroup$
– Did
Jan 28 at 21:39
$begingroup$
Ohh I see. I was looking for "sign change" (i.e. $X_k geq 0$ and $X_{k+1} < 0$), and I thought "reversal" would be a synonym, but it's not... My bad! Do you know if there is a good question about proving that there is an infinite number of sign changes for a random walk (symmetric Bernoulli case) @Did?
$endgroup$
– Basj
Jan 28 at 21:41
$begingroup$
Ohh I see. I was looking for "sign change" (i.e. $X_k geq 0$ and $X_{k+1} < 0$), and I thought "reversal" would be a synonym, but it's not... My bad! Do you know if there is a good question about proving that there is an infinite number of sign changes for a random walk (symmetric Bernoulli case) @Did?
$endgroup$
– Basj
Jan 28 at 21:41
|
show 2 more comments
$begingroup$
For the symmetric random walk with $X_0=0$ and conditioned on $X_{2n}=0$, the average number of reversals should be $n$. Each outcome is a random ordering of $n$ plus signs and $n$ minus signs. A reversal takes place at any of the $2n-1$ time points from $1$ to $2n-1$, when the neighboring signs are opposite. Given the sign of one neighbor, the chance that the other neighbor has an opposite sign is ${nover 2n-1}$. Adding up over the time points shows that the average number of sign changes is $n$.
The original question however is about the average number of reversals up to the first return $T$ to the origin. The argument above can be modified to show that, for $n>1$,
$$E(mbox{reversals} | T=2n) = n - 1 = T/2-1,$$ so that the expected number of reversals is infinite.
$endgroup$
2
$begingroup$
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $frac{2}{3}$ so 1 is both the median and the mode.
$endgroup$
– Henry
Mar 9 '11 at 1:06
$begingroup$
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach.
$endgroup$
– cardinal
Mar 18 '11 at 14:58
$begingroup$
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $sum_{n=1}^{infty}2/4^n = 2/3$
$endgroup$
– Henry
Mar 18 '11 at 17:58
$begingroup$
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event ${X_2 geq X_1}$ for i.i.d. $mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $mathbb{P}(X_2 geq X_1) = frac{1}{2}(1+mathbb{P}(X_2 = X_1)) = frac{2}{3}$.
$endgroup$
– cardinal
Mar 19 '11 at 4:26
add a comment |
$begingroup$
For the symmetric random walk with $X_0=0$ and conditioned on $X_{2n}=0$, the average number of reversals should be $n$. Each outcome is a random ordering of $n$ plus signs and $n$ minus signs. A reversal takes place at any of the $2n-1$ time points from $1$ to $2n-1$, when the neighboring signs are opposite. Given the sign of one neighbor, the chance that the other neighbor has an opposite sign is ${nover 2n-1}$. Adding up over the time points shows that the average number of sign changes is $n$.
The original question however is about the average number of reversals up to the first return $T$ to the origin. The argument above can be modified to show that, for $n>1$,
$$E(mbox{reversals} | T=2n) = n - 1 = T/2-1,$$ so that the expected number of reversals is infinite.
$endgroup$
2
$begingroup$
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $frac{2}{3}$ so 1 is both the median and the mode.
$endgroup$
– Henry
Mar 9 '11 at 1:06
$begingroup$
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach.
$endgroup$
– cardinal
Mar 18 '11 at 14:58
$begingroup$
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $sum_{n=1}^{infty}2/4^n = 2/3$
$endgroup$
– Henry
Mar 18 '11 at 17:58
$begingroup$
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event ${X_2 geq X_1}$ for i.i.d. $mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $mathbb{P}(X_2 geq X_1) = frac{1}{2}(1+mathbb{P}(X_2 = X_1)) = frac{2}{3}$.
$endgroup$
– cardinal
Mar 19 '11 at 4:26
add a comment |
$begingroup$
For the symmetric random walk with $X_0=0$ and conditioned on $X_{2n}=0$, the average number of reversals should be $n$. Each outcome is a random ordering of $n$ plus signs and $n$ minus signs. A reversal takes place at any of the $2n-1$ time points from $1$ to $2n-1$, when the neighboring signs are opposite. Given the sign of one neighbor, the chance that the other neighbor has an opposite sign is ${nover 2n-1}$. Adding up over the time points shows that the average number of sign changes is $n$.
The original question however is about the average number of reversals up to the first return $T$ to the origin. The argument above can be modified to show that, for $n>1$,
$$E(mbox{reversals} | T=2n) = n - 1 = T/2-1,$$ so that the expected number of reversals is infinite.
$endgroup$
For the symmetric random walk with $X_0=0$ and conditioned on $X_{2n}=0$, the average number of reversals should be $n$. Each outcome is a random ordering of $n$ plus signs and $n$ minus signs. A reversal takes place at any of the $2n-1$ time points from $1$ to $2n-1$, when the neighboring signs are opposite. Given the sign of one neighbor, the chance that the other neighbor has an opposite sign is ${nover 2n-1}$. Adding up over the time points shows that the average number of sign changes is $n$.
The original question however is about the average number of reversals up to the first return $T$ to the origin. The argument above can be modified to show that, for $n>1$,
$$E(mbox{reversals} | T=2n) = n - 1 = T/2-1,$$ so that the expected number of reversals is infinite.
answered Mar 8 '11 at 22:38
user940
2
$begingroup$
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $frac{2}{3}$ so 1 is both the median and the mode.
$endgroup$
– Henry
Mar 9 '11 at 1:06
$begingroup$
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach.
$endgroup$
– cardinal
Mar 18 '11 at 14:58
$begingroup$
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $sum_{n=1}^{infty}2/4^n = 2/3$
$endgroup$
– Henry
Mar 18 '11 at 17:58
$begingroup$
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event ${X_2 geq X_1}$ for i.i.d. $mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $mathbb{P}(X_2 geq X_1) = frac{1}{2}(1+mathbb{P}(X_2 = X_1)) = frac{2}{3}$.
$endgroup$
– cardinal
Mar 19 '11 at 4:26
add a comment |
2
$begingroup$
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $frac{2}{3}$ so 1 is both the median and the mode.
$endgroup$
– Henry
Mar 9 '11 at 1:06
$begingroup$
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach.
$endgroup$
– cardinal
Mar 18 '11 at 14:58
$begingroup$
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $sum_{n=1}^{infty}2/4^n = 2/3$
$endgroup$
– Henry
Mar 18 '11 at 17:58
$begingroup$
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event ${X_2 geq X_1}$ for i.i.d. $mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $mathbb{P}(X_2 geq X_1) = frac{1}{2}(1+mathbb{P}(X_2 = X_1)) = frac{2}{3}$.
$endgroup$
– cardinal
Mar 19 '11 at 4:26
2
2
$begingroup$
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $frac{2}{3}$ so 1 is both the median and the mode.
$endgroup$
– Henry
Mar 9 '11 at 1:06
$begingroup$
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $frac{2}{3}$ so 1 is both the median and the mode.
$endgroup$
– Henry
Mar 9 '11 at 1:06
$begingroup$
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach.
$endgroup$
– cardinal
Mar 18 '11 at 14:58
$begingroup$
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach.
$endgroup$
– cardinal
Mar 18 '11 at 14:58
$begingroup$
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $sum_{n=1}^{infty}2/4^n = 2/3$
$endgroup$
– Henry
Mar 18 '11 at 17:58
$begingroup$
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $sum_{n=1}^{infty}2/4^n = 2/3$
$endgroup$
– Henry
Mar 18 '11 at 17:58
$begingroup$
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event ${X_2 geq X_1}$ for i.i.d. $mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $mathbb{P}(X_2 geq X_1) = frac{1}{2}(1+mathbb{P}(X_2 = X_1)) = frac{2}{3}$.
$endgroup$
– cardinal
Mar 19 '11 at 4:26
$begingroup$
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event ${X_2 geq X_1}$ for i.i.d. $mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $mathbb{P}(X_2 geq X_1) = frac{1}{2}(1+mathbb{P}(X_2 = X_1)) = frac{2}{3}$.
$endgroup$
– cardinal
Mar 19 '11 at 4:26
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f25836%2fnumber-of-reversals-of-direction-to-return-in-random-walk%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I guess you are interested in a 1D discrete random walk?
$endgroup$
– Fabian
Mar 8 '11 at 21:26
1
$begingroup$
Are you fixing the length or stopping the walk the first time it returns to the origin or what? What precisely is the random variable you're interested in?
$endgroup$
– Qiaochu Yuan
Mar 8 '11 at 21:26
$begingroup$
@Qiaochu: I am stopping the walk the first time it returns to the origin, if it started there too. The random variable I am considering is: the number of reverses of direction.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28
$begingroup$
@Fabian, yes, 1D discrete random walk.
$endgroup$
– Qiang Li
Mar 8 '11 at 21:28