# Find minimum conditional entropy

Task : Given $X$ random variables. Find out the minimum conditional entropy for a variable $x_i \in X$ when $x_i$ is conditioned upon any combination $k$ remaining variables. Find $min(Entropy (x_i | k\,variables))$. Value need not be exact, approximate solutions are fine.

However, I am wondering is it possible to find out the solution to the above mentioned problem. Without resolving to enumerate [brute force approach] all possible subsets of size $k$ from remaining $n-1$ variables. And keep a track of the minimum conditional entropy obtained. $Entropy(x_i | Remaining\,variables)$ is the lowest but I intend to get more tighter bound.

• What do you know about X? I can think of a case where $x_i$ is independent of all other variables, then its entropy is maximal regardless of the conditioning, or a case where $x_u$ is highly dependent on the others, then the entropy can go to 0 when conditioning on $k$ variables that determine $x_i$. – Ran G. May 25 '16 at 1:42
• @RanG. What should be known about X? Please ignore my incompetence in stats. Knowledge of which information will make the task of finding the minimum entropy for $$X_i$$ when conditioned by a set $$k$$ remaining variables efficient. No prior knowledge is given about $$X$$. – letsBeePolite Jan 29 '17 at 18:48