Mixing
Proving that the mean number of times that a vector with $n$ $0$'s and $n$ $1$'s changes value is $n$.
$begingroup$
Let $n$ be a positive integer and $Omega$ be the set of all $2n$-tuples of $n$ $0$'s and $n$ $1$'s. Clearly,
$$|Omega|=frac{(2n)!}{(n!)^2}.$$
For each $xinOmega$, let $f(x)$ be the number of times $x$ changes from $0$ to $1$ or from $1$ to $0$. For example:
$f(0,0,0,1,1,1)=1$,
$f(0,1,0,1,1,0)=4$,
$f(0,1,0,1,0,1)=5$,
$f(0,0,1,1,0,1)=3$.
I want to find the mean of $f(x)$. That is,
$$m(n):=frac{1}{|Omega|}sum_{xinOmega}f(x).$$
After calculating $m(n)$ for $n=1,2,3$, I think it may be true that $m(n)=n$. However I don't know if it is true.
I had a couple of ideas which didn't solved the problem but may help someone here.
Since $x_i$ is different to $x_{i+1}$ if and only if $(x_i+x_{i+1}) bmod{2}=1$,
$$f(x)=sum_{i=1}^{2n-1}(x_i+x_{i+1}) bmod{2}.$$
I would apreciate any help.
combinatorics elementary-number-theory
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
$endgroup$
|
show 4 more comments
$begingroup$
Let $n$ be a positive integer and $Omega$ be the set of all $2n$-tuples of $n$ $0$'s and $n$ $1$'s. Clearly,
$$|Omega|=frac{(2n)!}{(n!)^2}.$$
For each $xinOmega$, let $f(x)$ be the number of times $x$ changes from $0$ to $1$ or from $1$ to $0$. For example:
$f(0,0,0,1,1,1)=1$,
$f(0,1,0,1,1,0)=4$,
$f(0,1,0,1,0,1)=5$,
$f(0,0,1,1,0,1)=3$.
I want to find the mean of $f(x)$. That is,
$$m(n):=frac{1}{|Omega|}sum_{xinOmega}f(x).$$
After calculating $m(n)$ for $n=1,2,3$, I think it may be true that $m(n)=n$. However I don't know if it is true.
I had a couple of ideas which didn't solved the problem but may help someone here.
Since $x_i$ is different to $x_{i+1}$ if and only if $(x_i+x_{i+1}) bmod{2}=1$,
$$f(x)=sum_{i=1}^{2n-1}(x_i+x_{i+1}) bmod{2}.$$
I would apreciate any help.
combinatorics elementary-number-theory
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
$endgroup$
$begingroup$
Have you tried counting the number of permutations with 1 change, 2 changes, 3 changes, etc?
$endgroup$
– stuart stevenson
Jan 31 at 22:52
$begingroup$
Your examples don't make sense. Firstly, do you really mean "let $f(x)$ be the number of times x changes from $0$ to $1$"? Or should it be "let $f(x)$ be the number of times x changes from $0$ to $1$ or from $1$ to $0$"? Secondly, $f(0,1,0,1,1,0)$ can't be $3$ under either interpretation.
$endgroup$
– TonyK
Jan 31 at 22:52
$begingroup$
@TonyK I fixed it.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:55
$begingroup$
If $n=1$, we have $Omega={(0,1),(1,0)}$. Then $f(0,1)=f(1,0)=1$ and the mean really is $1$.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:57
1
$begingroup$
Hint: compute the probability that $f$ changes in a given position, and use linearity of expected value.
$endgroup$
– Robert Israel
Jan 31 at 23:20
|
show 4 more comments
$begingroup$
Let $n$ be a positive integer and $Omega$ be the set of all $2n$-tuples of $n$ $0$'s and $n$ $1$'s. Clearly,
$$|Omega|=frac{(2n)!}{(n!)^2}.$$
For each $xinOmega$, let $f(x)$ be the number of times $x$ changes from $0$ to $1$ or from $1$ to $0$. For example:
$f(0,0,0,1,1,1)=1$,
$f(0,1,0,1,1,0)=4$,
$f(0,1,0,1,0,1)=5$,
$f(0,0,1,1,0,1)=3$.
I want to find the mean of $f(x)$. That is,
$$m(n):=frac{1}{|Omega|}sum_{xinOmega}f(x).$$
After calculating $m(n)$ for $n=1,2,3$, I think it may be true that $m(n)=n$. However I don't know if it is true.
I had a couple of ideas which didn't solved the problem but may help someone here.
Since $x_i$ is different to $x_{i+1}$ if and only if $(x_i+x_{i+1}) bmod{2}=1$,
$$f(x)=sum_{i=1}^{2n-1}(x_i+x_{i+1}) bmod{2}.$$
I would apreciate any help.
combinatorics elementary-number-theory
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
$endgroup$
Let $n$ be a positive integer and $Omega$ be the set of all $2n$-tuples of $n$ $0$'s and $n$ $1$'s. Clearly,
$$|Omega|=frac{(2n)!}{(n!)^2}.$$
For each $xinOmega$, let $f(x)$ be the number of times $x$ changes from $0$ to $1$ or from $1$ to $0$. For example:
$f(0,0,0,1,1,1)=1$,
$f(0,1,0,1,1,0)=4$,
$f(0,1,0,1,0,1)=5$,
$f(0,0,1,1,0,1)=3$.
I want to find the mean of $f(x)$. That is,
$$m(n):=frac{1}{|Omega|}sum_{xinOmega}f(x).$$
After calculating $m(n)$ for $n=1,2,3$, I think it may be true that $m(n)=n$. However I don't know if it is true.
I had a couple of ideas which didn't solved the problem but may help someone here.
Since $x_i$ is different to $x_{i+1}$ if and only if $(x_i+x_{i+1}) bmod{2}=1$,
$$f(x)=sum_{i=1}^{2n-1}(x_i+x_{i+1}) bmod{2}.$$
I would apreciate any help.
combinatorics elementary-number-theory
combinatorics elementary-number-theory
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
edited Jan 31 at 23:01
Gabriel Ribeiro
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
asked Jan 31 at 22:42
Gabriel RibeiroGabriel Ribeiro
1,518623
1,518623
$begingroup$
Have you tried counting the number of permutations with 1 change, 2 changes, 3 changes, etc?
$endgroup$
– stuart stevenson
Jan 31 at 22:52
$begingroup$
Your examples don't make sense. Firstly, do you really mean "let $f(x)$ be the number of times x changes from $0$ to $1$"? Or should it be "let $f(x)$ be the number of times x changes from $0$ to $1$ or from $1$ to $0$"? Secondly, $f(0,1,0,1,1,0)$ can't be $3$ under either interpretation.
$endgroup$
– TonyK
Jan 31 at 22:52
$begingroup$
@TonyK I fixed it.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:55
$begingroup$
If $n=1$, we have $Omega={(0,1),(1,0)}$. Then $f(0,1)=f(1,0)=1$ and the mean really is $1$.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:57
1
$begingroup$
Hint: compute the probability that $f$ changes in a given position, and use linearity of expected value.
$endgroup$
– Robert Israel
Jan 31 at 23:20
|
show 4 more comments
$begingroup$
Have you tried counting the number of permutations with 1 change, 2 changes, 3 changes, etc?
$endgroup$
– stuart stevenson
Jan 31 at 22:52
$begingroup$
Your examples don't make sense. Firstly, do you really mean "let $f(x)$ be the number of times x changes from $0$ to $1$"? Or should it be "let $f(x)$ be the number of times x changes from $0$ to $1$ or from $1$ to $0$"? Secondly, $f(0,1,0,1,1,0)$ can't be $3$ under either interpretation.
$endgroup$
– TonyK
Jan 31 at 22:52
$begingroup$
@TonyK I fixed it.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:55
$begingroup$
If $n=1$, we have $Omega={(0,1),(1,0)}$. Then $f(0,1)=f(1,0)=1$ and the mean really is $1$.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:57
1
$begingroup$
Hint: compute the probability that $f$ changes in a given position, and use linearity of expected value.
$endgroup$
– Robert Israel
Jan 31 at 23:20
$begingroup$
Have you tried counting the number of permutations with 1 change, 2 changes, 3 changes, etc?
$endgroup$
– stuart stevenson
Jan 31 at 22:52
$begingroup$
Have you tried counting the number of permutations with 1 change, 2 changes, 3 changes, etc?
$endgroup$
– stuart stevenson
Jan 31 at 22:52
$begingroup$
Your examples don't make sense. Firstly, do you really mean "let $f(x)$ be the number of times x changes from $0$ to $1$"? Or should it be "let $f(x)$ be the number of times x changes from $0$ to $1$ or from $1$ to $0$"? Secondly, $f(0,1,0,1,1,0)$ can't be $3$ under either interpretation.
$endgroup$
– TonyK
Jan 31 at 22:52
$begingroup$
Your examples don't make sense. Firstly, do you really mean "let $f(x)$ be the number of times x changes from $0$ to $1$"? Or should it be "let $f(x)$ be the number of times x changes from $0$ to $1$ or from $1$ to $0$"? Secondly, $f(0,1,0,1,1,0)$ can't be $3$ under either interpretation.
$endgroup$
– TonyK
Jan 31 at 22:52
$begingroup$
@TonyK I fixed it.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:55
$begingroup$
@TonyK I fixed it.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:55
$begingroup$
If $n=1$, we have $Omega={(0,1),(1,0)}$. Then $f(0,1)=f(1,0)=1$ and the mean really is $1$.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:57
$begingroup$
If $n=1$, we have $Omega={(0,1),(1,0)}$. Then $f(0,1)=f(1,0)=1$ and the mean really is $1$.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:57
1
1
$begingroup$
Hint: compute the probability that $f$ changes in a given position, and use linearity of expected value.
$endgroup$
– Robert Israel
Jan 31 at 23:20
$begingroup$
Hint: compute the probability that $f$ changes in a given position, and use linearity of expected value.
$endgroup$
– Robert Israel
Jan 31 at 23:20
|
show 4 more comments
2 Answers
2
active
oldest
votes
$begingroup$
For now, think of each $0$ and $1$ as being distinct. For each symbol $x$, there are $2n$ equally likely possibilities:
$x$ occurs at the right end of the string.
$x$ occurs just to the left of one of the $n-1$ other same symbols.
$x$ occurs just to the left of one of the $n$ other opposite symbols.
This means that with probability $frac{n}{2n}=frac12$, $x$ will be the left symbol in a pair of opposite symbols. Since there are $2n$ symbols, and each has a probability of $frac12$ of being the left element of an opposite pair, the expected number of opposing pairs is $2ncdot frac12=n$.
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
$endgroup$
add a comment |
$begingroup$
We can use the linearity of expectation. There are $2n-1$ spaces between the bits. The chance that a given space is between two different bits is $frac n{2n-1}$ because whatever bit is to the left, there are $n$ opposite bits and $n-1$ similar bits for the right. We therefore expect $(2n-1)cdot frac n{2n-1}=n$ transitions.
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
I like your answer better.
$endgroup$
– Mike Earnest
Feb 1 at 18:17
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%2f3095595%2fproving-that-the-mean-number-of-times-that-a-vector-with-n-0s-and-n-1s%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$
For now, think of each $0$ and $1$ as being distinct. For each symbol $x$, there are $2n$ equally likely possibilities:
$x$ occurs at the right end of the string.
$x$ occurs just to the left of one of the $n-1$ other same symbols.
$x$ occurs just to the left of one of the $n$ other opposite symbols.
This means that with probability $frac{n}{2n}=frac12$, $x$ will be the left symbol in a pair of opposite symbols. Since there are $2n$ symbols, and each has a probability of $frac12$ of being the left element of an opposite pair, the expected number of opposing pairs is $2ncdot frac12=n$.
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
$endgroup$
add a comment |
$begingroup$
For now, think of each $0$ and $1$ as being distinct. For each symbol $x$, there are $2n$ equally likely possibilities:
$x$ occurs at the right end of the string.
$x$ occurs just to the left of one of the $n-1$ other same symbols.
$x$ occurs just to the left of one of the $n$ other opposite symbols.
This means that with probability $frac{n}{2n}=frac12$, $x$ will be the left symbol in a pair of opposite symbols. Since there are $2n$ symbols, and each has a probability of $frac12$ of being the left element of an opposite pair, the expected number of opposing pairs is $2ncdot frac12=n$.
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
$endgroup$
add a comment |
$begingroup$
For now, think of each $0$ and $1$ as being distinct. For each symbol $x$, there are $2n$ equally likely possibilities:
$x$ occurs at the right end of the string.
$x$ occurs just to the left of one of the $n-1$ other same symbols.
$x$ occurs just to the left of one of the $n$ other opposite symbols.
This means that with probability $frac{n}{2n}=frac12$, $x$ will be the left symbol in a pair of opposite symbols. Since there are $2n$ symbols, and each has a probability of $frac12$ of being the left element of an opposite pair, the expected number of opposing pairs is $2ncdot frac12=n$.
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
$endgroup$
For now, think of each $0$ and $1$ as being distinct. For each symbol $x$, there are $2n$ equally likely possibilities:
$x$ occurs at the right end of the string.
$x$ occurs just to the left of one of the $n-1$ other same symbols.
$x$ occurs just to the left of one of the $n$ other opposite symbols.
This means that with probability $frac{n}{2n}=frac12$, $x$ will be the left symbol in a pair of opposite symbols. Since there are $2n$ symbols, and each has a probability of $frac12$ of being the left element of an opposite pair, the expected number of opposing pairs is $2ncdot frac12=n$.
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
answered Jan 31 at 23:40
Mike EarnestMike Earnest
27.4k22152
27.4k22152
add a comment |
add a comment |
$begingroup$
We can use the linearity of expectation. There are $2n-1$ spaces between the bits. The chance that a given space is between two different bits is $frac n{2n-1}$ because whatever bit is to the left, there are $n$ opposite bits and $n-1$ similar bits for the right. We therefore expect $(2n-1)cdot frac n{2n-1}=n$ transitions.
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
I like your answer better.
$endgroup$
– Mike Earnest
Feb 1 at 18:17
add a comment |
$begingroup$
We can use the linearity of expectation. There are $2n-1$ spaces between the bits. The chance that a given space is between two different bits is $frac n{2n-1}$ because whatever bit is to the left, there are $n$ opposite bits and $n-1$ similar bits for the right. We therefore expect $(2n-1)cdot frac n{2n-1}=n$ transitions.
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
I like your answer better.
$endgroup$
– Mike Earnest
Feb 1 at 18:17
add a comment |
$begingroup$
We can use the linearity of expectation. There are $2n-1$ spaces between the bits. The chance that a given space is between two different bits is $frac n{2n-1}$ because whatever bit is to the left, there are $n$ opposite bits and $n-1$ similar bits for the right. We therefore expect $(2n-1)cdot frac n{2n-1}=n$ transitions.
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
$endgroup$
We can use the linearity of expectation. There are $2n-1$ spaces between the bits. The chance that a given space is between two different bits is $frac n{2n-1}$ because whatever bit is to the left, there are $n$ opposite bits and $n-1$ similar bits for the right. We therefore expect $(2n-1)cdot frac n{2n-1}=n$ transitions.
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
answered Feb 1 at 0:39
Ross MillikanRoss Millikan
301k24200375
301k24200375
$begingroup$
I like your answer better.
$endgroup$
– Mike Earnest
Feb 1 at 18:17
add a comment |
$begingroup$
I like your answer better.
$endgroup$
– Mike Earnest
Feb 1 at 18:17
$begingroup$
I like your answer better.
$endgroup$
– Mike Earnest
Feb 1 at 18:17
$begingroup$
I like your answer better.
$endgroup$
– Mike Earnest
Feb 1 at 18:17
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%2f3095595%2fproving-that-the-mean-number-of-times-that-a-vector-with-n-0s-and-n-1s%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$
Have you tried counting the number of permutations with 1 change, 2 changes, 3 changes, etc?
$endgroup$
– stuart stevenson
Jan 31 at 22:52
$begingroup$
Your examples don't make sense. Firstly, do you really mean "let $f(x)$ be the number of times x changes from $0$ to $1$"? Or should it be "let $f(x)$ be the number of times x changes from $0$ to $1$ or from $1$ to $0$"? Secondly, $f(0,1,0,1,1,0)$ can't be $3$ under either interpretation.
$endgroup$
– TonyK
Jan 31 at 22:52
$begingroup$
@TonyK I fixed it.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:55
$begingroup$
If $n=1$, we have $Omega={(0,1),(1,0)}$. Then $f(0,1)=f(1,0)=1$ and the mean really is $1$.
$endgroup$
– Gabriel Ribeiro
Jan 31 at 22:57
1
$begingroup$
Hint: compute the probability that $f$ changes in a given position, and use linearity of expected value.
$endgroup$
– Robert Israel
Jan 31 at 23:20