Une question d'entrevue: à propos de la probabilité

Question

Une question d'entrevue:

Soit une fonction f (x) que 1/4 fois renvoie 0, 3/4 fois renvoie 1. Ecrivez une fonction g (x) en utilisant f (x) qui 1/2 fois renvoie 0, 1/2 fois renvoie 1.

Mon implémentation est:

 function g(x) = {
    if (f(x) == 0){ // 1/4 
        var s = f(x) 
        if( s == 1) {// 3/4 * 1/4
            return s  //   3/16
        } else {
            g(x)
        } 
    } else { // 3/4
            var k = f(x)
            if( k == 0) {// 1/4 * 3/4
                return k // 3/16 
            }  else {
                g(x)
            }       
    }
}
 

Ai-je raison? Quelle est votre solution? (Vous pouvez utiliser n'importe quelle langue)

Answer 1

Si vous appelez f(x) deux fois de suite, les résultats suivants sont possibles (en supposant que les appels successifs à f(x) sont indépendants et identiquement distribués essais):

00 (probability 1/4 * 1/4)
01 (probability 1/4 * 3/4)  
10 (probability 3/4 * 1/4)  
11 (probability 3/4 * 3/4)

01 et 10 se produire avec une probabilité égale. Donc itérer jusqu'à ce que vous obtenez l'un de ces cas, alors retourne 0 ou 1 de façon appropriée:

do
  a=f(x); b=f(x);
while (a == b);

return a;

Il pourrait être tentant de considérer f(x) une seule fois par itération et de garder la trace des deux plus récentes, mais qui ne fonctionne pas. Supposons que le premier rouleau est de 1, avec une probabilité 3/4. Vous auriez boucle jusqu'à ce que le premier 0, alors retourne 1 (avec une probabilité 3/4).

Answer 2

Votre solution est correcte, si quelque peu inefficace et avec plus dupliqué logique. Voici un Python de mise en œuvre de la même algorithme dans un nettoyant forme.

def g ():
    while True:
        a = f()
        if a != f():
            return a

Si f() est cher vous souhaitez obtenir plus sophistiqués, avec l'aide de la match/mismatch informations pour essayer de revenir avec le moins d'appels à elle. C'est là la plus efficace possible solution.

def g ():
    lower = 0.0
    upper = 1.0
    while True:
        if 0.5 < lower:
            return 1
        elif upper < 0.5:
            return 0
        else:
            middle = 0.25 * lower + 0.75 * upper
            if 0 == f():
                lower = middle
            else:
                upper = middle

Cela prend environ 2,6 appels d' g() en moyenne.

La façon dont cela fonctionne est ce. Nous essayons de choisir un nombre aléatoire de 0 à 1, mais il nous arrive d'arrêter dès que nous saurons si le nombre est 0 ou 1. Nous commençons à savoir que le nombre est dans l'intervalle (0, 1). 3/4 des nombres sont dans le bas de 3/4 de l'intervalle, et 1/4 sont dans le top 1/4 de l'intervalle. Nous décidons de qui repose sur un appel à l' f(x). Cela signifie que nous sommes maintenant dans un petit intervalle.

Si nous laver, rincer et répéter un nombre de fois suffisant, nous pouvons déterminer notre nombre fini aussi précisément que possible, et ils ont absolument la même probabilité de liquidation dans n'importe quelle région de l'original de l'intervalle. En particulier, nous avons une même probabilité de liquidation plus grand que ou à moins de 0.5.

Si vous vouliez vous pourriez répéter l'idée de générer un flux continu de bits un par un. C'est, en effet, sensiblement le moyen le plus efficace de générer un tel flux, et est la source de l'idée de l'entropie dans la théorie de l'information.

Answer 3

Le problème avec votre algorithme est qu'il se répète avec une forte probabilité. Mon code:

function g(x) = {
    var s = f(x) + f(x) + f(x); 
    // s = 0, probability:  1/64
    // s = 1, probability:  9/64
    // s = 2, probability: 27/64
    // s = 3, probability: 27/64
    if (s == 2) return 0;
    if (s == 3) return 1;

    return g(x); // probability to go into recursion = 10/64, with only 1 additional f(x) calculation
}

J'ai mesuré nombre moyen de fois f(x) a été calculé pour votre algorithme et pour le mien. Pour que le vôtre f(x) a été calculé autour de 5,3 fois par un g(x) calcul. Avec mon algorithme, ce nombre a été réduit à environ 3.5. Le même est vrai pour d'autres réponses à ce jour et depuis ils sont en fait le même algorithme que vous avez dit.

P. S.: votre définition ne mentionne pas "aléatoire" pour le moment, mais probablement que c'est assumé. Voir mon autre réponse.

Answer 4

Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1

Cette affirmation littéralement, f(x) si appelé à quatre reprises renvoie toujours zéro une fois et de 1 à 3 reprises. C'est différent que de dire que f(x) est un probabalistic de la fonction et de 0 à 1 ratio s'approche de 1 à 3 (1/4 vs 3/4) au cours de nombreuses itérations. Si la première interprétation est valide, que la seule valable en fonction de f(x) qui permettra de répondre aux critères, peu importe où dans la séquence de démarrage de la séquence 0111 répéter. (ou 1011 ou 1101 ou 1110 qui sont de la même séquence à partir d'un autre point de départ). Compte tenu de cette contrainte, l'

  g()= (f() == f())

devrait suffire.

Answer 5

Comme déjà mentionné votre définition n'est pas aussi bien quant à la probabilité. En général cela signifie que non seulement la probabilité est bonne, mais distribution également. Sinon, vous pouvez simplement écrire g(x) qui sera de retour 1,0,1,0,1,0,1,0 - il retourner à 50/50, mais les chiffres ne sont pas être aléatoire.

Une autre tricherie approche pourrait être:

var invert = false;
function g(x) {
    invert = !invert;
    if (invert) return 1-f(x);
    return f(x);
}

Cette solution sera mieux que tous les autres car il demande f(x) qu'une seule fois. Mais les résultats ne seront pas très aléatoire.