This post is improved from Determine binary function $f(x)$ by partial observation of $x$. Since the form of the problem is changed in a great extent. I would like to create a new post rather than edit the old one. If it is inappropriate, feel free to edit these two.
Let us start with some random variables $X_1, \dots, X_n$ and $Y$. Suppose Alice wants to transmit $Y$ to Bob by using $n$ communication channels. She does this by directly sending $X_i$ through the $i$-th channel respectively. Of course, the fact that this coding is correct gives us $$ H(Y|X_1,\dots,X_n)=0 $$ Now, here is an eavesdropper Eve. She can observe random $k$ channels out of $n$. In other words, she will know random $k$ variables out of $X_1,\dots,X_n$. Suppose the coding scheme can guarantee that Eve will not gain too more information about $Y$, by $$ \frac{1}{\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} I(Y; (X_i : i \in A)) \leq \epsilon $$ Then we can derive a bound about $\sum_{i=1}^n H(X_i)$: $$ \frac{1}{n}\sum_{i=1}^n H(X_i) \geq \frac{1}{(n-k)\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} H((X_i:i \notin A)) \\ \geq \frac{1}{(n-k)\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} I(Y;(X_i:i \notin A) | (X_i:i \in A)) \\ = \frac{1}{(n-k)\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} \left( I(Y;X_1,\dots,X_n) - I(Y;(X_i:i \in A)) \right) \\ =\frac{1}{n-k}(H(Y)-\epsilon) $$ My question:
Is this bound tight or asymptotic optimal? Is there any reference related to this problem, since it seems to be quite natural?
Trivial result. For $k = n-1$ and $\epsilon=0$, the bound is tight. For a construction one can refer to here.
Result from Xitip. I have used Xitip to verify the inequality where $n \leq 5$. I found that when I slightly increase the coefficient ($1/(n-k)$), the program reported that it would be no longer a Shannon-type inequality. This fact suggests that if the bound is not tight, we may find a family of new non-Shannon-type inequalities.
Cross-posted at https://cstheory.stackexchange.com/questions/39102/.