Citat:
Ursprungligen postat av en kopp kaffe
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...
Jag förstår inte riktigt frågan. Påståendet
Pr[max_S \sum_{x_i \in S} x_i = 0 (mod 2)] \leq 1/2 ± \epsilon
verkar inte bero på T överhuvudtaget. Dessutom, vad i "max_S \sum_{x_i \in S} x_i = 0 (mod 2)" är det som är slumpmässigt, och på vilket sätt? Och sen förstår jag inte "Låt
S vara en mängd index av storlek
k". Vad exakt menar du med index här?