We have a set X of N elements. We want to get a new set X' having a size M < N.
Choose a first element x from X and put it in X' for each element x in (X - X') Let x' the element from X' which is the closest to x (that is x' = argmin distance(x, x') for all x' in X') d = distance(x, x') if ( uniform_random([0,1]) < d / f ) add x to X'
How can I choose the value f such that the size of the set X' at the end will be for instance the half of the size of X (that is, M approximates or equals N/2). I suppose that I should choose f such that the probability d / f equals 1/2 (or approximates 1/2 for most values of d), but how to do that ?
Additional details (that are not necesarily usefull for this question): the elements are actually vectors, and the distance between two vectors is the euclidean distance.
Note that d is not a constant (while f is a constant that I want to fix). d depends on the distance between each element x and its closest element x', so d is not always the same.
Suppose that the order in which we test the elements x is always random. For any set X, if we choose the value of f relatively small then we will get a relatively hight number of elements in the final set X', if we choose the value of f relatively big we will get a relatively small number of elements in the final set X'. If I experimentally vary the value of f many times I can always (for any set X) find a value of f for which the final number of elements in X' approaches N/2. So experimentally I can find a good value for f if I test many times which different values of f, but I want to determine it heuristically (not by testing many times and varying f).
EDIT: By the way, the only one method which seems to give an acceptable results is: let mean_d the mean distance of each x to its nearest x'. We put f = 2mean_d, thus the probability d/f = d/(2mean_d) usually approximate 1/2 if the most of distances d are not far from mean_d. We also put f = (2mean_d)+d' where d' depends on how many distances are higher than mean_d, or f = (2mean_d)-d' where d' depends on how many distances are less than mean_d. Does this make sense ? Do you think it can be improved ?