Rademacher function and Khinchin’s equality

By | November 14, 2015

Fair coin에 대하여 이 상황을 설명할 수 있는 또 다른 방법이 있는데, Rademacher function을 이용하는 방법이 있다. 함수는 다음과 같이 정의된다:

    \[ r_{j}\left(t\right):=\sign\left(\sin\left(2\pi2^{j}t\right)\right),\quad0<t<1,\quad j=0,1,2,\dots. \]

여기서 sample space는 \left(0,1\right)이며 probability measure는 \left[0,1\right]에서의 Lebesgue measure이다. 그러면 모든 n\ge1에 대하여

    \[ m\left(\left\{ r_{j_{1}}=\varepsilon_{1},\dots,r_{j_{n}}=\varepsilon_{n}\right\} \right)=2^{-n} \]

를 얻는다. 여기서 \varepsilon_{j}\in\left\{ -1,1\right\}이다. 이 사실은 \left\{ r_{j}\right\}가 independent random variable이라는 것을 보여준다.

Lemma. r_{j}를 Rademacher sequence라 하자. 자연수 N에 대하여 \left\{ a_{j}\right\} _{j=1}^{\infty}\subset\mathbb{C}라 하자. 그러면

    \[ \prob\left(\left\{ \left|\sum_{j=1}^{N}r_{j}a_{j}\right|>\lambda\left(\sum_{j=1}^{N}\left|a_{j}\right|^{2}\right)^{\frac{1}{2}}\right\} \right)\le4e^{-\frac{\lambda^{2}}{2}} \]

이다.

Proof. 우선 a_{i}\in\mathbb{R}이라 가정하자. Rademancher function의 정의는

    \[ r_{j}\left(t\right)=\mathrm{sign}\left(\sin\left(2\pi2^{j}t\right)\right)\quad0<t<1\quad j=0,1,\dots \]

이다. 그러므로 임의의 양수 \rho에 대하여 \left\{ r_{j}\right\}가 independent이므로

    \[ \Exp\left[e^{\rho S_{N}}\right]=\prod_{j=1}^{N}\Exp\left[e^{\rho r_{j}a_{j}}\right] \]

를 얻는다.

그리고 A_{j}=\left\{ 0<t<1:r_{j}\left(t\right)=1\right\}, B_{j}=\left\{ 0<t<1:r_{j}\left(t\right)=-1\right\}라 하면 m\left(A_{j}\right)=\frac{1}{2}, m\left(B_{j}\right)=\frac{1}{2}이므로 임의의 1\le j\le N에 대하여

    \begin{align*} \Exp\left[e^{\rho r_{j}a_{j}}\right] & =\int_{0}^{1}e^{\rho r_{j}\left(t\right)a_{j}}dt\\ & =\frac{1}{2}\left[e^{a_{j}\rho}+e^{-a_{j}\rho}\right]\\ & =\cosh\left(a_{j}\rho\right) \end{align*}

를 얻는다. 그리고 임의의 실수 x에 대하여 \cosh x\le e^{\frac{x^{2}}{2}}이다. 이는

    \[ e^{\frac{x^{2}}{2}}-\cosh x=\sum_{n=0}^{\infty}\left(\frac{1}{n!2^{n}}-\frac{1}{\left(2n\right)!}\right)x^{2n} \]

이로부터 \left(2n\right)!\ge n!2^{n}이 음이 아닌 정수 n에 대하여 성립하기 때문에 부등식을 얻는다. 그러므로

    \begin{align*} \Exp\left[e^{\rho r_{j}a_{j}}\right] & \le\prod_{j=1}^{N}e^{\rho^{2}a_{j}^{2}/2}\\ & =\exp\left(\rho^{2}\sum_{j=1}^{N}\frac{1}{2}a_{j}^{2}\right) \end{align*}

이다. \sigma^{2}=\sum_{j=1}^{n}a_{j}^{2}이라 하자. 그러면 양수 \lambda>0에 대하여

    \begin{align*} &\relphantom{=} \prob\left(\left\{ S_{N}>\lambda\sigma\right\} \right)\\ & =\prob\left(\left\{ \rho S_{N}>\lambda\rho\sigma\right\} \right)\\ & =\prob\left(\left\{ e^{\rho S_{N}}>e^{\lambda\rho\sigma}\right\} \right)\\ & \le\frac{\Exp\left[e^{\rho S_{N}}\right]}{e^{\lambda\rho\sigma}}\le e^{\rho^{2}\sigma^{2}/2}e^{-\lambda\rho\sigma}\le e^{-\frac{\lambda^{2}}{2}} \end{align*}

를 얻는다. 여기서 마지막 부등식은 \rho에 대해서 극댓값을 얻어내는 결과다.

비슷한 방법으로

    \[ \prob\left(\left\{ S_{N}<-\lambda\sigma\right\} \right)\le e^{-\frac{\lambda^{2}}{2}} \]

를 얻어내므로

    \[ \prob\left(\left|S_{N}\right|>\lambda\sigma\right)\le2e^{-\frac{\lambda^{2}}{2}} \]

를 얻는다.

이제 a_{j}\in\mathbb{C}라 하면 실수부와 허수부로 나누어서 공략을 하면

    \[ \prob\left(\left|S_{N}\right|>\lambda\sigma\right)\le4e^{-\frac{\lambda^{2}}{2}} \]

를 얻는다.


Theorem (Khinchin’s equality). 1\leq p<\infty이라면 임의의 자연수 N\left\{ a_{j}\right\} _{j=1}^{N}\subset\mathbb{C}
대하여

    \[ \Exp\left[\left|\sum_{j=1}^{N}r_{j}a_{j}\right|^{p}\right]\approx_{p,d}\left(\sum_{j=1}^{N}\left|a_{j}\right|^{2}\right)^{\frac{p}{2}} \]

이다.

Proof. (i) p=2일 때는 직교성에 의해서 쉽게 보인다. 즉

    \begin{align*} \Exp\left[\left|\sum_{j=1}^{N}r_{j}a_{j}\right|^{2}\right] & =\sum_{i,j=1}^{n}\Exp\left[r_{j}\overline{r_{i}}a_{i}\overline{a_{j}}\right]\\ & =\sum_{i=1}^{n}\left|a_{i}\right|^{2}\Exp\left[\left|r_{i}\right|^{2}\right]\\ & =\sum_{i=1}^{N}\left|a_{i}\right|^{2} \end{align*}

를 얻는다.

(ii) 1<p<\infty일 때 upper bound를 구해보도록 하자. \sum_{j=1}^{N}\left|a_{j}\right|^{2}=1이라 하자. S_{N}을 이전과 같이 S_{N}=\sum_{j=1}^{N}a_{j}r_{j}이라 하자. 그러면 앞의 Lemma에 의하여

    \begin{align*} & \relphantom{=}\Exp\left[\left|S_{N}\right|^{p}\right]\\ & =\int_{0}^{\infty}\prob\left(\left\{ \left|S_{N}\right|>\lambda\right\} \right)p\lambda^{p-1}d\lambda\\ & \le\int_{0}^{\infty}4e^{-\frac{\lambda^{2}}{2}}p\lambda^{p-1}d\lambda=:C\left(p\right)<\infty \end{align*}

이다.

(iii) 1<p<\infty일 때 lower bound를 구해보도록 한다. 이는 (i)과 (ii), duality에 의해 얻는다. 그러면 (i)과 Hölder’s inequality에 의하여

    \begin{align*} \sum_{j=1}^{N}\left|a_{j}\right|^{2}= & \Exp\left[\left|\sum_{j=1}^{N}r_{j}a_{j}\right|^{2}\right]\\ & \le\Exp\left(\left|\sum_{j=1}^{N}a_{j}r_{j}\right|^{p}\right)^{\frac{1}{p}}\Exp\left(\left|\sum_{j=1}^{N}a_{j}r_{j}\right|^{p^{\prime}}\right)^{\frac{1}{p^{\prime}}} \end{align*}

을 얻는다.

1<p^{\prime}<\infty이므로 (ii)에 의하여

    \[ \Exp\left(\left|\sum_{j=1}^{N}a_{j}r_{j}\right|^{p^{\prime}}\right)^{\frac{1}{p^{\prime}}}\lesssim_{p}\left(\sum_{j=1}^{N}\left|a_{j}\right|^{2}\right)^{\frac{1}{2}} \]

를 얻는다. 그러므로

    \[ \left(\sum_{j=1}^{N}\left|a_{j}\right|^{2}\right)^{\frac{1}{2}}\lesssim_{p}\Exp\left(\left|\sum_{j=1}^{N}a_{j}r_{j}\right|^{p}\right)^{\frac{1}{p}} \]

를 얻는다.

(iv) p=1일 때 Hölder’s inequality에 의하여

    \begin{align*} & \relphantom{=}\Exp\left[\left|S_{N}\right|^{2}\right]\\ & =\Exp\left[\left|S_{N}\right|^{\frac{2}{3}}\left|S_{N}\right|^{\frac{4}{3}}\right]\\ & \le\Exp\left[\left|S_{N}\right|\right]^{\frac{2}{3}}\left(\Exp\left[S_{N}\right]^{4}\right)^{\frac{1}{3}} \end{align*}

를 얻으며 (ii)에 의하여 \left(\Exp\left[S_{N}\right]^{4}\right)^{\frac{1}{3}}\apprle_{p}\left(\sum_{j=1}^{N}\left|a_{j}\right|^{2}\right)^{2}를 얻는다. 그러므로

    \begin{align*} \Exp\left[\left|S_{N}\right|\right]^{\frac{2}{3}}\left(\Exp\left[S_{N}\right]^{4}\right)^{\frac{1}{3}} & \lesssim_{p}\left(\Exp\left|S_{N}\right|\right)^{\frac{2}{3}}\left(\sum_{j=1}^{N}\left|a_{j}\right|^{2}\right)^{\frac{2}{3}}\\ & \lesssim_{p}\left(\Exp\left|S_{N}\right|\right)^{\frac{2}{3}}\left(\Exp\left|S_{N}\right|^{2}\right)^{\frac{2}{3}} \end{align*}

를 얻는다. 따라서

    \[ \Exp\left[\left|S_{N}\right|^{2}\right]\lesssim_{p}\left(\Exp\left|S_{N}\right|\right)^{2} \]

를 얻어서 증명이 끝난다.


Leave a Reply

Your email address will not be published. Required fields are marked *