I'm working on a generalization of the Min-Hash algorithm to allow the meaningful comparison of ordered values such as integers. The core trick is to use deterministic randomness as a replacement for hash-functions.
However, to get this thing to work I need a way to deterministically sample from a discrete distribution. I.e. if I repeatedly draw samples from a discrete distribution I need to get the same set of values for every call.
Library functions like
sample of the language
R use standard sampling algorithms which typically use uniform-sampling from the cumulative distribution. Hence, they need some pseudo-random numbers. By seeding and resetting this random number generator prior to each call, it is possible to cut out the randomness and make things deterministic.
sample then behaves like a mathematical function.
Consider following example:
value: a b c d e f g h i j prob: 0.070 0.0774 0.083 0.090 0.096 0.103 0.109 0.116 0.122 0.129 setSeed(1) sample(value,5, prob, replace = TRUE) >>> a, c, e, j, a setSeed(1) sample(value,5, prob, replace = TRUE) >>> a, c, e, j, a
However, in case the distribution changes slightly (i.e another value
k gets inserted) the values returned from these standard sampling algorithms change drastically.
setSeed(1) sample(value, 5, prob, replace = TRUE) >>> a, c, e, j, a insert('k') >>> value: a b c d e f g h i j k >>> prob: 0.062 0.068 0.073 0.079 0.085 0.090 0.096 0.102 0.107 0.113 0.119 setSeed(1) sample(value,5, prob, replace = TRUE) >>> b, d, f, k, b
So, despite the distribution changed only marginally, the drawn sample changed broadly. However, I would like to see just a minor change, something like
>>> a, c, e, j, a <-- initial sample from initial density >>> a, c, k, j, a <-- desired sample after small density change >>> b, d, f, k, b <-- actual sample after small density change
A slow but working algorithm would be to 'simulate' this sampling by using 10.000 bins. Each bin contains a single 'value'. The number of bins of a certain value corresponds to the probability of the value in the distribution. Drawing from this simulation then works by drawing integers
i 1-10.000 and returning the value of the bin with number
i. If bins get replaced with another value, the drawn sample changes only slightly, because on every call the same bins get selected.
So the problems with standard algorithms is, that they typically sort/rearrange these bins to get the speedup. However, thats not possible in that case.
Is there a way to sample from the density distribution itself while ensuring that the change in the drawn sample is similar to the change of the distribution?