What is the distribution of a norm of a vector with random components?

Question

Let's say that there is an $n$-dimensional vector $X\in \{0, 1, 2\}^n $. If each component of $X$ are uniform random in $\{0, 1, 2\}$, that is each component is sampled from $\{0, 1, 2\}$ with equal probability, what is the distribution that $||X||_2$ is following? I think that we can compute the distribution of $X$ using multivariate distribution, but my problem does not seem to a problem of multivariate distribution.

This statement might also be written as follows :

For uniformly distributed random variables $X_1, X_2, \cdots, X_n$, what is the distribution of $\sqrt{X_1^2+X_2^2+\cdots+X_n^2}$ ?

If they are too complicated, I want to know how to find their standard deviation, when using Gaussian assumption.

Thank you in advance.

Answer 1

$\def\eqdef{\stackrel{\text{def}}{=}}\def\P{\Bbb{P}}$ The multivariate distribution can indeed be used to solve the problem, but it's not the distribution of $\ X\ $ itself that can be expressed in terms of that distribution, but that of the vector $\ \big(N_0,N_1,N_2\big)\ $, where $$ N_i\eqdef\big|\big\{\,j\,\big|X_j=i\,\big\}\big|\ . $$ In fact, $$ \P\big(\,N_0=i_0,N_1=i_1,N_2=i_2\,)={n\choose i_0\,i_ 1\,i_2}\left(\frac{1}{3}\right)^n\, $$ and since $$ \sum_{j=1}^nX_j^2=N_1+4N_2\ , $$ it's not difficult to express the distribution of $\ \sum_\limits{j=1}^nX_j^2\ $, and hence that of its square root, in terms of this multivariate distribution.

Note that $\ N_1+4N_2\ $ can realise any of the integer values from $\ 0\ $ to $\ 4n-6\ $ inclusive, $\ 4n-4, 4n-3\ $, or $\ 4n\ $, and no others. We have $\ N_1+4N_2=4n\ $ if and only if $\ N_2=n\ $ and $\ N_0=N_1=0\ $, $\ N_1+4N_2=4n-3\ $ if and only if $\ N_2=n-1, N_1=1\ $ and $\ N_0=0\ $, and $\ N_1+4N_2=4n-4\ $ if and only if $\ N_2=n-1,$$\, N_1=0\ $ and $\ N_0=1\ $. Thus, \begin{align} \P\big(N_1+4N_2=4n\big)&={n\choose0\,0\,n}\left(\frac{1}{3}\right)^n=\left(\frac{1}{3}\right)^n\\ \P\big(N_1+4N_2=4n-3\big)&={n\choose0\,1\,n}\left(\frac{1}{3}\right)^n=n\left(\frac{1}{3}\right)^n\\ \P\big(N_1+4N_2=4n-4\big)&={n\choose1\,0\,n}\left(\frac{1}{3}\right)^n=n\left(\frac{1}{3}\right)^n\\ \end{align} We also have $\ N_1+4N_2=s\ $ for $\ 0\le s\le4n-6\ $ if and only if $\ \max\left(0,\left\lceil \frac{s-n}{4}\right\rceil\right)\le N_2\le\max\left(0,\left\lfloor \frac{s}{4}\right\rfloor\right)\ $, $\ N_1=s-4N_2\ $ and $\ N_0=$$\,n-N_1-N_2=n-s+3N_2\ $. Therefore \begin{align} \P\big(\,N_1+4N_2=s\,\big)&=\sum_{j=\max\left(0,\left\lceil\frac{s-n}{4}\right\rceil\right)}^{\max\left(0,\left\lfloor \frac{s}{4}\right\rfloor\right)}{n\choose n-s+3j\ s-4j\ j}\left(\frac{1}{3}\right)^n\\ &=\sum_{j=\max\left(0,\left\lceil\frac{s-n}{4}\right\rceil\right)}^{\max\left(0,\left\lfloor \frac{s}{4}\right\rfloor\right)}\frac{n!}{(n-s+3j)!(s-4j)!j!}\left(\frac{1}{3}\right)^n\ . \end{align} Finally, $\ \|X\|_2=r\ $ if and only if $\ N_1+4N_2=r^2\ $. Therefore, setting $\ L(k)\eqdef\max\left(0,\left\lceil\frac{k}{4}\right\rceil\right)\ $ and $\ U(k)\eqdef\max\left(0,\left\lfloor\frac{k}{4}\right\rfloor\right)\ $, we have \begin{align} \P\big(&\|X\|_2=r\big)=\\ &\cases{\sum_\limits{L\big(r^2-n\big)}^{U\big(r^2\big)}\frac{n!}{(n-r^2+3j)!(r^2-4j)!j!}\left(\frac{1}{3}\right)^n&if $\ r^2\in\Bbb{Z},0\le r^2\le4n-6$\\ n\left(\frac{1}{3}\right)^n&if $\ r=2\sqrt{n-1}\ $ or $\ r=\sqrt{4n-3}$\\ \left(\frac{1}{3}\right)^n&if $\ r=2\sqrt{n}$\\ 0&otherwise.} \end{align}