COS Method

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Included manuscript sections

• worked_enclosure_result.tex

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{Directed probability enclosures}\label{ch:intervals}
2 
3 \label{sec:final-4}
4 
5 \chapterlead{An analytic remainder estimate controls the error of a mathematical
6 approximation. A numerical enclosure must also control the arithmetic used
7 to evaluate it. This chapter joins directed arithmetic to explicit
8 remainder bounds, yielding an interval for an exactly supplied positive
9 spectrum under the stated arithmetic trust assumptions.}
10 
11 The notation follows the analytic development: $\kappa$ is the cumulant generating function, $b$ the support endpoint, $N$ the retained mode count, and $J_k$ the payoff coefficient. The implementation-name correspondence is given in Appendix~\ref{app:reproduction}.
12 
13 \section{Interval target}
14 
15 For a positive central quadratic form
16 \[
17 Q=\sum_{j=1}^{r}\lambda_jZ_j^2,
18 \qquad
19 \lambda_j>0,
20 \]
21 the output is not merely a point estimate.  It is
22 \[
23 \boxed{
24 \log_{10}P(Q\ge q)\in[d_-,d_+].
25 }
26 \]
27 Hence the corresponding multiplicative uncertainty satisfies
28 \[
29 \boxed{
30 \frac{p_+}{p_-}\le 10^{d_+-d_-}.
31 }
32 \]
33 
34 The finite transform and exponential prefactor are evaluated by
35 directed-rounding interval arithmetic.  The resulting interval is enlarged by
36 two independently proved analytic remainders: a support/periodization alias
37 bound and an omitted-COS-mode bound.
38 
39 \section{No exact saddlepoint is required}
40 
41 Choose any
42 \[
43 0<\theta<\frac{1}{2\lambda_{\max}}.
44 \]
45 Exponential tilting gives
46 \[
47 P(Q\ge q)
48 =
49 e^{\kappa(\theta)-\theta q}
50 S_\theta(q),
51 \]
52 where
53 \[
54 S_\theta(q)
55 =
56 E_\theta\!\left[
57 e^{-\theta(Q-q)}
58 1_{\{Q\ge q\}}
59 \right].
60 \]
61 
62 The interval proof does not require \(\theta\) to be the exact saddlepoint.
63 A high-precision saddlepoint is used only as an efficient design choice.
64 Once serialized as an exact decimal input, it is simply a valid tilt inside
65 the MGF domain.
66 
67 The same is true of the support endpoint \(b\) and the auxiliary Chernoff
68 parameter \(\eta\).  Correctness requires only
69 \[
70 b>q\ge0,\qquad b>0,
71 \qquad
72 \theta<\eta<\frac{1}{2\lambda_{\max}}.
73 \]
74 
75 \section{Rigorous support and alias control}
76 
77 Under the tilted measure,
78 \[
79 P_\theta(Q>b)
80 \le
81 \exp\left\{
82 \kappa(\eta)-\kappa(\theta)-(\eta-\theta)b
83 \right\}.
84 \]
85 
86 The full-characteristic-function cosine expansion periodizes the tilted density
87 on \([0,b]\).  Because the original positive quadratic form is supported on
88 \([0,\infty)\), the total positive-tail mass aliased back into one fundamental
89 interval is at most \(P_\theta(Q>b)\).
90 
91 The actual payoff omitted above \(b\) is at most
92 \[
93 e^{-\theta(b-q)}P_\theta(Q>b).
94 \]
95 
96 Therefore
97 \[
98 \boxed{
99 E_{\rm support}
100 \le
101 P_\theta(Q>b)
102 \left(
103 1+e^{-\theta(b-q)}
104 \right).
105 }
106 \]
107 
108 \section{Rigorous infinite-mode control}
109 
110 Define
111 \[
112 a_j=
113 \frac{2\lambda_j}{1-2\theta\lambda_j}.
114 \]
115 The normalized tilted characteristic function satisfies
116 \[
117 |\phi_\theta(t)|
118 =
119 \prod_{j=1}^r
120 \left(
121 1+(a_jt)^2
122 \right)^{-1/4}.
123 \]
124 
125 Since
126 \[
127 1+(a_jt)^2\ge(a_jt)^2,
128 \]
129 we have
130 \[
131 |\phi_\theta(t)|
132 \le
133 C_\theta t^{-r/2},
134 \qquad
135 C_\theta=\prod_j a_j^{-1/2}.
136 \]
137 
138 For the payoff coefficient
139 \[
140 J_k=
141 \int_q^b
142 e^{-\theta(x-q)}
143 \cos(k\pi x/b)\,dx,
144 \]
145 the elementary bound
146 \[
147 |J_k|\le\frac1\theta
148 \]
149 holds.
150 
151 Let
152 \[
153 \nu=\frac r2>1,\qquad N\ge1.
154 \]
155 For a finite transform retaining modes \(0,\ldots,N-1\),
156 \[
157 \boxed{
158 E_{\rm series}
159 \le
160 \frac{2C_\theta}{b\theta}
161 \left(\frac{b}{\pi}\right)^\nu
162 \left[
163 N^{-\nu}
164 +
165 \frac{N^{1-\nu}}{\nu-1}
166 \right].
167 }
168 \]
169 
170 This implemented interval backend therefore requires \(r>2\).  Lower-rank positive
171 forms can use a different tail bound and are not claimed by this theorem.
172 
173 \section{Final enclosure theorem}
174 
175 Let \(\boldsymbol S_N\) be the directed-rounding interval containing the finite
176 \(N\)-mode tilted COS sum, and set
177 \[
178 E=E_{\rm support}+E_{\rm series}.
179 \]
180 Then
181 \[
182 \boxed{
183 S_\theta(q)
184 \in
185 \boldsymbol S_N+[-E,E].
186 }
187 \]
188 
189 If the lower endpoint of this interval is positive, directed rounding gives
190 \[
191 \boxed{
192 \log P(Q\ge q)
193 \in
194 \kappa(\theta)-\theta q
195 +
196 \log\left(
197 \boldsymbol S_N+[-E,E]
198 \right).
199 }
200 \]
201 
202 All finite arithmetic in this expression is enclosed by the interval backend.
203 
204 \section{Completing the running calculation}\label{sec:worked-enclosure}
205 The factor, spectrum, and tilt of Sections~\ref{sec:worked-law}--\ref{sec:worked-tilt} now determine a complete positive-spectrum calculation at $q=40$. The exact diagonalization supplies the coefficients $(1,1,2,2)$. The implementation receives those coefficients as exact decimal literals, together with a serialized decimal approximation to the admissible tilt. Correctness does not require that decimal to equal the radical saddlepoint exactly.
206 
207 \input{worked_enclosure_result.tex}
208 
209 \begin{figure}[!htbp]
210 \centering
211 \includegraphics[width=\linewidth]{figures_production/worked_enclosure_refinement.pdf}
212 \caption{The running example under a requested multiplicative width of $2\%$. Increasing the mode count narrows the directed interval from a failing width of approximately $2.461\%$ to a passing width of approximately $1.373\%$. Diamonds mark the independent closed-form reference. The reference-centered axis is rounded for display only.}
213 \label{fig:worked-enclosure-refinement}
214 \end{figure}
215 
216 The certificate in this example concerns the tail evaluation for the exact spectrum. Its connection to the matrix is the explicit algebraic diagonalization above. It does not test a black-box eigensolver. Chapter~\ref{ch:spectrum} gives the separate post-verification theorem required for a general computed eigensystem.
217 
218 \section{Independent exact interval control through \texorpdfstring{\(10^{-5000}\)}{1e-5000}}
219 
220 For the control
221 \[
222 Q=0.02\chi^2_{80},
223 \]
224 the survival probability has the finite exact formula
225 \[
226 P(Q\ge q)
227 =
228 e^{-x}
229 \sum_{j=0}^{39}
230 \frac{x^j}{j!},
231 \qquad
232 x=\frac{q}{0.04}.
233 \]
234 
235 This finite expression was evaluated independently by directed-rounding
236 interval arithmetic, without using K-COS.  The K-COS enclosure and this exact
237 control enclosure are compared at thresholds targeting
238 \[
239 p\approx10^{-100},
240 \qquad
241 10^{-1000},
242 \qquad
243 10^{-5000}.
244 \]
245 
246 With $N=128$ and 90 interval decimal digits, the resulting K-COS widths
247 are listed below. Widths and ratios are computed from the full outward
248 endpoints before rounding the displayed values. At all three stored inputs,
249 the independent exact-law interval is fully contained in the K-COS interval.
250 
251 \begin{center}
252 \begin{tabular}{@{}rrr@{}}
253 \toprule
254 target & width in $\log_{10}p$ & multiplicative ratio minus one\\
255 \midrule
256 $10^{-100}$ &
257 $8.93\times10^{-13}$ &
258 $2.06\times10^{-12}$\\
259 $10^{-1000}$ &
260 $7.01\times10^{-12}$ &
261 $1.62\times10^{-11}$\\
262 $10^{-5000}$ &
263 $3.34\times10^{-11}$ &
264 $7.70\times10^{-11}$\\
265 \bottomrule
266 \end{tabular}
267 \end{center}
268 
269 Thus the \(10^{-5000}\) result is not merely a point estimate agreeing with a
270 reference.  For the exact supplied spectrum, it comes with a directed-rounding
271 logarithmic enclosure whose probability ratio satisfies
272 \[
273 \boxed{
274 \frac{p_+}{p_-}
275 \le
276 1+7.70\times10^{-11}
277 }
278 \]
279 The displayed upper bound is rounded upward from the directed ratio bound.
280 
281 \begin{figure}[htbp]
282 \centering
283 \includegraphics[width=\linewidth]{figures_production/figure_24_interval_deep_tail_width.pdf}
284 \caption{Directed log-probability widths on exact scaled-chi-square controls at fixed $N=128$ and 90 interval digits. Values come from the corrected full decimal endpoint records. Subtracting rounded binary64 endpoints would give a different diagnostic.}
285 \label{fig:interval-tail-width}
286 \end{figure}
287 
288 
289 
290 
291 \section{Arithmetic width versus analytic width}
292 
293 At the \(10^{-5000}\) control, the interval precision was swept from 40 to 120
294 decimal digits.  The total certified width remained essentially
295 \[
296 3.34247\times10^{-11}
297 \]
298 decades.
299 
300 Over the same sweep, the arithmetic-only width contracted from approximately
301 \[
302 7.5\times10^{-37}
303 \]
304 to
305 \[
306 6.3\times10^{-117}
307 \]
308 decades.
309 
310 \begin{figure}[htbp]
311 \centering
312 \includegraphics[width=\linewidth]{figures_production/figure_25_interval_arithmetic_vs_analytic.pdf}
313 \caption{Increasing interval precision suppresses finite-arithmetic width but leaves the analytic remainder essentially unchanged at fixed support and mode count. Both quantities are shown separately for the control near $10^{-5000}$. More digits alone cannot remove a truncation error.}
314 \label{fig:interval-arithmetic}
315 \end{figure}
316 
317 This separation is important.  Increasing numerical precision cannot improve
318 an analytic truncation theorem.  Conversely, once interval arithmetic is far
319 below the analytic error budget, numerical rounding is no longer the limiting
320 uncertainty.
321 
322 \section{Guarantee boundary}
323 
324 The directed enclosure has the following scope:
325 
326 \begin{quote}
327 For an exact supplied positive decimal spectrum of rank greater than two, the
328 backend returns a directed-rounding logarithmic probability enclosure enlarged
329 by proved analytic support/alias and omitted-mode bounds.
330 \end{quote}
331 
332 The result is conditional on correctness of the interval-arithmetic library
333 implementation.  The implementation uses \texttt{mpmath.iv}, whose
334 interval layer applies downward and upward endpoint rounding.
335 
336 A completely end-to-end guarantee beginning from an arbitrary floating-point
337 matrix requires one more layer: either a rigorously enclosed matrix-to-spectrum
338 computation, or an exact/residual completion step whose linear algebra is also
339 performed with verified interval or ball arithmetic.
340 
341 The supplied interval backend evaluates the exact spectrum directly.
342 Packet centers, moments, and their propagated errors are not evaluated with
343 directed arithmetic in this implementation. The packetized path therefore
344 retains its separate analytic guarantee.
345 
346 
347 

Back to source controls

Back to COS Method