I had this question in Learning theory, but it's really just a question in probability theory to be honest, so I'm gonna try to rephrase it in a way that really emphasizes what I was trying to do to solve it:

Let $\mathcal X_N=\{0,1\}^N$, $\mathcal Y=\{0,1\}$ and define a uniform distribution, $\mathcal D_N$, on $\mathcal X_N \times \mathcal Y$. Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge \forall \, 1\leq j \leq m, \,x_j(i)=y_j)>\delta$

Original phrasing:

Let $\mathcal X_N=\{0,1\}^N$, $\mathcal Y=\{0,1\}$ and define a uniform distribution, $\mathcal D_N$, on $\mathcal X_N \times \mathcal Y$. Define the hypothesis class $\mathcal H_N = \{h_i: \mathcal X_N \to \mathcal Y \mid 1 \leq i \leq N \}$, where $h_i(x) = x(i)$.

Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge L_S(h)=0)>\delta$

So a few things:

$S$ is obtained by randomly and independently drawing $(x,y)$ pairs from $\mathcal D_N$,

$L_D(i) = \mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y)$,

x(i) - is the i'th coordinate of the $N$ dimensional vector x.

What I tried to do was:

First of all, fix an $i\in \{1,...,N\}$ and consider $\mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y) = 2\frac{2^{N-1}}{2^{N+1}} = \frac{1}{2} > \epsilon $ for any $\epsilon \in (0,\frac{1}{2})$ so the first requirement is rather redundant.

Second, independently drawing a sequence $S$ of $m$ pairs (with repetition) such that every pair has $x(i)=y$ is with probability $\mathbb P_{S\sim \mathcal D^m} (\forall \, 1\leq j \leq m : x_j(i)=y_j) = \prod_{j=1}^m \mathbb P_{(x,y)\sim \mathcal D} (x_j(i)=y_j) = \frac{1}{2^m}$.

Now that's for a single fixed $i\in [N]$, trying to lower bound the probability of an existence of such an $i$ could either be done by just ignoring the rest and saying $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j)\geq \frac{1}{2^m} > \delta$
But that is a very gross estimation so I calculated the probability exactly using inclusion-exclusion principle like so:

let $1 \leq i_1 < i_2 <... < i_k \leq N\,$ then $\mathbb P_{S\sim \mathcal D^m} (\bigwedge_{t=1}^k \{ \forall \, 1\leq j \leq m, \,x_j(i_t)=y_j\}) = (\prod_{t=1}^k \mathbb P_{S\sim \mathcal D^m} (x(i)=y))^m = \frac{1}{2^{km}}$

finally we get:

$\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j) = \sum_{i=1}^N (-1)^{i-1}{{N}\choose{i}}(\frac{1}{2^m})^i$

And now my goal is to lower bound this by $\delta$ and using some closed form of this expression.

My question is first, is my analysis even correct and second, how would you proceed?

Thanks in advance!


2 Answers 2


Since each $x$ is uniformly chosen, the probability of having a certain value at the $i$'th spot is independent of the probability of finding some other certain value in the $j$'th spot. You showed this already, but notice it means that you dont need the inclusion-exclusion principle, and instead the probability will just be the probability of the complement, which is $1-\frac{1}{2^{km}}$. You can now easily choose $k$ such that this probability would be bigger than $\delta$

  • $\begingroup$ You are right about the independence in choosing each coordinate of the vector and each vector in $S$, hence the probabilities $\frac{1}{2^{mk}},\, k\in \{1,2,...,N\}$ but these aren't the events that intersect. The events $A(i): \{\forall \,1\leq j \leq m : x_j(i)=y_j \}$ are not independent, it is very much possible for a single vector (or even all m vectors) to have both the i'th and j'th coordinate equal to y. Plus this solution doesn't depend on $N$. The complement of what I'm trying to calculate would be $\mathbb P (\text{no } i \in [N] \text{satisifies } : \forall j\in [m]: x_j(i)=y_j)$ $\endgroup$
    – giorgioh
    Mar 30, 2021 at 9:34
  • $\begingroup$ I believe what you've calculated is the probability that for $k$ fixed $i\in [N]\,$ values at least one of them doesn't satisfy the property of having the coordinate same as $y$. $\endgroup$
    – giorgioh
    Mar 30, 2021 at 9:39
  • $\begingroup$ You need to know the probability that a certain index wont be a good hypothesis, then from independence, raise that number to the power of $N$ (here it was $k$) to get the probability that no hypothesis is correct. Its complement would have probability $1-\frac{1}{2^{Nm}}$ and now choose $N$ big enough so this value will be larger than $\delta$ $\endgroup$
    – nir shahar
    Mar 30, 2021 at 11:02
  • $\begingroup$ But the probability that a certain index, say $i$ isn't a good hypothesis on $S$ isn't $\frac{1}{2^m}$ since it suffices that at least one of $j=1,2,...,m$ have $x_j(i)\neq y_j$. Unless I got it all wrong and that is the probability, although an explanation on why that is would be helpful. $\endgroup$
    – giorgioh
    Mar 30, 2021 at 11:07

Your analysis appears fine, it remains to apply the binomial formula to compute your sum.

$\sum\limits_{i=1}^N (-1)^{i-1} {N\choose i}\frac{1}{2^{mi}}=1-\sum\limits_{i=0}^{N}(-1)^i {N\choose i}\frac{1}{2^{mi}}=1-\left(1-\frac{1}{2^m}\right)^N\ge 1-e^{-N/2^m}\ge\delta$,

Where the last inequality holds for $N\ge 2^m\log\frac{1}{1-\delta}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.