# Expected maximum given population size, mean, and variance

How would one estimate the maximum given population size, a few moments, and perhaps some additional assumption on the distribution?

Something like "I'm going to do $N_s≫1$ measurements out of population of size $N_p≫N_s$; will record mean $μ_s$, standard deviation $σ_s$, and maximal value in the sample $X_s$; I am willing to assume binomial (or Poisson, etc) distribution; what is the expected maximal value $X_p$ of the entire population?"

Related question: does one need to make the assumptions on the nature of the population distribution, or the sample statistics would be enough to estimate $X_p$?

Edit: the background I just added in the comments may not be clear enough. So here it is:

The end purpose it to print a set of shapes (wires, gates, etc) on a VLSI circuit that matches the designed shapes (a.k.a. targets) as well as possible. The measure of fitness of the manufactured set of shapes is the MAXIMAL difference from the target, rather than the $\sigma$ along the $~10^9$ location. The reason for evaluating the maximum difference is clear: a single short circuit is bad enough to bring down the entire chip, and then it wouldn't matter how close you were to the target in the remaining 99.999999% of the chip's location.

The problem is that it's very costly to measure the printed shape in too many locations: you literally need to look though an electron microscope at the half-manufactured chip (that's going to get trashed after the destructive measurements), adjust for metrology errors, etc. Therefore more than $10^4$ measurements is hardly ever being done. The result of those measurement is the maximal target difference $X_s$ of the SAMPLE, as well as any other sample statistics you may wish for.

And now one needs to estimate the maximal difference $X_p$ for the entire population... And now one wishes that he paid more attention in the statistics class back in college...

• Can you clarify: Do we have a 1-D distribution $D$ from which we get $N_s$ examples $\{x_i\}_{i=1}^{N_s}$? By population size $N_p$ do you mean that the values which random variable takes is finite and the size of this set of values is $N_p$? Commented Oct 14, 2013 at 20:13
• @Theja: yes, the population distribution is 1-D, and $N_p$ is the number of values from the distribution. Here's the background: the shape of a manufactured part is deemed acceptable iff the maximal deviation $X_p$ from the desired shape, as measured over $10^9$-ish locations, is small enough. In fact, $X_p$ became the measure of the shape's fitness in the industry. It's infeasible to measure (manufactured - desired) at every of the $10^9$ location, so only a sample of $10^5$-ish points are measured. Thus the question: how to estimate $X_p$ given $X_s$ of the sample and the sample's momenta. Commented Oct 14, 2013 at 20:42

Try 1:

If $X \sim U[a,b]$ (uniform, either discrete or continuous), then the MLE estimator for b (which is $\max_{x \in [a,b]} X$) is essentially $\max_{i=1,...,N_s}x_i$.

I chose uniform distribution because it is the worst case distribution in terms of entropy. This is in line with the MaxEnt (maximum entropy) principle. I also assumed a linear order in the values of the random variable.

We can make the following claim about the estimator $\max_{i=1,...,N_s}x_i$ to its mean using Hoeffdings inequality (without assuming that $X \sim U[a,b]$). Assuming $x_i$ are i.i.d from some distribution with bounded support $[a,b]$, we have \begin{align*} \mathbb{P}_{x_1,...,x_{N_s}}\left(|\max_{i=1,...,N_s}x_i - \mathbb{E}[\max_{i=1,...,N_s}x_i]| \geq \epsilon\right) \leq 2\exp\left(\frac{-2\epsilon^2}{N_s(b-a)}\right) \end{align*} Here we do not need to know $b$ exactly, any rough or crude upper bound will suffice. The above concentration is only saying that the estimator is close to the expected value of the estimator which is not the same as being close to the unknown $\max_{x \in [a,b]}X = b$.

Additional comment: I would make the measurements uniformly at random over the plane/chip so that hopefully no region with high $X$ values is missed. This observation is independent of the above.

• (1) I am curious why MaxEnt might apply here, because it seems to me that the more long-tailed the underlying distribution becomes, the more uncertain any sample-based estimate of its maximum will be. That suggests this principle might not even be relevant to the question. (2) Of what value is an inequality relating the maximum of a sample to its expectation when the concern is about the maximum of the population? This inequality seems to ignore the potentially huge negative bias in using the maximum of a sample to estimate the population max.
– whuber
Commented Oct 14, 2013 at 21:16
• (3) Why make measurements uniformly at random, which is known to leave fairly large spatial gaps with high probability, when other procedures--such as gridded samples--will surely leave smaller gaps?
– whuber
Commented Oct 14, 2013 at 21:17
• I am not applying MaxEnt per se. I chose uniform distribution over an interval as my data model. GIven that, the estimator for the upper interval bound is the answer given in my answer. I alluded to maxEnt because it says (I think) when you have no information, use the distribution with the maximum entropy. Commented Oct 14, 2013 at 21:28
• I don't believe MaxEnt says anything like that at all: you must always bear in mind the purpose of the distributional assumption. I can't decipher what else you said in that comment--too many "estimators" appear in one sentence--but nevertheless I still see nothing in this answer that directly relates properties of the sample to the maximum of the population.
– whuber
Commented Oct 14, 2013 at 21:31
• @whuber, though I did put forth the idea of sampling uniformly from the surface, I am not sure if it leaves gaps as you mention. In fact, I think one way to achieve uniform sampling is to fit a grid to your planar surface and pick some of these points uniformly at random with replacement. Commented Oct 14, 2013 at 21:33

Try 2:

This is a heuristic and I don't know of any statistical guarantees. The procedure is as follows:

• construct the empirical distribution function. If it looks exponential, convert the values to log scale to see a power-law tail.
• Fit a curve on this modified histogram. That is, do a 1-D regression. Hopefully the curve mimics the tail of a well-behaved distribution.
• Pick the point where the line intersects the x-axis in the interval $[\max_{i=1,...,N_s}x_i,\infty)$.

This is another estimator of the max value of the support of the population.