Stats
Bounding the probability of low-weight vectors in the rowspace of a random sparse binary matrix
Step-by-step statistics solution: Bounding the probability of low-weight vectors in the rowspace of a random sparse binary matrix
As an Amazon Associate, I earn from qualifying purchases. For more practice problems like this, see Schaum’s Outline of Statistics, 6th Edition.
1. What the problem asks – plain language
We are given a binary matrix
[ H\in\mathbb F_{2}^{m\times h},\qquad m=\beta n,\;h=(1-\beta)n ,\;0<\beta<\tfrac12 . ]
Each row of (H) contains exactly (t) ones (the remaining entries are zero) and the (t) positions are chosen uniformly at random; the rows are independent of one another.
The question is:
What is the probability that some non‑zero linear combination of the rows of (H) has fewer than (t) ones?
Equivalently, we want an upper bound on
[ \boxed{\; \Pr\Bigl(\exists\,y\in\mathbb F_{2}^{m}!\setminus!{0}: 0<|y^{\top}H|_{0}<t\Bigr) \;} ]
i.e. an upper bound on the chance that the row‑space (the linear code generated by the rows) contains a codeword whose Hamming weight is smaller than the row weight (t).
2. Full solution
The proof proceeds in three stages
- Fix a set of rows (equivalently a non‑zero vector (y)).
- Show that for a fixed set the weight of the sum is very unlikely to be < (t).
- Union‑bound over all possible sets of rows.
All calculations are explicit; no step is omitted.
2.1 Notation for a fixed set of rows
For a non‑empty subset (S\subseteq{1,\dots ,m}) let
[ X_S \;:=\; \sum_{i\in S} \text{row}i(H)\pmod 2\in\mathbb F_2^{h}, \qquad W_S:=|X_S|{0}\; . ]
(W_S) is the Hamming weight of the binary vector obtained by adding (mod 2) the rows in (S).
If (y) is the indicator vector of (S) (i.e. (y_i=1\iff i\in S)), then (y^{\top}H = X_S) and the event we are interested in is
[ \exists\, S\neq\varnothing:\; 0<W_S<t . ]
2.2 Distribution of a single column for a fixed (S)
Consider a particular column (j\in{1,\dots ,h}).
Each row contains the column (j) with probability
[ p:=\frac{t}{h}\qquad\bigl(\text{because a row chooses }t\text{ of the }h\text{ positions uniformly}\bigr). ]
The rows are independent, hence the number of rows of (S) that have a ‘1’ in column (j) is
[ Z_{j,S}\sim\operatorname{Binomial}\bigl(|S|,p\bigr). ]
The column contributes a ‘1’ to (X_S) iff (Z_{j,S}) is odd. Therefore
[ \Pr\bigl(X_{S,j}=1\bigr)=\Pr\bigl(Z_{j,S}\text{ is odd}\bigr) =\frac{1-(1-2p)^{|S|}}{2}. \tag{1} ]
For later use we note the elementary bound
[ \frac{1-(1-2p)^{s}}{2} \le \frac{s p}{1} \qquad\text{for all }s\ge 1, \tag{2} ]
which follows from the inequality ((1-2p)^{s}\ge 1-2sp).
2.3 Expected weight of (X_S)
Summing (1) over the (h) columns gives
[ \mu_S:=\mathbb E[W_S]= h\;\frac{1-(1-2p)^{|S|}}{2}. \tag{3} ]
Because (p=t/h) and (h=(1-\beta)n),
[ \mu_S = \frac{h}{2}\Bigl(1-(1-2t/h)^{|S|}\Bigr) =\frac{h}{2}\Bigl(1-(1-\tfrac{2t}{h})^{|S|}\Bigr) \ge |S|t\Bigl(1-\frac{|S|t}{h}\Bigr) . \tag{4} ]
| (The last inequality comes from expanding ((1-2p)^{ | S | }) and discarding the non‑negative higher‑order terms.) | ||
| Since (h=\Theta(n)) and (t=O(\log n)), the correction term ( | S | t/h) is at most (O(\log n /n)) and can be ignored for every ( | S | \le m). Consequently |
[ \boxed{\;\mu_S\ge \tfrac12|S|t\qquad\text{for all }S\neq\varnothing.\;} \tag{5} ]
In particular
- for
Original question: Bounding the probability of low-weight vectors in the rowspace of a random sparse binary matrix on Cross Validated (Stats Stack Exchange), licensed CC BY-SA.