qsys_maxima_twomoment.h File Reference

Two-moment approximation for the maximum of n iid non-negative variables. More...

#include <cmath>
#include <cstddef>
#include <string>
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for qsys_maxima_twomoment.h:

Go to the source code of this file.

Classes
struct	line::qsys::MaximaResult< T >
	Two-moment description of a maximum. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
MaximaResult< T >	line::qsys::qsys_maxima_twomoment (std::size_t n, const T &mean, const T &cs2, const T &q=num_traits< T >::from_int(0), bool exactFitted=true)
	Two-moment approximation for the maximum of n iid non-negative variables.

Detailed Description

Two-moment approximation for the maximum of n iid non-negative variables.

Templated port of matlab/src/api/qsys/qsys_maxima_twomoment.m, cross-checked against jar/src/main/java/jline/api/qsys/Qsys_maxima_twomoment.java.

THE SHAPE OF THE ANSWER. For a law with an exponential-like tail the maximum of n samples grows like c~^2 (log n + ...): doubling n ADDS a constant, it does not scale the answer. The two moments buy the SLOPE and an offset:

x_n(q) = c~^2 [log(n eta) - log log(1/q)] (1.9) E[M_n] = c~^2 [log(n eta) + gamma] cs2 >= 1: c~^2 = cs2, eta = (cs2+1)/(2 cs2^2) (1.11)-(1.12) cs2 < 1: c~^2 = sqrt(cs2), eta = exp((1-sqrt(cs2))/sqrt(cs2))

WHEN NOT TO USE IT: n must pass n* ~ cs2/q (4.22), because with a highly variable law only about n p of the samples can contend for the maximum. Measured against exact maxima the closed form is within a few percent for n >= 100 at cs2 = 4 and 16, and useless at n = 10 for cs2 = 16 – exactly what n* predicts.

AND WHEN TWO MOMENTS ARE NOT ENOUGH: below cs2 = 1 the maximum is genuinely family-dependent. An Erlang and a shifted exponential with the same two moments have maxima differing by tens of percent, diverging as n grows, because their tails decay at different rates.

ARITHMETIC. Logarithms throughout: transcendental only.

Reference: C. Crow, D. Goldberg, W. Whitt (2007). Two-moment approximations for maxima. Operations Research 55(3), 532-548.

Definition in file qsys_maxima_twomoment.h.