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 languageR
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?
sample
samples values (pseudo-) randomly, so you should expect the output values to be rather random than predictable...sample
does not use any CDF, it just returns random integers. Also: what do you mean by sampling from density? $\endgroup$sample
works in a very simple manner: it samples values (pseudo-)randomly, by default each value with the same probability, but if you useprob
parameter it uses different probabilities as defined by user. Change in output is the expected behavior of this function if you change the input. Refer to the function documentation if it is not clear. $\endgroup$