Repository navigation
Random matches in larger sketches #51
Description
Using 14 bits per bin gives 1/2^14 chance of random match (for reasonable bin width).
Random matches ~ binomial(nbins, 2^-BBITS)
E(Random matches) = nbins / 2^BBITS
So Jaccard adjustment = obs - random / nbins - random
Random >=1 when nbins > 16k. If considering larger sketches e.g. 1M bins random =~ 60, maybe important for lower identity matches
Activity
RagnarGrootKoerkamp commentedon Aug 6, 2025
In simd-sketch I do something similar:
when doing this bottom-b bit hashing, where you only store the 1 or 8 lowest bits of each hash, there is a 1/2 resp 1/256 collision probability.
For very dissimilar genomes, the number of random matches is
binomial(s, 1/2), but the actual number of matches may actually be less thans/2(s= #bins) because the standard deviation in the binomial also goes down. In fact you can have some true kmer matches but still be belows/2.Either way, the takeaway is that you have to be careful in very low similarity settings, and make sure to report a jaccard similarity >=0.
johnlees commentedon Aug 6, 2025
Thanks @RagnarGrootKoerkamp! Will sort this here too