Causal Inference on Discrete Data using Additive Noise Models

Introduction

Inferring causal relations by analyzing statistical dependences among observed random variables is a challenging task if no controlled randomized experiments are available. So-called constraint-based approaches to causal discovery (Pearl, 2000; Spirtes et al., 1993) select among all directed acyclic graphs (DAGs) those that satisfy the Markov condition and the faithfulness assumption, i.e., those for which the observed independences are imposed by the structure rather than being a result of specific choices of parameters of the Bayesian network. These approaches are unable to distinguish among causal DAGs that impose the same independences. In particular, it is impossible to distinguish between $X\rightarrow Y$ and $Y\rightarrow X$. More recently, several methods have been suggested that use not only conditional independences, but also more sophisticated properties of the joint distribution. For simplicity, we explain the ideas for the two variable setting since this case is particularly challenging. Kano & Shimizu (2003) use models

where $f$ is a linear function and $N$ is additive noise that is independent of the hypothetical cause $X$. This is an example for an additive noise model from $X$ to $Y$. Apart from trivial cases, $P(X,Y)$ can only admit such a model from $X$ to $Y$ and from $Y$ to $X$ in the bivariate Gaussian case. Hoyer et al. (2009) generalize the method to non-linear functions $f$ and showed that generic models of this form generate joint distributions that do not admit such an additive noise model from $Y$ to $X$. Zhang & Hyvarinen (2009) augment the model by applying a non-linear function $g$ to the rhs of eq. (1) and still obtain identifiability for generic cases. Peters et al. (2009) use independent linear additive noise models in order to detect whether a sample of a time series has been reversed. Their positive results further support this way of causal reasoning. All these proposals, however, were only designed for real-valued variables $X$ and $Y$.

For discrete variables, Sun et al. (2008) propose a method to measure the complexity of causal models via a Hilbert space norm of the logarithm of conditional densities and prefer models that induce smaller norms. Sun et al. (2006) fit joint distributions of cause and effect with conditional densities whose logarithm is a second order polynomial (up to the log-partition function) and show that this often makes causal directions identifiable when some or all variables are discrete. For discrete variables, several Bayesian approaches (Heckerman et al., 1999) are also applicable, but the construction of good priors are challenging and often the latter are designed such that Markov equivalent DAGs still remain indistinguishable.

The main idea of the causal inference method we propose goes as follows: If such an additive noise model exists in one direction but not in the other, we prefer the former based on Occam’s Razor and infer it to be the causal direction.

Such a procedure is only sensible if there are only few instances, in which there is an additive noise models in both directions. If, for example, all additive noise models from $X$ to $Y$ also allow an additive noise model from $Y$ to $X$, we could not draw any causal conclusions at all. We will show that reversible cases are very rare and thereby answer this theoretical question.

For a practical causal inference method we have to test whether the data admits an additive noise model and thus have to perform a discrete regression. But since in the discrete case regularization of the regression function is not necessary, in principle we would have to check all possible functions and test whether they result in independent residuals. This is highly intractable, of course, and we therefore propose an efficient heuristic procedure that proved to work very well in practice.

In section 2 we extend the concept of additive noise models to discrete random variables and show the corresponding identifiability results for generic cases in section 3. In section 4 we introduce an efficient algorithm for causal inference on finite data, for which we show experimental results in section 5. We conclude in section 6.

Additive Noise Models for Discrete Variables

As it has been proposed for the continuous case by Shimizu et al. (2006); Hoyer et al. (2009); Zhang & Hyvarinen (2009) we assume the following causal principle to hold throughout the remainder of this article:

Causal Inference Principle (for discrete random variables) Whenever $Y$ satisfies an additive noise model with respect to $X$ and not vice versa then $X$ is a cause for $Y$, and we write $X\rightarrow Y$.

Janzing & Steudel (2009) give further theoretical support for this principle using the concept of Kolmogorov complexity and Peters et al. (2009) use this way of reasoning for detecting the arrow of time.

Note that whenever there is no additive noise model in any direction (which may well happen) we do not draw any causal conclusions and other causal inference methods should be tried.

Furthermore we require $n(0)\geq n(j)$ for all $j\neq 0$. This does not restrict the model class, but is due to a freedom we have in choosing $f$ and $N$: If Y=f(X)+N,\,N\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X, then we can always construct a new function $f_{j}$, such that Y=f_{j}(X)+N_{j},\,N_{j}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X by choosing $f_{j}(i)=f(i)+j$ and $n_{j}(i)=n(i+j)$.

Such an additive noise model is called reversible if there is also an additive noise model from $Y$ to $X$, i.e. if it satisfies an additive noise model in both directions.

2 Cyclic Constraint

We can extend additive noise models to random variables which inherit a cyclic structure and therefore take values in a periodic domain. Random variables are usually defined as measurable maps from a probability space into the real numbers. We thus make the following definition

Let $(\Omega,\mathcal{F},{\mathbf{P}})$ be a probability space. A function $X:\Omega\rightarrow\mathbf{Z}/m\mathbf{Z}$ is called an $m$-cyclic random variable if $X^{-1}(k)\in\mathcal{F}\;\forall k\in\mathbf{Z}/m\mathbf{Z}$. All other concepts of probability theory (like distributions and expectations) can be constructed analogous to the well-known case, in which $X$ takes values $\{0,\ldots,m-1\}$.

3 Relations

The following two remarks are essential in order to understand the relationship between integer and cyclic constraints:

(1) The difference between these two models manifests in the target domain. If we consider an ANM from $X$ to $Y$ it is important whether we put integer or cyclic constraints on $Y$ (and thus on $N$). It does not make a difference, however, whether we consider the regressor $X$ to be cyclic (with a cycle larger than the support of $X$) or not. The independence constraint remains the same.

(2) In the finite case additive noise models with cyclic constraints are more general than the ones with integer constraints: Assume there is an ANM $Y=f(X)+N$, where all variables are taken to be non-cyclic and $Y$ takes values between $k$ and $l$, say. Then we still have an ANM $Y=f(X)+N$ if we regard $Y$ to be $l-k+1$-cyclic because $N\mod(l-k+1)$ remains independent of $X$. It is possible, however, that N\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}\diagup\hskip 3.98337ptX, but N\mod(l-k+1)\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X (see Example 2 in Section 3.2.1).

Identifiability

Whether an additive noise model is allowed depends on the form of the joint distribution ${\mathbf{P}}^{(X,Y)}$. Let $F$ be the subset of the set $A$ of all possible joint distributions that allow an additive noise model from $X$ to $Y$ in the “forward direction”, whereas $B$ allows an additive noise model in the backward direction from $Y$ to $X$. Some trivial examples like $p_{X}(0)=1,n(0)=1$ and $f(0)=2$ immediately show that there are joint distributions allowing additive noise models in both directions, meaning $F\cap B\neq\emptyset$ (see Figure 1). But how large is this intersection? Our method would not be useful if we find out that $F$ and $B$ are almost the same sets. Then most additive noise models can be fit in either both directions or in none. For additive noise models with integer constraints and with cyclic constraints we identify the intersection $B\cap F$ and show that it is indeed a very small set. If we are unlucky and the data generating process we consider happens to be in $B\cap F$, our method does not give wrong results, but answers “I do not know the answer”. In all other situations the method identifies the correct direction given that we observe enough data. The proofs are provided in the appendix.

Figure 3 shows a (rather non-generic) example that allows an ANM in both directions if we choose $p_{X}(a_{i})=\frac{1}{36},p_{X}(b_{i})=\frac{2}{36}$ for $i=1,\ldots,4$ and $p_{X}(a_{i})=\frac{2}{36},p_{X}(b_{i})=\frac{4}{36}$ for $i=5,\ldots,8$.

The $C_{i}$s are shifted versions of each other

The probability distributions on the $C_{i}$s are shifted and scaled versions of each other with the same shift constant as above: For $x\in C_{i}$

As for the other theorems of this section the proof is provided in the appendix. Its main point is based on the asymmetric effects of the “corners” of the joint distribution. In order to allow for an infinite support of $X$ (or $Y$) the proof generalizes the concept of “corners”.

1.2 X𝑋X and Y𝑌Y have infinite support

Consider an additive noise model $X\rightarrow Y$ where both $X$ and $Y$ have infinite support. We distinguish between two cases

Note that the first case is again a complete characterization of all instances of a joint distribution, an ANM in both directions is conform with. The second case does not yield a complete characterization, but shows how restricted we are for a given function $f$ and noise $N$ in order to choose a distribution ${\mathbf{P}}^{X}$ that yields a reversible ANM.

2 Cyclic Constraint

Note that the model $Y=f(X)+N$ is reversible if and only if there is a function $g$, such that

First, we give three examples of additive noise models that are not identifiable. This restricts the class of situations in which identifiability can be expected. Figure 4 shows instances of all three examples.

If $Y=f(X)+N$ for a bijective and affine $f$ and uniformly distributed $X$, then the model is reversible.

2.2 Identifiability Results

Motivated by the counter examples we now make the assumptions that $f$ is not constant (Example 1(i)), $N$ is not uniformly distributed (Example 1(ii)) and that not both $X$ and $Y$ are uniformly distributed (Example 2). Without proof we state the conjecture that this is already enough to ensure identifiability meaning an ANM can only hold in one direction.

Assume $X,Y$ and $N$ are random variables that are not uniformly distributed and non-degenerate (that is they do not only take one value). Assume further that we have an additive noise model Y=f(X)+N,\,N\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X with non-constant $f$. Then there is no additive noise model from $Y$ to $X$.

3 Mixed Constraints

With the results developed in the last two section we can cover even models with mixed constraints (for the precise conditions of “usually” see Section 3.2):

Practical Method for Causal Inference

Based on our theoretical findings in Section 3 we propose the following method for causal inference (see Hoyer et al. (2009) for the continuous case):

Given: iid data of the joint distribution ${\mathbf{P}}^{(X,Y)}$.

Regularization of the regression function is at least in principle not necessary in the discrete case. Since we may observe many different values of $Y$ for one specific $X$ value there is no risk in overfitting. This introduces further difficulties compared to continuous regression since in principle we now have to try all possible functions from $X$ to $Y$ and compare the corresponding values of the loss function.

(2) Even if all values of the true function $f$ are one of the $m:=\#\{\min Y,\min Y+1,\ldots,\max Y\}$ considered values, the problem of checking all possible functions is not tractable: If $n=20$ and $m=16$ there are $16^{20}=2^{80}$ possible functions (the amount of particles in the universe is estimated to be $\approx 10^{79}$). We thus propose the following heuristic but very efficient procedure (the experimental results will show that it works very reliably in practice):

2 Independence Test and Dependence Measure

Assume we are given joint iid samples $(W_{i},Z_{i})$ of the discrete variables $W$ and $Z$ and we want to test whether $W$ and $Z$ are independent. In our implementation we only use Person’s $\chi^{2}$ test (e.g. E. L. Lehmann (2005)), which is most commonly used. It computes the difference between observed frequencies and expected frequencies in the contingency table. The test statistic is known to converge towards a $\chi^{2}$ distribution, which is taken as an approximation even in the finite sample case. For very few samples, however, this approximation and therefore the test will usually fail. It has been suggested (e.g. RProject (2009)) that instead of a $\chi^{2}$ test, Fisher’s exact test (E. L. Lehmann, 2005) could be used if not more than $80\%$ of the expected counts are larger than 5 (“Cochran’s condition”).

For a dependence measure we simply use the $p$-value of the independence test or the test statistic if the $p$-value is too small (in a computer system the $p$-value is sometimes regarded to be zero).

Experiments

We first investigate the performance of our method on synthetic data sets. Therefore we simulate data from additive noise models and check whether the method is able to rediscover the true model. We showed in Section 3 that only very few examples allow a reversible ANM.

Data sets 1a and 1b support these theoretical results. We simulate a large amount of data (1000–2000 data points) from many randomly chosen models. All models that allow an ANM in both directions are instances of our examples from above (without exception).

Data sets 2a and 2b show how well our method performs for small data size and models that are close to non-identifiable.

Data set 3a investigates empirically the run-time performance of our regression method and compares it with a brute-force search.

Data set 3b shows that the method does not favor one direction if the supports of $X$ and $Y$ are of different size.

The results given in Table 1 show that the methods works well on almost all simulated data sets. The algorithm outputs “bad fit in both directions” in roughly $5\%$ of all cases, which corresponds to the chosen test level. The model is non-identifiable only in very few cases, which are shown in Table 1. All of these cases are instances of the counter examples from above. This experiment further supports our proposition that the model is identifiable in the generic case.

Data set 2a (close to non-identifiable). For this data set we sample from the model $Y=f(X)+N$ with

Depending on the parameter $r$ we sample $X$ from

For each value of the parameter $r$ ranging between $-0.2\leq r\leq 0.2$ we use 100 different samples, each of which has the size 400.

In Theorem 2 we proved that the ANM is reversible if and only if $r=0$. Figure 5 shows that the algorithm identifies the correct direction for $r\neq 0$. Again, the test level of $\alpha=5\%$ introduces indecisiveness of roughly the same size, which can be seen for $|r|\geq 0.15$. The number of such cases can be reduced by decreasing $\alpha$ (but would lead to some wrongly accepted backward models, too).

Each time we simulated a uniformly distributed $X$ with $i$ values between $-\frac{i-1}{2}$ and $\frac{i-1}{2}$ for $i=3,5,7,\ldots,19$. For each noise/regressor distribution we simulated 100 data sets.

For $N_{1}$ and $i=9$, for example, there are $(11-(-2))^{9}\approx 1.1\cdot 10^{10}$ possible functions in total and $5^{9}\approx 2.0\cdot 10^{6}$ functions with positive empirical support. Our method only checked $104\pm 33$ functions before termination. The full results are shown in Figure 6.

1.2 Cyclic Constraints

The results given in Table 2 show that the method works well on almost all simulated data sets. The algorithm outputs “bad fit in both directions” in roughly $5\%$ of all cases, which corresponds to the chosen test level. The model is non-identifiable only in very few cases, which are shown in Table 3. All of these cases are instances of the counter examples from above. This experiment further supports our theoretical result that the model is identifiable in the generic case.

Example 1 and the fact that $n(0)\neq n(2)$ (see proof of Proposition 7) show that the model is not identifiable if and only if the noise distribution is uniform, i.e. if and only if $r=\frac{1}{2}$. The further $r$ is away from $\frac{1}{2}$, the more the noise differs from a uniform distribution and the easier it should be for our method to detect the true direction. For each value of the parameter $r$ we use 100 different samples, each of which has size 200. Figure 8 shows the results.

For $r=0.58$ and $r=0.68$ (indicated by the arrows in Figure 8) we further investigate the dependence on the data size. Clearly, $r=0.58$ results in a model that is still very close to non-identifiability and thus we need more data to perform well (see Figure 8). Note that non-identifiable models lead to very few, but not to wrong decisions.

2 Real Data.

Data set 4 (abalone). We also applied our method to the abalone data set (Nash et al., 1994) from the UCI Machine Learning Repository (Asuncion & Newman, 2007). We tested the sex $X$ of the abalone (male (1), female (2) or infant (0)) against length $Y_{1}$, diameter $Y_{2}$ and height $Y_{3}$, which are all measured in mm, and have $70,57$ and $28$ different values, respectively. Compared to the number of samples (up to 4177) we treat this data as being discrete. Because we do not have information about the underlying continuous length we have to assume that the data structure has not been destroyed by the user-specific discretization. We regard $X\rightarrow Y_{1}$, $X\rightarrow Y_{2}$ and $X\rightarrow Y_{3}$ as being the ground truth, since the sex is probably causing the size of the abalone, but not vice versa.

Clearly, the $Y$ variables do not have a cyclic structure. For the sex variable, however, the most natural model would be a structureless set which is contained in the cyclic constraints; for comparison we try both models for $X$. Our method with integer constraints is able to identify all 3 directions correctly. Since $X$ may be cyclic we also try to fit an ANM from $Y$ to $X$ with the cyclic constraints. Again, these models are rejected (see Table 5 and Figure 9). We used $\alpha=5\%$ and the first 1000 samples of the data set.

As mentioned earlier it is not surprising that we would accept an ANM from $X$ to $Y$ even if we put cyclic constraints on $Y$ (which are certainly violated for this data set). We would obtain the following $p$-values: $p\mbox{-value}_{X\rightarrow Y1}=0.17,p\mbox{-value}_{X\rightarrow Y1}=0.19$ and $p\mbox{-value}_{X\rightarrow Y1}=0.05$.

For this data set the method proposed by (Sun et al., 2006) returns a slightly higher likelihood for the true causal directions than for the false directions, but this difference is so small, that the algorithm does not consider it to be significant.

The abalone data set also shows that working with $p$-values requires some carefulness. For synthetic data sets that we simulate from one fixed model the $p$-values do not depend on the data size. In real world data, however, this often is the case. If the data generating process does not exactly follow the model we assume, but is reasonable close to it, we get good fits for moderate data sizes. Only including more and more data reveals the small difference between process and model, which therefore leads to small $p$-values. Figure 10 shows how the $p$-values vary if we include the first $n$ data points of the abalone data set (in total: 4177). One can see that although the $p$-values for the correct direction decrease they are clearly preferable to the $p$-values of the wrong direction. This is a well-known problem in applied statistics that also has to be considered using our method.

For $1000$ data points both directions are rejected ($p\mbox{-value}_{M\rightarrow T}=2e-4$, $p\mbox{-value}_{T\rightarrow M}=1e-13$). Figure 11 shows, however, that again the $p\mbox{-values}_{M\rightarrow T}$ are decreasing much slower than $p\mbox{-values}_{T\rightarrow M}$ thus using other criteria than simple $p$-values we still may prefer this direction and propose it as the true one.

Conclusions and Future Work

We proposed a method that is able to infer the cause-effect relationship between two discrete random variables. We proved that for generic choices the direction of a discrete additive noise model is identifiable in the population case and we developed an efficient algorithm that is able to infer the causal relationship between two variables for a finite amount of data. Since it is known that $\chi^{2}$ fails for small data sizes, changing the independence test for those cases may lead to an even higher performance of the algorithm.

Our method can be generalized in two directions: (1) handling more than two variables is straightforward from a practical point of view (although one may have to introduce regularization to make the regression computationally feasible) and (2) it should be investigated how our procedure can be applied to the case, where one variable is discrete and the other continuous. Corresponding identifiability results remain to be shown.

In future work additive noise models should be tested on more real world data sets in order to support (or disprove) additive noise models as a principle in causal inference. Furthermore we hope that more fundamental and general principles for identifying causal relationships will be developed that cover additive noise models as a special case. Nevertheless we regard our work as an important step towards understanding the difference between cause and effect.

Now we consider the other case, namely that $X$ has finite support. Then we define $C_{0},\ldots,C_{l}$ to be disjoint sets, such that $f$ is constant on each of them: $c_{i}:=f(C_{i})$. This time, it does not matter which of these sets is called $C_{0}$. Since

The rest of the proof is valid for both cases (either $X$ or $Y$ has finite support): Consider $C_{i}$ for any $i$. According to the assumption that an additive noise model $Y\rightarrow X$ holds we have

with $d_{i}=g(c_{i})-g(c_{0})$. Thus $C_{i}=C_{0}+d_{i}$ (including $d_{0}=0$).

For $x\in C_{i}$ (which implies $f(x)=c_{i}$) we have

In order to show that we have an reversible ANM we define the function $g$ as follows

B Proof of Theorem 3

${\mathbf{P}}(N=k)>0\,\forall\,m\leq k\leq l$ and ${\mathbf{P}}(N=k)=0$, else.

Start with any arbitrary $x_{1}=\min\{f^{-1}(f(x_{1}))\}$ and define

This implies $f(\hat{x}_{1})>f(x_{1})$ and $x_{1}\in C_{f(\hat{x}_{1})}$.

We have that either $\max\{f^{-1}(f(\hat{x}_{1}))\}>\max\{f^{-1}(f(x_{1}))\}$ or $\min\{f^{-1}(f(\hat{x}_{1}))\}<\min\{f^{-1}(f(x_{1}))\}$: Otherwise $C_{f(\hat{x}_{1})}$ and $C_{f(\hat{x}_{1})-1}$ satisfy

Because of $\hat{x}_{1}\in C_{f(\hat{x}_{1})},\hat{x}_{1}\notin C_{f(\hat{x}_{1})-1}$ this contradicts the existence of an backward additive noise model. Wlog we therefore assume $\max\{f^{-1}(f(\hat{x}_{1}))\}>\max\{f^{-1}(f(x_{1}))\}$. Then we even have $\hat{x}_{1}>x_{1}$,

(Otherwise we can use the same argument as above with $C_{f(x_{1})+N_{\max}}$ and $C_{f(x_{1})+N_{\max}+1}$.) Define further

Since $f^{-1}(f(x_{1}))\subset C_{f(x_{1})+N_{\max}}$, but $f^{-1}(f(x_{1}))\cap C_{f(x_{1})+N_{\max}+1}=\emptyset$, such a value must exist. Again, we can define $\hat{x}_{2}$ in the same way as above.

over the sequence $(x_{1},\hat{x}_{1},x_{2},\hat{x}_{2},\ldots,x_{n})$. But since we computed the boxes in a deterministic way, the same $\alpha$ satisfies

Note that a corresponding equation with the same constant $\alpha$ holds for the opposite direction. This leads to a contradiction, since there is no probability distribution for $X$ with infinite support that can fulfill this condition (no matter if $\alpha$ is greater, equal or smaller than $1$).

This direction is proved in exactly the same way as in Theorem 2.

C Proof of Theorem 5

regarding $(i)$: Each distribution $Y\,|\,X=x_{j}$ has to have the same support (up to an additive shift) and thus the same number of elements with probability greater than :

For $(ii)$ we now consider 3 different cases and show necessary conditions for reversibility each.

Assume Y=f(X)+N,\,N\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X for bijective $f$ and $n(l)\neq 0,p(k)\neq 0\,\forall k,l$. If the model is reversible with a bijective $g$, then $X$ and $Y$ are uniformly distributed.

Proof. Since $g$ is bijective we have that $\forall y\exists t_{y}\,:\,g(t_{y})=g(y)-1$. It follows from (2)

Since $f$ is bijective it follows that $q(y)=q(t_{y})$. This holds for all $y$ and thus $Y$ and $X$ are uniformly distributed. $\square$

$g$ is not injective. Assume $g(y_{0})=g(y_{1})$. From (2) it follows that

which imply equality constraints on $n$. To determine the number of constraints we define a function that maps the arguments of the numerator to those of the denominator

Assume Y=f(X)+N,\,N\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X and $n(l)\neq 0,p(k)\neq 0\,\forall k,l$. Assume further that the model is reversible with a non-injective $g$.

introduces a functional relationship between $p$ and $n$. $\square$

$f$ is not injective. Assume $f(x_{0})=f(x_{1})$. In a slight abuse of notation we write

Assume Y=f(X)+N,\,N\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X, $f$ is not injective and $n(l)\neq 0,p(k)\neq 0\,\forall k,l$. Assume further that the model is reversible for a function $g$.

The rest follows analogously to the proof of Proposition 7. $\square$

Note that these three cases are sufficient since $f$ and $g$ injective implies $n=m$ and $f$ and $g$ bijective.

References