2
$\begingroup$

Let $\mathbf{x}$ be a random Gaussian vector in $\mathbb{R}^n$, i.e. $\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_n)$. Then for any fixed unit vector $\mathbf{u}$, one has $\mathbf{u}\mathbf{u}^\top \mathbf{x}$ is independent of $(\mathbf{I}_n-\mathbf{u}\mathbf{u}^\top)\mathbf{x}$ and trivially their sum is $\mathbf{x}$ itself.

My question is as following. Let $\mathbf{y}$ be a random vector sampled from a uniform coordinate distribution, that is $\mathbf{y}$ is distributed uniformly across $\{\sqrt{n}\mathbf{e}_1, \sqrt{n}\mathbf{e}_2,\cdots,\sqrt{n} \mathbf{e}_n\}$, where $\mathbf{e}_i$ is the $i$-th standard basis vector.

Can we similarly decompose $\mathbf{y}$ into two parts such that those two parts are independent of each other?

$\endgroup$
2
  • $\begingroup$ Have you examined the answer below? $\endgroup$
    – Hans
    Commented May 1, 2018 at 19:40
  • $\begingroup$ Sorry for the lateness. I have checked it. Thank you! $\endgroup$
    – Wuchen
    Commented May 17, 2018 at 13:53

1 Answer 1

2
$\begingroup$

$\newcommand{\al}{\alpha} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\epsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}} \newcommand{\tf}{\tilde f} \newcommand{\tg}{\tilde g}$

Let $Y:=\mathbf{y}/\sqrt n$ and $e_i:=\mathbf e_i$, so that $Y$ is uniformly distributed on the set $\{e_1,\dots,e_n\}$. Let also $I$ denote the identity operator on $\R^n$.

It appears reasonable to interpret the OP's question as follows: Do there exist linear operators $A$ and $B$ on $\R^n$ such that $B=I-A$ and the random vectors $AY$ and $BY$ are (stochasticaly) independent and each of them is not almost surely constant? Let us show that the answer to this question is no.

Indeed, let $f_1,\dots, f_k$ denote all the distinct vectors in the set $\{Ae_1,\dots,Ae_n\}$, and then let \begin{equation} I_r:=\{p\in[n]\colon Ae_p=f_r\} \tag{1} \end{equation} for $r\in[k]$,
where $[n]:=\{1,\dots,n\}$. Note that $f_1,\dots, f_k$ are all the distinct values of the random vector $AY$, and $$\PP(AY=f_r)=|I_r|/n$$ for $r\in[k]$, where $|\cdot|$ denotes the cardinality. Similarly, let $g_1,\dots, g_\ell$ denote all the distinct vectors in the set $\{Be_1,\dots,Be_n\}$, and then let \begin{equation} J_s:=\{p\in[n]\colon Be_p=g_s\} \tag{2} \end{equation} for $s\in[\ell]$, so that $$\PP(BY=g_s)=|J_s|/n$$ for $s\in[\ell]$. (At this point, let us pretend to forget the condition $B=I-A$, which implies $\ell=k$ and, without loss of generality, $J_r=I_r$ for all $r\in[k]=[\ell]$.)
We also have $$\PP(AY=f_r,BY=g_s)=|I_r\cap J_s|/n$$ for $r\in[k]$ and $s\in[\ell]$.

So, the independence of $AY$ and $BY$ means that for all $r\in[k]$ and $s\in[\ell]$ \begin{equation*} |I_r\cap J_s|=|I_r|\,|J_s|/n. \tag{2.5} \end{equation*} Note that the sets $I_r$ and $J_s$ are nonempty, and so, by (2.5), $|I_r\cap J_s|$ is a natural number (that is, a strictly positive integer).

We have the following number-theoretic proposition:

Proposition 1. Suppose that, for all $r\in[k]$ and $s\in[\ell]$, \begin{equation*} n_{rs}=a_rb_s, \end{equation*} where $n_{rs}$ is a natural number and $a_r$ and $b_s$ real numbers. Then there exist natural numbers $u_1,\dots,u_k,v_1,\dots,v_\ell$ such that \begin{equation*} n_{rs}=u_rv_s \end{equation*} for all $r\in[k]$ and $s\in[\ell]$.

This will be proved a bit later in this answer. At this point, let us just use Proposition 1 in conjunction with (2.5), to see that \begin{equation*} |I_r\cap J_s|=u_rv_s \end{equation*} for some natural numbers $u_1,\dots,u_k,v_1,\dots,v_\ell$ and all $r\in[k]$ and $s\in[\ell]$. Let \begin{equation*} u:=\sum_1^k u_r,\quad v:=\sum_1^\ell v_s. \end{equation*} Note also that $(I_r\cap J_s\colon r\in[k], s\in[\ell])$ is a partition of the set $[n]$. So, there is a $u\times v$ matrix $B$ consisting of $u_r\times v_s$ blocks $B_{rs}$ such that for all $r\in[k]$, $s\in[\ell]$, and $p\in[n]$ we have \begin{equation*} p\in I_r\cap J_s\iff p\Vvdash B_{rs}, \end{equation*} where $\Vvdash$ means "is an entry of". Note also that $uv=n$ and the set of all entries of the matrix $B$ is precisely the set $[n]$. Moreover, we have the one-to-one correspondence
\begin{equation*} [u]\times[v]\ni(i,j)\leftrightarrow p=b_{i,j}\in[n] \end{equation*} between the sets $[u]\times[v]$ and $[n]$, where $b_{i,j}$ is the $ij$-entry of the matrix $B$. Accordingly, for $(i,j)\in[u]\times[v]$ let \begin{equation*} e_{ij}:=e_p\quad\text{if }p=b_{i,j}; \tag{3} \end{equation*} so, we get a double-index re-enumeration $e_{ij}$ of $e_p$.

Next, note that any row index $i\in[u]$ of the matrix $B$ uniquely determines the corresponding block row index $r_i$ so that for any $j\in[v]$ there is a (unique) $s\in[\ell]$ such that $b_{ij}\Vvdash B_{r_i s}$. Similarly, any column index $j\in[v]$ of the matrix $B$ uniquely determines the corresponding block column index $s_j$. Therefore, in view of (1), (2), and (3), \begin{equation*} Ae_{ij}=\tf_i:=f_{r_i},\quad Be_{ij}=\tg_j:=g_{s_j} \end{equation*} for all $i\in[u]$ and $j\in[v]$.

If $u=1$, then $k=1$, so that the set $\{Ae_1,\dots,Ae_n\}$ is a singleton set, and hence the random vector $AY$ is actually a (nonrandom) constant. Similarly, if $v=1$, then the random vector $BY$ is a constant.

Excluding these two trivial cases, suppose now that $u,v\ge2$, and also recall at this point that $B=I-A$. We have $e_{ij}=Ae_{ij}+Be_{ij}=\tf_i+\tg_j$ for $i,j$ in $\{1,2\}$ (say). Hence, \begin{equation*} 0=(\tf_1+\tg_1)+(\tf_2+\tg_2)-(\tf_1+\tg_2)-(\tf_2+\tg_1) =e_{11}+e_{22}-e_{12}-e_{21}, \end{equation*} which is a contradiction.

Thus, to complete the answer, it remains to prove Proposition 1. For each pair $(r,s)\in[k]\times[\ell]$, consider the prime factor decomposition \begin{equation*} n_{rs}=\prod_{\al=1}^\infty p_\al^{N_{rs\al}}, \end{equation*} where $p_\al$ is the $\al$th prime number and the $N_{rs\al}$'s are some nonnegative integers (only finitely many of then nonzero). The condition $n_{rs}=a_rb_s$ implies that \begin{equation*} N_{11\al}+N_{rs\al}=N_{r1\al}+N_{1s\al} \end{equation*} for all $r,s$. So, Proposition 1 reduces to

Lemma 1. Suppose that $N_{rs}$'s are nonnegative integers such that \begin{equation*} N_{11}+N_{rs}=N_{r1}+N_{1s} \end{equation*} for all $(r,s)\in[k]\times[\ell]$. Then there exist nonnegative integers $m_1,\dots,m_k,n_1,\dots,n_\ell$ such that \begin{equation*} N_{rs}=m_r+n_s \end{equation*} for all $(r,s)\in[k]\times[\ell]$.

It remains to prove Lemma 1. This can be done by the following explicit construction of $m_1,\dots,m_k,n_1,\dots,n_\ell$: for all $(r,s)\in[k]\times[\ell]$, \begin{equation*} m_1:=\max_1^k(N_{11}-N_{r1})\ge N_{11}-N_{11}=0, \end{equation*} \begin{equation*} r\ge2\implies m_r:=N_{r1}-N_{11}+m_1\ge N_{r1}-N_{11}+N_{11}-N_{r1}=0, \end{equation*} \begin{align*} n_s:=N_{1s}-m_1 &=N_{1s}+\min_{r=1}^k(N_{r1}-N_{11}) \\ &=\min_{r=1}^k(N_{1s}+N_{r1}-N_{11}) =\min_{r=1}^k N_{rs}\ge0. \end{align*} So, $m_1,\dots,m_k,n_1,\dots,n_\ell$ are nonnegative integers. Also, for all $(r,s)\in[k]\times[\ell]$, \begin{equation*} m_1+n_s=m_1+N_{1s}-m_1=N_{1s} \end{equation*} and, if $r\ge2$, \begin{equation*} m_r+n_s=N_{r1}-N_{11}+m_1+N_{1s}-m_1=N_{rs}. \end{equation*} Thus, all the necessary proofs are completed.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .