vendredi 27 août 2021

Uniform Distribution: Bug or Paradox

Imagine 10 cars randomly, uniformly distributed on a round track of length 1. If the positions are represented by a C double in the range [0,1> then they can be sorted and the gaps between the cars should be the position of the car in front minus the position of the car behind. The last gap needs 1 added to account for the discontinuity.

In the program output, the last column has very different statistics and distribution from the others. The rows correctly add to 1. What's going on?

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int compare (const void * a, const void * b)
{
  if (*(double*)a > *(double*)b) return 1;
  else if (*(double*)a < *(double*)b) return -1;
  else return 0;
}

double grand_f_0_1(){
  static FILE * fp = NULL;
  uint64_t bits;

  if(fp == NULL) fp = fopen("/dev/urandom", "r");
  fread(&bits, sizeof(bits), 1, fp);
  return (double)bits * 5.421010862427522170037264004349e-020; // https://stackoverflow.com/a/26867455
}

int main()
{
  static int n = 10;
  double values[n];
  double diffs[n];
  int i, j;
  
  for(j=0; j<10000; j++) {
  
    for(i=0; i<n; i++) values[i] = grand_f_0_1();

    qsort(values, n, sizeof(double), compare);
    
    for(i=0; i<(n-1); i++) diffs[i] = values[i+1] - values[i];
    diffs[n-1] = 1. + values[0] - values[n-1];

    for(i=0; i<n; i++) printf("%.5f%s", diffs[i], i<(n-1)?"\t":"\n");

  }
  
  return(0);
}



Aucun commentaire:

Enregistrer un commentaire