What numbers can simulate 1/2? The Next CEO of Stack OverflowHistory of Irrationality resultsCoefficients in the periodic part of continued fractions for real quadratic algebraic numbersDiophantine approximations of ratios of transcendental numbersBounds for number of coin toss switchesStochastically flipping coins until we see a certain number of heads in two possible durations of timeWhich distributions can you sample if you can sample a Gaussian?Conjecture on irrational algebraic numbersOn Bailey–Borwein–Plouffe formula for irrational numbersExamples of Sets with Positive Upper Densitysimulate coin tossing by die tossing
What numbers can simulate 1/2?
The Next CEO of Stack OverflowHistory of Irrationality resultsCoefficients in the periodic part of continued fractions for real quadratic algebraic numbersDiophantine approximations of ratios of transcendental numbersBounds for number of coin toss switchesStochastically flipping coins until we see a certain number of heads in two possible durations of timeWhich distributions can you sample if you can sample a Gaussian?Conjecture on irrational algebraic numbersOn Bailey–Borwein–Plouffe formula for irrational numbersExamples of Sets with Positive Upper Densitysimulate coin tossing by die tossing
$begingroup$
Given two numbers $p,qin(0,1)$, we say that $p$ can simulate $q$ if, given a biased coin with probability $p$, we can toss it a bounded number of times and use the results to simuate a biased coin with probability $q$.
In this math.SE question the following results were proved:
- No rational number except $1/2$ can simulate $1/2$;
- Some irrational numbers can simulate $1/2$, for example: $1/2 pm 1/sqrt12$, or $1/2^1/n$ for any integer $n$.
Q1. What is the set of all numbers $pin (0,1)$ which can simulate $1/2$?
Q2. What is the set of all numbers $pin (0,1)$ which can simulate $1/3$?
nt.number-theory pr.probability algebraic-number-theory
edited 2 days ago
user44191
3,01811532
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
$endgroup$
|
show 1 more comment
$begingroup$
Given two numbers $p,qin(0,1)$, we say that $p$ can simulate $q$ if, given a biased coin with probability $p$, we can toss it a bounded number of times and use the results to simuate a biased coin with probability $q$.
In this math.SE question the following results were proved:
- No rational number except $1/2$ can simulate $1/2$;
- Some irrational numbers can simulate $1/2$, for example: $1/2 pm 1/sqrt12$, or $1/2^1/n$ for any integer $n$.
Q1. What is the set of all numbers $pin (0,1)$ which can simulate $1/2$?
Q2. What is the set of all numbers $pin (0,1)$ which can simulate $1/3$?
nt.number-theory pr.probability algebraic-number-theory
edited 2 days ago
user44191
3,01811532
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
$endgroup$
2
$begingroup$
There's the trivial: such $p$ must be algebraic (as "simulating $frac12$" is given by a polynomial equation).
$endgroup$
– user44191
2 days ago
$begingroup$
To extend some of the arguments from the linked math.SE problem: no matter how the coin "simulates" $frac12$, you always get that $frac12 = p P(p) = (1 - p) Q(1 - p)$ for some polynomials $P, Q$ (although the method of simulation - specifically, whether the "all heads" and "all tails" are counted together - does affect how $P, Q$ are related). Correspondingly, I'd expect some statement about valuations of $p$ and $1 - p$ to be helpful (though I don't have enough experience myself to figure out the appropriate statement).
$endgroup$
– user44191
2 days ago
1
$begingroup$
Another question: which rational numbers $q$ can be simulated by a rational number other than $q$ and $1-q$?
$endgroup$
– Brendan McKay
2 days ago
$begingroup$
Perhaps of interest: $2/5$ can not simulate $1/5$. Proof: If it did, we would have $a_0 2^0 3^n + cdot + a_n 2^n 3^0 = 5^n-1$ with $a_n=0$ or $a_n=1$, which is impossible mod $3$.
$endgroup$
– Matt F.
yesterday
$begingroup$
@MattF. That can be covered by a generalization of the argument I discussed above: if $p$ can simulate $q$, then for any nonarchimedean additive valuation $| |$ such that $|p| > 0$, either $|q| > 0$ or $|1 - q| > 0$, and the choice of $q$ or $1 - q$ must be the same for all such valuations (slightly stronger, $|q| geq |p|$ or $|1 - q| geq |p|$).
$endgroup$
– user44191
yesterday
|
show 1 more comment
$begingroup$
Given two numbers $p,qin(0,1)$, we say that $p$ can simulate $q$ if, given a biased coin with probability $p$, we can toss it a bounded number of times and use the results to simuate a biased coin with probability $q$.
In this math.SE question the following results were proved:
- No rational number except $1/2$ can simulate $1/2$;
- Some irrational numbers can simulate $1/2$, for example: $1/2 pm 1/sqrt12$, or $1/2^1/n$ for any integer $n$.
Q1. What is the set of all numbers $pin (0,1)$ which can simulate $1/2$?
Q2. What is the set of all numbers $pin (0,1)$ which can simulate $1/3$?
nt.number-theory pr.probability algebraic-number-theory
edited 2 days ago
user44191
3,01811532
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
$endgroup$
Given two numbers $p,qin(0,1)$, we say that $p$ can simulate $q$ if, given a biased coin with probability $p$, we can toss it a bounded number of times and use the results to simuate a biased coin with probability $q$.
In this math.SE question the following results were proved:
- No rational number except $1/2$ can simulate $1/2$;
- Some irrational numbers can simulate $1/2$, for example: $1/2 pm 1/sqrt12$, or $1/2^1/n$ for any integer $n$.
Q1. What is the set of all numbers $pin (0,1)$ which can simulate $1/2$?
Q2. What is the set of all numbers $pin (0,1)$ which can simulate $1/3$?
nt.number-theory pr.probability algebraic-number-theory
nt.number-theory pr.probability algebraic-number-theory
edited 2 days ago
user44191
3,01811532
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
edited 2 days ago
user44191
3,01811532
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
edited 2 days ago
user44191
3,01811532
edited 2 days ago
user44191
3,01811532
edited 2 days ago
user44191
3,01811532
3,01811532
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
asked 2 days ago
Erel Segal-HaleviErel Segal-Halevi
1,456927
1,456927
2
$begingroup$
There's the trivial: such $p$ must be algebraic (as "simulating $frac12$" is given by a polynomial equation).
$endgroup$
– user44191
2 days ago
$begingroup$
To extend some of the arguments from the linked math.SE problem: no matter how the coin "simulates" $frac12$, you always get that $frac12 = p P(p) = (1 - p) Q(1 - p)$ for some polynomials $P, Q$ (although the method of simulation - specifically, whether the "all heads" and "all tails" are counted together - does affect how $P, Q$ are related). Correspondingly, I'd expect some statement about valuations of $p$ and $1 - p$ to be helpful (though I don't have enough experience myself to figure out the appropriate statement).
$endgroup$
– user44191
2 days ago
1
$begingroup$
Another question: which rational numbers $q$ can be simulated by a rational number other than $q$ and $1-q$?
$endgroup$
– Brendan McKay
2 days ago
$begingroup$
Perhaps of interest: $2/5$ can not simulate $1/5$. Proof: If it did, we would have $a_0 2^0 3^n + cdot + a_n 2^n 3^0 = 5^n-1$ with $a_n=0$ or $a_n=1$, which is impossible mod $3$.
$endgroup$
– Matt F.
yesterday
$begingroup$
@MattF. That can be covered by a generalization of the argument I discussed above: if $p$ can simulate $q$, then for any nonarchimedean additive valuation $| |$ such that $|p| > 0$, either $|q| > 0$ or $|1 - q| > 0$, and the choice of $q$ or $1 - q$ must be the same for all such valuations (slightly stronger, $|q| geq |p|$ or $|1 - q| geq |p|$).
$endgroup$
– user44191
yesterday
|
show 1 more comment
2
$begingroup$
There's the trivial: such $p$ must be algebraic (as "simulating $frac12$" is given by a polynomial equation).
$endgroup$
– user44191
2 days ago
$begingroup$
To extend some of the arguments from the linked math.SE problem: no matter how the coin "simulates" $frac12$, you always get that $frac12 = p P(p) = (1 - p) Q(1 - p)$ for some polynomials $P, Q$ (although the method of simulation - specifically, whether the "all heads" and "all tails" are counted together - does affect how $P, Q$ are related). Correspondingly, I'd expect some statement about valuations of $p$ and $1 - p$ to be helpful (though I don't have enough experience myself to figure out the appropriate statement).
$endgroup$
– user44191
2 days ago
1
$begingroup$
Another question: which rational numbers $q$ can be simulated by a rational number other than $q$ and $1-q$?
$endgroup$
– Brendan McKay
2 days ago
$begingroup$
Perhaps of interest: $2/5$ can not simulate $1/5$. Proof: If it did, we would have $a_0 2^0 3^n + cdot + a_n 2^n 3^0 = 5^n-1$ with $a_n=0$ or $a_n=1$, which is impossible mod $3$.
$endgroup$
– Matt F.
yesterday
$begingroup$
@MattF. That can be covered by a generalization of the argument I discussed above: if $p$ can simulate $q$, then for any nonarchimedean additive valuation $| |$ such that $|p| > 0$, either $|q| > 0$ or $|1 - q| > 0$, and the choice of $q$ or $1 - q$ must be the same for all such valuations (slightly stronger, $|q| geq |p|$ or $|1 - q| geq |p|$).
$endgroup$
– user44191
yesterday
2
2
$begingroup$
There's the trivial: such $p$ must be algebraic (as "simulating $frac12$" is given by a polynomial equation).
$endgroup$
– user44191
2 days ago
$begingroup$
There's the trivial: such $p$ must be algebraic (as "simulating $frac12$" is given by a polynomial equation).
$endgroup$
– user44191
2 days ago
$begingroup$
To extend some of the arguments from the linked math.SE problem: no matter how the coin "simulates" $frac12$, you always get that $frac12 = p P(p) = (1 - p) Q(1 - p)$ for some polynomials $P, Q$ (although the method of simulation - specifically, whether the "all heads" and "all tails" are counted together - does affect how $P, Q$ are related). Correspondingly, I'd expect some statement about valuations of $p$ and $1 - p$ to be helpful (though I don't have enough experience myself to figure out the appropriate statement).
$endgroup$
– user44191
2 days ago
$begingroup$
To extend some of the arguments from the linked math.SE problem: no matter how the coin "simulates" $frac12$, you always get that $frac12 = p P(p) = (1 - p) Q(1 - p)$ for some polynomials $P, Q$ (although the method of simulation - specifically, whether the "all heads" and "all tails" are counted together - does affect how $P, Q$ are related). Correspondingly, I'd expect some statement about valuations of $p$ and $1 - p$ to be helpful (though I don't have enough experience myself to figure out the appropriate statement).
$endgroup$
– user44191
2 days ago
1
1
$begingroup$
Another question: which rational numbers $q$ can be simulated by a rational number other than $q$ and $1-q$?
$endgroup$
– Brendan McKay
2 days ago
$begingroup$
Another question: which rational numbers $q$ can be simulated by a rational number other than $q$ and $1-q$?
$endgroup$
– Brendan McKay
2 days ago
$begingroup$
Perhaps of interest: $2/5$ can not simulate $1/5$. Proof: If it did, we would have $a_0 2^0 3^n + cdot + a_n 2^n 3^0 = 5^n-1$ with $a_n=0$ or $a_n=1$, which is impossible mod $3$.
$endgroup$
– Matt F.
yesterday
$begingroup$
Perhaps of interest: $2/5$ can not simulate $1/5$. Proof: If it did, we would have $a_0 2^0 3^n + cdot + a_n 2^n 3^0 = 5^n-1$ with $a_n=0$ or $a_n=1$, which is impossible mod $3$.
$endgroup$
– Matt F.
yesterday
$begingroup$
@MattF. That can be covered by a generalization of the argument I discussed above: if $p$ can simulate $q$, then for any nonarchimedean additive valuation $| |$ such that $|p| > 0$, either $|q| > 0$ or $|1 - q| > 0$, and the choice of $q$ or $1 - q$ must be the same for all such valuations (slightly stronger, $|q| geq |p|$ or $|1 - q| geq |p|$).
$endgroup$
– user44191
yesterday
$begingroup$
@MattF. That can be covered by a generalization of the argument I discussed above: if $p$ can simulate $q$, then for any nonarchimedean additive valuation $| |$ such that $|p| > 0$, either $|q| > 0$ or $|1 - q| > 0$, and the choice of $q$ or $1 - q$ must be the same for all such valuations (slightly stronger, $|q| geq |p|$ or $|1 - q| geq |p|$).
$endgroup$
– user44191
yesterday
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
Depends on what kind of "description" you want, but consider the question of the probabilities $p$ that can simulate $1/2$ with exactly $n$ flips. The events you have are:
- One event with probability $p^n$
$n$ events with probability $p^n-1(1-p)$
$binomn2$ events with probability $p^n-2(1-p)^2$- ...
- One event with probability $(1-p)^n$
So if you pick any integers $a_0, a_1, ldots a_n$ with $0 leq a_i leq binomni$ then you get a polynomial that $p$ has to satisfy. Of course such a polynomial may or may not have a root on $(0, 1)$, but we can at least enumerate the solutions in this manner.
Clearly transcendental values for $p$ are right out. Moreover we have an explicit description of what the minimal polynomial of a solution has to look like, and any number $p in (0, 1)$ satisfying such a polynomial is indeed a solution.
In some sense that could be considered a complete answer, although maybe we want to know which potential minimal polynomials correspond to actual solutions.
Notice that if we have two symmetries here. First, a biased coin that comes up heads with probability $p$ is just as good as a biased coin that comes up heads with probability $1 - p$; we can just relabel "heads" and "tails" on the coin. Second, a scheme that assigns a set of outcomes to "heads" and the complement to "tails" is just as good as the scheme making the opposite assignment. In terms of the choices of $a_i$ this amounts to (1) replacing $a_i$ with $binomni - a_i$ or (2) replacing $a_i$ with $a_n-i$.
We can also rule out any case where swapping the roles of $p$ and $1-p$ results in larger coefficients across the board. For instance, if we have $n = 2$ then clearly we can't have $HT$ having an equal probability to $HH, TH, TT$ since $p(HT) = p(TH)$.
Let's do the first few values of $n$. For $n = 0$ there are of course no solutions and for $n = 1$ there is only the solution $p = 1/2$. For $n = 2$ there are the solutions $p = sqrt2/2$ as well as $p = 1/2$ again.
Okay, now let's try $n = 3$. If I've enumerated right, the possible equivalence classes are:
- (1, 0, 0, 0); (0, 3, 3, 1); (0, 0, 0, 1); (1, 3, 3, 0)
- (0, 2, 0, 0); (1, 1, 3, 1); (0, 0, 2, 0); (1, 3, 1, 1)
- (1, 2, 0, 0); (0, 1, 3, 1); (0, 0, 1, 2); (1, 3, 1, 0)
- (0, 3, 0, 0); (1, 0, 3, 1); (0, 0, 3, 0); (1, 3, 0, 1)
- (1, 3, 0, 0); (0, 0, 3, 1)
- (1, 0, 1, 0); (0, 3, 2, 1); (0, 1, 0, 1); (1, 2, 3, 0)
- (1, 1, 1, 0); (0, 2, 2, 1); (0, 1, 1, 1); (1, 2, 2, 0)
- (0, 2, 1, 0); (1, 1, 2, 1); (0, 1, 2, 0); (1, 2, 1, 1)
- (1, 2, 1, 0); (0, 1, 2, 1);
- (0, 3, 1, 0); (1, 0, 2, 0); (0, 1, 3, 0); (0, 2, 0, 1)
- (1, 0, 2, 0); (0, 3, 1, 1); (0, 2, 0, 1); (1, 1, 3, 0)
- (1, 1, 2, 0); (0, 2, 1, 1)
- (0, 2, 2, 0); (1, 1, 1, 1)
- (0, 3, 2, 0); (1, 0, 1, 1); (0, 2, 3, 0); (1, 1, 0, 1)
- (1, 0, 3, 0); (0, 3, 0, 1)
Let's try one representative from each class.
$p^3 = 1/2$. This gives us the solution $p = sqrt[3]4/2$
$2p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 2p^2(1-p) = 1/2$. This polynomial has three real roots, one of which is a valid probability.
$3p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 3p^2(1-p) = 1/2$. This has the solution $p = 1/2$, and corresponds to taking whichever of heads or tails we got more of.
$p^3 + p(1-p)^2 = 1/2$. The real solution is a valid probability.
Okay, I lied, I'm not going to try every single case. But we did come up with a couple of new solutions we didn't previously know about.
There are some things we could systematically do here, like eliminating the cases that correspond to ignoring some number of the coin flips or employing Descartes's rule of signs to skip some cases where there are no real roots. I don't know if this would reach a bijective solution or not, but it's worth a try.
answered yesterday
Daniel McLauryDaniel McLaury
240217
$endgroup$
1
$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
yesterday
$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
1
$begingroup$
For your second-to-last representative, it corresponds to taking the majority answer from 3 coin flips, not the first flip (the first flip corresponds to the equation $p^3 + 2p^2(1 - p) + p(1 - p)^2 = frac12$).
$endgroup$
– user44191
yesterday
$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
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: "504"
;
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%2fmathoverflow.net%2fquestions%2f326806%2fwhat-numbers-can-simulate-1-2%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Depends on what kind of "description" you want, but consider the question of the probabilities $p$ that can simulate $1/2$ with exactly $n$ flips. The events you have are:
- One event with probability $p^n$
$n$ events with probability $p^n-1(1-p)$
$binomn2$ events with probability $p^n-2(1-p)^2$- ...
- One event with probability $(1-p)^n$
So if you pick any integers $a_0, a_1, ldots a_n$ with $0 leq a_i leq binomni$ then you get a polynomial that $p$ has to satisfy. Of course such a polynomial may or may not have a root on $(0, 1)$, but we can at least enumerate the solutions in this manner.
Clearly transcendental values for $p$ are right out. Moreover we have an explicit description of what the minimal polynomial of a solution has to look like, and any number $p in (0, 1)$ satisfying such a polynomial is indeed a solution.
In some sense that could be considered a complete answer, although maybe we want to know which potential minimal polynomials correspond to actual solutions.
Notice that if we have two symmetries here. First, a biased coin that comes up heads with probability $p$ is just as good as a biased coin that comes up heads with probability $1 - p$; we can just relabel "heads" and "tails" on the coin. Second, a scheme that assigns a set of outcomes to "heads" and the complement to "tails" is just as good as the scheme making the opposite assignment. In terms of the choices of $a_i$ this amounts to (1) replacing $a_i$ with $binomni - a_i$ or (2) replacing $a_i$ with $a_n-i$.
We can also rule out any case where swapping the roles of $p$ and $1-p$ results in larger coefficients across the board. For instance, if we have $n = 2$ then clearly we can't have $HT$ having an equal probability to $HH, TH, TT$ since $p(HT) = p(TH)$.
Let's do the first few values of $n$. For $n = 0$ there are of course no solutions and for $n = 1$ there is only the solution $p = 1/2$. For $n = 2$ there are the solutions $p = sqrt2/2$ as well as $p = 1/2$ again.
Okay, now let's try $n = 3$. If I've enumerated right, the possible equivalence classes are:
- (1, 0, 0, 0); (0, 3, 3, 1); (0, 0, 0, 1); (1, 3, 3, 0)
- (0, 2, 0, 0); (1, 1, 3, 1); (0, 0, 2, 0); (1, 3, 1, 1)
- (1, 2, 0, 0); (0, 1, 3, 1); (0, 0, 1, 2); (1, 3, 1, 0)
- (0, 3, 0, 0); (1, 0, 3, 1); (0, 0, 3, 0); (1, 3, 0, 1)
- (1, 3, 0, 0); (0, 0, 3, 1)
- (1, 0, 1, 0); (0, 3, 2, 1); (0, 1, 0, 1); (1, 2, 3, 0)
- (1, 1, 1, 0); (0, 2, 2, 1); (0, 1, 1, 1); (1, 2, 2, 0)
- (0, 2, 1, 0); (1, 1, 2, 1); (0, 1, 2, 0); (1, 2, 1, 1)
- (1, 2, 1, 0); (0, 1, 2, 1);
- (0, 3, 1, 0); (1, 0, 2, 0); (0, 1, 3, 0); (0, 2, 0, 1)
- (1, 0, 2, 0); (0, 3, 1, 1); (0, 2, 0, 1); (1, 1, 3, 0)
- (1, 1, 2, 0); (0, 2, 1, 1)
- (0, 2, 2, 0); (1, 1, 1, 1)
- (0, 3, 2, 0); (1, 0, 1, 1); (0, 2, 3, 0); (1, 1, 0, 1)
- (1, 0, 3, 0); (0, 3, 0, 1)
Let's try one representative from each class.
$p^3 = 1/2$. This gives us the solution $p = sqrt[3]4/2$
$2p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 2p^2(1-p) = 1/2$. This polynomial has three real roots, one of which is a valid probability.
$3p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 3p^2(1-p) = 1/2$. This has the solution $p = 1/2$, and corresponds to taking whichever of heads or tails we got more of.
$p^3 + p(1-p)^2 = 1/2$. The real solution is a valid probability.
Okay, I lied, I'm not going to try every single case. But we did come up with a couple of new solutions we didn't previously know about.
There are some things we could systematically do here, like eliminating the cases that correspond to ignoring some number of the coin flips or employing Descartes's rule of signs to skip some cases where there are no real roots. I don't know if this would reach a bijective solution or not, but it's worth a try.
answered yesterday
Daniel McLauryDaniel McLaury
240217
$endgroup$
1
$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
yesterday
$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
1
$begingroup$
For your second-to-last representative, it corresponds to taking the majority answer from 3 coin flips, not the first flip (the first flip corresponds to the equation $p^3 + 2p^2(1 - p) + p(1 - p)^2 = frac12$).
$endgroup$
– user44191
yesterday
$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
add a comment |
$begingroup$
Depends on what kind of "description" you want, but consider the question of the probabilities $p$ that can simulate $1/2$ with exactly $n$ flips. The events you have are:
- One event with probability $p^n$
$n$ events with probability $p^n-1(1-p)$
$binomn2$ events with probability $p^n-2(1-p)^2$- ...
- One event with probability $(1-p)^n$
So if you pick any integers $a_0, a_1, ldots a_n$ with $0 leq a_i leq binomni$ then you get a polynomial that $p$ has to satisfy. Of course such a polynomial may or may not have a root on $(0, 1)$, but we can at least enumerate the solutions in this manner.
Clearly transcendental values for $p$ are right out. Moreover we have an explicit description of what the minimal polynomial of a solution has to look like, and any number $p in (0, 1)$ satisfying such a polynomial is indeed a solution.
In some sense that could be considered a complete answer, although maybe we want to know which potential minimal polynomials correspond to actual solutions.
Notice that if we have two symmetries here. First, a biased coin that comes up heads with probability $p$ is just as good as a biased coin that comes up heads with probability $1 - p$; we can just relabel "heads" and "tails" on the coin. Second, a scheme that assigns a set of outcomes to "heads" and the complement to "tails" is just as good as the scheme making the opposite assignment. In terms of the choices of $a_i$ this amounts to (1) replacing $a_i$ with $binomni - a_i$ or (2) replacing $a_i$ with $a_n-i$.
We can also rule out any case where swapping the roles of $p$ and $1-p$ results in larger coefficients across the board. For instance, if we have $n = 2$ then clearly we can't have $HT$ having an equal probability to $HH, TH, TT$ since $p(HT) = p(TH)$.
Let's do the first few values of $n$. For $n = 0$ there are of course no solutions and for $n = 1$ there is only the solution $p = 1/2$. For $n = 2$ there are the solutions $p = sqrt2/2$ as well as $p = 1/2$ again.
Okay, now let's try $n = 3$. If I've enumerated right, the possible equivalence classes are:
- (1, 0, 0, 0); (0, 3, 3, 1); (0, 0, 0, 1); (1, 3, 3, 0)
- (0, 2, 0, 0); (1, 1, 3, 1); (0, 0, 2, 0); (1, 3, 1, 1)
- (1, 2, 0, 0); (0, 1, 3, 1); (0, 0, 1, 2); (1, 3, 1, 0)
- (0, 3, 0, 0); (1, 0, 3, 1); (0, 0, 3, 0); (1, 3, 0, 1)
- (1, 3, 0, 0); (0, 0, 3, 1)
- (1, 0, 1, 0); (0, 3, 2, 1); (0, 1, 0, 1); (1, 2, 3, 0)
- (1, 1, 1, 0); (0, 2, 2, 1); (0, 1, 1, 1); (1, 2, 2, 0)
- (0, 2, 1, 0); (1, 1, 2, 1); (0, 1, 2, 0); (1, 2, 1, 1)
- (1, 2, 1, 0); (0, 1, 2, 1);
- (0, 3, 1, 0); (1, 0, 2, 0); (0, 1, 3, 0); (0, 2, 0, 1)
- (1, 0, 2, 0); (0, 3, 1, 1); (0, 2, 0, 1); (1, 1, 3, 0)
- (1, 1, 2, 0); (0, 2, 1, 1)
- (0, 2, 2, 0); (1, 1, 1, 1)
- (0, 3, 2, 0); (1, 0, 1, 1); (0, 2, 3, 0); (1, 1, 0, 1)
- (1, 0, 3, 0); (0, 3, 0, 1)
Let's try one representative from each class.
$p^3 = 1/2$. This gives us the solution $p = sqrt[3]4/2$
$2p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 2p^2(1-p) = 1/2$. This polynomial has three real roots, one of which is a valid probability.
$3p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 3p^2(1-p) = 1/2$. This has the solution $p = 1/2$, and corresponds to taking whichever of heads or tails we got more of.
$p^3 + p(1-p)^2 = 1/2$. The real solution is a valid probability.
Okay, I lied, I'm not going to try every single case. But we did come up with a couple of new solutions we didn't previously know about.
There are some things we could systematically do here, like eliminating the cases that correspond to ignoring some number of the coin flips or employing Descartes's rule of signs to skip some cases where there are no real roots. I don't know if this would reach a bijective solution or not, but it's worth a try.
answered yesterday
Daniel McLauryDaniel McLaury
240217
$endgroup$
1
$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
yesterday
$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
1
$begingroup$
For your second-to-last representative, it corresponds to taking the majority answer from 3 coin flips, not the first flip (the first flip corresponds to the equation $p^3 + 2p^2(1 - p) + p(1 - p)^2 = frac12$).
$endgroup$
– user44191
yesterday
$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
add a comment |
$begingroup$
Depends on what kind of "description" you want, but consider the question of the probabilities $p$ that can simulate $1/2$ with exactly $n$ flips. The events you have are:
- One event with probability $p^n$
$n$ events with probability $p^n-1(1-p)$
$binomn2$ events with probability $p^n-2(1-p)^2$- ...
- One event with probability $(1-p)^n$
So if you pick any integers $a_0, a_1, ldots a_n$ with $0 leq a_i leq binomni$ then you get a polynomial that $p$ has to satisfy. Of course such a polynomial may or may not have a root on $(0, 1)$, but we can at least enumerate the solutions in this manner.
Clearly transcendental values for $p$ are right out. Moreover we have an explicit description of what the minimal polynomial of a solution has to look like, and any number $p in (0, 1)$ satisfying such a polynomial is indeed a solution.
In some sense that could be considered a complete answer, although maybe we want to know which potential minimal polynomials correspond to actual solutions.
Notice that if we have two symmetries here. First, a biased coin that comes up heads with probability $p$ is just as good as a biased coin that comes up heads with probability $1 - p$; we can just relabel "heads" and "tails" on the coin. Second, a scheme that assigns a set of outcomes to "heads" and the complement to "tails" is just as good as the scheme making the opposite assignment. In terms of the choices of $a_i$ this amounts to (1) replacing $a_i$ with $binomni - a_i$ or (2) replacing $a_i$ with $a_n-i$.
We can also rule out any case where swapping the roles of $p$ and $1-p$ results in larger coefficients across the board. For instance, if we have $n = 2$ then clearly we can't have $HT$ having an equal probability to $HH, TH, TT$ since $p(HT) = p(TH)$.
Let's do the first few values of $n$. For $n = 0$ there are of course no solutions and for $n = 1$ there is only the solution $p = 1/2$. For $n = 2$ there are the solutions $p = sqrt2/2$ as well as $p = 1/2$ again.
Okay, now let's try $n = 3$. If I've enumerated right, the possible equivalence classes are:
- (1, 0, 0, 0); (0, 3, 3, 1); (0, 0, 0, 1); (1, 3, 3, 0)
- (0, 2, 0, 0); (1, 1, 3, 1); (0, 0, 2, 0); (1, 3, 1, 1)
- (1, 2, 0, 0); (0, 1, 3, 1); (0, 0, 1, 2); (1, 3, 1, 0)
- (0, 3, 0, 0); (1, 0, 3, 1); (0, 0, 3, 0); (1, 3, 0, 1)
- (1, 3, 0, 0); (0, 0, 3, 1)
- (1, 0, 1, 0); (0, 3, 2, 1); (0, 1, 0, 1); (1, 2, 3, 0)
- (1, 1, 1, 0); (0, 2, 2, 1); (0, 1, 1, 1); (1, 2, 2, 0)
- (0, 2, 1, 0); (1, 1, 2, 1); (0, 1, 2, 0); (1, 2, 1, 1)
- (1, 2, 1, 0); (0, 1, 2, 1);
- (0, 3, 1, 0); (1, 0, 2, 0); (0, 1, 3, 0); (0, 2, 0, 1)
- (1, 0, 2, 0); (0, 3, 1, 1); (0, 2, 0, 1); (1, 1, 3, 0)
- (1, 1, 2, 0); (0, 2, 1, 1)
- (0, 2, 2, 0); (1, 1, 1, 1)
- (0, 3, 2, 0); (1, 0, 1, 1); (0, 2, 3, 0); (1, 1, 0, 1)
- (1, 0, 3, 0); (0, 3, 0, 1)
Let's try one representative from each class.
$p^3 = 1/2$. This gives us the solution $p = sqrt[3]4/2$
$2p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 2p^2(1-p) = 1/2$. This polynomial has three real roots, one of which is a valid probability.
$3p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 3p^2(1-p) = 1/2$. This has the solution $p = 1/2$, and corresponds to taking whichever of heads or tails we got more of.
$p^3 + p(1-p)^2 = 1/2$. The real solution is a valid probability.
Okay, I lied, I'm not going to try every single case. But we did come up with a couple of new solutions we didn't previously know about.
There are some things we could systematically do here, like eliminating the cases that correspond to ignoring some number of the coin flips or employing Descartes's rule of signs to skip some cases where there are no real roots. I don't know if this would reach a bijective solution or not, but it's worth a try.
answered yesterday
Daniel McLauryDaniel McLaury
240217
$endgroup$
Depends on what kind of "description" you want, but consider the question of the probabilities $p$ that can simulate $1/2$ with exactly $n$ flips. The events you have are:
- One event with probability $p^n$
$n$ events with probability $p^n-1(1-p)$
$binomn2$ events with probability $p^n-2(1-p)^2$- ...
- One event with probability $(1-p)^n$
So if you pick any integers $a_0, a_1, ldots a_n$ with $0 leq a_i leq binomni$ then you get a polynomial that $p$ has to satisfy. Of course such a polynomial may or may not have a root on $(0, 1)$, but we can at least enumerate the solutions in this manner.
Clearly transcendental values for $p$ are right out. Moreover we have an explicit description of what the minimal polynomial of a solution has to look like, and any number $p in (0, 1)$ satisfying such a polynomial is indeed a solution.
In some sense that could be considered a complete answer, although maybe we want to know which potential minimal polynomials correspond to actual solutions.
Notice that if we have two symmetries here. First, a biased coin that comes up heads with probability $p$ is just as good as a biased coin that comes up heads with probability $1 - p$; we can just relabel "heads" and "tails" on the coin. Second, a scheme that assigns a set of outcomes to "heads" and the complement to "tails" is just as good as the scheme making the opposite assignment. In terms of the choices of $a_i$ this amounts to (1) replacing $a_i$ with $binomni - a_i$ or (2) replacing $a_i$ with $a_n-i$.
We can also rule out any case where swapping the roles of $p$ and $1-p$ results in larger coefficients across the board. For instance, if we have $n = 2$ then clearly we can't have $HT$ having an equal probability to $HH, TH, TT$ since $p(HT) = p(TH)$.
Let's do the first few values of $n$. For $n = 0$ there are of course no solutions and for $n = 1$ there is only the solution $p = 1/2$. For $n = 2$ there are the solutions $p = sqrt2/2$ as well as $p = 1/2$ again.
Okay, now let's try $n = 3$. If I've enumerated right, the possible equivalence classes are:
- (1, 0, 0, 0); (0, 3, 3, 1); (0, 0, 0, 1); (1, 3, 3, 0)
- (0, 2, 0, 0); (1, 1, 3, 1); (0, 0, 2, 0); (1, 3, 1, 1)
- (1, 2, 0, 0); (0, 1, 3, 1); (0, 0, 1, 2); (1, 3, 1, 0)
- (0, 3, 0, 0); (1, 0, 3, 1); (0, 0, 3, 0); (1, 3, 0, 1)
- (1, 3, 0, 0); (0, 0, 3, 1)
- (1, 0, 1, 0); (0, 3, 2, 1); (0, 1, 0, 1); (1, 2, 3, 0)
- (1, 1, 1, 0); (0, 2, 2, 1); (0, 1, 1, 1); (1, 2, 2, 0)
- (0, 2, 1, 0); (1, 1, 2, 1); (0, 1, 2, 0); (1, 2, 1, 1)
- (1, 2, 1, 0); (0, 1, 2, 1);
- (0, 3, 1, 0); (1, 0, 2, 0); (0, 1, 3, 0); (0, 2, 0, 1)
- (1, 0, 2, 0); (0, 3, 1, 1); (0, 2, 0, 1); (1, 1, 3, 0)
- (1, 1, 2, 0); (0, 2, 1, 1)
- (0, 2, 2, 0); (1, 1, 1, 1)
- (0, 3, 2, 0); (1, 0, 1, 1); (0, 2, 3, 0); (1, 1, 0, 1)
- (1, 0, 3, 0); (0, 3, 0, 1)
Let's try one representative from each class.
$p^3 = 1/2$. This gives us the solution $p = sqrt[3]4/2$
$2p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 2p^2(1-p) = 1/2$. This polynomial has three real roots, one of which is a valid probability.
$3p^2(1-p) = 1/2$. The real root here is negative.
$p^3 + 3p^2(1-p) = 1/2$. This has the solution $p = 1/2$, and corresponds to taking whichever of heads or tails we got more of.
$p^3 + p(1-p)^2 = 1/2$. The real solution is a valid probability.
Okay, I lied, I'm not going to try every single case. But we did come up with a couple of new solutions we didn't previously know about.
There are some things we could systematically do here, like eliminating the cases that correspond to ignoring some number of the coin flips or employing Descartes's rule of signs to skip some cases where there are no real roots. I don't know if this would reach a bijective solution or not, but it's worth a try.
answered yesterday
Daniel McLauryDaniel McLaury
240217
edited yesterday
answered yesterday
Daniel McLauryDaniel McLaury
240217
answered yesterday
Daniel McLauryDaniel McLaury
240217
answered yesterday
Daniel McLauryDaniel McLaury
240217
240217
1
$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
yesterday
$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
1
$begingroup$
For your second-to-last representative, it corresponds to taking the majority answer from 3 coin flips, not the first flip (the first flip corresponds to the equation $p^3 + 2p^2(1 - p) + p(1 - p)^2 = frac12$).
$endgroup$
– user44191
yesterday
$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
add a comment |
1
$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
yesterday
$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
1
$begingroup$
For your second-to-last representative, it corresponds to taking the majority answer from 3 coin flips, not the first flip (the first flip corresponds to the equation $p^3 + 2p^2(1 - p) + p(1 - p)^2 = frac12$).
$endgroup$
– user44191
yesterday
$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
1
1
$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
yesterday
$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
yesterday
$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
1
1
$begingroup$
For your second-to-last representative, it corresponds to taking the majority answer from 3 coin flips, not the first flip (the first flip corresponds to the equation $p^3 + 2p^2(1 - p) + p(1 - p)^2 = frac12$).
$endgroup$
– user44191
yesterday
$begingroup$
For your second-to-last representative, it corresponds to taking the majority answer from 3 coin flips, not the first flip (the first flip corresponds to the equation $p^3 + 2p^2(1 - p) + p(1 - p)^2 = frac12$).
$endgroup$
– user44191
yesterday
$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
yesterday
add a comment |
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f326806%2fwhat-numbers-can-simulate-1-2%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
2
$begingroup$
There's the trivial: such $p$ must be algebraic (as "simulating $frac12$" is given by a polynomial equation).
$endgroup$
– user44191
2 days ago
$begingroup$
To extend some of the arguments from the linked math.SE problem: no matter how the coin "simulates" $frac12$, you always get that $frac12 = p P(p) = (1 - p) Q(1 - p)$ for some polynomials $P, Q$ (although the method of simulation - specifically, whether the "all heads" and "all tails" are counted together - does affect how $P, Q$ are related). Correspondingly, I'd expect some statement about valuations of $p$ and $1 - p$ to be helpful (though I don't have enough experience myself to figure out the appropriate statement).
$endgroup$
– user44191
2 days ago
1
$begingroup$
Another question: which rational numbers $q$ can be simulated by a rational number other than $q$ and $1-q$?
$endgroup$
– Brendan McKay
2 days ago
$begingroup$
Perhaps of interest: $2/5$ can not simulate $1/5$. Proof: If it did, we would have $a_0 2^0 3^n + cdot + a_n 2^n 3^0 = 5^n-1$ with $a_n=0$ or $a_n=1$, which is impossible mod $3$.
$endgroup$
– Matt F.
yesterday
$begingroup$
@MattF. That can be covered by a generalization of the argument I discussed above: if $p$ can simulate $q$, then for any nonarchimedean additive valuation $| |$ such that $|p| > 0$, either $|q| > 0$ or $|1 - q| > 0$, and the choice of $q$ or $1 - q$ must be the same for all such valuations (slightly stronger, $|q| geq |p|$ or $|1 - q| geq |p|$).
$endgroup$
– user44191
yesterday