2
$\begingroup$

Let $(X_{1},\dots,X_{m})$ be joint distribution on $\{0,1\}^{m}$ with that $H_{\infty}(X_{1},\cdots,X_{m})\geq m-r$, where $H_{\infty}$ means min-entropy.

Let $P_{1},...,P_{n}\subseteq [m]$ be sets such that, $\forall j\in[n], |P_{j}|\geq(\log n)^{2},$ and let $Y_{j}$ be a random variable that defined by $Y_{j}=(\sum_{i\in P_{j}}X_{i})/|P_{j}|$.

the question is that, could you show that, there exists $l_{1},\dots,l_{s}\in[0,1]^{n}$, where $s=2^{O(r)}$ such that $\Pr[\exists l_{r},\|l_{r}-(Y_{1},...,Y_{n})\|_{\infty}\leq 0.01]\geq 0.99.$

I think this question, is equal to the following question.

Let $(X_{1},\dots,X_{m})$ be the uniform distribution over $\{0,1\}^{m}$.

Let $P_{1},...,P_{n}\subseteq [m]$ be sets such that, $\forall j\in[n], |P_{j}|\geq(\log n)^{2},$ and let $Y_{j}$ be a random variable that defined by $Y_{j}=(\sum_{i\in P_{j}}X_{i})/|P_{j}|$.

Then, could you show that, there exists $l_{1},\dots,l_{s}\in[0,1]^{n}$, such that $\Pr[\exists l_{r},\|l_{r}-(Y_{1},...,Y_{n})\|_{\infty}\leq 0.01]\geq 1-2^{\Omega(\log s)}.$

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .