アルゴリズムイントロダクション 練習問題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);
	}
}