Mixing
What happens to a random walk when we increase the probabilities of going right?
$begingroup$
Consider a random walk on the integers where the probability of transitioning from $n$ to $n+1$ is $p_n$ (and of course, the probability of transitioning from $n$ to $n-1$ is $1-p_n$); we assume all $p_n$ are strictly less than $1$. Suppose we know that this random walk is pretty well concentrated; for example, let us assume that we know that
$$P(|X(t) - (1/3)t| geq c sqrt{t}) leq e^{-c^2}$$ where $X(t)$ is the state of the walk after $t$ steps.
Now suppose we increase every $p_n$ by $epsilon$ (and correspondingly decrease the probability of transitioning from $n$ to $n-1$ by $epsilon$), where $epsilon$ is some number such that $p_n + epsilon < 1$ for all $n$. Let $Y(t)$ be the state of the new chain after $t$ steps. My question is: does a similar concentration result hold for $Y(t)$?
It seems very intuitive that $Y(t)$ should concentrate around $(1/3)t + 2 epsilon t$.
probability-theory markov-chains
asked Feb 22 '13 at 22:45
yvesyves
963
$endgroup$
add a comment |
$begingroup$
Consider a random walk on the integers where the probability of transitioning from $n$ to $n+1$ is $p_n$ (and of course, the probability of transitioning from $n$ to $n-1$ is $1-p_n$); we assume all $p_n$ are strictly less than $1$. Suppose we know that this random walk is pretty well concentrated; for example, let us assume that we know that
$$P(|X(t) - (1/3)t| geq c sqrt{t}) leq e^{-c^2}$$ where $X(t)$ is the state of the walk after $t$ steps.
Now suppose we increase every $p_n$ by $epsilon$ (and correspondingly decrease the probability of transitioning from $n$ to $n-1$ by $epsilon$), where $epsilon$ is some number such that $p_n + epsilon < 1$ for all $n$. Let $Y(t)$ be the state of the new chain after $t$ steps. My question is: does a similar concentration result hold for $Y(t)$?
It seems very intuitive that $Y(t)$ should concentrate around $(1/3)t + 2 epsilon t$.
probability-theory markov-chains
asked Feb 22 '13 at 22:45
yvesyves
963
$endgroup$
$begingroup$
What are the quantifiers on the concentration condition. Is it for one fixed t, but for all c?
$endgroup$
– jochen
Sep 3 '16 at 13:32
add a comment |
$begingroup$
Consider a random walk on the integers where the probability of transitioning from $n$ to $n+1$ is $p_n$ (and of course, the probability of transitioning from $n$ to $n-1$ is $1-p_n$); we assume all $p_n$ are strictly less than $1$. Suppose we know that this random walk is pretty well concentrated; for example, let us assume that we know that
$$P(|X(t) - (1/3)t| geq c sqrt{t}) leq e^{-c^2}$$ where $X(t)$ is the state of the walk after $t$ steps.
Now suppose we increase every $p_n$ by $epsilon$ (and correspondingly decrease the probability of transitioning from $n$ to $n-1$ by $epsilon$), where $epsilon$ is some number such that $p_n + epsilon < 1$ for all $n$. Let $Y(t)$ be the state of the new chain after $t$ steps. My question is: does a similar concentration result hold for $Y(t)$?
It seems very intuitive that $Y(t)$ should concentrate around $(1/3)t + 2 epsilon t$.
probability-theory markov-chains
asked Feb 22 '13 at 22:45
yvesyves
963
$endgroup$
Consider a random walk on the integers where the probability of transitioning from $n$ to $n+1$ is $p_n$ (and of course, the probability of transitioning from $n$ to $n-1$ is $1-p_n$); we assume all $p_n$ are strictly less than $1$. Suppose we know that this random walk is pretty well concentrated; for example, let us assume that we know that
$$P(|X(t) - (1/3)t| geq c sqrt{t}) leq e^{-c^2}$$ where $X(t)$ is the state of the walk after $t$ steps.
Now suppose we increase every $p_n$ by $epsilon$ (and correspondingly decrease the probability of transitioning from $n$ to $n-1$ by $epsilon$), where $epsilon$ is some number such that $p_n + epsilon < 1$ for all $n$. Let $Y(t)$ be the state of the new chain after $t$ steps. My question is: does a similar concentration result hold for $Y(t)$?
It seems very intuitive that $Y(t)$ should concentrate around $(1/3)t + 2 epsilon t$.
probability-theory markov-chains
probability-theory markov-chains
asked Feb 22 '13 at 22:45
yvesyves
963
asked Feb 22 '13 at 22:45
yvesyves
963
edited Feb 23 '13 at 23:09
yves
asked Feb 22 '13 at 22:45
yvesyves
963
asked Feb 22 '13 at 22:45
yvesyves
963
asked Feb 22 '13 at 22:45
yvesyves
963
963
$begingroup$
What are the quantifiers on the concentration condition. Is it for one fixed t, but for all c?
$endgroup$
– jochen
Sep 3 '16 at 13:32
add a comment |
$begingroup$
What are the quantifiers on the concentration condition. Is it for one fixed t, but for all c?
$endgroup$
– jochen
Sep 3 '16 at 13:32
$begingroup$
What are the quantifiers on the concentration condition. Is it for one fixed t, but for all c?
$endgroup$
– jochen
Sep 3 '16 at 13:32
$begingroup$
What are the quantifiers on the concentration condition. Is it for one fixed t, but for all c?
$endgroup$
– jochen
Sep 3 '16 at 13:32
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
NOTE: This is totally wrong - see comments.
Let $E(t)$ be the one-way random walk that adds one to its current state with probability $epsilon$ and remains in its current state with probability $1-epsilon$. Is it not true that $Y(t) = X(t) + E(t)$ exactly? - that is, the distributions of the random variables $Y(t)$ and $X(t) + E(t)$ are exactly the same?
Assuming I'm right that they are the same, then a concentration result for $Y$ follows from the hypothesized concentration result for $X$ and the standard concentration that can be calculated for $E(t)$: if $Y(t) - (frac13+epsilon)t$ exceeds $csqrt t$, then one of $X(t) - frac13t$ or $E(t) - epsilon t$ must exceed $frac c2sqrt t$.
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
$endgroup$
$begingroup$
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right.
$endgroup$
– yves
Feb 23 '13 at 2:06
$begingroup$
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property.
$endgroup$
– Greg Martin
Feb 23 '13 at 4:47
add a comment |
$begingroup$
Write $Z(t) = Y(t) - X(t)$. Then
[
Y(t)-(1/3 + 2epsilon)t = Big(X(t) - (1/3)tBig) + Big(E[Z(t)]-2epsilon tBig) + Big(Z(t) - E[Z(t)]Big).
]
The concentration of the first term is given by your assumption.
For the third term, $Z(t)$ is the sum of $t$ iid bounded random variables,
so $P(|Z(t) -E[Z(t)] | ge x sqrt{t} ) le 2 e^{-C x^2}$ for some constant $C>0$ by Hoeffding's inequality; this takes care of the third term above.
For the middle term, $E[Z(t)]-2epsilon t=0$ by noticing that $Z(t)-2epsilon t$ is a Martingale with zero mean at time 0.
By the union bound, with probability at least $1-2e^{-C x^2} - e^{-c^2}$ we get
[
|Y(t)-(1/3 + 2epsilon)t| le (c+x)sqrt t.
]
answered Jan 26 at 21:03
jlewkjlewk
1115
$endgroup$
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%2f311591%2fwhat-happens-to-a-random-walk-when-we-increase-the-probabilities-of-going-right%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$
NOTE: This is totally wrong - see comments.
Let $E(t)$ be the one-way random walk that adds one to its current state with probability $epsilon$ and remains in its current state with probability $1-epsilon$. Is it not true that $Y(t) = X(t) + E(t)$ exactly? - that is, the distributions of the random variables $Y(t)$ and $X(t) + E(t)$ are exactly the same?
Assuming I'm right that they are the same, then a concentration result for $Y$ follows from the hypothesized concentration result for $X$ and the standard concentration that can be calculated for $E(t)$: if $Y(t) - (frac13+epsilon)t$ exceeds $csqrt t$, then one of $X(t) - frac13t$ or $E(t) - epsilon t$ must exceed $frac c2sqrt t$.
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
$endgroup$
$begingroup$
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right.
$endgroup$
– yves
Feb 23 '13 at 2:06
$begingroup$
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property.
$endgroup$
– Greg Martin
Feb 23 '13 at 4:47
add a comment |
$begingroup$
NOTE: This is totally wrong - see comments.
Let $E(t)$ be the one-way random walk that adds one to its current state with probability $epsilon$ and remains in its current state with probability $1-epsilon$. Is it not true that $Y(t) = X(t) + E(t)$ exactly? - that is, the distributions of the random variables $Y(t)$ and $X(t) + E(t)$ are exactly the same?
Assuming I'm right that they are the same, then a concentration result for $Y$ follows from the hypothesized concentration result for $X$ and the standard concentration that can be calculated for $E(t)$: if $Y(t) - (frac13+epsilon)t$ exceeds $csqrt t$, then one of $X(t) - frac13t$ or $E(t) - epsilon t$ must exceed $frac c2sqrt t$.
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
$endgroup$
$begingroup$
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right.
$endgroup$
– yves
Feb 23 '13 at 2:06
$begingroup$
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property.
$endgroup$
– Greg Martin
Feb 23 '13 at 4:47
add a comment |
$begingroup$
NOTE: This is totally wrong - see comments.
Let $E(t)$ be the one-way random walk that adds one to its current state with probability $epsilon$ and remains in its current state with probability $1-epsilon$. Is it not true that $Y(t) = X(t) + E(t)$ exactly? - that is, the distributions of the random variables $Y(t)$ and $X(t) + E(t)$ are exactly the same?
Assuming I'm right that they are the same, then a concentration result for $Y$ follows from the hypothesized concentration result for $X$ and the standard concentration that can be calculated for $E(t)$: if $Y(t) - (frac13+epsilon)t$ exceeds $csqrt t$, then one of $X(t) - frac13t$ or $E(t) - epsilon t$ must exceed $frac c2sqrt t$.
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
$endgroup$
NOTE: This is totally wrong - see comments.
Let $E(t)$ be the one-way random walk that adds one to its current state with probability $epsilon$ and remains in its current state with probability $1-epsilon$. Is it not true that $Y(t) = X(t) + E(t)$ exactly? - that is, the distributions of the random variables $Y(t)$ and $X(t) + E(t)$ are exactly the same?
Assuming I'm right that they are the same, then a concentration result for $Y$ follows from the hypothesized concentration result for $X$ and the standard concentration that can be calculated for $E(t)$: if $Y(t) - (frac13+epsilon)t$ exceeds $csqrt t$, then one of $X(t) - frac13t$ or $E(t) - epsilon t$ must exceed $frac c2sqrt t$.
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
edited Feb 23 '13 at 4:47
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
answered Feb 23 '13 at 2:01
Greg MartinGreg Martin
36.5k23565
36.5k23565
$begingroup$
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right.
$endgroup$
– yves
Feb 23 '13 at 2:06
$begingroup$
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property.
$endgroup$
– Greg Martin
Feb 23 '13 at 4:47
add a comment |
$begingroup$
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right.
$endgroup$
– yves
Feb 23 '13 at 2:06
$begingroup$
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property.
$endgroup$
– Greg Martin
Feb 23 '13 at 4:47
$begingroup$
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right.
$endgroup$
– yves
Feb 23 '13 at 2:06
$begingroup$
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right.
$endgroup$
– yves
Feb 23 '13 at 2:06
$begingroup$
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property.
$endgroup$
– Greg Martin
Feb 23 '13 at 4:47
$begingroup$
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property.
$endgroup$
– Greg Martin
Feb 23 '13 at 4:47
add a comment |
$begingroup$
Write $Z(t) = Y(t) - X(t)$. Then
[
Y(t)-(1/3 + 2epsilon)t = Big(X(t) - (1/3)tBig) + Big(E[Z(t)]-2epsilon tBig) + Big(Z(t) - E[Z(t)]Big).
]
The concentration of the first term is given by your assumption.
For the third term, $Z(t)$ is the sum of $t$ iid bounded random variables,
so $P(|Z(t) -E[Z(t)] | ge x sqrt{t} ) le 2 e^{-C x^2}$ for some constant $C>0$ by Hoeffding's inequality; this takes care of the third term above.
For the middle term, $E[Z(t)]-2epsilon t=0$ by noticing that $Z(t)-2epsilon t$ is a Martingale with zero mean at time 0.
By the union bound, with probability at least $1-2e^{-C x^2} - e^{-c^2}$ we get
[
|Y(t)-(1/3 + 2epsilon)t| le (c+x)sqrt t.
]
answered Jan 26 at 21:03
jlewkjlewk
1115
$endgroup$
add a comment |
$begingroup$
Write $Z(t) = Y(t) - X(t)$. Then
[
Y(t)-(1/3 + 2epsilon)t = Big(X(t) - (1/3)tBig) + Big(E[Z(t)]-2epsilon tBig) + Big(Z(t) - E[Z(t)]Big).
]
The concentration of the first term is given by your assumption.
For the third term, $Z(t)$ is the sum of $t$ iid bounded random variables,
so $P(|Z(t) -E[Z(t)] | ge x sqrt{t} ) le 2 e^{-C x^2}$ for some constant $C>0$ by Hoeffding's inequality; this takes care of the third term above.
For the middle term, $E[Z(t)]-2epsilon t=0$ by noticing that $Z(t)-2epsilon t$ is a Martingale with zero mean at time 0.
By the union bound, with probability at least $1-2e^{-C x^2} - e^{-c^2}$ we get
[
|Y(t)-(1/3 + 2epsilon)t| le (c+x)sqrt t.
]
answered Jan 26 at 21:03
jlewkjlewk
1115
$endgroup$
add a comment |
$begingroup$
Write $Z(t) = Y(t) - X(t)$. Then
[
Y(t)-(1/3 + 2epsilon)t = Big(X(t) - (1/3)tBig) + Big(E[Z(t)]-2epsilon tBig) + Big(Z(t) - E[Z(t)]Big).
]
The concentration of the first term is given by your assumption.
For the third term, $Z(t)$ is the sum of $t$ iid bounded random variables,
so $P(|Z(t) -E[Z(t)] | ge x sqrt{t} ) le 2 e^{-C x^2}$ for some constant $C>0$ by Hoeffding's inequality; this takes care of the third term above.
For the middle term, $E[Z(t)]-2epsilon t=0$ by noticing that $Z(t)-2epsilon t$ is a Martingale with zero mean at time 0.
By the union bound, with probability at least $1-2e^{-C x^2} - e^{-c^2}$ we get
[
|Y(t)-(1/3 + 2epsilon)t| le (c+x)sqrt t.
]
answered Jan 26 at 21:03
jlewkjlewk
1115
$endgroup$
Write $Z(t) = Y(t) - X(t)$. Then
[
Y(t)-(1/3 + 2epsilon)t = Big(X(t) - (1/3)tBig) + Big(E[Z(t)]-2epsilon tBig) + Big(Z(t) - E[Z(t)]Big).
]
The concentration of the first term is given by your assumption.
For the third term, $Z(t)$ is the sum of $t$ iid bounded random variables,
so $P(|Z(t) -E[Z(t)] | ge x sqrt{t} ) le 2 e^{-C x^2}$ for some constant $C>0$ by Hoeffding's inequality; this takes care of the third term above.
For the middle term, $E[Z(t)]-2epsilon t=0$ by noticing that $Z(t)-2epsilon t$ is a Martingale with zero mean at time 0.
By the union bound, with probability at least $1-2e^{-C x^2} - e^{-c^2}$ we get
[
|Y(t)-(1/3 + 2epsilon)t| le (c+x)sqrt t.
]
answered Jan 26 at 21:03
jlewkjlewk
1115
edited Feb 21 at 5:40
answered Jan 26 at 21:03
jlewkjlewk
1115
answered Jan 26 at 21:03
jlewkjlewk
1115
answered Jan 26 at 21:03
jlewkjlewk
1115
1115
add a comment |
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%2f311591%2fwhat-happens-to-a-random-walk-when-we-increase-the-probabilities-of-going-right%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
$begingroup$
What are the quantifiers on the concentration condition. Is it for one fixed t, but for all c?
$endgroup$
– jochen
Sep 3 '16 at 13:32