在面试蚂蚁金服的时候遇到了这样的问题，感觉很经典的，但是如果之前没有遇到过还是很难想啊～

随机数生成器生成每一个随机数的概率是相同的。

Question1: From rand6() to rand3()

public class Solution{
    public int rand3(){
        int x = 0;
        return (x = rand6()) > 3? x%3 + 1 : x;
    }
}

这道题还是比较容易想出来的～

Question2: From rand2() to rand4()

public class Solution{
   public int rand4(){
        return 2*(rand2() - 1) + rand2();
   }
}

这里涉及到一种技巧，就是小随机生成器如何放大。用这种方式，例如从rand3() 到 rand9(), 就可以是3*(rand3() - 1) + rand3(). 具体证明可以用排列组合的方法，这里就不赘述了。

Question3: From rand3() to rand2()

我觉得看下边代码很简单，但是从rand3() 到 rand2() 但如何证明你的代码可以保证新随机数生成器生成每一个元素的概率是相同的呢？

public class Solution{
     public int rand2(){
        int x = rand3();
        while(x > 2){
           x = rand3();
        }
        return x;
     }
}

具体思路就是如果大随机数生成器生成的数值不在目标随机数生成器的范围内，就不断重试，直到条件满足为止。

证明：

我们以Y = 1 (生成随机数1)为例，根据全概率公式：

P(Y=1) = P(Y=1 | $1^{st}$ try) + P(Y=1 | $2^{nd}$ try) + P (Y=1 | $3^{rd}$ try) + ...... + P(Y=1 | $n^{th}$ try)
= ${\frac{1}{3}}$ + ${\frac{1}{3}}\times{\frac{1}{3}}$ + ${\frac{1}{3}}\times{\frac{1}{3}}^2$ + ......+ ${\frac{1}{3}}\times{\frac{1}{3}}^n$ = 1/2

从上边的证明我们可以得出，其实从大随机数生成器到小随机数生成器都可以用question3的方法来做。

总结

1. Question2: 小随机数生成器如何放大。
2. Question3: 大随机数生成器如何组装成小随机数生成器。

欢迎大家讨论，有什么不对的，还希望得到各位指正！