Basso limite di disgiunzione per discrepanza?
-
05-11-2019 - |
Domanda
Devo dimostrarlo $ Disc_ mu (disj) geq frac {1} {2n+1} $ per qualsiasi distribuzione $ mu: {0,1 }^n Times {0,1 }^n a [0,1] $. La disgiunzione è definita come
$ Disj (x, y) = left { inizio {array} [ll] +1 & text {if $ x cap y = vuoto $} 0 & text {altrimenti} end {array } a destra. $
La discrepanza per una funzione è definita come $ Disc_ mu (f) = max_r {disc_ mu (r, f) } $ su tutti i rettangoli $ R $ e inoltre
$$ disc_ mu (r, f) = | pr_ mu [(x, y) in r wedge f (x, y) = 1] - pr_ mu [(x, y) in r Wedge f (x, y) = 0] |. $$
Non capisco dove il $ frac {1} {2n+1} $ viene da e come definire un rettangolo adeguato $ R $.
Il problema è dato come esercizio senza una soluzione nel libro Complessità comunicativa Di E. Kushilevitz e N. Nisan a pagina 40.
Nessuna soluzione corretta