Let $\oplus$ sign denote bitwise addition modulo $2$. Let $n$ and $m$ be integers.
Consider the set of $m$ equations on $n$ variables as follows.
\[\begin{array}{l}
a_{1,1} x_{1} \oplus a_{1,2} x_{2} \oplus \ldots \oplus a_{1, n} x_{n}=b_{1} \\
a_{2,1} x_{1} \oplus a_{2,2} x_{2} \oplus \ldots \oplus a_{2, n} x_{n}=b_{2} \\
\vdots \\
a_{i, 1} x_{1} \oplus a_{i, 2} x_{2} \oplus \ldots \oplus a_{i, n} x_{n}=b_{i} \\
\vdots \\
a_{m, 1} x_{1} \oplus a_{m, 2} x_{2} \oplus \ldots \oplus a_{m, n} x_{n}=b_{i} \\
\end{array}\]
where $a_{i, j}$'s (for $1 \leq i \leq m, 1 \leq j \leq n, b_{i}$'s (for all $1 \leq i \leq m$, and $x_{k}$'s (for all $1 \leq k \leq n$ ) take values in $\{0,1\}$.
- What is the expected number of equations that can be satisfied if $x_i$'s are picked uniformly and independently at random.
