Skip to main content
14 of 25
deleted 26 characters in body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Analytic formula and an exponential bound

For $r \in [0, 1]$, define $\tau_m(r) \in [0, 1]$ by $$ \tau_m(r) := \frac{1}{\lambda(B_m(r))}\int_{B_m(r)} \frac{\lambda(B_m(1) \cap (B_m(1) + x))}{\lambda(B_m(1))}dx. $$

The case $r=1$ has been analysed in accepted answer. Extending user @Matt's comment, one can establish that

$$ \begin{split} \tau_m(r) &= \frac{1}{V_m^{cap}(r, 0)}\int_{0}^r ms^{m-1}V_m^{cap}(1, s/2)ds = \frac{1}{r^mV_m^{cap}(1, 0)}\int_{0}^r ms^{m-1}V_m^{cap}(1, s/2)ds\\ &= \frac{1}{V_m^{cap}(1, 0)}\int_{0}^1 ms^{m-1}V_m^{cap}(1, rs/2)ds, \end{split} $$

where $V_m(r; h)$ is the volume (i.e Lebesgue measure) of the half-lens $\{x \in B_m(r) \mid x_1 \ge h\}$.


Preamble. I propose to obtain an analytic formula for $\tau_m(r)$ in terms of special functions (mostly hypergeometric functions). We will also obtain a tight upper bound for $\tau_m(r)$.

The end result will be the following exponential decay of $\tau_m(r)$ as a function on the dimension $m$.

Theorem. For every $r \in [0, 1]$ and large integer $m$, we have the upper bound $$ \tau_m(r) \le \exp\left(-\frac{mr^2}{8-r^2}\right) + \frac{r(1-(r/2)^2)^{m/2}}{\sqrt{m\pi}}. $$ In particular, if $r=1$, then we have the upper bound $$ \tau_m(r) \le e^{-\frac{m}{7}} + \frac{2^{-m}}{\sqrt{m\pi}}. $$

enter image description here Proof. Now, it is a classical computaiton that $V_m^{cap}(1, h) = \beta_{1-h^2}\left(\frac{m+1}{2},\frac{1}{2}\right)$, where $\beta_x(a, b) := \int_0^xt^{a-1}(1-t)^{b-1}dt$ defines the incomplete beta function. In particular, $V_m^{cap}(0) = \beta_{1}\left(\frac{m+1}{2},\frac{1}{2}\right)$.

Thus, integrating by parts, we get

$$ \begin{split} V_m^{cap}(1,0)\tau_m(1) &= \int_{0}^1 s^{m-1}V_m^{cap}(rs/2)ds = \int_{0}^1 \beta_{1-(rs)^2/4}\left(\frac{m+1}{2},\frac{1}{2}\right)ds^m\\ &= \left[s^m\beta_{1-(rs)^2/4}\left(\frac{m+1}{2},\frac{1}{2}\right)\right]_0^1 + r\int_0^1 s^m(1-(rs)^2/4)^{\frac{m-1}{2}}ds \\ &= \beta_{1-(r/2)^2}\left(\frac{m+1}{2},\frac{1}{2}\right) + R_m, \end{split} \tag{1} $$ where $R_m := r\int_0^1 s^m(1-(rs/2)^2)^{\frac{m-1}{2}}ds$. Now, consider the change of variable $s = 2\sqrt{t}$. This gives $s^m(1-s^2/4)^{(m-1)/2}ds=2^mt^{n/2}\cdot(1-t)^{(m-1)/2}\cdot s^{-1/2}ds = 2^mt^{(m-1)/2}(1-t)^{(m-1)/2}$. Thus,

$$ \begin{split} R_m &= r\int_0^1 s^m(1-(rs)^2/4)^{\frac{m-1}{2}}ds = \frac{2^m}{r^m}\int_0^{(r/2)^2}t^{(m-1)/2}(1-r)^{(m-1)/2}dt\\ &=: \frac{2^m}{r^m}\beta_{(r/2)^2}\left(\frac{m+1}{2},\frac{1}{2}\right). \end{split} \tag{2} $$

Combining (1) and (2) then gives the analytic formula,

Analytic formula. For any $r \in [0, 1]$ and positive integer $m$, it holds that $$ \tau_m(r) = I_{1-(r/2)^2}\left(\frac{m+1}{2},\frac{1}{2}\right) + \frac{(2/r)^m\beta_{(r/2)^2}\left(\frac{m+1}{2},\frac{m+1}{2}\right)}{\beta_1\left(\frac{m+1}{2},\frac{1}{2}\right)}, $$ where $u \mapsto I_u(a, b) := \beta_u(a,b) / \beta_1(a, b)$ is the CDF of $(a,b)$-beta distribution.

Bounding the first term. Let $\delta := (r/2)^2$ and $p = I_{1-\delta}((m+1)/2,1/2)$. It is known since Temme (1992) that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(m+1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $1-e^{-z} \ge 2z/(2+z)\;\forall z \ge 0$, we see that

$$ \begin{split} \delta &\le 1 - t_{p}\left((m+1)/2,1/2\right) \ge 1-e^{-\frac{2Q_{1-p}(\Gamma(1/2,1))}{m+1}} \ge 1-e^{-\frac{2}{m+1}\left(\log\left(\frac{1}{p}\right) + \sqrt{\log\left(\frac{1}{p}\right)}\right)} \le \frac{2\alpha}{2+\alpha}, \end{split} $$

where $\alpha = \frac{2}{m+1}\log(1/p)$. Thus, $\alpha \ge \delta/(1 - \delta/2)$, from which

$$ \begin{split} I_{1-(r/2)^2}((m+1)/2,1/2) &= I_{1-\delta}((m+1)/2,1/2) = p = e^{-\frac{m+1}{2}\alpha} \le e^{-\frac{(m+1)\delta}{2-\delta}}\\ &\le e^{-\frac{m\delta}{2-\delta}} = e^{-\frac{mr^2}{8-r^2}} \end{split} $$

Bounding the second term. It is a well-known result that

$$ \beta_z(a,b) \equiv a^{-1}x^a{}_2F_1(a,1-b,a+1;z), $$

where $z \mapsto {}_2F_1(u, v, w; z)$ is the hypergeometric function. Thus, one computes

$$ \begin{split} (2/r)^m\beta_{(r/2)^2}\left(\frac{m+1}{2},\frac{m+1}{2}\right) &= \frac{r}{m+1}{}_2F_1\left(\frac{m+1}{2},\frac{1-m}{2},\frac{m+3}{2},(r/2)^2\right) \\ &= \frac{r}{m+1}{}_2F_1\left(\frac{1-m}{2},\frac{m+1}{2},\frac{m+3}{2},(r/2)^2\right)\\ &\approx \frac{r}{m+1}{}_2F_1\left(\frac{1-m}{2},\frac{m+1}{2},\frac{m+1}{2},(r/2)^2\right)\\ &= \frac{r}{m+1}(1-(r/2)^2)^{(m-1)/2}, \end{split} $$

where we have used the powerful identity ${}_2F_1(u, v, v; z) \equiv (1 - z)^{-u}$. On the other hand, Stirling's formula gives

$$ \beta_1\left(\frac{m+1}{2},\frac{1}{2}\right) \approx \Gamma(1/2)\left(\frac{m+1}{2}\right)^{-1/2} = \sqrt{\frac{\pi}{m+1}}. $$

Thus,

$$ \frac{2/r)^m\beta_{(r/2)^2}\left(\frac{m+1}{2},\frac{m+1}{2}\right)}{\beta_1\left(\frac{m+1}{2},\frac{1}{2}\right)} \approx \frac{r(1-(r/2)^2)^{(m-1)/2}}{\sqrt{\pi(m+1)}} $$

Putting every together then completes the proof of the theorem. $\quad\quad\quad\Box$

dohmatob
  • 6.9k
  • 1
  • 18
  • 76