随机数

证明，等概率随机

@Test
public void equalProbabilityRandom() {
  int testTimes = 10000000;
  int count = 0;
  for (int i = 0; i < testTimes; i++) {
    double random = Math.random();
    if (random < 0.5) {
      count++;
    }
  }
  System.out.println("随机概率为：" + ((double)count / (double) testTimes));  // 0.5000338
}

上述代码，出现[0, 0.5)范围的数的概率为0.5，同理，出现 [0, 0.1)的概率为 0.1，.... 故出现[0, x) （0 <= x < 1）的概率为x。

将 [0, x) 出现的概率由 x 变为 x^2

@Test
public void equalProbabilityRandom() {
  int testTimes = 10000000;
  int count = 0;
  for (int i = 0; i < testTimes; i++) {
    double random = Math.max(Math.random(), Math.random());
    if (random < 0.5) {
      count++;
    }
  }
  System.out.println("随机概率为：" + ((double)count / (double) testTimes));  // 0.2501026
}

Math.max(Math.random(), Math.random())，两次都必须出现 [0, x) 范围的数才符合范围。使用 max 取较大的数，判断较大的数是否为符合范围的，如果较大的符合，较小的数更符合，所以使用max而不是 min。

面试题

从15随机到17随机

有一个函数 f()，可以返回 1 ~ 5等概率的随机整数；要求使用 f()函数，生成一个新的随机函数g()，可以返回 1 ~ 7 的等概率的随机整数。

@Test
public void m1to5and1to7() {
  int testTimes = 1000000;
  int[] counts = new int[8];
  for (int i = 0; i < testTimes; i++) {
    int num = g();
    counts[num]++;
  }
  // 打印每个的次数
  for (int i = 0; i < counts.length; i++) {
    System.out.println("数字" + i + "出现的次数为" + counts[i]);
  }
}

// 返回 1 ~ 5等概率的随机整数
public int f() {
  return (int) (Math.random() * 5 + 1);
}

// 根据 f() 构造一个等概率的 0 1 发生器
public int f1() {
  // 1, 2, 3,   4, 5
  // 0, 0, 重来, 1, 1
  while (true) {
    int num = f();
    if (num < 3) {
      return 0;
    }
    if (num > 3) {
      return 1;
    }
  }
}

// 要想得到 1 ~ 7 范围的数，可以先构造 0 ~ 7 的等概率随机函数
// 使用 0 1 发生器构建二进制数，随机生成 0 ~ 7 内的数字
// 000  ~ 111
public int f2() {
  return (f1() << 2) + (f1() << 1) + f1();
}

// 使用f2() 剔除 7，或者剔除 0，完成 1~7的随机
public int g() {
  int num;
  do {
    num = f2();
  } while (num == 0);
  return num;
}

**扩展：**从a~b随机到c~d随机的实现。

从01不等概率随机到01等概率随机

给定一个函数x()，已知x会以固定概率返回0和1，但是0和1是不等概率随机的。比如0的概率为0.78，1的概率为0.22；如果通过不等概率随机变为等概率随机返回0和1的函数y()？

@Test
public void notEqual0and1() {
  int testTimes = 1000000;
  int[] counts = new int[2];
  for (int i = 0; i < testTimes; i++) {
    counts[y()]++;
  }
  for (int i = 0; i < counts.length; i++) {
    System.out.println("数字" + i + "出现的概率为" + counts[i]);
  }
}

public int x() {
  return Math.random() < 0.86 ? 0: 1;
}

// 将x()随机两次
// 出现 01 的概率是与出现 10的概率相同的
// 故代码如下：
public int y() {
  int num;
  do {
    num = x();
  } while (num == x());
  return num;
}