  Age of information (AoI) is a powerful metric to evaluate the freshness of
information, where minimization of average statistics, such as the average AoI
and average peak AoI, currently prevails in guiding freshness optimization for
related applications. Although minimizing the statistics does improve the
received information's freshness for status update systems in the sense of
average, the time-varying fading characteristics of wireless channels often
cause uncertain yet frequent age violations. The recently-proposed statistical
AoI metric can better characterize more features of AoI dynamics, which
evaluates the achievable minimum peak AoI under the certain constraint on age
violation probability. In this paper, we study the statistical AoI minimization
problem for status update systems over multi-state fading channels, which can
effectively upper-bound the AoI violation probability but introduce the
prohibitively-high computing complexity. To resolve this issue, we tackle the
problem with a two-fold approach. For a small AoI exponent, the problem is
approximated via a fractional programming problem. For a large AoI exponent,
the problem is converted to a convex problem. Solving the two problems
respectively, we derive the near-optimal sampling interval for diverse status
update systems. Insightful observations are obtained on how sampling interval
shall be tuned as a decreasing function of channel state information (CSI).
Surprisingly, for the extremely stringent AoI requirement, the sampling
interval converges to a constant regardless of CSI's variation. Numerical
results verify effectiveness as well as superiority of our proposed scheme.
