Heuristically determine a value f such that a probability d/f approaches 1/2 We have a set X of N elements. We want to get a new set X' having a size M &lt; 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]) &lt; 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 ?
OK, another answer :)

Size of the set X' clearly depends on the distribution of points, choice of starting points, and random chance.

If the points are always chosen from the same distribution, I'd try drawing |X'| as a function of f and |X|. To do that, I'd just do some monte-carlo simulations.

Also notice that f is a linear function of mean distance between points.