アルゴリズムイントロダクション 練習問題5.1-3
問題
0と1をそれぞれ確率1/2で出力する問題を考える。利用できるのは0か1かを出力する手続きBIASED-RANDOMである。BIASED-RANDOMは1を確率p、0を確率1-pで出力する(0
やっぱり実装まで。期待実行時間は出していない。あと証明もまだ(これはたぶんすぐできる)。
発想
- PK戦のサドンデスで、先攻が勝ったら1、後攻が勝ったら0を返すとすればよい
public class Utility { public static boolean randomBoolean() { boolean a = true; boolean b = true; double p = 0.7; // Any p is OK. s.t. 0 < p < 1 while (!(a ^ b) ) { a = randomBooleanByProbability(p); b = randomBooleanByProbability(p); } return a; } // BIASED-RANDOM public static boolean randomBooleanByProbability(double p) { if (Math.random() < p ) return true; else return false; } }
import static org.junit.Assert.*; import org.junit.Test; import com.gmail.seizans.algorithm.Utility; public class UtilityTest { @Test public void randomBooleanTest() throws Exception { int numberOfTrials = 20000; double minProb = 0.95; double maxProb = 1.05; int counter = 0; boolean isOk = false; for (int i = 0; i < numberOfTrials; i++) { if (Utility.randomBoolean() ) counter++; } if (numberOfTrials * minProb < counter * 2 && counter * 2 < numberOfTrials * maxProb ) { isOk = true; } assertTrue(isOk); } @Test public void randomBooleanByProbabilityTest() throws Exception { double p = 0.66666; int numberOfTrials = 20000; double minProb = 0.95; double maxProb = 1.05; boolean isOk = false; int counter = 0; for (int i = 0; i < numberOfTrials; i++) { if (Utility.randomBooleanByProbability(p) ) counter++; } if (p * numberOfTrials * minProb < counter && counter < p * numberOfTrials * maxProb) { isOk = true; } assertTrue(isOk); } }