While I find this fascinating, I'm sure this is old news to people in the business, like the people that run the grocery/chain store savings programs.
What I'd be really interested to see is why this works, and what it tells us about distribution of population by zip code. I'd imagine the places where this doesn't work as well, are the most densely populated zip codes, where the likely hood of duplicates on the given key increases, but I would never have guessed that the accuracy would be anywhere near 87%. (maybe there's alot more zipcodes than what I thought? maybe they used zip+4?)
Simple information theory; in a world of 6 billion people, 33 bits serves to uniquely identify anyone. 33 bits is a really low bar. It works because it can't hardly help but to work, sort of like the birthday paradox. In the US with approx 312 million (wikipedia) that's approximately 28.2 bits.
It doesn't tell us much about zip code distribution because zip codes are chosen to have approx the same number of people in each. As it turns out, that's exactly how you'd go about maximizing the amount of information the zip code carries... which is unsurprising since that's the entire purpose of a zip code. Gender is almost exactly one bit, and date of birth is 15ish bits with some bad uniformity assumptions, zip is another 15ish with bad uniformity assumptions[1], that's 31-ish total, subtract off 3-ish for the bad assumptions and you get 28, which covers 2^28 = 268,435,456 people, which is pretty close to the number cited (.87 times 312,000,000 = 271,440,000). I'll cop to tuning the fudge factor of three bits to nicely match the number given, but the bit count itself just comes from the space of possibilities.
In general, if you model this as an N balls in M bins problem, then even when N == M, you'd expect a fair amount of anonyonomity preserving collisions. Maybe 1/2 of people would collide. As we then double the number of bins, we'd roughly expect the number of collisions to be cut in half.
If you imagine putting 100 balls (people) into 800 = 100 * 2^3 bins (number of different birthday-zip-gender encodings) at random, about 1/8 of the bins will have more than one ball (person) [okay, this estimate is somewhat off by a smallish constant factor, it's only true that the 100th ball tossed will collide with probability 99/800 ~= 1/8 if there were no existing collisions, and the earlier balls thrown have less to collide with], and not be uniquely identifiable.
> Simple information theory; in a world of 6 billion people, 33 bits serves to uniquely identify anyone. 33 bits is a really low bar. It works because it can't hardly help but to work, sort of like the birthday paradox. In the US with approx 312 million (wikipedia) that's approximately 28.2 bits.
It's a powerful idea. I wrote a whole essay analyzing the anime _Death Note_ using the 33 bits idea (http://www.gwern.net/Death%20Note%20Anonymity) and I'm sure that's not even the tip of the iceberg.
The US population is 300 million and there's about 43,000 zip codes in the US. Assuming an even distribution, that's about 7,000 people per zip code. Cut it down to just one gender and we're at 3,500. The probability of a chosen person in that group having a a unique birthday is (364/365)^3500 = 0.0068%. Now, if we say that the person could have been born in one of the past sixty years, we get (21914/21915)^3500 = 85% as the probability that this person has been uniquely identified.
Birth date is pretty granular as well. A quick trip to the interwebs gives about 11k-12k people born each day, or 6k of each gender. There are 100k possible ZIP codes. The birth dates aren't evenly distributed, but they're reasonably close. The ZIP codes probably have a lot of clumping, but in dense urban areas they usually start cutting the areas into smaller pieces. The long tail of ZIP codes is probably well-populated. Out of 6k boys and 6k girls that share a birth date, expecting 5k of each to happen to land a unique ZIP out of 100k sounds reasonable to me.
Point of interest: there are 100K possible ZIP codes but only 42K-ish are actually in use in the US. Not that I think this makes it unreasonable for 5K of each to land unique ZIPs.
It turns out that zip codes aren't as populous as you might imagine.
As of the Y2K census, only a dozen zip codes have over 100,000 residents -- 80% of all zip codes have less than 15,000 residents, with the median zip code at 2,500.
Some zip codes have zero residents -- a few large office buildings have their own zip codes, but nobody actually has a home address there. Examples: the Empire State Building, the Pentagon, the former World Trade Center, IRS tax processing centers.
What I'd be really interested to see is why this works, and what it tells us about distribution of population by zip code. I'd imagine the places where this doesn't work as well, are the most densely populated zip codes, where the likely hood of duplicates on the given key increases, but I would never have guessed that the accuracy would be anywhere near 87%. (maybe there's alot more zipcodes than what I thought? maybe they used zip+4?)