Låt
T vara en mängd med binära strängar, säg en delmängd av GF(2)^
n. Låt
|T| = t. Låt
S vara en mängd index av storlek
k. Hur litet kan
T väljas (om det väljs slumpmässigt!) sådan att
Pr[max_S \sum_{x_i \in S} x_i = 0 (mod 2)] \leq 1/2 ± \epsilon
där
x \in T? Kort sagt: vi har en sampelmängd
T som är begränsad, hur liten kan de väljas för att en godtycklig mängd index skall ha en bias mindre än
\epsilon?
Har suttit och klurat på den ett tag nu... Om man t ex väljer en mängd
T som innehåller alla utom ett element i GF(2)^
n, då har vi ett index där det skiljer sig. Om vi väljer
S = {den positionen det skiljer sig}, så får vi en bias på
1/n. Men hur litet kan
T väljas?
Skulle behöva något tips i rätt riktning...