Trovare algoritmo randomizzato efficiente

Question

Sto facendo un corso su algoritmi randomizzati e ho incontrato una domanda che sto lottando per risolvere.

Dato un sistema di $ m $ equazioni lineari con $ n $ variabili sul campo finito $ mathbb {f_2} $ dove ogni equazione è di forma $ a_1x_1+...+a_nx_n = b mod 2 $ e $ x_i, a_i, b in {0,1 } $ e la moltiplicazione e la somma sono $ mod 2 $.

Prima parte della domanda è trovare un algoritmo randomizzato efficiente che trova un incarico alle variabili $\{0,1\}$ in modo che il valore atteso delle equazioni soddisfatte sia $ frac {m} {2} $. Questa parte è relativamente facile, scegliendo un assinga casuale su $\{0,1\}$ ci dà il risultato desiderato. Ogni equazione è soddisfatta della probabilità $ frac {1} {2} $ e valore atteso oltre $ m $ Le equazioni ci darà $ frac {m} {2} $ equazioni soddisfatte.

La seconda parte è quello con cui lotto, viene chiesto di dimostrare che esistono $ O (logm) $ assegnazioni alle variabili in modo tale che ogni equazione sia soddisfatta da almeno un incarico. E viene chiesto di proporre un algoritmo efficiente randomizzato che trova quelli $ O (logm) $ Assegnazioni con probabilità almeno $ frac {1} {2} $. C'è anche un suggerimento: permettere $ E_i $ essere un evento che l'assegnazione casuale soddisfa l'equazione $ i $, quindi eventi $ E_i (1 <= i <= m) $ sono $ 2 per quanto riguarda $ indipendente.

Non so davvero come affrontare questo. Qualsiasi aiuto sarebbe apprezzato.