Mixing
Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...
Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$
So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ [0,1] and returns $0$ if $f < 0.5$, $1$ if $f geq 0.5$.
I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $frac14$... and I can expand that solution to any $p$ where $p = frac12^x$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...
I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?
logic probability-theory random-number-generator
asked 4 hours ago
QuantumHoneybees
1062
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...
Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$
So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ [0,1] and returns $0$ if $f < 0.5$, $1$ if $f geq 0.5$.
I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $frac14$... and I can expand that solution to any $p$ where $p = frac12^x$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...
I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?
logic probability-theory random-number-generator
asked 4 hours ago
QuantumHoneybees
1062
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
If $p$ is a rational number, your question is covered by this question. If $p$ is an irrational number, I don't think it is possible (in finite many steps)...
– xskxzr
3 hours ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...
Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$
So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ [0,1] and returns $0$ if $f < 0.5$, $1$ if $f geq 0.5$.
I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $frac14$... and I can expand that solution to any $p$ where $p = frac12^x$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...
I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?
logic probability-theory random-number-generator
asked 4 hours ago
QuantumHoneybees
1062
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...
Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$
So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ [0,1] and returns $0$ if $f < 0.5$, $1$ if $f geq 0.5$.
I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $frac14$... and I can expand that solution to any $p$ where $p = frac12^x$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...
I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?
logic probability-theory random-number-generator
logic probability-theory random-number-generator
asked 4 hours ago
QuantumHoneybees
1062
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
QuantumHoneybees
1062
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
QuantumHoneybees
1062
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
QuantumHoneybees
1062
asked 4 hours ago
QuantumHoneybees
1062
1062
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
QuantumHoneybees is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
If $p$ is a rational number, your question is covered by this question. If $p$ is an irrational number, I don't think it is possible (in finite many steps)...
– xskxzr
3 hours ago
add a comment |Â
If $p$ is a rational number, your question is covered by this question. If $p$ is an irrational number, I don't think it is possible (in finite many steps)...
– xskxzr
3 hours ago
If $p$ is a rational number, your question is covered by this question. If $p$ is an irrational number, I don't think it is possible (in finite many steps)...
– xskxzr
3 hours ago
If $p$ is a rational number, your question is covered by this question. If $p$ is an irrational number, I don't think it is possible (in finite many steps)...
– xskxzr
3 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Suppose $p=sumlimits_n=1^infty frac12^np_n$, where $p_nin0,1$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^-(k-1)fracp_k2$, thus the probability of generating heads is $sumlimits_k=1^infty2^-kp_k =p$. The expected number of iterations is $2$.
Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.
answered 55 mins ago
Ariel
10.6k11332
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Suppose $p=sumlimits_n=1^infty frac12^np_n$, where $p_nin0,1$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^-(k-1)fracp_k2$, thus the probability of generating heads is $sumlimits_k=1^infty2^-kp_k =p$. The expected number of iterations is $2$.
Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.
answered 55 mins ago
Ariel
10.6k11332
add a comment |Â
up vote
2
down vote
Suppose $p=sumlimits_n=1^infty frac12^np_n$, where $p_nin0,1$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^-(k-1)fracp_k2$, thus the probability of generating heads is $sumlimits_k=1^infty2^-kp_k =p$. The expected number of iterations is $2$.
Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.
answered 55 mins ago
Ariel
10.6k11332
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Suppose $p=sumlimits_n=1^infty frac12^np_n$, where $p_nin0,1$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^-(k-1)fracp_k2$, thus the probability of generating heads is $sumlimits_k=1^infty2^-kp_k =p$. The expected number of iterations is $2$.
Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.
answered 55 mins ago
Ariel
10.6k11332
Suppose $p=sumlimits_n=1^infty frac12^np_n$, where $p_nin0,1$, i.e. $p_1p_2...$ is the base-2 expansion of $p$. To generate a $p$ biased coin, toss fair coins $c_1c_2...$ until you reach $i$ such that $p_i neq c_i$, and output heads iff $p_i>c_i$. The probability of generating heads in exactly $k$ iterations is $2^-(k-1)fracp_k2$, thus the probability of generating heads is $sumlimits_k=1^infty2^-kp_k =p$. The expected number of iterations is $2$.
Note that the above requires you to be able to output $p_i$ given $i$, so this will not work for noncomputable $p$.
answered 55 mins ago
Ariel
10.6k11332
answered 55 mins ago
Ariel
10.6k11332
answered 55 mins ago
Ariel
10.6k11332
answered 55 mins ago
Ariel
10.6k11332
10.6k11332
add a comment |Â
add a comment |Â
QuantumHoneybees is a new contributor. Be nice, and check out our Code of Conduct.
QuantumHoneybees is a new contributor. Be nice, and check out our Code of Conduct.
QuantumHoneybees is a new contributor. Be nice, and check out our Code of Conduct.
QuantumHoneybees is a new contributor. Be nice, and check out our Code of Conduct.
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99611%2fgiven-a-rng-that-outputs-0-or-1-with-an-equal-probability-make-a-rng-that-gener%23new-answer', 'question_page');
);
Post as a guest
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
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
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
If $p$ is a rational number, your question is covered by this question. If $p$ is an irrational number, I don't think it is possible (in finite many steps)...
– xskxzr
3 hours ago