Let $k$ be an even integer in $\{2, \ldots, N\}$. We assume in this question that the random variables $X_1, \ldots, X_N$ are $k$-independent. We introduce the following notations: $\mathcal{T}$ denotes the set $\{1, \ldots, N\}^k$. If $T = (n_1, \ldots, n_k) \in \mathcal{T}$ and $n \in \{1, \ldots, N\}$, we denote by $m_T(n)$ the multiplicity of $n$ in $T$, that is $$m_T(n) = \operatorname{Card}\left\{i \in \{1, \ldots, k\}; n_i = n\right\}$$ For $\ell \in \{1, \ldots, k\}$, we denote by $\mathcal{T}_\ell$ the set of $T$ in $\mathcal{T}$ involving exactly $\ell$ distinct indices, where each has multiplicity at least 2, namely: $T \in \mathcal{T}_\ell$ if $$\operatorname{Card}\left(\left\{n \in \{1, \ldots, N\}; m_T(n) > 0\right\}\right) = \ell,$$ and $$\forall n \in \{1, \ldots, N\}, \quad m_T(n) > 0 \Rightarrow m_T(n) \geq 2$$ Finally, we denote by $|\mathcal{T}_\ell|$ the cardinality of $\mathcal{T}_\ell$. I.5.a) Determine $|\mathcal{T}_1|$ and $|\mathcal{T}_\ell|$ for $\ell > k/2$. I.5.b) Justify $$\mathbb{E}\left[(S_N)^k\right] = \sum_{T \in \mathcal{T}} \prod_{n=1}^N \mathbb{E}\left[X_n^{m_T(n)}\right]$$ then $$\mathbb{E}\left[(S_N)^k\right] = \sum_{\ell=1}^{k/2} \sum_{T \in \mathcal{T}_\ell} \prod_{n=1}^N \mathbb{E}\left[X_n^{m_T(n)}\right]$$ I.5.c) Prove that $$\mathbb{E}\left[(S_N)^k\right] \leq \sum_{\ell=1}^{k/2} K^{k-2\ell} |\mathcal{T}_\ell|$$ I.5.d) Let $\ell \in \{1, \ldots, k/2\}$. Justify the following estimate: $$|\mathcal{T}_\ell| \leq \binom{N}{\ell} \ell^k \leq \frac{N^\ell}{\ell!} \ell^k$$ One may consider the set of $T \in \mathcal{T}$ involving at most $\ell$ distinct elements. I.5.e) For $\ell \in \{1, \ldots, k/2\}$, prove that $$\ell! \geq \ell^\ell e^{-\ell}$$ then deduce that $$|\mathcal{T}_\ell| \leq (Ne)^\ell \left(\frac{k}{2}\right)^{k-\ell}$$ I.5.f) Prove that $$\mathbb{E}\left[(S_N)^k\right] \leq \left(\frac{Kk}{2}\right)^k \sum_{\ell=1}^{k/2} \left(\frac{2Ne}{kK^2}\right)^\ell$$ I.5.g) We assume $$kK^2 \leq N.$$ Prove that $$\mathbb{E}\left[(S_N)^k\right] \leq \frac{\theta}{\theta - 1} \left(\frac{Nek}{2}\right)^{k/2} \leq 2\left(\frac{Nek}{2}\right)^{k/2},$$ where $$\theta := \frac{2Ne}{kK^2}$$ I.5.h) Prove (under hypothesis (27)) the following estimate: for all $t > 0$, $$\mathbb{P}\left(|S_N| \geq t\sqrt{N}\right) \leq 2\left(\frac{\sqrt{ek/2}}{t}\right)^k$$
Let $k$ be an even integer in $\{2, \ldots, N\}$. We assume in this question that the random variables $X_1, \ldots, X_N$ are $k$-independent.
We introduce the following notations: $\mathcal{T}$ denotes the set $\{1, \ldots, N\}^k$. If $T = (n_1, \ldots, n_k) \in \mathcal{T}$ and $n \in \{1, \ldots, N\}$, we denote by $m_T(n)$ the multiplicity of $n$ in $T$, that is
$$m_T(n) = \operatorname{Card}\left\{i \in \{1, \ldots, k\}; n_i = n\right\}$$
For $\ell \in \{1, \ldots, k\}$, we denote by $\mathcal{T}_\ell$ the set of $T$ in $\mathcal{T}$ involving exactly $\ell$ distinct indices, where each has multiplicity at least 2, namely: $T \in \mathcal{T}_\ell$ if
$$\operatorname{Card}\left(\left\{n \in \{1, \ldots, N\}; m_T(n) > 0\right\}\right) = \ell,$$
and
$$\forall n \in \{1, \ldots, N\}, \quad m_T(n) > 0 \Rightarrow m_T(n) \geq 2$$
Finally, we denote by $|\mathcal{T}_\ell|$ the cardinality of $\mathcal{T}_\ell$.
\textbf{I.5.a)} Determine $|\mathcal{T}_1|$ and $|\mathcal{T}_\ell|$ for $\ell > k/2$.
\textbf{I.5.b)} Justify
$$\mathbb{E}\left[(S_N)^k\right] = \sum_{T \in \mathcal{T}} \prod_{n=1}^N \mathbb{E}\left[X_n^{m_T(n)}\right]$$
then
$$\mathbb{E}\left[(S_N)^k\right] = \sum_{\ell=1}^{k/2} \sum_{T \in \mathcal{T}_\ell} \prod_{n=1}^N \mathbb{E}\left[X_n^{m_T(n)}\right]$$
\textbf{I.5.c)} Prove that
$$\mathbb{E}\left[(S_N)^k\right] \leq \sum_{\ell=1}^{k/2} K^{k-2\ell} |\mathcal{T}_\ell|$$
\textbf{I.5.d)} Let $\ell \in \{1, \ldots, k/2\}$. Justify the following estimate:
$$|\mathcal{T}_\ell| \leq \binom{N}{\ell} \ell^k \leq \frac{N^\ell}{\ell!} \ell^k$$
One may consider the set of $T \in \mathcal{T}$ involving at most $\ell$ distinct elements.
\textbf{I.5.e)} For $\ell \in \{1, \ldots, k/2\}$, prove that
$$\ell! \geq \ell^\ell e^{-\ell}$$
then deduce that
$$|\mathcal{T}_\ell| \leq (Ne)^\ell \left(\frac{k}{2}\right)^{k-\ell}$$
\textbf{I.5.f)} Prove that
$$\mathbb{E}\left[(S_N)^k\right] \leq \left(\frac{Kk}{2}\right)^k \sum_{\ell=1}^{k/2} \left(\frac{2Ne}{kK^2}\right)^\ell$$
\textbf{I.5.g)} We assume
$$kK^2 \leq N.$$
Prove that
$$\mathbb{E}\left[(S_N)^k\right] \leq \frac{\theta}{\theta - 1} \left(\frac{Nek}{2}\right)^{k/2} \leq 2\left(\frac{Nek}{2}\right)^{k/2},$$
where
$$\theta := \frac{2Ne}{kK^2}$$
\textbf{I.5.h)} Prove (under hypothesis (27)) the following estimate: for all $t > 0$,
$$\mathbb{P}\left(|S_N| \geq t\sqrt{N}\right) \leq 2\left(\frac{\sqrt{ek/2}}{t}\right)^k$$