samedi 17 juillet 2021

Write 50-50 random method using implemented biased random (without known probability) [closed]

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