Random number 1..5 to 1..7

http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/

If we somehow generate integers from 1 to a-multiple-of-7 (like 7, 14, 21, …) with equal probability, we can use modulo division by 7 followed by adding 1 to get the numbers from 1 to 7 with equal probability.

We can generate from 1 to 21 with equal probability using the following expression.
 5*foo() + foo() -5 

Let us see how above expression can be used.
1. For each value of first foo(), there can be 5 possible combinations for values of second foo(). So, there are total 25 combinations possible.
2. The range of values returned by the above equation is 1 to 25, each integer occurring exactly once.
3. If the value of the equation comes out to be less than 22, return modulo division by 7 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/7.

int my_rand() // returns 1 to 7 with equal probability

{

    int i;

    i = 5*foo() + foo() - 5;

    if (i < 22)

        return i%7 + 1;

    return my_rand();

}

int rand7()
{
 int x = 22;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;
 int r = 1 + (x % 7);
 return r;
}

int rand7() { int x = 25; while( x > 21) x = rand5() + 5*rand5() - 5;   int r = (x >> 3) + (x & 7); r = (r >= 7) ? r - 6 : r + 1; return r; } A dice, when you throw gives only 1,2,.....21 (since you are rejecting 22,23,24,25 a.k.a rejection sampling theorem) So total no. of possible are 21. No. of ways getting "1"=3 (5*1+1-5,5*2+3-5,5*3+1-1)%7+1 No. of ways getting "2"=3 (5*1+1-5,5*2+3-5,5*3+1-1)%7+1 No. of ways getting "3"=3 (5*1+2-5,5*2+4-5,5*3+2-1)%7+1 and so on.. P(1)=3/21=1/7 P(2)=3/21=1/7 and so on... Understand why these solutions are not right http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/ x=foo()+foo()-1; if (x !=8,9){ return x; } Now what's the probability here for p(1),p(2)...p(7)? no. of ways of producing "1" =1 (1+1-1) no. of ways of producing "2" =2 (2+1-1,1+2-1) and so on... Total no. of possible combination =5*5=25 P(1)=1/25; P(2)=2/25 and so on... So probabilities are not equal in this case !! return (foo() + foo()%4 -1); (foo()+foo()-1)%7+1

http://www.nerdparadise.com/tech/interview/randomness/
Imagine a 5x5 grid with numbered cells.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

You can randomly create a coordinate in this grid using x = rand5() and y = rand5(). If the cell that the random choice lands on is between 1 and 7, you can return that number. Otherwise, create new random coordinates and try again. 

function rand7():
    while true:
        x = rand5()
        y = rand5()
        if y == 1:
            return x
        if y == 2 and x <= 2:
            return 5 + x    

This is technically a correct solution to this problem. 

NOTE: It is important to stress that the 2nd if statement cannot be reduced to just y == 2 and then calling x = rand5() until x is a 1 or 2. This gives unfair probability to 6 and 7. If you do this, 1 through 5 EACH have a 1 in 25 chance of getting hit. 6 and 7 have a 1/10 chance of getting hit EACH. 

However, this solution it is not ideal. Each trial only has a 28% chance of hitting a coordinate in the desired range and a 72% chance of needing to repeat the calculation. The largest multiple of 7 below 25 is 21. So we can stretch out the ranges for each number such that it is 3 times more likely to get hit, like so...

1	1	1	2	2
2	3	3	3	4
4	4	5	5	5
6	6	6	7	7
7	-	-	-	-

At this point it would be silly to have a bunch of if statements to determine the result. The grid is merely a visualization of the logic. The general formula looks like this:

function rand7():
    while true:
        value = (rand5() - 1) * 5 + rand5() // 1 through 25 (fair)
        if value <= 21:
            value = value - 1 // 0 through 20 (fair)
            value = floor(value / 3) // 0 through 6 (fair)
            return value + 1 // 1 through 7 (fair)

As an exercise, try creating other mappings from some rand{X}() to some rand{Y}()

http://www.growingwiththeweb.com/2014/03/given-random5-implement-random7.html

public static int random5() {
    return new Random().nextInt(5) + 1;
}

public static int random7() {
    // Get 0, 5, 10, 15 or 20 then add 0-4 (4% chance for 0-24)
    int val = (random5() - 1) * 5 + (random5() - 1);
    // If 0-20, return the result modulo 7 + 1 (12% chance for 1-7), otherwise
    // call recursively (16% chance)
    return val >= 21 ? random7() : val % 7 + 1;
}

Also refer to http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/
http://ariya.ofilabs.com/2007/11/random-number-1-5-to-1-7.html

题目：⽤用RAND2()去实现RAND6()
解法：
Generate a range of values where each value is equally likely (and where the range has at least 6 elements).
If we can do this, then we discard the elements greater than the previous multiple of 6 and mod the rest of them by 6.
This will give us a value within the range of 0 to 5 with each value being equally likely
int sum = -1;
while (true) {
  sum = 4 * rand.nextInt(2) + 2 * rand.nextInt(2) + rand.nextInt(2);
  if (sum <= 5) {
    break;
  }
}
return sum;

题目二：⽤用RAND5()去实现RAND7()
while(true) {
  int num = 5 * rand5() + rand5();
  if(num < 21) {
    return num % 7;
  }
}

这里可以sum=2*rand5() + rand5()吗？不可以，因为这样value wouldn't be equally distributed. For example, there would be two ways of
getting a 6 (6=2*1+4 and 6=2*2+2) but only one way of getting a 0 (0=2*0+0). The values in the range are not equally probable.
http://www.jiuzhang.com/qa/662/

1. 有一个骰子（随机生成1-6），求用这个骰子模拟一个1-7的随机数生成器。
2. 有一个随机生成1-5的生成器，求用这个生成器生成一个1-7的随机数生成器。
3. 有一个随机生成器生成0和1的概率分别是p和1-p。用它模拟一个01等概率的随机数生成器。

对于问题1和2，是一样的。以1为例子，算法的核心叫做“再来一瓶”：
随机两次，结果可能有(1,1), (1,2) ... (6,6) 一共36种可能性。将他们分为8组，前7组每组5对数，最后一组就是(6,6)。如果你随机到前面7组的情况，就返回对应的组号。如果随机到(6,6)，那么恭喜你，重复上述过程，再扔两次（再来一瓶）
这个题的误区是，以为用%7的方式可以解决问题，但是6和7是互质的，无论扔多少次，6的无论多少次幂都不会整除7。

对于问题3。本质也是，再来一瓶：丢两次，有四种可能性：
00 - 概率 p * p
01 - 概率 p * (1-p)
10 - 概率 (1-p) * p
11 - 概率 (1-p) * (1-p)

我们知道01和10的概率是一样的，那么如果扔到01，那么就认为是0，如果扔到10就认为是1，这样他们是等概率的。如果扔到00或者11怎么办呢？恭喜你，“再来一瓶”，重新丢两次，重复上述过程。

http://www.fgdsb.com/2015/01/03/implement-rand10-with-rand7/

要保证rand10()在整数1-10的均匀分布，可以构造一个1-10n的均匀分布的随机整数区间（n为任何正整数）。假设x是这个1-10n区间上的一个随机整数，那么x%10+1就是均匀分布在1-10区间上的整数。由于(rand7()-1)*7+rand7()可以构造出均匀分布在1-49的随机数（原因见下面的说明），可以将41～49这样的随机数剔除掉，得到的数1-40仍然是均匀分布在1-40的，这是因为每个数都可以看成一个独立事件。

1 2 3 4 5 6 7

int rand10() {     int x = 0;     do {         x = (rand7() - 1) * 7 + rand7();     } while(x > 40);     return x % 10 + 1; }

Follow Up:
如何用随机函数rand5来构造随机函数rand7

也是一样，想出组合的方法。Rand5产生1到5的数，减1就产生0到4的数，乘以5后可以产生的数是：0,5,10,15,20。 再加上第二个Rand5()产生的1,2,3,4,5。我们可以得到1到25， 而且每个数都只由 一种组合得到，即上述代码可以等概率地生成1到25。组合如下：
5 * (Rand5() - 1) + Rand5()

1 2 3 4 5 6

int rand7(){     int x = ~(1<<31); // max int     while(x > 21)         x = 5 * (rand5() - 1) + rand5(); // rand25     return x % 7 + 1; }

从上面一系列的分析可以发现，如果给你两个生成随机数的函数Randa和Randb， 你可以通过以下方式轻松构造Randab，生成1到ab的随机数：
Randab = b (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa

Read full article from Random number 1..5 to 1..7