-1

Given :
I was given a function that generates randomly 0 or 1. It generates 0 with probability p and 1 with probability 1-p.
Requirement:
I need to create a function that generates a number between 0 and 6 randomly with uniform probability by utilizing the above given function.

Note:cant use inbuilt random functions.

Can someone help me with this.

Thanks in advance

taurz
  • 194
  • 2
  • 9
  • If you search in your browser for "random dice roll", you'll find references that can explain this much better than we can manage here. This problem has been presented and solved in many places. – Prune Jun 28 '19 at 18:14
  • Did you even read my question? How it is a duplicate? My questions is completely different, check the answer below that is what I am looking for. The thread you linked uses inbuilt random method and also it is completely out of contest of what I am looking for. – taurz Jun 28 '19 at 18:19
  • My misread -- I read it as a uniform *float* distribution. Duplicate vote withdrawn. This is still dealt with elsewhere, but not so trivial to find. – Prune Jun 28 '19 at 18:23
  • Does this answer your question? [How to generate a random integer in the range \[0,n\] from a stream of random bits without wasting bits?](https://stackoverflow.com/questions/6046918/how-to-generate-a-random-integer-in-the-range-0-n-from-a-stream-of-random-bits) – Peter O. Nov 18 '20 at 07:16

1 Answers1

1

You can skew a biased random function to become unbiased by checking for a sequence of 01 or 10 and ignoring other results, this way you have a fair coin with a 50% chance of outputting any of the said sequences ((1-p)*p == p*(1-p)

With this fair coin you can then roll 3 bits and output the rolled number, if you roll a 7 (111) just repeat the process.

hbejgel
  • 4,674
  • 2
  • 17
  • 27
  • 2
    Here's a similar question with a more thorough explanation: https://stackoverflow.com/questions/1986859/unbiased-random-number-generator-using-a-biased-one – hbejgel Jun 28 '19 at 15:09
  • Thank you for the concise answer @hbejgel. Just wanted to make sure I understood it correctly. so once I have the unbiased [0,1] function. I then need to call it inside my [0,6] function three times to get an three bit number and then I return a number between [0,6] based on the three bit number. for example if i got 110 I return index 6 from my array [0,1,2,3,4,5,6] which is 6 right? – taurz Jun 28 '19 at 15:31
  • 2
    @sarat: almost correct. You will need to call random function 3 times again if you get the binary `111`. In that case, it will point to 8 which will give you IndexOutOfBound exception. So, you need to check if all bits are set to 1 or not. If yes, generate all 3 bits once again. – CodeHunter Jun 28 '19 at 19:10
  • @CodeHunter Thank you for the comment. I understood it now clearly. – taurz Jun 29 '19 at 03:26