Rich Morin :: tchotchkes

Checking out Benford's Law...

I spend far too much time following links on Boing Boing, Digg, and Slashdot, but they're really rather addictive (and make a nice break from my other activities :-). Anyway, after reading a fascinating article on Benford's Law (courtesy of Digg), I decided to check its assertions for myself...

Benford's Law asserts that the distribution of the first digits in many sets of numbers will follow the function "log10(1 + 1/d)", where 'd' is the value of the digit. So, for example, '1' will the leading digit about 30% of the time. Although the article gives a plausible explanation, the assertion sounds so odd that I wanted to check it out for myself.

As it happens, I have a plausible data set very close at hand: the byte counts of the files on my Mac OS X system. So, I hacked up a bit of Perl code to walk the file tree, tallying the file sizes. Here's the code:

#!/usr/bin/env perl
#
# fdf - first digit frequency (in file sizes)
#
#  Usage: sudo fdf
#
# Benford's Law predicts the probability of 'd' occurring as the first
# digit of a number to be log10(1 + 1/d), assuming that the number has
# at least four digits.  For details, see:
#
#  "Following Benford's Law, or Looking Out for No. 1"
#  http://www.rexswain.com/benford.html
#
# Written by Rich Morin, rdm@cfcl.com

use strict;
use warnings;

use File::Find;
use POSIX qw(log10);

our (@cnt, $cnt);

{
  my ($d, $data, $hist, $path, $pred);

  $path = '/';

  finddepth(\&wanted, $path);

  print "cnt: $cnt\n\n";
  print "d  pred.  data           1         2         3         4\n";
  print "                123456789 123456789 123456789 123456789\n";

  foreach $d (1 .. 9) {

    $pred = 100 * log10(1 + 1.0/$d);
    $data = (100.0 * $cnt[$d]) / $cnt;
    $hist = '*' x int($data + 0.5);

    printf("%d (%4.1f): %4.1f  %s\n",
           $d, $pred, $data, $hist);
} }


sub wanted {

  my $s = -s $_;

  if (-f $_) {
    if ($s > 999) {
      $cnt++;
      $cnt[ substr($s, 0, 1) ]++;
} } }

There's no real magic in the code above. It just does a depth-first traversal of the file tree, calling the "wanted" function for each node. After the tree walk finishes, the code prints the results:

cnt: 766281

d  pred.  data           1         2         3         4
                123456789 123456789 123456789 123456789
1 (30.1): 32.1  ********************************
2 (17.6): 19.7  ********************
3 (12.5): 13.4  *************
4 ( 9.7):  9.4  *********
5 ( 7.9):  7.3  *******
6 ( 6.7):  6.0  ******
7 ( 5.8):  4.8  *****
8 ( 5.1):  4.1  ****
9 ( 4.6):  3.1  ***

Although there is certainly some variation from the pred(icted) values, the file system data follows the expected curve about as well as some of the data shown in the article. I also suspect that the file size distribution may be skewed by certain "systematic" effects (e.g., integral numbers of blocks in some types of binary files). In any case, it's enough to convince me...

Technorati Tags: Benford's Law, mathematics, Perl

Checking out Benford's Law... in Computers , Science , Technology - posted at Sat, 28 Jan, 22:19 Pacific | «e» | TrackBack