I have $n$ random vectors ${\bf r}_i$ for $i=1,2,\dots,n$, each with dimension $1 \times m$, and $n$ random matrices ${\bf S}_i$ for $i=1,2,\dots,n$, each with dimension $M \times m$. The elements of ${\bf r}_i$ and ${\bf S}_i$ belong to GF(2). ${\bf r}_i$'s are i.i.d and Every ${\bf r}_i$ has only one non-zero element and the probability that its $k$-th element is 1 is $p_k$ for a non-increasing probability distribution $p_k$ such that $\sum_{k=1}^m p_k =1$. ${\bf S}_i$'s are i.i.d random matices and the $jk$-th element of ${\bf S}_i$ is chosen to be equal to 1 independently of other elements according to a Bernoulli random distribution with probability $p_k$ (this is equal to the distribution discussed above). For vectors ${\bf a}_i$ of size $1 \times M$ for $i=1,2,\dots,n$ whose elements belong to GF(2) we define the $n \times m$ random matrix $\mathbb{H}_{n \times m}$ as \begin{equation} \mathbb{H}_{n \times m}({\bf a}_1, {\bf a}_2, \dots, {\bf a}_n) = \begin{bmatrix} {\bf r}_1 + {\bf a}_1 {\bf S}_1 \\ {\bf r}_2 + {\bf a}_2 {\bf S}_2 \\ \vdots \\{\bf r}_n + {\bf a}_n {\bf S}_n \end{bmatrix} \end{equation} I need to find the expected value of the minimum rank of matrices $\mathbb{H}_{n \times m}$ when the expectation is taken over all such random matrices ${\bf S}_i$ and random vectors ${\bf r}_i$ and the minimum rank is found over all such vectors ${\bf a}_i$. In other words I need to find \begin{equation} \mathbb{E}_{{\bf r}_1 \dots {\bf r}_n {\bf S}_1 \dots {\bf S}_n} \left[ \min_{{\bf a}_1 \dots {\bf a}_n} \left[\mathrm{rank}\left( \mathbb{H}_{n \times m}({\bf a}_1, {\bf a}_2, \dots, {\bf a}_n) \right) \right] \right] \end{equation} I know that this is very complicated to find. However, If I can find any bounds that would also be nice. Can I approximate the nasty rank function with a better well-behaving convex function? I know that this is possible in case of square matrices but $\mathbb{H}$ is an $n \times m$ matrix. If it helps, we can assume that $m >> M$ and $m >> n$ and we may assume that the above probability distribution is Zipfian. Any thoughts would be highly appreciated.