Generate integer from 0 to 1 with equal probability - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T02:59:45Z https://cs.stackexchange.com/feeds/question/52381 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/52381 1 Generate integer from 0 to 1 with equal probability noman pouigt https://cs.stackexchange.com/users/36212 2016-01-28T06:10:36Z 2016-01-28T06:32:31Z <p>I am trying to get around this problem of my own making. I want to generate 0 or 1 with another function(gr0_4()) which generates random number from 0 to 4.</p> <p>I am wondering if I can approach this way:</p> <p>a). if gr0_4() = 0 or 1 then I will use 0</p> <p>b). if gr0_4() = 2 or 3 then I will use 1</p> <p>c). if gr0_4() = 4 I will repeat the a) and b) steps.</p> <p>Is my understanding correct that the "a" and "b" step each has 50% probability of happening?</p> <pre><code>def gr0_1(): while True: x = gr0_4() if x == 0 or x == 1: return 0 elif x == 0 or x == 1: return 1 </code></pre> <p>What if I want to use gr0_1() to create gr1_7() i.e. create number between 1 to 7 with equal probability?</p> <p>Can I use below reasoning to create that function gr1_1().</p> <p>As 7 consists of 3 bits. I can generate each bit with equal probability using gr0_1(). So I will call gr0_1() three times and based on that value I get, I will set/unset the corresponding bits to generate a number between 1 to 7 including the numbers 1 and 7. However I can get the number 0 but I don't want that so I will repeat the process again. Will the probability of each number generation between 1 to 7 will be 1/7 in that case also?</p> <p>Some simple mathematical calculation will be nice to answer this. I tried to read up on rejection sampling but couldn't understand much.</p> https://cs.stackexchange.com/questions/52381/generate-integer-from-0-to-1-with-equal-probability/52382#52382 2 Answer by David Richerby for Generate integer from 0 to 1 with equal probability David Richerby https://cs.stackexchange.com/users/9550 2016-01-28T06:32:31Z 2016-01-28T06:32:31Z <p>Yes, this is exactly rejection sampling and it works in the way you think it works, assuming that your initial procedure <code>gr_04()</code> generates the numbers $0$&ndash;$4$ with equal probability (you say it's random but you don't say it's uniform).</p> <p>If $X$ is distributed uniformly on $\{0, \dots, 4\}$, then $\Pr(x\in\{0,1\}) = \Pr(x\in\{2,3\}) = 2/5$. With probability $1/5$, you'll have to try again but, on your second attempt, the probability of getting $0$ or&nbsp;$1$ is still equal to the probability of getting $2$ or&nbsp;$3$. The number of attempts you have to make before you get something in $\{0, \dots, 3\}$ is just a geometric random variable with parameter $p=4/5$ and this has expectation $(1-p)/p = 1/4$ so, on average, you'll have to make $5/4$ calls to <code>gr_04()</code>, including the one that succeeds.</p> <p>The analysis of your second example is similar: your procedure generates each possible answer with the same probability and each attempt succeeds with probability $7/8$, so you'll need an average of $8/7$ calls to <code>gr_01()</code>, which means an average of $(8/7)(5/4)=10/7$ calls to <code>gr_04()</code>.</p>