What numbers can simulate 1/2?History 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?


History 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













7












$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$?










share|cite|improve this question











$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.
    2 days ago










  • $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
    2 days ago















7












$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$?










share|cite|improve this question











$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.
    2 days ago










  • $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
    2 days ago













7












7








7


2



$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$?










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 2 days ago









user44191

3,02311532




3,02311532










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.
    2 days ago










  • $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
    2 days ago












  • 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.
    2 days ago










  • $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
    2 days ago







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.
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.
2 days ago












$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
2 days ago




$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
2 days ago










1 Answer
1






active

oldest

votes


















4












$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.






share|cite|improve this answer











$endgroup$








  • 1




    $begingroup$
    You mean $le$ not $lt$ in line 7.
    $endgroup$
    – Brendan McKay
    2 days ago










  • $begingroup$
    @BrendanMcKay: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago






  • 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
    2 days ago










  • $begingroup$
    @user44191: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago











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
);



);













draft saved

draft discarded


















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









4












$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.






share|cite|improve this answer











$endgroup$








  • 1




    $begingroup$
    You mean $le$ not $lt$ in line 7.
    $endgroup$
    – Brendan McKay
    2 days ago










  • $begingroup$
    @BrendanMcKay: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago






  • 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
    2 days ago










  • $begingroup$
    @user44191: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago















4












$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.






share|cite|improve this answer











$endgroup$








  • 1




    $begingroup$
    You mean $le$ not $lt$ in line 7.
    $endgroup$
    – Brendan McKay
    2 days ago










  • $begingroup$
    @BrendanMcKay: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago






  • 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
    2 days ago










  • $begingroup$
    @user44191: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago













4












4








4





$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.






share|cite|improve this answer











$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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 2 days ago

























answered 2 days ago









Daniel McLauryDaniel McLaury

240217




240217







  • 1




    $begingroup$
    You mean $le$ not $lt$ in line 7.
    $endgroup$
    – Brendan McKay
    2 days ago










  • $begingroup$
    @BrendanMcKay: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago






  • 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
    2 days ago










  • $begingroup$
    @user44191: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago












  • 1




    $begingroup$
    You mean $le$ not $lt$ in line 7.
    $endgroup$
    – Brendan McKay
    2 days ago










  • $begingroup$
    @BrendanMcKay: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago






  • 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
    2 days ago










  • $begingroup$
    @user44191: Fixed, thanks.
    $endgroup$
    – Daniel McLaury
    2 days ago







1




1




$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
2 days ago




$begingroup$
You mean $le$ not $lt$ in line 7.
$endgroup$
– Brendan McKay
2 days ago












$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
2 days ago




$begingroup$
@BrendanMcKay: Fixed, thanks.
$endgroup$
– Daniel McLaury
2 days ago




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
2 days ago




$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
2 days ago












$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
2 days ago




$begingroup$
@user44191: Fixed, thanks.
$endgroup$
– Daniel McLaury
2 days ago

















draft saved

draft discarded
















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

រឿង រ៉ូមេអូ និង ហ្ស៊ុយលីយេ សង្ខេបរឿង តួអង្គ បញ្ជីណែនាំ

Crop image to path created in TikZ? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Crop an inserted image?TikZ pictures does not appear in posterImage behind and beyond crop marks?Tikz picture as large as possible on A4 PageTransparency vs image compression dilemmaHow to crop background from image automatically?Image does not cropTikzexternal capturing crop marks when externalizing pgfplots?How to include image path that contains a dollar signCrop image with left size given

Romeo and Juliet ContentsCharactersSynopsisSourcesDate and textThemes and motifsCriticism and interpretationLegacyScene by sceneSee alsoNotes and referencesSourcesExternal linksNavigation menu"Consumer Price Index (estimate) 1800–"10.2307/28710160037-3222287101610.1093/res/II.5.31910.2307/45967845967810.2307/2869925286992510.1525/jams.1982.35.3.03a00050"Dada Masilo: South African dancer who breaks the rules"10.1093/res/os-XV.57.1610.2307/28680942868094"Sweet Sorrow: Mann-Korman's Romeo and Juliet Closes Sept. 5 at MN's Ordway"the original10.2307/45957745957710.1017/CCOL0521570476.009"Ram Leela box office collections hit massive Rs 100 crore, pulverises prediction"Archived"Broadway Revival of Romeo and Juliet, Starring Orlando Bloom and Condola Rashad, Will Close Dec. 8"Archived10.1075/jhp.7.1.04hon"Wherefore art thou, Romeo? To make us laugh at Navy Pier"the original10.1093/gmo/9781561592630.article.O006772"Ram-leela Review Roundup: Critics Hail Film as Best Adaptation of Romeo and Juliet"Archived10.2307/31946310047-77293194631"Romeo and Juliet get Twitter treatment""Juliet's Nurse by Lois Leveen""Romeo and Juliet: Orlando Bloom's Broadway Debut Released in Theaters for Valentine's Day"Archived"Romeo and Juliet Has No Balcony"10.1093/gmo/9781561592630.article.O00778110.2307/2867423286742310.1076/enst.82.2.115.959510.1080/00138380601042675"A plague o' both your houses: error in GCSE exam paper forces apology""Juliet of the Five O'Clock Shadow, and Other Wonders"10.2307/33912430027-4321339124310.2307/28487440038-7134284874410.2307/29123140149-661129123144728341M"Weekender Guide: Shakespeare on The Drive""balcony"UK public library membership"romeo"UK public library membership10.1017/CCOL9780521844291"Post-Zionist Critique on Israel and the Palestinians Part III: Popular Culture"10.2307/25379071533-86140377-919X2537907"Capulets and Montagues: UK exam board admit mixing names up in Romeo and Juliet paper"Istoria Novellamente Ritrovata di Due Nobili Amanti2027/mdp.390150822329610820-750X"GCSE exam error: Board accidentally rewrites Shakespeare"10.2307/29176390149-66112917639"Exam board apologises after error in English GCSE paper which confused characters in Shakespeare's Romeo and Juliet""From Mariotto and Ganozza to Romeo and Guilietta: Metamorphoses of a Renaissance Tale"10.2307/37323537323510.2307/2867455286745510.2307/28678912867891"10 Questions for Taylor Swift"10.2307/28680922868092"Haymarket Theatre""The Zeffirelli Way: Revealing Talk by Florentine Director""Michael Smuin: 1938-2007 / Prolific dance director had showy career"The Life and Art of Edwin BoothRomeo and JulietRomeo and JulietRomeo and JulietRomeo and JulietEasy Read Romeo and JulietRomeo and Julieteeecb12003684p(data)4099369-3n8211610759dbe00d-a9e2-41a3-b2c1-977dd692899302814385X313670221313670221