Optimization-Free Concentrated Matrix-Exponentials

1. Problem Statement

The paper addresses the challenge of approximating near-deterministic, strictly positive delays using probability distributions.

• Metric: The quality of approximation is measured by the Squared Coefficient of Variation (SCV), defined as $SCV(X) = \text{Var}(X)/E[X]^2$. A deterministic delay has an SCV of 0.
• The Erlang Limit: Within the Phase-Type (PH) distribution class, the Aldous–Shepp theorem establishes a fundamental lower bound: for any distribution of order $n$, the minimum achievable SCV is $1/n$. This is achieved by the Erlang distribution. Approximating deterministic delays using Erlang laws is known as "Erlangization."
• The Matrix-Exponential (ME) Opportunity: The ME class is a broader framework than PH (ME includes PH). ME distributions have rational Laplace transforms and can theoretically achieve much lower variability than PH distributions of the same order.
• The Gap: Previous numerical studies [2, 3, 4] demonstrated that ME distributions with complex-conjugate poles could significantly surpass the Erlang bound ($SCV < 1/n$) at finite orders. However, these constructions relied entirely on high-dimensional numerical optimization. It remained an open question whether this superiority was a structural property of the ME class or merely an artifact of specific numerical searches, and whether it held asymptotically (as $n \to \infty$).

2. Methodology

The authors propose a new, explicit family of distributions called the Powered-Fejér Concentrated Matrix-Exponential (PF-CME) family. This approach is optimization-free and relies on analytical construction rather than numerical search.

• Core Construction:
  • The method utilizes the Fejér kernel $\Phi_m(\theta)$, a non-negative trigonometric polynomial of order $m$.
  • The kernel is raised to a logarithmically growing power: $r_m = \lceil \log m \rceil$.
  • The resulting function is scaled and shifted to create a density function $f_m(t)$ with a common-damping structure (all poles share the same real part, $-1$).
• Parameters:
  • Order: The algebraic order of the resulting ME distribution is $n_m = 2r_m(m-1) + 1$.
  • Scaling: The frequency parameter is set to $\omega_m = 2\pi / h_m$, where $h_m = 2 \log m + \log \log m$.
  • Shift: The distribution is shifted so its principal peak aligns with the unit delay ($t=1$).
• Analytical Framework:
  • The authors utilize the common-damping framework, where the density takes the form $f(t) = C e^{-t} G(\omega t + \phi)$.
  • They derive exact closed-form expressions for the moments ($E[X], E[X^2]$) and the SCV using basis integrals of damped trigonometric functions.
  • The proof of concentration involves decomposing the distribution into a "base cell" (within one period) and a geometric tail, bounding the Fejér kernel in different regions (peak, transition, tail) to estimate the variance.

3. Key Contributions

1. First Analytical Proof of Asymptotic Superiority: The paper provides the first rigorous, analytical proof that a specific class of ME distributions can asymptotically surpass the Erlang bound ($1/n$).
2. Optimization-Free Construction: Unlike previous "Concentrated ME" (CME) methods, the PF-CME family is defined by explicit, closed-form parameters. No numerical optimization is required to generate these distributions.
3. Exact Moments and Parameters: The paper provides exact formulas for the moments and the SCV for any index $m$, allowing for precise calculation without simulation.
4. Resolution of an Open Question: It confirms that the ability of ME distributions to beat the Erlang bound is a structural property of the class (specifically those with common damping and complex poles), not just a result of numerical search artifacts.

4. Key Results

• Asymptotic SCV Decay:
  For the PF-CME family with order $n_m$, the SCV decays as:
  $$SCV(X_m) = \Theta\left(\frac{\log^3 n_m}{n_m^2}\right)$$
  Since $\frac{\log^3 n}{n^2}$ decays faster than the Erlang bound $\frac{1}{n}$, the PF-CME family asymptotically surpasses the Erlang limit.
• Crossover Point:
  While the family is asymptotically superior, it is not superior at very low orders. The authors calculate that the PF-CME family beats the Erlang bound (i.e., $SCV < 1/n$) starting at order $n \approx 7260$ (specifically between $m=519$ and $m=520$). Below this order, optimized numerical CME methods or Erlang distributions may still be preferable.
• Numerical Stability:
  The density is non-negative by construction (due to the properties of the Fejér kernel), avoiding the Gibbs-type overshoots often seen in classical numerical inverse Laplace transformation (NILT) formulas.

5. Significance

• Theoretical Impact: The work settles a long-standing theoretical question regarding the limits of the ME class. It proves that the "variance barrier" of the Erlang distribution is not absolute for all rational-transform distributions.
• Practical Application:
  • NILT Benchmark: The PF-CME family serves as a rigorous benchmark for numerical inverse Laplace transform algorithms, offering a stable, non-negative density.
  • Hybrid Approach: The authors suggest that for moderate orders ($n < 7260$), optimization-based methods remain superior. However, for very high orders or theoretical guarantees, PF-CME provides a reliable, closed-form alternative.
• Future Directions: The paper leaves open the question of whether a purely closed-form CME family can achieve the optimal decay rate of $\Theta(n^{-2})$ (without the logarithmic factor), which would be the theoretical limit for such distributions.

In summary, Battagliola and Peralta introduce a mathematically elegant, parameter-free family of distributions that rigorously demonstrates the superior concentration capabilities of Matrix-Exponential distributions over Phase-Type distributions, bridging the gap between numerical observations and analytical theory.