  We consider the problem of identifying the causal direction between two
discrete random variables using observational data. Unlike previous work, we
keep the most general functional model but make an assumption on the unobserved
exogenous variable: Inspired by Occam's razor, we assume that the exogenous
variable is simple in the true causal direction. We quantify simplicity using
R\'enyi entropy. Our main result is that, under natural assumptions, if the
exogenous variable has low $H_0$ entropy (cardinality) in the true direction,
it must have high $H_0$ entropy in the wrong direction. We establish several
algorithmic hardness results about estimating the minimum entropy exogenous
variable. We show that the problem of finding the exogenous variable with
minimum entropy is equivalent to the problem of finding minimum joint entropy
given $n$ marginal distributions, also known as minimum entropy coupling
problem. We propose an efficient greedy algorithm for the minimum entropy
coupling problem, that for $n=2$ provably finds a local optimum. This gives a
greedy algorithm for finding the exogenous variable with minimum $H_1$ (Shannon
Entropy). Our greedy entropy-based causal inference algorithm has similar
performance to the state of the art additive noise models in real datasets. One
advantage of our approach is that we make no use of the values of random
variables but only their distributions. Our method can therefore be used for
causal inference for both ordinal and also categorical data, unlike additive
noise models.
