Pourquoi cette valeur aléatoire a-t-elle une distribution 25/75 au lieu de 50/50?

139

Edit: Donc, fondamentalement, ce que j'essaie d'écrire est un hachage de 1 bit double.

Je veux mapper un doubleà trueou falseavec une chance de 50/50. Pour cela, j'ai écrit du code qui sélectionne des nombres aléatoires (juste à titre d'exemple, je veux l'utiliser sur des données avec des régularités et obtenir toujours un résultat 50/50) , vérifie leur dernier bit et incrémente ys'il est 1, ou ns'il est 0.

Cependant, ce code aboutit constamment à 25% yet 75% n. Pourquoi n'est-ce pas 50/50? Et pourquoi une distribution aussi étrange, mais simple (1/3)?

public class DoubleToBoolean {
    @Test
    public void test() {

        int y = 0;
        int n = 0;
        Random r = new Random();
        for (int i = 0; i < 1000000; i++) {
            double randomValue = r.nextDouble();
            long lastBit = Double.doubleToLongBits(randomValue) & 1;
            if (lastBit == 1) {
                y++;
            } else {
                n++;
            }
        }
        System.out.println(y + " " + n);
    }
}

Exemple de sortie:

250167 749833
gvlasov
la source
43
J'espère vraiment que la réponse est quelque chose de fascinant à propos de la génération aléatoire de variables à virgule flottante, plutôt que "LCG a une faible entropie dans les bits bas".
Sneftel
4
Je suis très curieux, à quoi sert un "hachage 1 bit pour double"? Je ne peux sérieusement penser à aucune application légitime d'une telle exigence.
corsiKa
3
@corsiKa Dans les calculs de géométrie, il y a souvent deux cas que nous cherchons à choisir parmi deux réponses possibles (par exemple, est-ce que pointer vers la gauche ou vers la droite de la ligne?), et parfois cela introduit le troisième cas dégénéré (le point est directement sur la ligne), mais vous n'avez que deux réponses disponibles, vous devez donc choisir de manière pseudo-aléatoire l'une des réponses disponibles dans ce cas. La meilleure façon de penser est de prendre un hachage de 1 bit de l'une des valeurs doubles données (rappelez-vous, ce sont des calculs de géométrie, donc il y a des doubles partout).
gvlasov
2
@corsiKa (commentaire divisé en deux car il est trop long) Nous pourrions commencer par quelque chose de plus simple comme doubleValue % 1 > 0.5, mais ce serait trop grossier car cela peut introduire des régularités visibles dans certains cas (toutes les valeurs sont dans la plage de longueur 1). Si c'est trop gros, devrions-nous probablement essayer des gammes plus petites, comme doubleValue % 1e-10 > 0.5e-10? Hé bien oui. Et prendre juste le dernier bit comme hachage de a, doublec'est ce qui se passe lorsque vous suivez cette approche jusqu'à la fin, avec le moins de modulo possible.
gvlasov
1
@kmote alors vous auriez toujours le bit le moins significatif fortement biaisé, et l'autre bit ne le compense pas - en fait, il est également biaisé vers zéro (mais moins), pour exactement la même raison. La distribution serait donc d'environ 50, 12,5, 25, 12,5. (lastbit & 3) == 0fonctionnerait cependant, aussi étrange que cela puisse paraître.
harold

Réponses:

165

Parce que nextDouble fonctionne comme ceci: ( source )

public double nextDouble()
{
    return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
}

next(x)fait xdes bits aléatoires.

Maintenant, pourquoi est-ce important? Parce qu'environ la moitié des nombres générés par la première partie (avant la division) sont inférieurs à 1L << 52, et donc leur significand ne remplit pas entièrement les 53 bits qu'il pourrait remplir, ce qui signifie que le bit le moins significatif du significande est toujours zéro pour ceux-ci.


En raison de l'attention que cela suscite, voici une explication supplémentaire de ce à quoi doubleressemble vraiment un en Java (et de nombreux autres langages) et pourquoi il était important dans cette question.

En gros, un doubleressemble à ceci: ( source )

double disposition

Un détail très important non visible sur cette image est que les nombres sont "normalisés" 1 telle sorte que la fraction de 53 bits commence par un 1 (en choisissant l'exposant tel qu'il en soit ainsi), que 1 est alors omis. C'est pourquoi l'image montre 52 bits pour la fraction (significande) mais il y a effectivement 53 bits dedans.

La normalisation signifie que si le code nextDoubledu 53e bit est défini, ce bit est le premier implicite 1 et il disparaît, et les 52 autres bits sont copiés littéralement dans le significande du résultat double. Cependant, si ce bit n'est pas mis à 1, les bits restants doivent être décalés vers la gauche jusqu'à ce qu'il soit mis à 1.

En moyenne, la moitié des nombres générés tombent dans le cas où le significand n'a pas du tout été décalé vers la gauche (et environ la moitié de ceux-ci ont un 0 comme bit le moins significatif), et l'autre moitié est décalée d'au moins 1 (ou est juste complètement zéro) donc leur bit le moins significatif est toujours 0.

1: pas toujours, il est clair que cela ne peut pas être fait pour zéro, qui n'a pas le plus élevé 1. Ces nombres sont appelés nombres dénormaux ou sous-normaux, voir wikipedia: nombre dénormal .

Harold
la source
16
Hourra! Juste ce que j'espérais.
Sneftel
3
@Matt C'est probablement une optimisation de la vitesse. L'alternative serait de générer l'exposant avec une distribution géométrique, puis la mantisse séparément.
Sneftel
7
@Matt: Définissez «meilleur». random.nextDouble()est généralement la "meilleure" manière pour ce à quoi il est destiné, mais la plupart des gens n'essaient pas de produire un hachage 1 bit à partir de leur double aléatoire. Cherchez-vous une distribution uniforme, une résistance à la cryptanalyse, ou quoi?
StriplingWarrior
1
Cette réponse suggère que si OP avait multiplié le nombre aléatoire par 2 ^ 53 et vérifié si l'entier résultant était impair, il y aurait eu une distribution 50/50.
rici
4
@ The111, il est dit ici que nextdoit renvoyer un int, donc il ne peut avoir que 32 bits de toute façon
harold
48

À partir de la documentation :

La méthode nextDouble est implémentée par la classe Random comme si par:

public double nextDouble() {
  return (((long)next(26) << 27) + next(27))
      / (double)(1L << 53);
}

Mais il déclare également ce qui suit (c'est moi qui souligne):

[Dans les premières versions de Java, le résultat était incorrectement calculé comme suit:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);

Cela peut sembler équivalent, sinon meilleur, mais en fait cela introduit une grande non-uniformité en raison du biais dans l'arrondissement des nombres à virgule flottante: il était trois fois plus probable que le bit de poids faible du significand soit 0 que ce serait 1 ! Cette non-uniformité n'a probablement pas beaucoup d'importance dans la pratique, mais nous nous efforçons d'atteindre la perfection.]

Cette note existe depuis Java 5 au moins (les documents pour Java <= 1.4 sont derrière un loginwall, trop paresseux pour être vérifié). Ceci est intéressant, car le problème persiste apparemment même en Java 8. Peut-être que la version "fixe" n'a jamais été testée?

Thomas
la source
4
Étrange. Je viens de reproduire ceci sur Java 8.
aioobe
1
C'est intéressant, car je viens de dire que le biais s'applique toujours à la nouvelle méthode. Ai-je tort?
harold
3
@harold: Non, je pense que vous avez raison et quiconque a essayé de corriger ce biais a peut-être fait une erreur.
Thomas
6
@harold Il est temps d'envoyer un e-mail aux gars de Java.
Daniel
8
"Peut-être que la version corrigée n'a jamais été testée?" En fait, en relisant ceci, je pense que le document traitait d'un problème différent. Notez qu'il mentionne l' arrondi , ce qui suggère qu'ils n'ont pas considéré le «trois fois plus probable» comme étant le problème, directement, mais plutôt que cela conduit à une distribution non uniforme lorsque les valeurs sont arrondies . Notez que dans ma réponse, les valeurs que j'énumère sont uniformément distribuées, mais le bit de poids faible tel que représenté au format IEEE ne sont pas uniformes. Je pense que le problème qu'ils ont résolu avait à voir avec l'uniformité globale, pas l'uniformité du bit faible.
ajb
33

Ce résultat ne me surprend pas compte tenu de la représentation des nombres à virgule flottante. Supposons que nous ayons un type à virgule flottante très court avec seulement 4 bits de précision. Si nous devions générer un nombre aléatoire entre 0 et 1, distribué uniformément, il y aurait 16 valeurs possibles:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Si c'est à cela qu'ils ressemblaient dans la machine, vous pouvez tester le bit de poids faible pour obtenir une distribution 50/50. Cependant, les flotteurs IEEE sont représentés comme une puissance de 2 fois une mantisse; un champ dans le flotteur est la puissance de 2 (plus un décalage fixe). La puissance de 2 est choisie de sorte que la partie "mantisse" soit toujours un nombre> = 1.0 et <2.0. Cela signifie qu'en effet, les nombres autres que ceux 0.0000qui seraient représentés comme ceci:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
... 
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

(L' 1avant le point binaire est une valeur implicite; pour les flottants 32 et 64 bits, aucun bit n'est réellement alloué pour contenir cela 1.)

Mais regarder ce qui précède devrait démontrer pourquoi, si vous convertissez la représentation en bits et regardez le bit faible, vous obtiendrez zéro 75% du temps. Cela est dû au fait que toutes les valeurs inférieures à 0,5 (binaire 0.1000), qui est la moitié des valeurs possibles, ont leurs mantisses décalées, provoquant l'apparition de 0 dans le bit bas. La situation est essentiellement la même lorsque la mantisse a 52 bits (sans compter le 1 implicite) comme a double.

(En fait, comme @sneftel l'a suggéré dans un commentaire, nous pourrions inclure plus de 16 valeurs possibles dans la distribution, en générant:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32 
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

Mais je ne suis pas sûr que ce soit le type de distribution auquel la plupart des programmeurs s'attendent, donc cela n'en vaut probablement pas la peine. De plus, cela ne vous rapporte pas beaucoup lorsque les valeurs sont utilisées pour générer des entiers, comme le sont souvent les valeurs aléatoires à virgule flottante.)

ajb
la source
5
Utiliser la virgule flottante pour obtenir des bits / octets / n'importe quoi au hasard me fait de toute façon frémir. Même pour les distributions aléatoires entre 0 et n, nous avons de meilleures alternatives (regardez arc4random_uniform) que random * n…
mirabilos