In the task I need to write a 50-50 random method using only already implemented biassed-random, which returns 0 or 1 with some probability we don't know
I really need some advice which algorithm should be. I tried next solution: call a biased random until the result is changed, and then return the counter div 2 and also tried with log2, but it also not works when the initial prob is near to 0.5. It works well when the "biased-probability" is far from 0,5, but when the implemented random method is fair enough, my idea doesn't work.
Here's the code:
package net.lim.algorithms;
import java.util.HashMap;
import java.util.Map;
public class BiasToNotBiasRand {
public static int biasRand() {
double seed = 0.99; //TODO change me
return Math.random() < seed ? 1 : 0;
}
public static long notBiasRand() {
int seed = biasRand();
int counter = 0;
while (true) {
int nextIt = biasRand();
counter++;
if (nextIt != seed) {
return (int) Math.round(Math.log10(counter) / Math.log10(2)) % 2;
//return counter % 2; // Another idea, also doesn't fit the task
}
}
}
public static void main(String[] args) {
Map<Long, Integer> resultMap = new HashMap<>();
for (int j = 0; j < 20; j++) {
for (int i = 0; i < 1000; i++) {
long result = notBiasRand();
resultMap.put(result, resultMap.getOrDefault(result, 0) + 1);
}
System.out.println(resultMap);
resultMap.clear();
}
}
}
The results for 0.99 is quite well:
{0=509, 1=491}
{0=530, 1=470}
{0=520, 1=480}
{0=512, 1=488}
{0=497, 1=503}
{0=470, 1=530}
{0=499, 1=501}
{0=499, 1=501}
But when change the "seed" to 0.5 there's completely mess:
{0=696, 1=304}
{0=743, 1=257}
{0=687, 1=313}
{0=714, 1=286}
Could you please advice me correct algorithm for this task?
Aucun commentaire:
Enregistrer un commentaire