On 11/24/17 8:58 PM, Jean-Christophe Deschamps wrote:
At 23:49 24/11/2017, you wrote:
On 11/24/17 5:26 PM, Jean-Christophe Deschamps wrote:
At 22:38 24/11/2017, you wrote:
One proof of the falsehood of your assertion is that we CAN fill a
database with some data using UIDs, and we will almost certainly
not get a collision, while you assertion we will.
This is an attempt at "proof by example". Keith is perfectly right
--mathematically speaking-- and your "proof" doesn't hold water, I
mean as a formal proof. The best proof that your "proof" isn't a
proof is that you feel obliged to add "almost certainly".
DISproof by example is a perfectly valid method. If someone makes a
claim that something is ALWAYS true, ONE counter example IS a
disproof. I said almost certainly as the chance of a collision isn't
0 (to be able to say with certainty) but is most defintely less than
the 100% claimed.
You're confusing one mathematical theorem and one practical statement.
The first is the _mathematical_ fact that any PRNG (using any fixed
number of random bits, which is what xUIDs are) will provide an
infinite number of collisions with probability 1. This is definitely
true. Of course here, the number of samples is implicitely infinite.
Your practical statement is that you can "most certainly" ignore the
possibility of collision when feeding 2^N xUIDs into a unique column
without loosing sleep. That's good enough in practice. The issue with
your "demonstration" is that 2^N is bounded, whatever finite N you
choose. Hence you don't contradict what Keith said, you just say
something different applying to restricted cases. You're speaking
about practice, while Keith told about math. You're both right, each
from his own point of view. But you can't claim to disproof a
trivially true theorem this way, by changing its premices.
An event with probability 10^-100000...000 (any finite number of
zeroes) will occur at least once, provided you run enough tries. It'll
occur an infinite number of times if you run an infinite number of
tries. Else its probability would be zero.
Your "disproof" amounts to say that 10^-100000...000 = 0
And neither Keith nor I ever said that an xUID collision will occur
with probability 1 after 2^64 samples. That would be false and that's
why people feel free to use xUIDs _AND_ sleep quietly.
JcD
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
The statement, and I quote, was
Actually a UUID or a GUID has a 100% certainty of a collision, not just
a possibility of a collision. Just as all hash algorithms which take
something and generate a shorter "hash" or "checksum" will always have
collisions. Without exception and as an absolute 100% certainty. There
is no way to avoid this mathematical certainty.
The claim makes a positive statement of a 100% chance of collision, and
makes an argument about it being a hash, and that it isn't just a chance.
Something happening at least one in an extremely large number of trials
was NEVER a 100% probability in any form of math I have heard of. The
number of records needed to have a significant chance of the collision,
is beyond any practical usage. If the claim was a non-zero chance, then
it would be true. Probability has always been related to times happened
/ times tried. So your claim is that 10^-10000... == 1, saying
something will EVENTUAL happen is a claim on non-zero probability, not
of 100% probability.
If you mean that a finite width field can't hold unique values for an
infinite of records, well, duh, why all the irrelevant references to
hashes or even that it is a UUID or a GUID.
If it was meant that EVENTUAL, after an impossibly long time, you will
get a collision, that is being absurd. I can say with better certainty
that long before that happens, the computers running this database are
going to break, so we will never get to the point of the collision.
--
Richard Damon
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
