This post is improved from [Determine binary function $f(x)$ by partial observation of $x$](https://mathoverflow.net/questions/280737/). 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](https://mathoverflow.net/posts/280737/).


**Result from Xitip**. I have used [Xitip](http://xitip.epfl.ch/) 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/>.



Derive a theoretical bound about coding with a partial eavesdropper
(comment) If all subsets of size k leak $\frac{\epsilon}{n}$ bits, then you are looking at threshold (secret-sharing) schemes. In that specific case, it is tight: the bound is the *threshold gap* and the construction is a ramp scheme. Your leak condition being quite loose, other structures usually require a different bound (possibly with non-Shannon-type inequalities).


