Assume you have a set of unique values $V$ with a known distribution (e.g. Normal, Uniform) but unknown size $|V|$.

Assume you have function $O(t)$ that tells you the value $v \in V$ that is closest to the target value $t$

If you generate another (smallish) set values $T$ under the same distribution, I feel that you can determine an approximation of $|V|$, given $|T|$, and the RMS or something of $T-O(T)$

Is there a formula?


V = [0.090, 0.135, 0.288, 0.413, 0.434, 0.715, 0.717, 0.797, 0.841, 0.904] (actual set)
T =     [0.096, 0.767, 0.900] (generated values)
O(T) =  [0.090, 0.797, 0.904] (closest values to T in V)
error = [0.006, 0.030, 0.004]

The assumption is that as $V$ grows, the error will shrink.

  • 1
    $\begingroup$ My values come from a Bernoulli$(1/2)$ distribution. $V$ is large enough that there is at least one $0$ and one $1$ in $V$. Thus, $O(t)$ is $0$ when $t\lt 1/2$, $1$ when $t\gt 1/2$, and indeterminate when $t=1/2$. Since this will be the case no matter how large $V$ is, how do you suppose $|V|$ could possibly be estimated? $\endgroup$ – whuber Sep 18 '17 at 20:36
  • $\begingroup$ What is $t$, the target value? Are you estimating something from a distribution? Perhaps you can include one concrete example and show how it works, and then ask for a generalisation. $\endgroup$ – Gijs Sep 18 '17 at 20:41
  • $\begingroup$ @Gijs $t$ can be any value. $O(t)$ just magically polls $V$ for the nearest value. $T$ is a generated set with the same distribution as $V$ to test $V$ against. $\endgroup$ – guest Sep 18 '17 at 21:00

If you know the distribution of $V$, find the distribution of the error of $O(t)$, which is indeed a formula of $N$, then given the observed errors you may try and derive the maximum likelihood estimator for $N$.

The distribution of the error of $O(t)$ is not easy I would think but you can start with this question and it's answers: Spacings between discrete uniform random variables.

  • 1
    $\begingroup$ could you post the formula please, at least for uniform or normal distributions? $\endgroup$ – guest Sep 19 '17 at 16:37

In the absense of a better answer I will use the following

Given Uniform distribution: $|V| \approx$ (1/error) - 1

this conclusion was reached by looking at ideally distributed sets, and their element's distance from an extremity:

[0.5] 1/2 => 1
[0.33, 0.66] 1/3 => 2
[0.25, 0.50, 0.75] 1/4 => 3
[0.2, 0.4, 0.6, 0.8] 1/5 => 4
  • $\begingroup$ What is "error" in this answer? How is it computed from the $|T|$ ordered pairs $(t_i, O(t_i)),\ t_i\in T$ generated by your procedure? $\endgroup$ – whuber Sep 19 '17 at 17:31
  • $\begingroup$ MAE or RMSE should both be fine. I'm not sure which is better though $\endgroup$ – guest Sep 20 '17 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.