3
$\begingroup$

Suppose $B\in\mathbb{R}^{m\times n}$ is a random binary matrix with i.i.d entries and $c\in \mathbb{R}^m$ is a strictly positive vector, that is $c_i>0$ for $i=1,2,\cdots m$. Also assume $m<n$, basically meaning that $B$ is a fat matrix. Is there any result (or any suggestion on how to approach the problem) that states for sufficiently large $n$, the linear system

$Bx=c$

has a strictly positive solution almost surely (obviously among the many possible ones, there is one would this property). Basically I am looking for a tail bound like

$\mathbb{P}(\nexists x>0: Bx=c)\leq f(n,m)$

where $f(n,m)\to 0$ as $n \to \infty$ and $m$ stays fixed. Any suggestions on finding a tail bound like above?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Let $1\leq i\leq m$. The probability that $B$ has no column with a unique one in the $i$th position is $(1-2^{-m})^n$. Thus the probability that $B$ has each such column is at least $1-m(1-2^{-m})^n$. If $B$ has all such columns (let their numbers be $j_1,\dots,j_m$ respectively) then one may assign very small values to $x_k$'s with $k\notin\{j_1,\dots,j_m\}$, and then determine $x_{j_i}$'s so that $Bx=c$. Thus one may take $$ f(m,n)=m(1-2^{-m})^n. $$ This is small provided that $2^m\log m=o(n)$.

ADDENDUM. On the other hand, let us see that no essentially better uniform bound is possible; that is, there exist suitable columns $c$ such that the probability is not that lagre.

Let $c_m>c_1+c_2+\dots+c_{m-1}$. Then a positive solution is possible only if some column in $B$ is equal to $e_m$; otherwise the sum of the first $m-1$ coordinates in $Bx$ majorizes the last one.

Thus we have for this case $f(n,m)\geq (1-2^{-m})^n$ which tends to a nonzero limit as $n=2^m$ and $m\to\infty$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks Ilya. It seems to me that the probability that B has each such columns is less than what you have stated as 1-n(1-2^{-m}). Did you take into account the cases that we have e_i, but not the right e_i's? (By e_i I mean a vector of all zeros except a one at the i-th entry) $\endgroup$
    – Ali
    Commented Sep 16, 2014 at 19:06
  • $\begingroup$ The probability of ONE bad event is $(1-2^{-m})^n$, and you have $n$ possible bad events. The probability of their union does not exceed the sum of their probabilities. What's wrong? $\endgroup$
    – Ilya Bogdanov
    Commented Sep 16, 2014 at 19:43
  • $\begingroup$ You are right. I missed the "at least argument". Say we have the limitation that $n<2^m$, in which case I doubt if we can claim $f(m,n)\to 0$ as $m$ increases. Is there any way we can think of a tighter bound? $\endgroup$
    – Ali
    Commented Sep 16, 2014 at 21:18
  • $\begingroup$ I have added some words on the uniform bound (i.e. the one working for all admissible $c$). If it is not what you want, you need to specify the set of valid $c$ (it should depend on $m$...). $\endgroup$
    – Ilya Bogdanov
    Commented Sep 16, 2014 at 22:22
  • $\begingroup$ This was a useful argument. By the way, can we not say that $f(n,m)\sim m(1-2^{-m})^n$ instead of $f(n,m)\sim n(1-2^{-m})^n$? We know $P(\tilde e_i)=(1-2^{-m})^n$ applying the UB to which gives $P(\cup_{i=1}^m \tilde e_i) \leq m(1-2^{-m})^n$ ? $\endgroup$
    – Ali
    Commented Sep 17, 2014 at 2:46
0
$\begingroup$

A very related study in the case of gaussian entries is the paper :

"Positive solutions for large random linear systems" https://arxiv.org/abs/1904.04559

Improve this answer
$\endgroup$

You must log in to answer this question.

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