Definition (p p p Given p ∈ N + p \in \mathbb{N}^+ p ∈ N + X ∈ L p X \in L_p X ∈ L p
∥ X ∥ p ≐ ( E [ ∣ X ∣ p ] ) 1 / p .
\Vert X \Vert_p \doteq \Big( \mathbb{E} \big[ |X|^p \big] \Big)^{1 / p}.
∥ X ∥ p ≐ ( E [ ∣ X ∣ p ] ) 1/ p .
We verify that this is a norm.
Denote a = ∥ X ∥ p a = \Vert X \Vert_p a = ∥ X ∥ p b = ∥ Y ∥ p b = \Vert Y \Vert_p b = ∥ Y ∥ p s = a + b s = a + b s = a + b ∣ ⋅ ∣ p | \cdot |^p ∣ ⋅ ∣ p
∥ a s ⋅ X a + b s ⋅ Y b ∥ p p = E [ ∣ a s ⋅ X a + b s ⋅ Y b ∣ p ] ≤ E [ a s ⋅ ∣ X a ∣ p + b s ⋅ ∣ Y b ∣ p ] = a s + b s = 1.
\begin{aligned}
\left\Vert \frac{a}{s} \cdot \frac{X}{a} + \frac{b}{s} \cdot \frac{Y}{b} \right\Vert_p^p
&= \mathbb{E} \Bigg[ \left\vert \frac{a}{s} \cdot \frac{X}{a} + \frac{b}{s} \cdot \frac{Y}{b} \right\vert^p \Bigg] \\
&\le \mathbb{E} \Bigg[ \frac{a}{s} \cdot \left\vert \frac{X}{a} \right\vert^p + \frac{b}{s} \cdot \left\vert \frac{Y}{b} \right\vert^p \Bigg] \\
&= \frac{a}{s} + \frac{b}{s} \\
&= 1.
\end{aligned}
s a ⋅ a X + s b ⋅ b Y p p = E [ s a ⋅ a X + s b ⋅ b Y p ] ≤ E [ s a ⋅ a X p + s b ⋅ b Y p ] = s a + s b = 1. Further, for q , p ∈ N + , q ≤ p q, p \in \mathbb{N}^+, q \le p q , p ∈ N + , q ≤ p ∥ X ∥ q ≤ ∥ X ∥ p \Vert X \Vert_q \le \Vert X \Vert_p ∥ X ∥ q ≤ ∥ X ∥ p ∣ ⋅ ∣ p / q | \cdot |^{p / q} ∣ ⋅ ∣ p / q
∥ X ∥ q p = ( E [ ∣ X ∣ q ] ) p / q ≤ E [ ( ∣ X ∣ q ) p / q ] = ∥ X ∥ p p .
\Vert X \Vert_q^p
= \Big( \mathbb{E} \big[ |X|^q \big] \Big)^{p / q}
\le \mathbb{E} \Big[ \big( |X|^q \big)^{p / q} \Big]
= \Vert X \Vert_p^p.
∥ X ∥ q p = ( E [ ∣ X ∣ q ] ) p / q ≤ E [ ( ∣ X ∣ q ) p / q ] = ∥ X ∥ p p .
Khintchine Inequality. Given p ∈ N + p \in \mathbb{N}^+ p ∈ N + a ⃗ = ( a 1 , … , a n ) ∈ R n \vec{a} = (a_1, \ldots, a_n) \in \mathbb{R}^n a = ( a 1 , … , a n ) ∈ R n X 1 , … , X n X_1, \ldots, X_n X 1 , … , X n
∥ ∑ i ∈ [ n ] a i ⋅ X i ∥ p ≤ p + 1 p ⋅ p ⋅ ∥ a ⃗ ∥ 2 ∈ O ( p ⋅ ∥ a ⃗ ∥ 2 ) .
\left\Vert \sum_{i \in [n]} a_i \cdot X_i \right\Vert_p
\le \frac{\sqrt{p + 1}}{\sqrt{p}} \cdot \sqrt{p} \cdot \Vert \vec{a} \Vert_2
\in O( \sqrt{p} \cdot \Vert \vec{a} \Vert_2 ).
i ∈ [ n ] ∑ a i ⋅ X i p ≤ p p + 1 ⋅ p ⋅ ∥ a ∥ 2 ∈ O ( p ⋅ ∥ a ∥ 2 ) .
Proof. Suppose that this holds when p p p p p p
∥ ∑ i ∈ [ n ] a i ⋅ X i ∥ p ≤ ∥ ∑ i ∈ [ n ] a i ⋅ X i ∥ p + 1 ∈ O ( p + 1 ⋅ ∥ a ⃗ ∥ 2 ) = O ( p ⋅ ∥ a ⃗ ∥ 2 ) .
\left\Vert \sum_{i \in [n]} a_i \cdot X_i \right\Vert_p
\le \left\Vert \sum_{i \in [n]} a_i \cdot X_i \right\Vert_{p + 1}
\in O \left( \sqrt{p + 1} \cdot \Vert \vec{a} \Vert_2 \right)
= O \left( \sqrt{p} \cdot \Vert \vec{a} \Vert_2 \right).
i ∈ [ n ] ∑ a i ⋅ X i p ≤ i ∈ [ n ] ∑ a i ⋅ X i p + 1 ∈ O ( p + 1 ⋅ ∥ a ∥ 2 ) = O ( p ⋅ ∥ a ∥ 2 ) . It is left to consider that p p p Z 1 , … , Z n Z_1, \ldots, Z_n Z 1 , … , Z n ∥ ∑ i ∈ [ n ] a i ⋅ X i ∥ p \left\Vert \sum_{i \in [n]} a_i \cdot X_i \right\Vert_p ∑ i ∈ [ n ] a i ⋅ X i p ∥ ∑ i ∈ [ n ] a i ⋅ Z i ∥ p \left\Vert \sum_{i \in [n]} a_i \cdot Z_i \right\Vert_p ∑ i ∈ [ n ] a i ⋅ Z i p
E [ ∣ ∑ i ∈ [ n ] a i ⋅ X i ∣ p ] = E [ ( ∑ i ∈ [ n ] a i ⋅ X i ) p ] , E [ ∣ ∑ i ∈ [ n ] a i ⋅ Z i ∣ p ] = E [ ( ∑ i ∈ [ n ] a i ⋅ Z i ) p ] ,
\begin{align*}
\mathbb{E} \Bigg[ \Bigg| \sum_{i \in [n]} a_i \cdot X_i \Bigg|^p \Bigg]
= \mathbb{E} \Bigg[ \Bigg( \sum_{i \in [n]} a_i \cdot X_i \Bigg)^p \Bigg], \\
\mathbb{E} \Bigg[ \Bigg| \sum_{i \in [n]} a_i \cdot Z_i \Bigg|^p \Bigg]
= \mathbb{E} \Bigg[ \Bigg( \sum_{i \in [n]} a_i \cdot Z_i \Bigg)^p \Bigg],
\end{align*}
E [ i ∈ [ n ] ∑ a i ⋅ X i p ] = E [ ( i ∈ [ n ] ∑ a i ⋅ X i ) p ] , E [ i ∈ [ n ] ∑ a i ⋅ Z i p ] = E [ ( i ∈ [ n ] ∑ a i ⋅ Z i ) p ] , can be expanded into a sum of expectation of monomials.
Each monomial with odd exponents has expectation 0 0 0 m 1 , … , m n m_1, \ldots, m_n m 1 , … , m n p p p
∏ i ∈ [ n ] ( a i ) m i E [ ( X i ) m i ] = ∏ i ∈ [ n ] ( a i ) m i ≤ ∏ i ∈ [ n ] ( a i ) m i E [ ( Z i ) m i ] ,
\prod_{i \in [n]} (a_i)^{m_i} \mathbb{E}[ \left( X_i \right)^{m_i} ]
= \prod_{i \in [n]} (a_i)^{m_i}
\le \prod_{i \in [n]} (a_i)^{m_i} \mathbb{E}[ \left( Z_i \right)^{m_i} ],
i ∈ [ n ] ∏ ( a i ) m i E [ ( X i ) m i ] = i ∈ [ n ] ∏ ( a i ) m i ≤ i ∈ [ n ] ∏ ( a i ) m i E [ ( Z i ) m i ] , where the last inequality holds since ( a i ) m i (a_i)^{m_i} ( a i ) m i E [ ( Z i ) m i ] = ( m i − 1 ) ! ! ≥ 1 \mathbb{E}[ \left( Z_i \right)^{m_i} ] = (m_i - 1)!! \ge 1 E [ ( Z i ) m i ] = ( m i − 1 )!! ≥ 1
Therefore ∥ ∑ i ∈ [ n ] a i ⋅ X i ∥ p p \left\Vert \sum_{i \in [n]} a_i \cdot X_i \right\Vert_p^p ∑ i ∈ [ n ] a i ⋅ X i p p ∥ ∑ i ∈ [ n ] a i ⋅ Z i ∥ p p \left\Vert \sum_{i \in [n]} a_i \cdot Z_i \right\Vert_p^p ∑ i ∈ [ n ] a i ⋅ Z i p p ∑ i ∈ [ n ] a i ⋅ Z i \sum_{i \in [n]} a_i \cdot Z_i ∑ i ∈ [ n ] a i ⋅ Z i N ( 0 , ∥ a ⃗ ∥ 2 ) N(0, \Vert \vec{a} \Vert_2) N ( 0 , ∥ a ∥ 2 )
∥ ∑ i ∈ [ n ] a i ⋅ X i ∥ p ≤ ∥ ∑ i ∈ [ n ] a i ⋅ Z i ∥ p = ∥ a ⃗ ∥ 2 ⋅ ( ( p − 1 ) ! ! ) 1 / p
\left\Vert \sum_{i \in [n]} a_i \cdot X_i \right\Vert_p
\le \left\Vert \sum_{i \in [n]} a_i \cdot Z_i \right\Vert_p
= \Vert \vec{a} \Vert_2 \cdot \big( \left( p - 1\right)!! \big)^{1 / p}
i ∈ [ n ] ∑ a i ⋅ X i p ≤ i ∈ [ n ] ∑ a i ⋅ Z i p = ∥ a ∥ 2 ⋅ ( ( p − 1 ) !! ) 1/ p Finally, note that
( p − 1 ) ! ! ≤ p p / 2 ⟹ ( ( p − 1 ) ! ! ) 1 / p ≤ p (p - 1) !! \le p^{p / 2} \Longrightarrow \big( \left( p - 1\right)!! \big)^{1 / p} \le \sqrt{p} ( p − 1 )!! ≤ p p /2 ⟹ ( ( p − 1 ) !! ) 1/ p ≤ p
□ \square □
Remark. See Wikipedia for obtaining a tighter estimation for odd p p p
Facts.
Suppose that Z ∼ N ( 0 , 1 ) Z \sim N(0, 1) Z ∼ N ( 0 , 1 )
∥ Z ∥ p p ≐ 1 2 π ∫ − ∞ ∞ ∣ z ∣ p exp ( − 1 2 z 2 ) d z = 2 2 π ∫ 0 ∞ z p exp ( − 1 2 z 2 ) d z = 2 2 π ∫ 0 ∞ ( 2 u ) p exp ( − u ) ⋅ 1 2 u d u , u = z 2 2 = 2 p / 2 π ∫ 0 ∞ u ( p + 1 ) / 2 − 1 exp ( − u ) d u = 2 p / 2 π ⋅ Γ ( p + 1 2 ) .
\begin{aligned}
\Vert Z \Vert_p^p
&\doteq \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^\infty |z|^p \exp \left( - \frac{1}{2} z^2 \right) \, d z \\
&= \frac{2}{\sqrt{2 \pi}} \int_{0}^\infty z^p \exp \left( - \frac{1}{2} z^2 \right) \, d z \\
&= \frac{2}{\sqrt{2 \pi}} \int_{0}^\infty (\sqrt{2u})^p \exp \left( - u \right) \cdot \frac{1}{\sqrt{2u}} \, d u, && u = \frac{z^2}{2} \\
&= \frac{ 2^{p / 2} }{ \sqrt{\pi} } \int_{0}^\infty u^{(p + 1) / 2 - 1} \exp \left( - u \right) \, d u \\
&= \frac{ 2^{p / 2} }{ \sqrt{\pi} } \cdot \Gamma \left( \frac{p + 1}{2} \right).
\end{aligned}
∥ Z ∥ p p ≐ 2 π 1 ∫ − ∞ ∞ ∣ z ∣ p exp ( − 2 1 z 2 ) d z = 2 π 2 ∫ 0 ∞ z p exp ( − 2 1 z 2 ) d z = 2 π 2 ∫ 0 ∞ ( 2 u ) p exp ( − u ) ⋅ 2 u 1 d u , = π 2 p /2 ∫ 0 ∞ u ( p + 1 ) /2 − 1 exp ( − u ) d u = π 2 p /2 ⋅ Γ ( 2 p + 1 ) . u = 2 z 2 Note that, when p p p
Γ ( p + 1 2 ) = ( p − 1 2 ) ! ,
\Gamma \left( \frac{p + 1}{2} \right) = \left( \frac{p - 1}{2} \right)!,
Γ ( 2 p + 1 ) = ( 2 p − 1 ) ! , and when p p p
Γ ( p + 1 2 ) = p − 1 2 ⋯ 1 2 ⋅ Γ ( 1 2 ) = p − 1 2 ⋯ 1 2 ⋅ π .
\Gamma \left( \frac{p + 1}{2} \right)
= \frac{p - 1}{2} \cdots \frac{1}{2} \cdot \Gamma \left( \frac{1}{2} \right)
= \frac{p - 1}{2} \cdots \frac{1}{2} \cdot \sqrt{\pi}.
Γ ( 2 p + 1 ) = 2 p − 1 ⋯ 2 1 ⋅ Γ ( 2 1 ) = 2 p − 1 ⋯ 2 1 ⋅ π . Therefore,
2 p / 2 π ⋅ Γ ( p + 1 2 ) = { 2 π ( p − 1 ) ! ! if p is odd , ( p − 1 ) ! ! if p is even .
\frac{ 2^{p / 2} }{ \sqrt{\pi} } \cdot \Gamma \left( \frac{p + 1}{2} \right)
= \begin{cases}
\begin{aligned}
&\sqrt{\frac{2}{\pi}} (p - 1)!! &\text{ if }\, p \,\text{ is odd },\, \\
& (p - 1)!! &\text{ if }\, p \,\text{ is even}.
\end{aligned}
\end{cases}
π 2 p /2 ⋅ Γ ( 2 p + 1 ) = ⎩ ⎨ ⎧ π 2 ( p − 1 )!! ( p − 1 )!! if p is odd , if p is even . Reference
[1]. https://en.wikipedia.org/wiki/Khintchine_inequality
[2]. https://people.eecs.berkeley.edu/~minilek/madalgo2015/notes1.pdf
← Back to all notes Back to top ↑