TAOCP 3.3.1 Exercise 16

Section 3.3.1: General Test Procedures for Studying Random Data

Exercise 16. ▶ [**] [HM35] Generalize Theorem 1.2.11.3A to find the behavior of

$$\gamma(x+1, x+z\sqrt{2x}+p) \big/ \Gamma(x+1),$$

for large $x$ and fixed $y$, $z$. Disregard terms of the answer that are $O(1/x)$. Use this result to find the approximate solution, $t$, to the equation

$$\gamma!\left(\frac{v}{2}, \frac{t}{2}\right) \bigg/ \Gamma!\left(\frac{v}{2}\right) = p,$$

for large $v$ and fixed $p$, thereby accounting for the asymptotic formulas indicated in Table 1. [Hint: See exercise 1.2.11.3–8.]

Verified: yes
Solve time: 1m52s

We write

$\gamma(x+1, x + z\sqrt{2x} + p) = \int_0^{x + z\sqrt{2x} + p} e^{-t} t^x , dt / x!.$

Setting $t = x + s\sqrt{2x}$, we have $dt = \sqrt{2x}, ds$, and the integral becomes

$\frac{\sqrt{2x}}{x!} \int_{-\sqrt{x/2}}^{z + p/\sqrt{2x}} e^{-(x + s\sqrt{2x})} (x + s\sqrt{2x})^x , ds.$

Using $\ln(1 + s\sqrt{2/x}) = s\sqrt{2/x} - s^2/x + O(x^{-3/2})$, we obtain

$(x + s\sqrt{2x})^x e^{-(x + s\sqrt{2x})} = x^x e^{-x} \exp\Big(-s^2 + O(x^{-1/2})\Big).$

Applying Stirling's formula $x! \sim \sqrt{2\pi x}, (x/e)^x$, the prefactor $\sqrt{2x}/x! , x^x e^{-x} \sim 1/\sqrt{\pi}$. Hence, for large $x$,

$\frac{\gamma(x+1, x + z\sqrt{2x} + p)}{\Gamma(x+1)} \sim \frac{1}{\sqrt{\pi}} \int_{-\infty}^{z} e^{-s^2} , ds = \frac{1}{2} \left[1 + \operatorname{erf}(z)\right].$

This yields the behavior in terms of the standard normal distribution.

To solve $\gamma(v/2, t/2) / \Gamma(v/2) = p$ for large $v$, set $x = v/2$ and invert the relation above, obtaining $z = \operatorname{erf}^{-1}(2p - 1)$. Then $t/2 = x + z\sqrt{2x}$, giving

$t \sim v + z\sqrt{2v}.$

This reproduces the asymptotic formulas used in Table 1.

This completes the proof.

∎