The actual title is “19 random digits is not enough to uniquely identify all human beings”.
The tl;dr is that you need at least 30 digits so it’s safe to assign a random number to a person with a close to zero probability of already being assigned.
I’m not really sure why the author is talking about 19 digits. Must be a reference to something I guess but I really don’t know what.
Also this doesn’t mention for how long this is valid for. New people keep getting born, so at some point 30 numbers won’t be enough unless we don’t care about reuse of the ones where people might be long gone.
Hmmm, 64 bits happens to work out as around 19.27 decimal digits. Maybe there's a connection here, although due to the nature of digits 19.27 effectively means up to 20 digits.
Agree on the 64 bit guess. And note that digits are exponential so going to 38 digits (128 bits) can account for 10 million times as many people as 30.
I can’t say what inspired 19 in the mind of the author, but the thing on the page is that 19 is the tipping point. It goes from 96% collision at 19 to 27% at 20. It’s the most amount of digits where you’ll probably have a collision.
The UUID scheme uses random digits. The article states that 19 random decimal digits (about 63 bits) yields a collision probability of 96%. More digits lowers the probability of collision to 0.0003% at 25 decimal digits (83 bits).
So yeah, UUID is great, but only because it uses 128 random bits, which is pretty much exactly along the lines of what the article is asserting.
> Suppose that you assigned everyone an 19 digit number. What is the probability that two human beings would have the same number?
If I assigner the numbers, I would carefully print 8 billion or so slips with different numbers, and place them in an urn. For each person, I'd draw from the urn, and then the probability of me assigning the same number to two humans is related to IT failures during generation. How many dollar bills share a serial number unintentionally?
A random-number scheme provides a way for any entity to generate an identifier without collaboration (this is why GUIDs are so popular). Your scheme, yes, provides a way to assign guaranteed unique identifiers, but at the cost of a centralized generator — both a performance and an authority bottleneck.
Well, if your timestamps include yy/mm/dd, I presume it would be exceedingly unlikely to get a collision even with rounding the hours and mins and secs.
What? What are we being pedantic about here exactly?
The quoted sentence is found immediately below the heading "19 random digits is not enough to uniquely identify all human beings" in the linked article. So... actually, it is specifically talking about random numbers.
And then the response...
> If I assigner the numbers, I would carefully print 8 billion or so slips with different numbers, and place them in an urn. For each person, I'd draw from the urn, and then the probability of me assigning the same number to two humans is related to IT failures during generation. How many dollar bills share a serial number unintentionally?
Is pretty blatantly describing a randomization procedure, if not going quite so over-explaining far to say "I draw from an urn without replacement and with some level of randomization to my movements and without knowledge or any tactile or other hints of which slip of paper is which"...
That is an alternative procedure, but it doesn’t seem (?) to provide any advantages over the randomized in a urn procedure, and it also doesn’t seem to remove the centralization problem.
Why is randomization important? And centralization likewise seems unimportant, as generating or sending a single auto-incrementing index number is really, really fast.
This is literally the technique I use at work for keeping track of part numbers: There's a single server that my individual CAD users can ask for a part number to describe the components of their assemblies, it does nothing but generate sequential, unique numbers. Engineers can't draw millions of parts per second, so it just works...and there's no probabilistic element with associated birthday paradox to the uniqueness of those IDs.
There are only 4.5 people born per second for this hypothetical server to handle in the long term. And at INSERT speeds of something like 3M/second, you could theoretically handle the initial storm of requests to serve all current living humans in about an hour. With 2^64 records, this scheme should be good for about 100 billion years assuming population growth levels off. That's a long time for that assumption to hold true, but I think optimizing for an event that might be only 50 billion years away is a little premature (also, the timeout when querying this server from Alpha Centauri might limit your transaction rate, but again, premature optimization).
That's barely even enough to cover everyone alive right now, much less everyone from here on. This is one thing we don't need to fuck up on. I think we'd need what, a trillion numbers? Two or three? How long do you think humans will exist as a species?
For once it'd be nice if we punted the problem a lot further than 100 years down the road.
Why 19 is important: log(2^63) ~= 19, which means a random 64-bit integer is not long enough to uniquely identify all human beings. A 128-bit integer or UUID is
2^63 allows giving each of the 8 billion people on earth over a billion numbers each with no repeats. 19 digits is plenty, since it only takes 10 digits to count all the people.
So, if you allocate numbers sequentially with a central authority, 10 digits would be enough.
The birthday paradox says that probability of collision with random identifiers becomes very big (a half or so) as soon as the number of instances approaches the square root of the number of available identifiers. In other words, if we used 20 digits, the birthday paradox rule of thumb would predict a probability of collision of around a half. (That is borne out by Lemire's table, which states 27%, which is close enough given the approximations here).
The solution proposed here is to use at least 30 digits; I wonder whether that is a good rule of thumb in general: to avoid collisions with a N-bit hash function, do not hash more than 2^(N/3) elements.
At any rate, hashing the 2^33 humans with 128 bits is good enough (probability of collision < 1e-18), and with 256 bits definitely.
This is the most dystopian thing I've read in a while. Prison Planet Earth, where everyone is uniquely identified by a number, perhaps surgically implanted on an RFID tag? How much compute resource would be needed to create an AI minder for each and every human on top of that, constantly updating their social credit score on a daily basis?
Just to note, an explicit social credit score to many would be more preferable and transparently accessible than the the data widely collected and used by companies to gauge your social credit in the west: bank records, employment history, credit, rental history, civil court records, etc, all freely available with common reporting software.
If you don't live in the extreme 3rd world, you probably already have a unique identifier in the form of "Country or Territory+ID number". It turns out relying on names when billions of people are using the same list of a couple hundred names is troublesome for record keeping.
Your reasoning logic, applied consistently, would consider almost everything we have today dystopian. For example:
"Using the Hindu-Arabic numeral system instead of the Roman numeral system is the most dystopian thing I've heard about in a while. Prison Planet Earth, where everyone is uniquely identified by a number, perhaps surgically implanted on an RFID tag? How much compute resource would be needed to create an AI minder for each and every human on top of that, constantly updating their social credit score on a daily basis?"
It's the slippery slope argument taken to an extreme. The way to fight the slippery slope fallacy is to fight against the things that may be dystopian/bad. Not argue that anything that is good/neutral is bad because it may potentially make some minor dystopian/bad outcome slightly more likely. If you do want to make such an argument, then you have to weigh the pros vs the cons.
And it's very hard to see how a word problem to illustrate the Birthday Paradox comes anywhere close to the bad outweighing any possible benefit from it.
Given they’ve already collided on the 19 digit numbers, then it’s just the probability of having the same birthday: 1/365, smoothing over the rough edges of the real world.
If we’re not taking them as already collided, you multiply the two probabilities since they’re independent.
Edit: I realize you’re probably asking a more complex question I don’t yet know the answer to. Like a double birthday paradox.
My second answer is a lower bound on the correct answer and extremely close to correct. Think of finding the ID collision first.
The probability of having at least one ID collision where they also share the same birthday is pr(2 matching ids) * pr(birthday match in 2 people) + pr(3 matching ids) * pr(birthday match in 3 people)...
The probability of having 3 matching IDs is extremely low. Assume you already have a match of size 2. Now you're looking for 1/10^19 match with ~1/10^10 draws. Not good odds. So we can ignore everything after the ID match of size 2, and get very close with 96% * 1/365 or 0.26%.
> If you want the probability to be effectively zero, you should use 30 digits or so.
You really don't need it to be effectively zero. Just significantly less than other sources of error. For 8 billion people, a 3% chance of there being single error somewhere on the whole planet is pretty good on the scale of issues that the QA team needs deal with. Especially when the fix is: Roll a second random number for that single unlucky person on Earth. That's pretty easily auto-detected and auto-fixed at generation time.
I worked on a big game that used 32-bit hashes of asset names even though we expected to get on the order of 10 collisions across the dataset. The solution was to detect collisions and tell artists to tweak their file names. Happened about 10 times over the course of many years and hundreds of thousands of assets.
If everyone who's generating the numbers can query a global centralized database, why would they be random in the first place? Isn't the whole point of a system like uuid (which this seems to be leaning in the general direction of) to avoid that sort of thing being necessary?
> If the title contains a gratuitous number or number + adjective, we'd appreciate it if you'd crop it. E.g. translate "10 Ways To Do X" to "How To Do X," and "14 Amazing Ys" to "Ys." Exception: when the number is meaningful, e.g. "The 5 Platonic Solids."
...but what they don't tell you is that at some point, somebody decided it would be a good idea for the site to automatically remove numbers from titles, with no regard for whether they're "meaningful".
The social security administration in the US solved this long ago. Reserve a few bits for “which source generated this integer”, then go sequential, or random w/o replacement for each shard.
(Note that SSN’s were not meant to be unique when this scheme was invented. They were designed to be reused periodically. Name, DOB and SSN should be unique though.)
Given the requirement to detect collisions and a process to reissue an ID for various legal reasons, I don't see a problem. In fact, don't use too many digits. If you use too many digits, collisions will be so rare that when they occur nobody will know how to handle them. Better to have a process that gets exercised a few times a year at minimum.
Another advantage to greatly-overeingineered random string lengths is that it makes brute-force namespace search technically infeasible. This is an increaasing problem with PSTN (public switched telephone networks) where there are simply too few digits in a phone number to prevent comprehensive dialing attacks. (Number reuse would be another principle problem.)
Long ago I'd read a Douglas Hofstadter essay (probably from his Scientific American puzzles column and compiled in Metamagical Themas) where he'd commented on the apparent idiocy of having very long account numbers which were clearly far larger than the possible object space.
That critique fails to consider any number of points, including the challenges of non-coordinated UUID assignments (as Lemire writes), the practice of coding other semantic information into parts of a larger string (e.g., branch or office identifiers, years, or other redundant information), systems which have grown out of mergers of multiple independent systems (where accounts from systems A and B might have collided, so A and B now require distinguishing, as well as C, D, E, ...), and as I've noted, the ease of searching the namespace for valid / assigned values.
72 comments
[ 4.7 ms ] story [ 140 ms ] threadThe tl;dr is that you need at least 30 digits so it’s safe to assign a random number to a person with a close to zero probability of already being assigned.
I’m not really sure why the author is talking about 19 digits. Must be a reference to something I guess but I really don’t know what.
Also this doesn’t mention for how long this is valid for. New people keep getting born, so at some point 30 numbers won’t be enough unless we don’t care about reuse of the ones where people might be long gone.
It:
- is a standard
- adoption is widespread in computing platforms
- addresses the birthday problem (in v4, chances of a collision in a 103 trillion set is 1 in a billion)
So yeah, UUID is great, but only because it uses 128 random bits, which is pretty much exactly along the lines of what the article is asserting.
https://en.wikipedia.org/wiki/Universally_unique_identifier#...
Does that mean if you randomly assign ID numbers to 8 billion people you’d get 8 collisions?
If I assigner the numbers, I would carefully print 8 billion or so slips with different numbers, and place them in an urn. For each person, I'd draw from the urn, and then the probability of me assigning the same number to two humans is related to IT failures during generation. How many dollar bills share a serial number unintentionally?
https://shinesolutions.com/2018/01/08/falsehoods-programmers...
to what degree do you think birth times are actually rounded rather than accurately recorded?
very much not done :)
The quoted sentence is found immediately below the heading "19 random digits is not enough to uniquely identify all human beings" in the linked article. So... actually, it is specifically talking about random numbers.
And then the response...
> If I assigner the numbers, I would carefully print 8 billion or so slips with different numbers, and place them in an urn. For each person, I'd draw from the urn, and then the probability of me assigning the same number to two humans is related to IT failures during generation. How many dollar bills share a serial number unintentionally?
Is pretty blatantly describing a randomization procedure, if not going quite so over-explaining far to say "I draw from an urn without replacement and with some level of randomization to my movements and without knowledge or any tactile or other hints of which slip of paper is which"...
1. Give the first person who asks the number 0000000000000000001.
2. Give the next person the previous person's number plus one.
3. Repeat.
The drawing-from-an-urn randomization or hashing is unnecessary if you just start with 8 billion or more numbers.
This is literally the technique I use at work for keeping track of part numbers: There's a single server that my individual CAD users can ask for a part number to describe the components of their assemblies, it does nothing but generate sequential, unique numbers. Engineers can't draw millions of parts per second, so it just works...and there's no probabilistic element with associated birthday paradox to the uniqueness of those IDs.
There are only 4.5 people born per second for this hypothetical server to handle in the long term. And at INSERT speeds of something like 3M/second, you could theoretically handle the initial storm of requests to serve all current living humans in about an hour. With 2^64 records, this scheme should be good for about 100 billion years assuming population growth levels off. That's a long time for that assumption to hold true, but I think optimizing for an event that might be only 50 billion years away is a little premature (also, the timeout when querying this server from Alpha Centauri might limit your transaction rate, but again, premature optimization).
* Better support for people born in an area without an internet connection (or with a spotty internet connection).
* No need to agree on a single issuing authority.
People are clever though and just began using the length of their string as their personal ID.
Edit: Also, would you mind changing that statement to not leave a preposition shooting off the end like Wile E Coyote?
This is the kind of pedantry up with which I will not put.
For once it'd be nice if we punted the problem a lot further than 100 years down the road.
There are about 8 * 10^9 people, or nearly 10^10.
So, if you allocate numbers sequentially with a central authority, 10 digits would be enough.
The birthday paradox says that probability of collision with random identifiers becomes very big (a half or so) as soon as the number of instances approaches the square root of the number of available identifiers. In other words, if we used 20 digits, the birthday paradox rule of thumb would predict a probability of collision of around a half. (That is borne out by Lemire's table, which states 27%, which is close enough given the approximations here).
The solution proposed here is to use at least 30 digits; I wonder whether that is a good rule of thumb in general: to avoid collisions with a N-bit hash function, do not hash more than 2^(N/3) elements.
At any rate, hashing the 2^33 humans with 128 bits is good enough (probability of collision < 1e-18), and with 256 bits definitely.
"Using the Hindu-Arabic numeral system instead of the Roman numeral system is the most dystopian thing I've heard about in a while. Prison Planet Earth, where everyone is uniquely identified by a number, perhaps surgically implanted on an RFID tag? How much compute resource would be needed to create an AI minder for each and every human on top of that, constantly updating their social credit score on a daily basis?"
It's the slippery slope argument taken to an extreme. The way to fight the slippery slope fallacy is to fight against the things that may be dystopian/bad. Not argue that anything that is good/neutral is bad because it may potentially make some minor dystopian/bad outcome slightly more likely. If you do want to make such an argument, then you have to weigh the pros vs the cons.
And it's very hard to see how a word problem to illustrate the Birthday Paradox comes anywhere close to the bad outweighing any possible benefit from it.
If we’re not taking them as already collided, you multiply the two probabilities since they’re independent.
Edit: I realize you’re probably asking a more complex question I don’t yet know the answer to. Like a double birthday paradox.
The probability of having at least one ID collision where they also share the same birthday is pr(2 matching ids) * pr(birthday match in 2 people) + pr(3 matching ids) * pr(birthday match in 3 people)...
The probability of having 3 matching IDs is extremely low. Assume you already have a match of size 2. Now you're looking for 1/10^19 match with ~1/10^10 draws. Not good odds. So we can ignore everything after the ID match of size 2, and get very close with 96% * 1/365 or 0.26%.
You really don't need it to be effectively zero. Just significantly less than other sources of error. For 8 billion people, a 3% chance of there being single error somewhere on the whole planet is pretty good on the scale of issues that the QA team needs deal with. Especially when the fix is: Roll a second random number for that single unlucky person on Earth. That's pretty easily auto-detected and auto-fixed at generation time.
I worked on a big game that used 32-bit hashes of asset names even though we expected to get on the order of 10 collisions across the dataset. The solution was to detect collisions and tell artists to tweak their file names. Happened about 10 times over the course of many years and hundreds of thousands of assets.
Of one option of course would be to provide different ID ranges to different issuing authorities (a la ip addresses).
The submission guidelines say:
> If the title contains a gratuitous number or number + adjective, we'd appreciate it if you'd crop it. E.g. translate "10 Ways To Do X" to "How To Do X," and "14 Amazing Ys" to "Ys." Exception: when the number is meaningful, e.g. "The 5 Platonic Solids."
...but what they don't tell you is that at some point, somebody decided it would be a good idea for the site to automatically remove numbers from titles, with no regard for whether they're "meaningful".
E.g.: <https://news.ycombinator.com/item?id=26826830> <https://news.ycombinator.com/item?id=26826830>
Search: <https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...>
You can be whatever you want to even a bee.
(Note that SSN’s were not meant to be unique when this scheme was invented. They were designed to be reused periodically. Name, DOB and SSN should be unique though.)
The random case is nice because there’s no coordination needed, but “you get this block” is not so hard for coordination.
Although I guess our ID issuing system will have to adjudicate issues of national sovereignty so maybe it is harder than it looks at first.
Long ago I'd read a Douglas Hofstadter essay (probably from his Scientific American puzzles column and compiled in Metamagical Themas) where he'd commented on the apparent idiocy of having very long account numbers which were clearly far larger than the possible object space.
That critique fails to consider any number of points, including the challenges of non-coordinated UUID assignments (as Lemire writes), the practice of coding other semantic information into parts of a larger string (e.g., branch or office identifiers, years, or other redundant information), systems which have grown out of mergers of multiple independent systems (where accounts from systems A and B might have collided, so A and B now require distinguishing, as well as C, D, E, ...), and as I've noted, the ease of searching the namespace for valid / assigned values.