1
$\begingroup$

Consider a random $n$ by $n$ $0$-$1$ matrix $M$ where $M_{i,j} = 1$ with probability $1/2$ and $0$ otherwise. Now choose a single random $0$-$1$ vector $v$ where $v_i=1$ with probability $1/2$.

What is the probability distribution of $u=Mv$?

Each $u_i$ is a binomial random variable $B(n,1/4)$. However the $u_i$ do not appear to be independent of each other. For example, if $u_1 = 0$ then it is likely that $v$ has very few $1$s and so the probability that $u_2$ is small will be higher.

$\endgroup$
0
$\begingroup$

For a fixed vector $a$ of $1$'s and $0$'s, $\sum_{i=1}^n a_i M_i$ is a vector of independent binomial$(\sum_{1=1}^n a_i, 1/2)$ random variables (here $M_i$ is the $i^{th}$ column of $M$). Let $S$ be the set of all such vectors $a$, of which there are $2^n$ and the probability that $v$ is equal to any given one is $\frac{1}{2^n}$.

Thus for any vector $x$ of non-negative integers not exceeding $n$, \begin{align} P[u=x] &= \frac{1}{2^n}\sum_{a \in S} P[u = x \mid v = a] \\ &= \frac{1}{2^n}\sum_{a \in S} P\left[\sum_{i=1}^n a_i M_i = x \right] \\ &= \frac{1}{2^n}\sum_{a \in S} \prod_{i=1}^n \binom{\sum_{j=1}^n a_j}{x_i} \left(\frac{1}{2}\right)^{\sum_{j=1}^n a_j} \chi\left\{x_i \leq \sum_{j=1}^n a_j \right\} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy