Benford's Law | Hacker News Reader

Benford's Law

en.wikipedia.org

107 pointsHooke44 comments

Did my thesis trying to apply insights from Benford's law to the design of the adders in your CPU. The idea was you make your low order bits, which see more activity, slower and more power efficient and your high order bits faster and less efficient. Meet the same timing overall but with less energy on average. Sadly, memory addresses were close to pure entropy for my purposes and the savings I was able to get were only around 5%, not enough for all the effort.

Hm, wouldn't that pay off with time though?

We try things, and sometimes, they even work. Good practice for when you do something that is worth the effort.

Benford's law works for random variables drawn from a uniform distribution whose upper bound is itself a random variable with a uniform distribution. But memory addresses are not drawn from such a distribution. The upper bound of the distribution of memory addresses is almost always a power of 2.

Yes, the fact that adders deal with so many memory addresses in practice means that the distribution of numbers I saw didn't end up working very much like Benford's law. The non-address data did but they weren't a large enough fraction of what was added together.

Isn't the power consumption of a modern adder defined by the power of the carry chain activity rather than the bits? And I have no reason to believe that the carry chains obey Zipf's/Benford's law (average carry chain length is log2(n)).

Bits are a local and transistor dominated function. Carry chains are non-local and interconnect dominated function.

As an example I can twizzle between adding 0 to 0 and 0 to 1 all day long with very little power. If however I start adding 65535 to 0 and 65535 to 1, I'm going to start activating enormous amount of power.

This depends in some part on your adder design. For the simplest adder, a ripple-carry adder, your power consumption is gong to scale with the width of the adder and an addition will take time proportional to the width to perform, with an energy cost proportional to to the width. This sort of adder doesn't really have any long lines for carrying bits long distances, everything is local once the data arrives at the adder.

With carry-bypass or carry-lookahead you have a time of the square root of the width and the costs are both proportional to the width, a constant factor larger than with a ripple adder. These are the ones used in most higher performance CPUs, or were back in 2007 when I thesing. You have some long lines here but never more than square root width and a small number compared to the number of transistors.

With tree adders you can add numbers in time proportional to the log of the width, costing a number of gates that grows as the square of the width. Now, if you assume that the inputs are all equally likely to be ones or zeros with no correlations then carry chains aren't likely to propagate very far up the tree. But as you point out if you happen to have an addition that creates a long carry chain then you'll end up switching most of the gates and using a lot of power. One of the things in my thesis that was actually practically useful was showing that you do frequently get long carry chains on real data meaning that the naive approach of counting gates works better for analyzing tree adders than trying to derive activity factors from simplified models of the inputs. These ones also have particularly long lines that have to be switched for long carry chains, and lots of them.

I got my data from using this tool Intel puts out to instrument binaries like, say, 'ls' or 'mozilla' and reading out the inputs for every use of the adder. Well, random stretches of 100 uses anyways for the browser, otherwise I wouldn't have been able to store enough data.

Benford's Law has been widely criticized as a technique to detect election fraud. A political scientist wrote a paper describing a variation. http://www-personal.umich.edu/~wmebane/pm06.pdf He used some data from the 2006 election in Mexico just to illustrate the proposed technique.

The paper has been used extensively by critics of the election as a proof of fraud. But they haven't been able to prove fraud any other way. The paper was never meant to be used as a strong proof of anything, it was mostly exploratory.

Isn't Benford's law just a phenomenon that indicates fit to a power law distribution? I'm probably missing something, but why not just try to fit the data to a power law and use the goodness of fit as the measure?

> sn't Benford's law just a phenomenon that indicates fit to a power law distribution?

I think so. From the wikipedia article...

> Benford's law tends to apply most accurately to data that are distributed uniformly across several orders of magnitude.

In this case they are using the second-digit Benford's law. Which just makes it more mysterious. At least to me.

Benford's law does not apply to unary systems such as tally marks.

Does that mean Benford doesn't work for counting things like votes or people?

This site tests Benford's Law on 30 different public datasets.

http://testingbenfordslaw.com/mexico-population-by-county

Looks to me like Benford works just fine for tally-type data like votes and populations.

Per your example. The numbers fit the population by municipality. Probably because the counts span several orders of magnitude. Some have millions (e.g Delegaciones in Mexico city). Some have hundreds( e.g Oaxaca ) However voting places are roughly the same size.

> Benford's law does not apply to unary systems such as tally marks. > Does that mean Benford doesn't work for counting things like votes or people?

Follow the links in the bit you quoted. It means numbers that are represented in a particular way, not those that represent the number of a particular thing.

Several years ago, I was chatting with a forensic accountant in a pub, and he was explaining about the use of Bendford's law in their work. I'd never heard of the law before, which is partly why it piqued my curiosity at the time. He explained that it was often used as a very quick sniff test for them, but not as proof of innocence or guilt.

Given the relative ease with which it could be calculated and analysed, it essentially became the first thing that they'd do once they'd got hold of the books. They'd do a quick analysis of the numbers, look at the distribution, and then use the outcome to give hints at where something unusual was going on. In his experience some 70-75% of the time, if Benford's law suggested something was odd, it was actually odd.

The 2004 Venezuela referendum is proved to be fraudulent without using the Benford distribution (it is not a law). On that election the opposition votes where invented based on the number of signatures requesting the recall vote per voting table, yet these same votes follow Benford quite well. On the other hand the government votes not only not follow the Benford distribution but have a flat (uniform) distribution.

What I am trying to say is that the Benford distribution is very useful, but it is not a definite proof of anything. It can point you to where you should dig deeper.

For more info about the 2004 Venezuela fraudulent election see: http://esdata.info/pdf/medina-es.pdf (Spanish) http://esdata.info/papers

Data Genetics did a great job doing a layman's write up on Benford's law, which is still one of the most fun math things to tell my family.

Here it is:

http://www.datagenetics.com/blog/march52012/index.html

Here is an interesting analysis of Benford's Law from a digital signal processing perspective: http://www.dspguide.com/ch34.htm

That was phenomenal. Thank you. I'd encourage anyone else interested in Benford's Law to skip straight to this book chapter, because it seems that most of the other material online overlooks the heart of the matter: i.e., that the law applies to distributions that are wide compared with unit distance along the logarithmic scale, but not to distributions that are narrow.

Used this to detect tax fraud for a state government and uncover a breach (by poor suppression techniques) of medicaid data. This little law is extraordinarily useful!

I applied Bendord’s law against hard drive bad block addresses across 20,000 enterprise storage arrays that called home. In theory, drive bad block LBAs should map perfectly to Benford’s distribution. In our system, there were a number of anomalies. Digging in further, I discovered that the engineeers periodically had the drives seek to a certain location, and write a status block. This happened frequently enough that it interrupted the drives internal “swirl” algorithm that was developed to keep the head from carving a “canyon” into the medium. At a microscopic level, our drives looked like the Grand Canyon.

This is fascinating!

The only time I've heard people talking about using Benford's law to detect anomalies was in the context of election fraud. This is much more exciting and practical.

Thanks! Unfortunately the raid controller needed those blocks during boot time, or it couldn’t recover properly. I may have convinced the engineers to turn on “read after write” for those blocks.

After explaining this discovery to my manager, I also explained how Benford’s law could be used to detect fraud in his corporate travel expenses. He seemed more interested in that application.....

How Benford's Law was discovered is fascinating - one of my favorite Radiolab episodes: http://www.radiolab.org/story/91699-from-benford-to-erdos/

Can somebody summarize for us who can't listen?

This was in the days before electronic calculators, when even mechanical adding machines were expensive and people used tables of logarithms (and trig functions) to calculate. [Think of Manhattan Project days.]

Benford was using a book of such tables (even random numbers came in books, in those days) and noticed that some pages of the book were much more dog-eared than others. That led him to wonder why those particular pages were being used more than others. He discovered that it correlated with the first digit of the numbers. Pages starting numbers with low digits were used more often than pages starting with higher digits.

Interesting note from the page: "Some well-known infinite integer sequences provably satisfy Benford's Law exactly including Fibonacci numbers, factorials, and the powers of almost any number."

What are the numbers whose powers don't satisfy the law? 0 of course and any power of 10 will have only leading 1's. Any product of just 2's and 5's, probably?

Powers of two satisfy Benford's law. In order for powers of an integer k to not satisfy Benford's law, k would have to be a rational power of 10; in fact it would have to be an integer power of 10 because if 10^(m/n) is rational then it's an integer.

But a quick calculation makes it look like powers of two don't satisfy Benford's law, For example the first power of 2 which begins with 7 is 2^46, and the first power of 2 which begins with 9 is 2^53. This takes so long, roughly speaking, because 2^10 = 1024 is so close to a power of ten.

That surprised me since I saw the "generalization to digits beyond the first" in the article and it's clear that powers of 2 or 5 clearly don't have a Benford-style distribution of their last digits. However, that was a misunderstanding on my part, since that generalization says something about the first n digits, and any fixed n will eventually not include the last digit of the number.

In fact powers of any integer don't have a Benford-style distribution of their last digits, since those digits will repeat periodicially. For example powers of 2 end in 2, 4, 8, 6, 2, 4, 8, 6, ...

Yes they do. Python is a good resource for quick back-of-the-envelope calculations like this, I just tested the first digit of the powers of 2 from 0 to 9999. The percentages were 30.10, 17.61, 12.49, 9.70, 7.91, 6.70, 5.79, 5.12, and 4.58. These agree almost precisely with the Wikipedia numbers. Ditto for powers of 5.

I agree. But for powers from 1 to 50 those same percentages are 30, 20, 10, 10, 10, 8, 2, 10, 0. In particular there is only one power of 2 in this range starting in 7 and none that ends in 9. This might make someone doing hand computation suspicious. (But really you can't tell much from such a small sample.)

Had to try it! (Clojure)

     (frequencies
      (take 100
            (map #(first (str (first %)))
     	    (iterate (fn [[x y]] [y (+' x y)]) [0 1]))))
     
     => {\0 1, \1 30, \2 18, \3 12, \4 9, \5 8, \6 6, \7 5, \8 7, \9 4}

i.e. Yup, Fibonacci up to 100, 30% start with 1, 18% start with 2.

I applied it to a sizable chunk of company expense data when auditing accounts payable. It highlighted some managers who made consistent purchases from the same vendor, not the multi-million dollar fraud I was hoping to find.

    not the multi-million dollar fraud I was hoping to find.

Why were you hoping to find this?

Like Midas, it is the dream of all green auditors until they find it and realize the downsides.

Was a contributor to a short-lived website/blog for business folks. My non-de-plume was Benford :)

But prices are often $.99 cents, or $9.99, or $99.99, etc.

EDIT: Ok, ignore. Article mentioned it.

FTA:

>Distributions that would not be expected to obey Benford's Law

> ...

>Where numbers are influenced by human thought: e.g. prices set by psychological thresholds ($1.99)

> Where numbers are influenced by human thought

Fraud?

Yes.

Reply on news.ycombinator.com