Return to Question

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function $f: \mathbb{R}^n \to \{0,1\}$ such that $\mathrm{H}(f(\boldsymbol{x})) = \log 2 = 1$, where $\mathrm{H}$ is the entropy function. Consider the lower bound of $$ S_k = \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}}\mathrm{I}((\boldsymbol{x}_i : i \in A);f(\boldsymbol{x})) $$ where $\mathrm{I}$ stands for mutual information. It is easy to see that when $k<n$, the lower bound is exactly $0$ since we could construct $\boldsymbol{x}$ and $f$ like

• $\boldsymbol{x}$ satisfies that $\boldsymbol{x}_1,\dots,\boldsymbol{x}_n$ are i.i.d. and $\boldsymbol{x}_1$ has the $1/2$ probability to be $0$ and $1$, respectively.
• $f((x_1,\dots,x_n)) = (x_1 + \cdots + x_n) \bmod{2}$.

However, if we restrict $\boldsymbol{x}$ to follow $$ \sum_{i=1}^n \Pr(\boldsymbol{x}_i \neq 0) \leq \epsilon n $$ with some "small" $\epsilon \in [0,1]$. It seems like that we could get a non-trivial lower bound.

My question:

Can we derive a non-trivial lower bound of $S_k$ with given $n$ and $\epsilon$?

Any idea or reference would be welcome indeed.

Background. This question is an abstract from a point-to-point communication with $n$ channels observed by a partial eavesdropper. "$0$" means no message. Hence the last restriction above actually controls the communication complexity, to some extent.

Cross-posted at https://cstheory.stackexchange.com/q/39053.

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function $f: \mathbb{R}^n \to \{0,1\}$ such that $\mathrm{H}(f(\boldsymbol{x})) = \log 2 = 1$, where $\mathrm{H}$ is the entropy function. Consider the lower bound of $$ S_k = \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}}\mathrm{I}((\boldsymbol{x}_i : i \in A);f(\boldsymbol{x})) $$ where $\mathrm{I}$ stands for mutual information. It is easy to see that when $k<n$, the lower bound is exactly $0$ since we could construct $\boldsymbol{x}$ and $f$ like

• $\boldsymbol{x}$ satisfies that $\boldsymbol{x}_1,\dots,\boldsymbol{x}_n$ are i.i.d. and $\boldsymbol{x}_1$ has the $1/2$ probability to be $0$ and $1$, respectively.
• $f((x_1,\dots,x_n)) = (x_1 + \cdots + x_n) \bmod{2}$.

However, if we restrict $\boldsymbol{x}$ to follow $$ \sum_{i=1}^n \Pr(\boldsymbol{x}_i \neq 0) \leq \epsilon n $$ with some "small" $\epsilon \in [0,1]$. It seems like that we could get a non-trivial lower bound.

My question:

Can we derive a non-trivial lower bound of $S_k$ with given $n$ and $\epsilon$?

Any idea or reference would be welcome indeed.

Background. This question is an abstract from a point-to-point communication with $n$ channels observed by a partial eavesdropper. "$0$" means no message. Hence the last restriction above actually controls the communication complexity, to some extent.

Trivial bound. Finding the bound of $S_k$ is equivalent to study $$ T_k = \frac{1}{\binom{n}{k}}\sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}}\mathrm{H}(f(\boldsymbol{x}) | (\boldsymbol{x}_i : i \in A)) $$ By some trivial method it seems that $$ T_k \leq \mathrm{H}(\epsilon(n-k)) $$ if $\epsilon(n-k) \leq 1/2$, where $\mathrm{H}(p) = - p \log p - (1-p) \log (1-p)$. I think it is quite loose.

Cross-posted at https://cstheory.stackexchange.com/q/39053.

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function $f: \mathbb{R}^n \to \{0,1\}$ such that $\mathrm{H}(f(\boldsymbol{x})) = \log 2 = 1$, where $\mathrm{H}$ is the entropy function. Consider the lower bound of $$ S_k = \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}}\mathrm{I}((\boldsymbol{x}_i : i \in A);f(\boldsymbol{x})) $$ where $\mathrm{I}$ stands for mutual information. It is easy to see that when $k<n$, the lower bound is exactly $0$ since we could construct $\boldsymbol{x}$ and $f$ like

• $\boldsymbol{x}$ satisfies that $\boldsymbol{x}_1,\dots,\boldsymbol{x}_n$ are i.i.d. and $\boldsymbol{x}_1$ has the $1/2$ probability to be $0$ and $1$, respectively.
• $f((x_1,\dots,x_n)) = (x_1 + \cdots + x_n) \bmod{2}$.

However, if we restrict $\boldsymbol{x}$ to follow $$ \sum_{i=1}^n \mathrm{E}(\boldsymbol{x}_i \neq 0) \leq \epsilon n $$ with some "small" $\epsilon \in [0,1]$. It seems like that we could get a non-trivial lower bound.

My question:

Can we derive a non-trivial lower bound of $S_k$ with given $n$ and $\epsilon$?

Any idea or reference would be welcome indeed.

Background. This question is an abstract from a point-to-point communication with $n$ channels observed by a partial eavesdropper. "$0$" means no message. Hence the last restriction above actually controls the communication complexity, to some extent.

Cross-posted at https://cstheory.stackexchange.com/q/39053  .

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function $f: \mathbb{R}^n \to \{0,1\}$ such that $\mathrm{H}(f(\boldsymbol{x})) = \log 2 = 1$, where $\mathrm{H}$ is the entropy function. Consider the lower bound of $$ S_k = \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}}\mathrm{I}((\boldsymbol{x}_i : i \in A);f(\boldsymbol{x})) $$ where $\mathrm{I}$ stands for mutual information. It is easy to see that when $k<n$, the lower bound is exactly $0$ since we could construct $\boldsymbol{x}$ and $f$ like

• $\boldsymbol{x}$ satisfies that $\boldsymbol{x}_1,\dots,\boldsymbol{x}_n$ are i.i.d. and $\boldsymbol{x}_1$ has the $1/2$ probability to be $0$ and $1$, respectively.
• $f((x_1,\dots,x_n)) = (x_1 + \cdots + x_n) \bmod{2}$.

However, if we restrict $\boldsymbol{x}$ to follow $$ \sum_{i=1}^n \Pr(\boldsymbol{x}_i \neq 0) \leq \epsilon n $$ with some "small" $\epsilon \in [0,1]$. It seems like that we could get a non-trivial lower bound.

My question:

Can we derive a non-trivial lower bound of $S_k$ with given $n$ and $\epsilon$?

Any idea or reference would be welcome indeed.

Background. This question is an abstract from a point-to-point communication with $n$ channels observed by a partial eavesdropper. "$0$" means no message. Hence the last restriction above actually controls the communication complexity, to some extent.

Cross-posted at https://cstheory.stackexchange.com/q/39053.

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function $f: \mathbb{R}^n \to \{0,1\}$ such that $\mathrm{H}(f(\boldsymbol{x})) = \log 2 = 1$, where $\mathrm{H}$ is the entropy function. Consider the lower bound of $$ S_k = \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}}\mathrm{I}((\boldsymbol{x}_i : i \in A);f(\boldsymbol{x})) $$ where $\mathrm{I}$ stands for mutual information. It is easy to see that when $k<n$, the lower bound is exactly $0$ since we could construct $\boldsymbol{x}$ and $f$ like

• $\boldsymbol{x}$ satisfies that $\boldsymbol{x}_1,\dots,\boldsymbol{x}_n$ are i.i.d. and $\boldsymbol{x}_1$ has the $1/2$ probability to be $0$ and $1$, respectively.
• $f((x_1,\dots,x_n)) = (x_1 + \cdots + x_n) \bmod{2}$.

However, if we restrict $\boldsymbol{x}$ to follow $$ \sum_{i=1}^n \mathrm{E}(\boldsymbol{x}_i \neq 0) \leq \epsilon n $$ with some "small" $\epsilon \in [0,1]$. It seems like that we could get a non-trivial lower bound.

My question:

Can we derive a non-trivial lower bound of $S_k$ with given $n$ and $\epsilon$?

Any idea or reference would be welcome indeed.

Background. This question is an abstract from a point-to-point communication with $n$ channels observed by a partial eavesdropper. "$0$" means no message. Hence the last restriction above actually controls the communication complexity, to some extent.

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function $f: \mathbb{R}^n \to \{0,1\}$ such that $\mathrm{H}(f(\boldsymbol{x})) = \log 2 = 1$, where $\mathrm{H}$ is the entropy function. Consider the lower bound of $$ S_k = \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}}\mathrm{I}((\boldsymbol{x}_i : i \in A);f(\boldsymbol{x})) $$ where $\mathrm{I}$ stands for mutual information. It is easy to see that when $k<n$, the lower bound is exactly $0$ since we could construct $\boldsymbol{x}$ and $f$ like

• $\boldsymbol{x}$ satisfies that $\boldsymbol{x}_1,\dots,\boldsymbol{x}_n$ are i.i.d. and $\boldsymbol{x}_1$ has the $1/2$ probability to be $0$ and $1$, respectively.
• $f((x_1,\dots,x_n)) = (x_1 + \cdots + x_n) \bmod{2}$.

However, if we restrict $\boldsymbol{x}$ to follow $$ \sum_{i=1}^n \mathrm{E}(\boldsymbol{x}_i \neq 0) \leq \epsilon n $$ with some "small" $\epsilon \in [0,1]$. It seems like that we could get a non-trivial lower bound.

My question:

Can we derive a non-trivial lower bound of $S_k$ with given $n$ and $\epsilon$?

Any idea or reference would be welcome indeed.

Background. This question is an abstract from a point-to-point communication with $n$ channels observed by a partial eavesdropper. "$0$" means no message. Hence the last restriction above actually controls the communication complexity, to some extent.

Cross-posted at https://cstheory.stackexchange.com/q/39053 .