\documentclass[twoside,11pt,pdf]{article}

\usepackage{jair}
\usepackage{general}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{theapa}
\usepackage{graphicx}
\usepackage{psfrag}

\renewcommand{\boldnu}{{\boldsymbol \nu}}


\newcommand{\Ev}{\mbox{${\cal O}$}}

%\newcommand{\Ptheta}{P_{\theta}}
%\newcommand{\Pthetapr}{P_{\theta'}}
%\newcommand{\Pthetahat}{P_{\hat{\theta}}}
%\newcommand{\Pthetalambda}{P_{\theta,\lambda}}
%\newcommand{\lambdawU}{\mbox{$\lambda_{w,U}$}}


%\newcommand{\LOD}{\mbox{$L_{\emph{OD}}$}}
%\newcommand{\LFV}{\mbox{$L_{\emph{FV}}$}}
%\newcommand{\LSigmapr}{\mbox{$L_{P,\Sigma'}$}}
%\newcommand{\LSigma}{\mbox{$L_{P,\Sigma}$}}
%\newcommand{\Lcar}{\mbox{$L_{P,\emph{car}}$}}
%\newcommand{\Lwcar}{\mbox{$L_{P,\emph{w-car}}$}}
%\newcommand{\Lscar}{\mbox{$L_{P,\emph{s-car}}$}}
%\newcommand{\Lxcar}{\mbox{$L_{\emph{x-car}}$}}

%\newcommand{\Lsat}{\mbox{$L_{P,\emph{sat}}$}}


%\newcommand{\cSigma}{\mbox{$c_{\Sigma}$}}
%\newcommand{\conscar}{\mbox{$c_{\emph{car}}$}}
%\newcommand{\conswcar}{\mbox{$c_{\emph{w-car}}$}}
%\newcommand{\consscar}{\mbox{$c_{\emph{s-car}}$}}
%\newcommand{\consxcar}{\mbox{$c_{\emph{x-car}}$}}

%\newcommand{\conssat}{\mbox{$c_{\emph{sat}}$}}


%\newcommand{\Sigmacar}{\mbox{$\Sigma_{\emph{car}}$}}
%\newcommand{\Sigmawcar}{\mbox{$\Sigma_{\emph{w-car}}$}}
%\newcommand{\Sigmascar}{\mbox{$\Sigma_{\emph{s-car}}$}}
%\newcommand{\Sigmaxcar}{\mbox{$\Sigma_{\emph{x-car}}$}}

%\newcommand{\Sigmaccar}{\mbox{$\Sigma_{\emph{ccar}}$}}
%\newcommand{\Sigmasat}{\Sigma_{\emph{sat}}}
%\newcommand{\Lambdacar}{\mbox{$\Lambda_{\emph{car}}$}}
%\newcommand{\Lambdawcar}{\mbox{$\Lambda_{\emph{w-car}}$}}
%\newcommand{\Lambdascar}{\mbox{$\Lambda_{\emph{s-car}}$}}
%\newcommand{\Lambdaxcar}{\mbox{$\Lambda_{\emph{x-car}}$}}

\newcommand{\mar}{\mbox{\emph{mar}}}
\newcommand{\mcar}{\mbox{\emph{mcar}}}
\newcommand{\car}{\mbox{\emph{car}}}
\newcommand{\Car}{\mbox{\emph{Car}}}

\newcommand{\wcar}{\mbox{\emph{w-car}}}
\newcommand{\scar}{\mbox{\emph{s-car}}}
\newcommand{\xcar}{\mbox{\emph{x-car}}}
\newcommand{\ccar}{\mbox{\emph{ccar}}}
\newcommand{\Ccar}{\mbox{\emph{Ccar}}}

\newcommand{\pd}{\mbox{\emph{pd}}}


\newcommand{\support}{\mbox{support}}
\renewcommand{\max}{\mbox{max}}

%\newcommand{\carcomp}{\mbox{$\sim_{\emph{car}}\,$}}
%\newcommand{\wcarcomp}{\mbox{$\sim_{\emph{w-car}}\,$}}
%\newcommand{\scarcomp}{\mbox{$\sim_{\emph{s-car}}\,$}}
%\newcommand{\xcarcomp}{\mbox{$\sim_{\emph{x-car}}\,$}}
%\newcommand{\notcarcomp}{\mbox{$\not\sim_{\emph{car}}\,$}}
%\newcommand{\notwcarcomp}{\mbox{$\not\sim_{\emph{w-car}}\,$}}
%\newcommand{\notscarcomp}{\mbox{$\not\sim_{\emph{s-car}}\,$}}
%\newcommand{\notxcarcomp}{\mbox{$\not\sim_{\emph{x-car}}\,$}}


\newcommand{\cargen}{CAR{\sc gen}}
\newcommand{\cargenstar}{CAR{\sc gen}$^*$}


\newcommand{\figurepath}{/home/jaeger/B/Papers/Evidence/Figures}
\newcommand{\citeGruHal}{Gr\"unwald and Halpern~\citeyear{GruHal03}}
\newcommand{\shortciteGLR}{\emph{GvLR}}
\newcommand{\shortciteGH}{\emph{GH}}

\jairheading{24}{2005}{889-917}{11/04}{12/05}
\ShortHeadings{Ignorability in Statistical and Probabilistic Inference}{Jaeger}
\firstpageno{889}

\bibliographystyle{theapa}

\title{Ignorability in Statistical and Probabilistic Inference}
\author{\name Manfred Jaeger \email jaeger@cs.aau.dk\\
\addr Institut for Datalogi, Aalborg Universitet\\
Fredrik Bajers Vej 7 E, DK-9220 Aalborg \O\\
}
\date{}

\begin{document}
\maketitle

\begin{abstract}
  When dealing with incomplete data in statistical learning, or incomplete 
observations in probabilistic inference, one needs to distinguish the fact
that a certain event is observed from the fact that the observed event has
happened. Since the modeling and computational complexities entailed by 
maintaining this proper distinction are often prohibitive, one asks for 
conditions under which it can be safely ignored. Such conditions are given
by the missing at random (mar) and coarsened at random (car) assumptions. 
In this paper we provide an in-depth analysis of several questions relating to
mar/car assumptions. Main purpose of our study is to provide 
criteria by which one may evaluate whether a car assumption is 
reasonable for a particular data collecting or observational process.
This question is complicated by the fact that several distinct 
versions of mar/car assumptions exist. We therefore first provide an
overview over these different versions, in which we highlight
the distinction between distributional and coarsening variable induced 
versions. We show that distributional versions are less restrictive and 
sufficient for most applications. We then address from two different perspectives
the question of when the mar/car assumption is warranted. First we provide
a ``static'' analysis that characterizes the admissibility of the car 
assumption in terms of the support structure of the joint probability distribution
of complete data and incomplete observations. Here we obtain an equivalence 
characterization that  improves and extends  a recent result by 
Gr\"unwald and Halpern. We then turn to a ``procedural'' analysis that 
characterizes the admissibility of the car assumption in terms of procedural 
models for the actual data (or observation) generating process. The main result
of this analysis is that the stronger coarsened completely at random (ccar)
condition is arguably the most reasonable assumption, as it alone corresponds 
to data coarsening procedures that satisfy a natural robustness  property.
\end{abstract}


\section{Introduction}

Probabilistic models have become the preeminent tool for reasoning under uncertainty 
in AI. A probabilistic model consists of a state space $W$, and a probability distribution
over the states $x\in W$. A given probabilistic model is used for probabilistic inference
based on observations. An observation determines a subset $U$\ of $W$\ that 
the true state now is known to belong to. Probabilities then are updated 
by conditioning on $U$. 

The required probabilistic models are often learned from empirical data using
statistical parameter estimation techniques. The data can consist of sampled exact
states from $W$, but more often it consists of incomplete observations, which only 
establish that the exact data point $x$\ belongs to a subset $U\subseteq W$. Both when 
learning a probabilistic model, and when using it for probabilistic inference,
one should, in principle, distinguish the event that a certain observation
$U$\ has been made (``$U$\ is observed'') from the event that the true state 
of $W$\ is a member of $U$\ (``$U$\ has occurred''). Ignoring this distinction
in probabilistic inference can lead to flawed probability assignments by conditioning.
Illustrations for this are given by well-known probability puzzles like the 
Monty-Hall problem or the three prisoners paradox. Ignoring this distinction
in statistical learning can lead to the construction of models that do not 
fit the true distribution on $W$. In spite of these known difficulties, one usually
tries to avoid the extra complexity incurred by making the proper distinction 
between ``$U$\ is observed'' and ``$U$\ has occurred''. In statistics there 
exists a sizable literature on ``ignorability'' conditions that permit learning
procedures to ignore this distinction. In the AI literature dealing with
probabilistic inference this topic has received rather scant attention, though it 
has been realized early on \cite{Shafer85,Pearl88}. Recently, however, 
\citeGruHal\ have provided a more in-depth analysis of ignorability from a 
probabilistic inference point of view. 

The ignorability conditions required for learning and inference have basically the
same mathematical form, which is  expressed in the \emph{missing at random} (\mar) or 
\emph{coarsened at random} (\car) conditions. In this paper we investigate several 
questions relating to these formal conditions. The central theme of this
investigation is to provide a deeper insight into what makes an observational
process satisfy, or violate, the coarsened at random condition. This question
is studied from two different angles: first (Section~\ref{sec:carcond}) 
we identify qualitative properties of the joint distribution of true states and
observations that make the \car\ assumption feasible at all. The qualitative
properties we here consider are constraints on what states and observations
have nonzero probabilities. This directly extends the work of 
\citeGruHal\ (henceforth also referred to as \shortciteGH). In fact, our main result
in Section~\ref{sec:carcond} is an extension and improvement over one of the main 
results in \shortciteGH. Secondly (Section~\ref{sec:procmodels}), we investigate
general types of observational procedures that will lead to \car\ 
observations. This, again, directly extends some of the material in \shortciteGH,
as well as earlier work by Gill, van der Laan \& Robins~\citeyear{GilvdLRob97} 
(henceforth also referred to as \shortciteGLR).
We develop a formal framework that allows us to analyze previous and new types
of procedural models in a unified and systematic way. In particular, this framework
allows us to specify precise conditions for what makes certain types of observational
processes ``natural'' or ``reasonable''. The somewhat surprising result 
of this analysis is that the arguably most natural classes of observational 
processes correspond exactly to those processes that will result in observations
that are \emph{coarsened completely at random} (\ccar) -- a strengthened version
of \car\ that often has been considered  an unrealistically strong assumption.



\section{Fundamentals of Coarse Data and Ignorability}

There exist numerous definitions in the literature of what it
means that data is missing or coarsened at 
random~\cite{Rubin76,DawDic77,HeiRub91,Heitjan94,Heitjan97,GilvdLRob97,GruHal03}.
While all capture the same basic principle, various definitions are subtly 
different in a way that can substantially affect their implications. In 
Section~\ref{sec:defcar}
we give a fairly comprehensive overview of the variant definitions, and 
analyze their relationships. In this survey 
we aim at providing a uniform framework and terminology for different 
\mar/\car\ variants. Definitions are attributed to those earlier sources 
where their basic content has first appeared, even though our definitions 
and our terminology can differ in some details from the original versions
(cf. also the remarks at the end of Section~\ref{sec:defcar}). 

Special emphasis is placed on the distinction between \emph{distributional} and 
\emph{coarsening variable induced} versions of \car. In this paper the main focus will then
be on distributional versions. In Section~\ref{sec:usingcar} we summarize results
showing that distributional \car\ is sufficient to establish ignorability for
probabilistic inference. 


\subsection{Defining \Car}
\label{sec:defcar}


We begin with the concepts introduced by Rubin~\citeyear{Rubin76} for the special case of data
with missing values. Assume that we are concerned with a multivariate random
variable $\boldX=(X_1,\ldots,X_k)$, where each $X_i$\ takes values in a finite 
state space $V_i$. Observations of $\boldX$\ are incomplete, i.e. we observe 
values $\boldy=(y_1,\ldots,y_k)$, where each $y_i$\ can be either the value
$x_i\in V_i$\ of $X_i$, or the special 'missingness symbol' $*$. One can view
$\boldy$\ as the realization of a random variable $\boldY$\ that is a function
of $\boldX$\ and a \emph{missingness indicator}, $\boldM$, which is a random
variable with values in $\{0,1\}^k$:
\begin{equation}
  \label{eq:YfXM}
  \boldY=f(\boldX,\boldM),
\end{equation}
where $\boldy=f(\boldx,\boldm)$\ is defined by
\begin{equation}
  \label{eq:defoffXM}
  y_i=\left\{
    \begin{array}{ll}
      x_i & \mbox{if }\ m_i=0\\
      *  & \mbox{if }\ m_i=1
    \end{array}
    \right. .
\end{equation}

Rubin's~\citeyear{Rubin76} original definition of missing at random is  a 
condition on the conditional distribution of $\boldM$: the data is 
\emph{missing at random} iff for all $\boldy$\ and all $\boldm$:
\begin{equation}
  \label{eq:M-mar}
  P(\boldM=\boldm\mid\boldX)
  \hspace{3mm}\mbox{is constant on}\hspace{3mm}
  \{\boldx\mid P(\boldX=\boldx)>0, f(\boldx,\boldm)=\boldy\}.
\end{equation}
We refer to this condition as the $\boldM$-\mar\ condition, to indicate the
fact that it is expressed in terms of the missingness indicator $\boldM$. 

\begin{examenv}
  \label{ex:T1T2-1}
Let $\boldX=(X_1,X_2)$\ with $V_1=V_2=\{p,n\}$. We interpret $X_1,X_2$\
as two  medical tests 
with possible outcomes \emph{positive} or \emph{negative}. 
Suppose that test $X_1$\ always is performed first on a patient, and 
that test $X_2$\ is performed if and only if $X_1$\ comes out positive.
Possible observations that can be made then are
\begin{displaymath}
  \begin{array}{l}
    (n,*)=f((n,n),(0,1))=f((n,p),(0,1)),\\
    (p,n)=f((p,n),(0,0)),\\
    (p,p)=f((p,p),(0,0)).
  \end{array}
\end{displaymath}
For $\boldy=(n,*)$\ and $\boldm=(0,1)$\ we obtain
\begin{displaymath}
  P(\boldM=\boldm\mid \boldX=(n,n))=P(\boldM=\boldm\mid \boldX=(n,p))=1,
\end{displaymath}
so that (\ref{eq:M-mar}) is satisfied. For other values of $\boldy$\ and
$\boldm$\ condition (\ref{eq:M-mar}) trivially holds, because the sets
of $\boldx$-values in (\ref{eq:M-mar}) then are singletons (or empty). 
\end{examenv}

We can also eliminate the random vector $\boldM$\ from the definition of 
\mar, and formulate a definition directly terms of the joint distribution
of $\boldY$\ and $\boldX$. For this, observe that each
observed $\boldy$\ can be identified with the set 
\begin{equation}
  \label{eq:defUofy}
  U(\boldy):=\{\boldx\mid \emph{for all}\ i: y_i\neq *\ \Rightarrow\ x_i=y_i\}.
\end{equation}
The set $U(\boldy)$\ contains the complete data values consistent with 
the observed $\boldy$. We can now 
rephrase $\boldM$-\mar\ as
\begin{equation}
  \label{eq:d-mar}
  P(\boldY=\boldy\mid \boldX) 
  \hspace{3mm}\mbox{is constant on}\hspace{3mm}
  \{\boldx\mid P(\boldX=\boldx)>0, \boldx\in U(\boldy)\}.
\end{equation}
We call this the \emph{distributional} \mar\ condition, abbreviated 
$d$-\mar, because it is in terms of the joint distribution of the 
complete data $\boldX$, and the observed data $\boldY$. 


\begin{examenv}
  \label{ex:T1T2-2}
(continued from Example~\ref{ex:T1T2-1}) We have 
\begin{displaymath}
  U((n,*))=\{(n,n),(n,p)\},\ U((p,n))=\{(p,n)\},\ U((p,p))=\{(p,p)\}. 
\end{displaymath}
Now we compute
\begin{displaymath}
  P(\boldY=(n,*)\mid \boldX=(n,n)))=P(\boldY=(n,*)\mid \boldX=(n,p)))=1.
\end{displaymath}
Together with the (again trivial) conditions for the two other possible
$\boldY$-values, this shows (\ref{eq:d-mar}).
\end{examenv}



$\boldM$-\mar\ and $d$-\mar\ are equivalent, because given $\boldX$\ there 
is a one-to-one correspondence between $\boldM$\ and $\boldY$, i.e. there 
exists a function $h$\ such that for all $\boldx,\boldy$\ with $\boldx\in U(\boldy)$:
\begin{equation}
  \label{eq:invertf}
  \boldy=f(\boldx,\boldm)\ \Leftrightarrow\ 
  \boldm=h(\boldy)
\end{equation}
($h$\ simply translates $\boldy$\ into a $\{0,1\}$-vector by replacing 
occurrences of $*$\ with 1, and all other values in $\boldy$\ with 0).
Using (\ref{eq:invertf}) one can easily derive a one-to-one 
correspondence between 
conditions (\ref{eq:M-mar}) and (\ref{eq:d-mar}), and hence obtain the equivalence
of $\boldM$-\mar\ and $d$-\mar.

One advantage of $\boldM$-\mar\ is that it easily leads to the strengthened 
condition of \emph{missing completely at random} \cite{Rubin76}:
\begin{equation}
  \label{eq:M-mcar}
   P(\boldM=\boldm\mid\boldX)
  \hspace{3mm}\mbox{is constant on}\hspace{3mm}
  \{\boldx\mid P(\boldX=\boldx)>0\}.
\end{equation}
We refer to this as the $\boldM$-\mcar\ condition. 

\begin{examenv}
  \label{ex:T1T2-3}
(continued from Example~\ref{ex:T1T2-2}) 
We obtain
\begin{displaymath}
  P(\boldM=(0,1)\mid \boldX=(n,p))=1\neq 0 = P(\boldM=(0,1)\mid \boldX=(p,p)).
\end{displaymath}
Thus, the observations here are not $\boldM$-\mcar. 
\end{examenv}

A distributional version
of \mcar\ is slightly more complex, and we defer its statement to the more general
case of coarse data, which we now turn to.

Missing attribute values are only one special way in 
which observations can be incomplete. Other possibilities include imperfectly observed 
values (e.g. $X_i$\ is only known to be either $x\in V_i$\ or 
$x'\in V_i$), partly attributed values (e.g. for $x\in V_i=V_j$\ it is 
only known that $X_i=x$\ or $X_j=x$), etc. 
In all cases, the incomplete observation of $\boldX$\ defines the
set of possible instantiations of $\boldX$\ that are consistent with the 
observation. This leads to the general concept of \emph{coarse data}~\cite{HeiRub91},
which generalizes the concept of missing data to observations of arbitrary
subsets of the state space. In this general setting it is convenient to abstract
from the particular structure of the state space as a product $\times_{i=1}^k V_i$\
induced by a multivariate $\boldX$, and instead just assume a univariate random 
variable $X$\ taking values in a set $W=\{x_1,\ldots,x_n\}$\ (of course, this does
not preclude the possibility that in fact $W=\times_{i=1}^k V_i$). Abstracting
from the missingness indicator $\boldM$, one can imagine coarse data as being 
produced by $X$\ and  a \emph{coarsening variable} $G$. 
Again, one can also take the coarsening variable $G$\ out of the picture,
and model coarse data directly as the joint distribution of $X$\ and 
a random variable $Y$\ (the \emph{observed data}) with values in 
$2^W$. This is the view we will mostly adopt, and therefore the motivation for 
the following definition.



\begin{defenv}
\label{def:obsmods}
  Let $W=\{x_1,\ldots,x_n\}$. The \emph{coarse data space} for $W$\ is
\begin{displaymath}
  \Omega(W):=\{ (x,U)\mid x\in W, U\subseteq W:\ x\in U\}. 
\end{displaymath}
A \emph{coarse data
distribution} is any probability distribution $P$\ on $\Omega(W)$.
\end{defenv}


A coarse data distribution can be seen as the joint distribution $P(X,Y)$\ of a 
random variable $X$\ with values in $W$, and a random variable $Y$\ with values
in $2^W\setminus\emptyset$. The joint distribution of $X$\ and $Y$\ is constrained by 
the condition $X\in Y$. Note that, thus,  coarse data spaces and coarse 
data distributions actually represent 
both the true complete data and its coarsened observation. 
In the remainder of this paper, $P$\ without any arguments will always denote 
a coarse data distribution in the sense of Definition~\ref{def:obsmods}, and can
be used interchangeably with $P(X,Y)$. When we need to refer to (joint) distributions
of other random variables, then these are listed explicitly as arguments of $P$. 
E.g.: $P(X,G)$\ is the joint distribution of $X$\ and $G$. 

\emph{Coarsening variables} as introduced by the following 
definition are a means for specifying the conditional distribution of $Y$\ given 
$X$. 

%The event that $Y=U\subseteq W$, i.e. that the coarse data 
%$U$\ is observed, corresponds to the subset
%\begin{displaymath}
%  O_U:=\{(x,U)\in\Omega(W)\mid x: x\in U\}
%\end{displaymath}
%of $\Omega(W)$. This has to be distinguished from the event that the actual 
%value of $X$\ is in $U$, which, as a subset of $\Omega(W)$, we simply denote
%with $U$:
%\begin{displaymath}
%  U=\{(x,U')\in\Omega(W)\mid x,U': x\in U\}.
%\end{displaymath}

\begin{defenv}
  \label{def:coarseningvar}
  Let $G$\ be a random variable with values in a finite state space $\Gamma$, and
  \begin{equation}
    \label{eq:defG1}
    f:W\times\Gamma\rightarrow 2^W\setminus\emptyset,
  \end{equation}
such that 
\begin{itemize}
\item for all $x$\ with $P(X=x)>0$: $x\in f(x,g)$;
\item for all $x,x'$\ with $P(X=x)>0,P(X=x')>0$, all $U\in 2^W\setminus\emptyset$, 
and all $g\in \Gamma$:
\begin{equation}
  \label{eq:defG2}
  f(x,g)=U, x'\in U
  \hspace{2mm}\Rightarrow\hspace{2mm}
  f(x',g)=U.
\end{equation}
\end{itemize}
We call the pair $(G,f)$\ a \emph{coarsening variable} for $X$. Often we also refer 
to $G$\ alone as a coarsening variable, in which case the function $f$\ is
assumed to be implicitly given. 


A coarse data distribution $P$\ is \emph{induced} by $X$\ and 
$(G,f)$\ if $P$\ is the joint distribution
of $X$\ and $f(X,G)$. 
\end{defenv}


The condition (\ref{eq:defG2}) has not always been made explicit in the 
introduction of coarsening variables. However, as noted by Heitjan~\citeyear{Heitjan97}, it
is usually implied in the concept of a coarsening variable. 
\shortciteGLR\ (pp. 283-285) consider a somewhat more general setup in which 
$f(x,g)$\ does not take values in $2^W$\ directly, but $y=f(x,g)$\ is some
observable from which $U=\alpha(y)\subseteq W$\ is obtained via a further mapping 
$\alpha$. The introduction of such an intermediate observable $Y$\ is necessary,
for example, when dealing with real-valued random variables $X$. Since we then
will not have any statistically tractable models for general distributions
on $2^{\Rset}$, a parameterization $Y$\ for a small subset of $2^{\Rset}$\ 
is needed. For example, $Y$\ could take values in $\Rset\times\Rset$, and 
$\alpha(y_1,y_2)$\ might be defined as the interval 
$[\min\{y_1,y_2\},\max\{y_1,y_2\}]$. \shortciteGLR\ do not require 
(\ref{eq:defG2}) in general; instead they call $f$\ \emph{Cartesian} when 
(\ref{eq:defG2}) is satisfied. 

The following definition generalizes property (\ref{eq:invertf}) of missingness
indicators to arbitrary coarsening variables.

\begin{defenv}
\label{def:invertible}
The coarsening variable $(G,f)$\ is called \emph{invertible} if there exists a function
\begin{equation}
  \label{eq:defG3}
  h:  2^W\setminus\emptyset \rightarrow \Gamma,
\end{equation}
such that for all $x,U$\ with $x\in U$, and all $g\in\Gamma$:
\begin{equation}
  \label{eq:defG4}
  U=f(x,g)
  \hspace{2mm}\Leftrightarrow\hspace{2mm}
  g=h(U).
\end{equation}
\end{defenv}

An alternative reading of (\ref{eq:defG4}) is that $G$\ is observable: from the coarse
observation $U$\ the value $g\in\Gamma$\ can be reconstructed, so that $G$\ can be treated
as a fully observable random variable. 

We can now generalize the definition of missing (completely) at random to 
the coarse data setting. We begin with the generalization of $\boldM$-\mar.

\begin{defenv}
 \label{def:G-car}
{\rm  \cite{Heitjan97}}
  Let $G$\ be a coarsening variable for $X$. The joint distribution
$P(X,G)$\  is $G$-\car\ if for all $U\subseteq W$, and $g\in \Gamma$:
\begin{equation}
  \label{eq:G-car}
  P(G=g\mid X) 
  \hspace{3mm}\mbox{is constant on}\hspace{3mm}
  \{x\mid P(X=x)>0,f(x,g)=U\}.
\end{equation}
\end{defenv}

By marginalizing out the coarsening variable $G$\ (or by not assuming
a variable $G$\ in the first place), we obtain the following distributional
version of \car.

\begin{defenv}
\label{def:d-car}
  {\rm \cite{HeiRub91}}
  Let $P$\ be a coarse data distribution. $P$\ is $d$-\car\ if for 
all $U\subseteq W$
\begin{equation}
  \label{eq:d-car}
  P(Y=U\mid X) 
  \hspace{3mm}\mbox{is constant on}\hspace{3mm}
  \{x\mid P(X=x)>0, x\in U\}.
\end{equation}
\end{defenv}

If $X$\ is multivariate, and incompleteness of observations consists of  missing values, 
then $d$-\car\ coincides with $d$-\mar, and $\boldM$-\car\ with $\boldM$-\mar. 

Condition (\ref{eq:G-car}) refers to the joint distribution of $X$\ and $G$,
condition (\ref{eq:d-car}) to the joint distribution of $X$\ and $Y$. 
Since $Y$\ is a function of $X$\ and $G$, one can always determine
from the joint distribution of $X$\ and $G$\ whether 
$d$-\car\ holds for their induced coarse data distribution.
Conversely, when only the coarse data distribution $P(X,Y)$\ and a coarsening
variable $G$\ inducing $P(X,Y)$\ are given, it is in general not possible 
to determine whether $P(X,G)$\ is $G$-\car, because the joint distribution
$P(X,G)$\ cannot be reconstructed from the given information.
However, under suitable assumptions on $G$\ it is possible to infer 
that $P(X,G)$\ is $G$-\car\ only from the induced $P(X,Y)$\ being $d$-\car. 
With the following two theorems we clarify these relationships between 
$G$-\car\ and $d$-\car. These theorems are essentially restatements in our
conceptual framework of results already given by  \shortciteGLR\ (pp. 284-285).


\begin{theoenv}
\label{theo:dcarandGcar}
  A coarse data distribution $P(X,Y)$\ is $d$-\car\ iff there exists a 
coarsening variable $G$\ inducing $P(X,Y)$,  such that $P(X,G)$\ is $G$-\car.
\end{theoenv}


\begin{proofenv}
  First assume that $P(X,Y)$\ is $d$-\car. We construct a canonical coarsening variable
$G$\ inducing $P(X,Y)$\ as follows: let $\Gamma=2^W\setminus \emptyset$\ and 
$f(x,U):=U$\ for all $x\in W$\ and $U\in\Gamma$.  Define a $\Gamma$-valued 
coarsening variable $G$\ by $P(G=U\mid X=x):=P(Y=U\mid X=x)$. Clearly, the
coarse data distribution induced by $G$\ is the original $P(X,Y)$,
and $P(X,G)$\ is $G$-\car. 

Conversely, assume that $P(X,G)$\ is $G$-\car\ for some $G$\ inducing $P(X,Y)$. 
Let $U\subseteq W$, $x\in U$. Then
  \begin{eqnarray*}
    P(Y=U\mid X=x) & = & 
    P(G\in\{g\in \Gamma\mid f(x,g)=U\}\mid X=x)\\
    & =  &
    \sum_{g\in\Gamma:f(x,g)=U} P(G=g\mid X=x).
  \end{eqnarray*}
Because of (\ref{eq:defG2}) the summation here is over the same values
$g\in\Gamma$\ for all $x\in U$. Because of $G$-\car, the conditional probabilities
$P(G=g\mid X=x)$\ are constant for $x\in U$. Thus $ P(Y=U\mid X=x)$\ is
constant for $x\in U$, i.e. $d$-\car\ holds.
\end{proofenv}

The following example shows that $d$-\car\ does not in general imply $G$-\car, and that
a fixed coarse data distribution $P(X,Y)$\ can be induced both by a coarsening
variable for which $G$-\car\ holds, and by another coarsening variable for which
$G$-\car\ does not hold.

\begin{examenv}
\label{ex:T1T2-4}
(continued from Example~\ref{ex:T1T2-3})
We have already seen that the coarse data distribution here is $d$-mar
and $\boldM$-\mar, 
and hence $d$-car\ and $\boldM$-\car. 

$\boldM$\ is not the only coarsening variable inducing $P(X,Y)$. In fact, it is not
even the simplest: let $G_1$\ be a trivial random variable that can only assume
one state, i.e. $\Gamma_1=\{g\}$. Define $f_1$\ by
\begin{displaymath}
  \begin{array}{l}
    f_1((n,n),g)=f_1((n,p),g)= \{(n,n),(n,p)\}, \\
    f_1((p,n),g)=\{(p,n)\}, \\
    f_1((p,p),g)=\{(p,p)\}.
  \end{array}
\end{displaymath}
Then $G_1$\ induces $P(X,Y)$, and $P(X,G_1)$\ also is trivially $G$-car. 

Finally, let $G_2$\ be defined by $\Gamma_2=\{g_1,g_2\}$\ and
$f_2(x,g_i)=f_1(x,g)$\ for all $x\in W$\ and $i=1,2$. Thus, $G_2$\ is 
just like $G_1$, but the trivial state space of $G_1$\ has been split
into two elements with identical meaning. Let the conditional distribution 
of $G_2$\ given $X$\ be 
\begin{displaymath}
  \begin{array}{l}
    P(G_2=g_1\mid X=(n,n))=P(G_2=g_2\mid X=(n,p))=2/3, \\
    P(G_2=g_2\mid X=(n,n))=P(G_2=g_1\mid X=(n,p))=1/3, \\
    P(G_2=g_1\mid X=(p,n))=P(G_2=g_1\mid X=(p,p))=1.
  \end{array}
\end{displaymath}
Again, $G_2$\ induces $P(X,Y)$. However, $P(X,G_2)$\ is not $G$-\car, because
\begin{displaymath}
  \begin{array}{l}
    f_2((n,n),g_1)=f_2((n,p),g_1)=\{(n,n),(n,p)\}, \\
    P(G_2=g_1\mid X=(n,n))\neq P(G_2=g_1\mid X=(n,p))
  \end{array}
\end{displaymath}
violates the $G$-\car\ condition.
$G_2$\ is not invertible in the sense of Definition~\ref{def:invertible}: when,
for example, $U=\{(n,n),(n,p)\}$\ is observed, it is not possible to determine
whether the value of $G_2$\ was $g_1$\ or $g_2$.
\end{examenv}

The following theorem 
shows that the non-invertibility of $G_2$\ in the preceding example
is the reason why we cannot deduce $G$-\car\ for $P(X,G_2)$\ from 
the $d$-\car\ property of the induced $P(X,Y)$.
This theorem completes our picture of the $G$-\car / $d$-\car\ relationship.


\begin{theoenv}
\label{theo:dcarandinvertibleG}
  Let $P(X,Y)$\ be a coarse data distribution, $G$ an invertible coarsening variable
inducing $P(X,Y)$.
If $P(X,Y)$\ is $d$-\car, then $P(X,G)$\ is $G$-\car. 
\end{theoenv}

\begin{proofenv}
Let $U\subseteq W$,
$g\in\Gamma$, and $x\in U$, such that $P(X=x)>0$\ and  $f(x,g)=U$. 
Since $G$\ is invertible, we have that $f(x,g')\neq U$\ for all $g'\neq g$,
and hence
\begin{displaymath}
  P(G=g\mid X=x)=P(Y=U\mid X=x).
\end{displaymath}
From the assumption that $P$\ is $d$-\car\ it follows that the right-hand
probability is constant for $x\in U$, and hence the same holds for the left-hand
side, i.e. $G$-\car\ holds.
\end{proofenv}



We now turn to coarsening completely at random (\ccar). It is straightforward to 
generalize the definition of $\boldM$-\mcar\ to general coarsening variables:
\begin{defenv}
\label{def:G-ccar}
  {\rm \cite{Heitjan94}}
Let $G$\ be a coarsening variable for $X$. The joint distribution 
$P(X,G)$\ is $G$-\ccar\ if for all $g\in\Gamma$
\begin{equation}
  \label{eq:G-ccar}
  P(G=g\mid X)
  \hspace{3mm}\mbox{is constant on}\hspace{3mm}
  \{x\mid P(X=x)>0\}.
\end{equation}
\end{defenv}

A distributional version of \ccar\ does not seem to have been formalized previously
in the literature. \shortciteGLR\ refer to coarsening completely at random, but 
do not provide a formal definition. However, it is implicit in their discussion that
they have in mind a slightly restricted version of our following definition  
(the restriction being a limitation to the case $k=1$\ in Theorem~\ref{theo:equivd-ccar}
below). 

We first observe that one cannot give a definition of $d$-\ccar\ as a variant of 
Definition~\ref{def:G-ccar} in the same way as Definition~\ref{def:d-car} varies
Definition~\ref{def:G-car}, because that would lead us to the condition
that $P(Y=U\mid X)$\ is constant on $\{x\mid P(X=x)>0\}$. This would be 
inconsistent with the existence of $x\in W\setminus U$\ with $P(X=x)>0$.
However, the real semantic core of $d$-\car, arguably, is not so much captured by
Definition~\ref{def:d-car}, as by the characterization given in Theorem~\ref{theo:dcarandGcar}.
For $d$-\ccar, therefore, we make an analogous characterization the basis of the
definition:


\begin{defenv}
\label{def:dccar}
  A coarse data distribution $P(X,Y)$\ is $d$-\ccar\ iff there exists a 
coarsening variable $G$\ inducing $P(X,Y)$,  such that $P(X,G)$\ is $G$-\ccar.
\end{defenv}


The following theorem provides a constructive characterization of $d$-\ccar.

\begin{theoenv}
\label{theo:equivd-ccar}
  A coarse data distribution $P(X,Y)$\ is $d$-\ccar\ iff there exists a family
$\{{\cal W}_1,$ $\ldots,{\cal W}_k\}$\ of partitions of $W$, and a probability distribution 
  $(\lambda_1,\ldots,\lambda_k)$\ on $({\cal W}_1,\ldots,{\cal W}_k)$, such
that for all $x\in W$\ with $P(X=x)>0$:
\begin{equation}
  \label{eq:d-ccar}
  P(Y=U\mid X=x)=\sum_{
    \begin{array}{c}
      \scriptstyle{i\in 1,\ldots, k}\\
      \scriptstyle{x\in U\in {\cal W}_i}
    \end{array}
} \lambda_i.
\end{equation}
\end{theoenv}

\begin{proofenv}
  Assume that $P$\ is $d$-\ccar. Let $G$\ be a coarsening variable inducing
$P(X,Y)$, such that $P(X,G)$\ is  $G$-\ccar.
Because of (\ref{eq:defG2}), each value $g_i\in \Gamma$\ induces a partition
${\cal W}_i=\{U_{i,1},\ldots, U_{i,k(i)}\}$, such that 
$f(x,g_i)=U_{i,j}\Leftrightarrow x\in U_{i,j}$. The partitions 
${\cal W}_i$\ together with $\lambda_i:=P(G=g_i\mid X)$\ then 
provide a representation of $P(X,Y)$\ in the form (\ref{eq:d-ccar}). 

Conversely, if $P(X,Y)$\ is given by (\ref{eq:d-ccar}) 
via partitions ${\cal W}_1,\ldots, {\cal W}_k$\
and parameters $\lambda_i$, one defines a coarsening variable 
$G$\ with $\Gamma=\{1,\ldots,k\}$, $P(G=g_i\mid X=x)=\lambda_i$\ for 
all $x$\ with $P(X=x)>0$, and $f(x,i)$\ as that $U\in {\cal W}_i$\ 
containing $x$. $P(X,G)$\ then is $G$-\ccar\ and induces $P(X,Y)$, 
and hence  $P(X,Y)$\ is $d$-\ccar.
\end{proofenv}

As before, we have that the $G$-\ccar\ property of $P(X,G)$\ cannot be 
determined from the induced coarse data distribution: 

\begin{examenv}
\label{ex:T1T2-5}
(continuation of Example~\ref{ex:T1T2-4}) $P(X,Y)$\ is 
$d$-\ccar\ and induced by any of the three coarsening variables 
$\boldM$, $G_1$, $G_2$. However, $P(X,G_1)$\ is $G$-\ccar, while 
$P(X,\boldM)$\ and $P(X,G_2)$\ are not. 
\end{examenv}

The previous example also shows that no analog of Theorem~\ref{theo:dcarandinvertibleG}
holds for $\ccar$: $\boldM$\ is invertible, but from $d$-\ccar\ for the induced 
$P(X,Y)$\ we here cannot infer $G$-\ccar\ for $P(X,\boldM)$. 




\begin{figure}[t]

\psfrag{coarsedata}[c]{Coarse observations}
\psfrag{missdata}[c]{Missing values}

%\psfrag{atrand}[r]{\ldots at random}
%\psfrag{catrand}[r]{\ldots completely at random}
\psfrag{atrand}[r]{}
\psfrag{catrand}[r]{}



\psfrag{Gcar}[c]{\framebox{$G$-\car}}
\psfrag{Gccar}[c]{\framebox{$G$-\ccar}}
\psfrag{dcar}[c]{\framebox{$d$-\car}}
\psfrag{dccar}[c]{\framebox{$d$-\ccar}}
\psfrag{dmar}[c]{\framebox{$d$-\mar}}
\psfrag{Mmar}[c]{\framebox{$\boldM$-\mar}}
\psfrag{Mmcar}[c]{\framebox{$\boldM$-\mcar}}






\psfrag{arr1}[c]{$\Longleftrightarrow$}
\psfrag{arr2}{$\Longleftrightarrow$}
\psfrag{arr3}[c]{$\Longleftarrow$}
\psfrag{arr4}[c]{$\Longrightarrow$}
\psfrag{arr5}[c]{$\Longleftarrow$}
\psfrag{arr6}[c]{$\Longrightarrow$}
\psfrag{arr7}[c]{$\Uparrow$}


%\psfrag{Ginvert}[c]{\parbox{33mm}{\begin{center}
%exists $G$\\ 
%for all invertible $G$
%\vspace*{5mm}
%\end{center}}}
%\psfrag{forsomeG}[c]{exists $G$}

\psfrag{Ginvert}[c]{(a)(b)}
\psfrag{forsomeG}[c]{(a)}
\psfrag{MeqG}[c]{(c)}



  \centering
  \includegraphics[scale=0.6]{\figurepath/schema.eps}
  \caption{Versions of \car. (a): there exists $G$\ such that this implication holds; (b): for all
invertible $G$\ this implication holds; (c): equivalence holds for $G=\boldM$.}
  \label{fig:carversions}
\end{figure}


Figure~\ref{fig:carversions} summarizes the different versions of \mar/\car\ we have 
considered. 
The distributional versions $d$-\car\ and $d$-\ccar\ are weaker than their 
$\boldM$- and $G$- counterparts, and therefore the less restrictive assumptions.
At the same time, they are sufficient to establish ignorability for most statistical
learning and probabilistic inference tasks. For the case of probabilistic inference
this will be detailed by Theorem~\ref{theo:carcharac} in the following section.
For statistical inference problems, too, the required ignorability results can be 
obtained from the distributional \car\ versions, unless a specific coarsening
variable is explicitly part of the inference problem. Whenever a coarsening variable
$G$\  is introduced only as an artificial construct for modeling the connection between
incomplete observations and complete data, one must be aware that the 
$G$-\car\ and $G$-\ccar\ conditions can be unnecessarily restrictive, and may lead 
us to reject ignorability when, in fact, ignorability holds (cf. Examples~\ref{ex:T1T2-3}
and \ref{ex:T1T2-5}).

We conclude this section with three additional important remarks on definitions of \car,
which are needed to complete the picture of different approaches to \car\ in the
literature:\\

\emph{Remark 1:} All of the definitions given here are \emph{weak} versions of \mar/\car. Corresponding
\emph{strong} versions are obtained by dropping the restriction $P(X=x)>0$\ from
(\ref{eq:M-mar}),(\ref{eq:d-mar}),(\ref{eq:M-mcar}),(\ref{eq:G-car}),(\ref{eq:d-car}),(\ref{eq:G-ccar}),
respectively (\ref{eq:d-ccar}). Differences between weak and strong versions of \car\
are studied in previous work~\cite{JaegerAnnStat}. The results there obtained indicate that in the context
of probability updating the weak versions are more suitable. For this reason we do not 
go into the details of strong versions here.
\\

\emph{Remark 2:}
Our definitions of \car\  differ from those 
originally given by Rubin and Heitjan in that our definitions are ``global'' 
definitions that view \mar/\car\ as a property of a  joint distribution of 
complete and coarse data. The original definitions, on the other hand, are conditional
on a single observation $Y=U$, and do not impose constraints on the joint distribution
of $X$\ and $Y$\ for other values of $Y$. These ``local'' \mar/\car\ assumptions
are all that is required to justify the application of certain probabilistic or 
statistical inference techniques to the single observation $Y=U$. The global \mar/\car\
conditions we stated justify these inference techniques as general strategies that 
would be applied to any possible observation. 
Local versions of \car\ are more natural under a Bayesian statistical philosophy, whereas
global versions are required under a frequentist interpretation. Global versions
of \car\ have also been used in other works (e.g., \citeR{JacKei95,GilvdLRob97,Nielsen97,Cator04}). 
\\

\emph{Remark 3:} The definitions and results stated here are strictly limited to the
case of finite $W$. As already indicated in the discussion following Definition~\ref{def:coarseningvar},
extensions of \car\ to more general state spaces $C$\ typically require a setup
in which observations are modeled by a random variable taking values in a more 
manageable state space than $2^C$. Several such formalizations of \car\ for continuous
state spaces have been investigated  (e.g., \citeR{JacKei95,GilvdLRob97,Nielsen00,Cator04}).  

\subsection{Ignorability}
\label{sec:usingcar}

\Car\ and \mar\ assumptions are needed for ignoring the distinction between
``$U$\ is observed'' and ``$U$\ has occurred'' in statistical inference and
probability updating. In statistical inference, for example, $d$-\car\ is required 
to justify likelihood maximizing techniques like the \emph{EM} algorithm~\cite{DemLaiRub77}
for learning from incomplete data. In this paper the emphasis is on probability 
updating. We therefore briefly review the significance of \car\ in this context.
We use the well-known Monty Hall problem.

\begin{examenv}
\label{ex:Monty1}
  A contestant at a game show is asked to choose one from three closed doors 
$A,B,C$, behind one of which is hidden a valuable prize, the others each 
hiding a goat.  The contestant chooses door $A$, say. The host now 
opens door $B$, revealing a goat. At this point the contestant is allowed 
to change her choice from $A$\ to $C$. Would this be advantageous? 

Being a savvy probabilistic reasoner, the contestant knows that she should
analyze the situation using the coarse data space $\Omega(\{A,B,C\})$, and 
compute the probabilities
\begin{displaymath}
  P(X=A\mid Y=\{A,C\}),\  P(X=C\mid Y=\{A,C\}).
\end{displaymath}
She makes the following assumptions: 1. A-priori all doors are equally  likely
to hide the prize. 2. Independent from the contestants choice, the host 
will always open one door. 3. The host will never open the door chosen
by the contestant. 4. The host will never open the door hiding the prize.
5. If more than one possible door remain for the host, he will 
determine by a fair coin flip which one to open.
From this, the contestant first obtains
\begin{equation}
  \label{eq:Monty1notcar}
  P(Y=\{A,C\}\mid X=A)=1/2,\ P(Y=\{A,C\}\mid X=C)=1,
\end{equation}
and then
\begin{displaymath}
  P(X=A\mid Y=\{A,C\})=1/3,\  P(X=C\mid Y=\{A,C\})=2/3.
\end{displaymath}
The conclusion, thus, is that it will be advantageous to switch to door $C$. A
different conclusion is obtained by simply conditioning in the state space
$W$\ on ``$\{A,C\}$\ has occurred'':
\begin{displaymath}
  P(X=A\mid X\in\{A,C\})=1/2,\  P(X=C\mid X\in\{A,C\})=1/2.
\end{displaymath}
\end{examenv}

\begin{examenv}
  \label{ex:Monty2}
Consider a similar situation as in the previous example, but now assume that
just after the contestant has decided for herself that she would pick door
$A$, but before communicating her choice to the host, the host says 
``let me make things a little easier for you'', opens door $B$, and reveals
a goat. Would changing from $A$\ to $C$\ now be advantageous? 

The contestant performs a similar analysis as before, but now based on the
following assumptions: 1. A-priori all doors are equally  likely
to hide the prize. 2. The host's decision to open a door was independent
from the location of the prize. 3. Given his decision to open a door,
the host chose by a fair coin flip one of the two doors not hiding the prize.
Now
\begin{equation}
  \label{eq:Monty2car}
  P(Y=\{A,C\}\mid X=A)=P(Y=\{A,C\}\mid X=C),
\end{equation}
and hence
\begin{displaymath}
  P(X=A\mid Y=\{A,C\})=1/2,\  P(X=C\mid Y=\{A,C\})=1/2.
\end{displaymath}
In particular here
\begin{displaymath}
  \begin{array}{l}
    P(X=A\mid Y=\{A,C\})=P(X=A\mid X\in\{A,C\})\\
    P(X=C\mid Y=\{A,C\})=P(X=C\mid X\in\{A,C\}),
  \end{array}
\end{displaymath}
i.e. the difference between ``$\{A,C\}$\ is observed'' and ``$\{A,C\}$\ has
occurred'' can be ignored for probability updating.
\end{examenv}

The coarse data distribution in Example~\ref{ex:Monty1} is not $d$-\car\ 
(as evidenced by (\ref{eq:Monty1notcar})), whereas the coarse data distribution in
Example~\ref{ex:Monty2} is  $d$-\car\ (as shown, in part, by (\ref{eq:Monty2car})). The 
connection between ignorability in probability updating and the $d$-\car\ assumption
has been shown in \shortciteGLR\ and \shortciteGH. The following theorem restates this
connection in our terminology.

\begin{theoenv}
  \label{theo:carcharac}
Let $P$\ be a coarse data distribution. The following are equivalent:
\begin{description}
\item[(i)] $P$\ is $d$-\car.
\item[(ii)] For all $x\in W$, $U\subseteq W$\ with $x\in U$\ and $P(Y=U)>0$:
  \begin{displaymath}
    P(X=x\mid Y=U)=P(X=x\mid X\in U).
  \end{displaymath}
\item[(iii)] For all $x\in W$, $U\subseteq W$\ with $x\in U$\ and $P(X=x)>0$:
  \begin{displaymath}
  P(Y=U\mid X=x)=\frac{P(Y=U)}{P(X\in U)}.
   \end{displaymath}
\end{description}
\end{theoenv}

The equivalence (i)$\Leftrightarrow$(ii) is shown in \shortciteGH, based on
\shortciteGLR. For the equivalence with (iii) see \cite{JaegerAnnStat}.

%In the context of probability updating there does not seem to be a special role
%for \ccar\ rather than \car. In the context of learning, on the other hand, 
%some inference techniques may need the stronger \ccar\ assumption for their 
%justification \cite{Rubin76,JaegerAnnStat}. 
%\emph{Really: G-ccar needed, not d-ccar. But d-ccar relevant due to pd}

\section{Criteria for \Car\ and \Ccar}
\label{sec:carcond}


Given a coarse data distribution $P$\ it is, in principle, easy to determine whether
$P$\ is $d$-\car\ ($d$-\ccar) based on Definition~\ref{def:d-car}, respectively 
Theorem~\ref{theo:equivd-ccar}
(though in case of $d$-\ccar\ a test might require a search over possible families of 
partitions). However, typically $P$\ is not completely known. Instead, we usually have some partial 
information about $P$. In the case of statistical inference problems this information consists
of a sample ${U_1},\ldots, {U_N} $\ of the coarse data variable $Y$. In the case of 
conditional probabilistic inference, we know the marginal of $P$\ on $W$. In both cases we 
would like to decide whether the partial knowledge of $P$\ that we possess, in conjunction with 
certain other assumptions on the structure of $P$\ that we want to make, is consistent with $d$-\car,
respectively $d$-\ccar, i.e. whether there exists a distribution $P$\ that is $d$-\car\ 
($d$-\ccar), and satisfies our partial knowledge and our additional assumptions. 

In statistical problems, additional assumptions on $P$\ usually come in the form of a 
parametric representation of the distribution of $X$. When $\boldX=(X_1,\ldots,X_k)$\
is multivariate, such a parametric representation can consist, for example, in a 
factorization of the joint distribution of the $X_i$, as induced by certain conditional 
independence assumptions. In probabilistic inference problems an analysis of the evidence
gathering process can lead to assumptions about the likelihoods of possible observations. 
In all these cases, one has to determine whether the constraints
imposed on $P$\ by the partial knowledge and assumptions are consistent with the 
constraints imposed by the $d$-\car\ assumption. In general, this will lead to computationally
very difficult optimization or constraint satisfaction problems. 

Like \shortciteGH, we will  focus in this section on a rather idealized special problem within
this wider area, and consider the case where our constraints on $P$\ only establish what 
values the variables $X$\ and $Y$\ can assume with nonzero probability, i.e. the constraints
on $P$\ consist of prescribed sets of support for $X$\ and $Y$. We can interpret this special 
case as a reduced form of a more specific statistical setting, by assuming that the observed 
sample ${U_1},\ldots, {U_N} $\ only is used to infer what observations are possible,
and that the parametric model for $X$, too, only is used to determine what $x\in W$\ 
have nonzero probabilities. Similarly, in the probabilistic inference setting, this 
special case occurs when the knowledge of the distribution of $X$\ 
only is used to identify the $x$\ with $P(X=x)>0$, and assumptions on the evidence generation only pertain
to the set of possible observations. 

\shortciteGH\ represent a specific  support structure of $P$\ in form of a $0,1$-matrix,
which they call the ``CARacterizing matrix''. In the following definition we provide an equivalent,
but different, encoding of support structures of $P$. 
 

\begin{defenv}
\label{def:supphypgraph}
  A \emph{support hypergraph} (for a given coarse data space $\Omega(W)$) 
  is a hypergraph of the form
  $({\cal N},W')$, where
  \begin{itemize}
  \item ${\cal N}\subseteq 2^W\setminus\emptyset$\ is the set of nodes,
    \item $W'\subseteq W$\ is the set of edges, such that each edge $x\in W'$\
      just contains the nodes $\{U\in {\cal N} \mid x\in U\}$.
  \end{itemize}
  $({\cal N},W')$\ is called the support hypergraph of the distribution 
  $P$\ on $\Omega(W)$\ iff ${\cal N}= \{U\subseteq 2^W\setminus\emptyset \mid  P(Y=U)>0\}$, 
  and $W'=\{x\in W\mid P(X=x)>0\}$. 
  A support hypergraph is \car\emph{-compatible} iff it is the support hypergraph
  of some $d$-\car\ distribution $P$.
\end{defenv}

\begin{figure}[htbp]
\psfrag{A}[c]{$A$}
\psfrag{B}[c]{$B$}
\psfrag{C}[c]{$C$}
\psfrag{AC}[c]{$\{A,C\}$}
\psfrag{AB}[c]{$\{A,B\}$}
\psfrag{BC}[c]{$\{B,C\}$}

\psfrag{(a)}[c]{(a)}
\psfrag{(b)}[c]{(b)}


  \centering
  \includegraphics[scale=0.7]{\figurepath/montyhypgraphs.eps}
  \caption{Support hypergraphs for Examples~\ref{ex:Monty1} and \ref{ex:Monty2}}
  \label{fig:montyhypgraphs}
\end{figure}

\begin{examenv}
  Figure~\ref{fig:montyhypgraphs} (a) shows the support hypergraph of the 
coarse data distribution in Example~\ref{ex:Monty1}; (b) for 
Example~\ref{ex:Monty2}.
\end{examenv}

%Note that a support hypergraph can only encode sets of support of $P$\ that are defined
%by the margianl selts of support of $X$\ and $Y$. It is not possible, for example, 
%to represent in a support hypergraph that for some $x,x',U,U'$: 
%$P((x,U))>0,P((x',U'))>0$, and $P((x,U'))=0$. 

The definition of support hypergraph may appear strange, as a much more natural definition
would take the states $x\in W$\ with $P(X=x)>0$\ as the nodes, and the observations
$U\subseteq W$\ as the edges. The support hypergraph of Definition~\ref{def:supphypgraph}
is just the dual of this natural support hypergraph. It turns out that these duals
are more useful for the purpose of our analysis. 

A support hypergraph can contain multiple edges containing the same nodes. This corresponds
to multiple states that are not distinguished by any of the possible observations.
Similarly, a support hypergraph can contain multiple nodes that belong to exactly
the same edges. This corresponds to different observations $U,U'$\ with
$U\cap \{x\mid P(X=x)>0\}=U'\cap \{x\mid P(X=x)>0\}$. On the other hand, a support 
hypergraph cannot contain any node that is not contained in at least one edge
(this would correspond to an observation $U$\ with $P(Y=U)>0$\ but 
$P(X\in U)=0$). Similarly, it cannot contain empty edges. These are the only 
restrictions on support hypergraphs:

\begin{theoenv}
  A hypergraph $({\cal N},{\cal E})$\ with finite ${\cal N}$\ and ${\cal E}$\
is the support hypergraph of some distribution $P$, iff each node in 
${\cal N}$\ is contained in at least one edge from ${\cal E}$, and
all edges are nonempty.
\end{theoenv}

\begin{proofenv}
  Let $W={\cal E}$\ and define $P(X=x)=1/\cardinal{\cal E}$\ for all  
$x\in W$. For each node $n\in {\cal N}$\ let $U(n)$\ be 
$\{x\in W\mid n\in x\}$\ (nonempty!), and define $P(Y=U(n)\mid X=x)=1/\cardinal{x}$.
Then $({\cal N},{\cal E})$\ is the support hypergraph of $P$.
\end{proofenv}

While (almost) every hypergraph, thus, can be the support hypergraph of some
distribution, only rather special hypergraphs can be the support hypergraphs
of a $d$-\car\ distribution. Our goal, now, is to characterize these \car-compatible
support hypergraphs. 
The following proposition gives a first such characterization. It is similar to 
lemma 4.3 in \shortciteGH. 

\begin{propenv}
\label{prop:existsvaluation}
  The support hypergraph $({\cal N},W')$\ is \car-compatible
  iff there exists a function 
  $\nu:{\cal N}\rightarrow (0,1]$, such that for all $x\in W'$
  \begin{equation}
    \label{eq:carcompiff}
    \sum_{U\in{\cal N}: U\in x} \nu(U)= 1
  \end{equation}
\end{propenv}


\begin{proofenv}
First note that in this proposition we are looking at $x$\ and $U$\ as edges and nodes,
respectively, of the support hypergraph, so that writing $U\in x$\ makes sense, and 
means the same as $x\in U$\ when $x$\ and $U$\ are seen as states, respectively sets of states, 
in the coarse data space. 

  Suppose $({\cal N},W')$\ is the support hypergraph of a $d$-\car\ distribution $P$.
It follows from Lemma~\ref{theo:carcharac} that $\nu(U):=P(Y=U)/P(X\in U)$\ defines
a function $\nu$\ with the required property. Conversely, assume that $\nu$\ is
given. Let $P(X)$\ be any distribution on $W$\ with support $W'$. Setting 
$P(Y=U\mid X=x):=\nu(U)$\ for all $U\in{\cal N}$, and $x\in W'\cap U$\ 
extends $P$\ to a $d$-\car\ distribution whose support hypergraph is just $({\cal N},W')$.
\end{proofenv}

\begin{coroenv}
\label{cor:nestededges}
  If the support hypergraph contains (properly) nested edges, then it is not
\car-compatible.
\end{coroenv}


\begin{examenv}
  The support hypergraph from Example~\ref{ex:Monty1} contains nested edges. 
Without any numerical computations, it thus follows alone from the qualitative analysis 
of what observations could have been made, that the coarse data distribution is not
$d$-\car, and hence conditioning is not a valid update strategy.
\end{examenv}

The proof of Proposition~\ref{prop:existsvaluation} shows (as already observed by
\shortciteGH) that if a support hypergraph is \car-compatible, then it is \car-compatible
for any given distribution $P(X)$ with support $W'$, i.e. the support assumptions encoded in the 
hypergraph, together with the $d$-\car\ assumption (if jointly consistent), do not impose
any constraints on the distribution of $X$\ (other than having the prescribed set of 
support). The same is not true for the marginal of $Y$: for a \car-compatible 
support hypergraph $({\cal N},W')$\ there will usually also exist distributions $P(Y)$\
on ${\cal N}$\ such that $P(Y)$\ cannot be extended to a $d$-\car\ distribution with 
the support structure specified by the 
hypergraph $({\cal N},W')$. 
%For this reason is the analysis we obtain through the
%study of support hypergraphs stronger within the context of probability updating
%than within the context of statistical inference, because here the reduction of 
%existing knowledge of $P$\ to constraints on sets of support is not as significant. 

Proposition~\ref{prop:existsvaluation} already provides a complete characterization of 
\car-compatible support hypergraphs, and can be used as the basis of a decision procedure
for \car-compatibility using methods for linear constraint satisfaction. However, 
Proposition~\ref{prop:existsvaluation} does not provide very much real insight into
what makes an evidence hypergraph \car-compatible. Much more intuitive insight is 
provided by Corollary~\ref{cor:nestededges}. The criterion provided by Corollary~\ref{cor:nestededges}
is not complete: as the following example shows, there exist support hypergraphs
without nested edges that are not \car-compatible.

\begin{figure}[htbp]
\psfrag{U1}[l]{$U_1$}
\psfrag{U2}[l]{$U_2$}
\psfrag{U3}[l]{$U_3$}
\psfrag{U4}[r]{$U_4$}
\psfrag{U5}[r]{$U_5$}
\psfrag{U6}[r]{$U_6$}
\psfrag{x1}[c]{$x_1$}
\psfrag{x2}[c]{$x_2$}
\psfrag{x3}[c]{$x_3$}
\psfrag{x4}[c]{$x_4$}
\psfrag{x5}[c]{$x_5$}


  \centering
  \includegraphics[scale=0.8]{\figurepath/sixnodes.eps}
  \caption{\car-incompatible support hypergraph without nested edges}
  \label{fig:6nodessupphyp}
\end{figure}


\begin{examenv}
  Let $({\cal N},W')$\ be as shown in Figure~\ref{fig:6nodessupphyp}. By assuming 
the existence of a suitable function $\nu$, and summing (\ref{eq:carcompiff}) 
once over $x_1$\ and $x_2$, and once over $x_3,x_4,x_5$, we obtain the 
contradiction $2=\sum_{i=1}^6 \nu({U_i})=3$. Thus, $({\cal N},W')$\ is 
not \car-compatible. 
\end{examenv}


We now proceed to extend  the partial characterization of \car-compatibility
provided by Corollary~\ref{cor:nestededges} to a complete characterization. Our 
following result improves on theorem 4.4 of \shortciteGH\ by giving a necessary
and sufficient condition for \car-compatibility, rather than just several 
necessary ones, and, arguably, by providing a criterion that is
more intuitive and easier to apply.
Our characterization is based on the following definition. 



\begin{defenv}
\label{def:edgefunction}
  Let $({\cal N},W')$\ be a support hypergraph. Let 
  $\boldx=x_1,\ldots,x_k$\ be a finite sequence of edges from $W'$, 
  possibly containing repetitions of the same edge. 
  Denote the length 
  $k$\ of the sequence by $\cardinal{\boldx}$. 
  For $x\in W$\ we denote with $1_x$\ the indicator function on ${\cal N}$ induced
by $x$, i.e. 
\begin{displaymath}
  1_x(U):=\left\{
    \begin{array}{ll}
      1 & \mbox{if}\ U\in x\\
      0 & \mbox{else}
    \end{array}
\right.
\hspace{10mm} (U\in {\cal N}).
\end{displaymath}
The function $1_{\boldx}(U):=\sum_{x\in \boldx}1_x(U)$\ then counts
the number of edges in $\boldx$\ that contain $U$. For two sequences $\boldx,\boldx'$\
we write $1_{\boldx}\leq 1_{\boldx'}$\ iff $1_{\boldx}(U)\leq 1_{\boldx'}(U)$\ for all
$U$.
\end{defenv}

\begin{examenv}
\label{ex:illuedgefunction}
For the evidence hypergraph in Figure~\ref{fig:6nodessupphyp} we have that 
$1_{(x_1,x_2)}=1_{(x_3,x_4,x_5)}$\ is the function on ${\cal N}$\ which
is constant 1. 

For $\boldx=(x_1,x_3,x_4,x_5)$\ one obtains $1_{\boldx}(U)=2$\ for
$U=U_1,U_2,U_3$, and $1_{\boldx}(U)=1$\ for $U=U_4,U_5,U_6$. The same function
also is defined by $\boldx=(x_1,x_1,x_2)$. 

In any evidence hypergraph, one has that for two single edges
$x,x'$: $1_x<1_{x'}$\ iff $x$\ is a proper subset of $x'$.  
\end{examenv}

We now obtain the following characterization (which is partly inspired 
by known  conditions for the existence of finitely additive measures, see \citeR{BhaBha83}):

\begin{theoenv}
\label{theo:graphcrit}
  The support hypergraph $({\cal N},W')$\ is \car-compatible
   iff for every two sequences $\boldx,\boldx'$\ of edges from 
  $W'$\ we have
  \begin{align}
    & 1_{\boldx} = 1_{\boldx'}\ \ \Rightarrow\ \ \cardinal{\boldx}= \cardinal{\boldx'}, \mbox{and}
    \label{eq:carcompcond1}\\
    & 1_{\boldx} \leq  1_{\boldx'}, 1_{\boldx} \neq  1_{\boldx'} \ 
    \Rightarrow\ \ \cardinal{\boldx} < \cardinal{\boldx'}.
    \label{eq:carcompcond2}
  \end{align}
\end{theoenv}

\begin{proofenv}
  Denote $k:=\cardinal{W'}$, $l:=\cardinal{{\cal N}}$. Let $\boldA=(a_{i,j})$\ be the
incidence matrix of $({\cal N},W')$, i.e. $\boldA$\ is an $k\times l$\ matrix with
$a_{i,j}=1$\ if $U_j\in x_i$, and $a_{i,j}=0$\ if $U_j\not\in x_i$\ (using some
indexings $i,j$\ for $W'$\ and ${\cal N}$). 

Condition (\ref{prop:existsvaluation}) now reads: 
\begin{equation}
  \label{eq:local301}
  \mbox{exists } \boldnu\in (0,1]^l\ \mbox{with}\ \boldA\boldnu={\boldsymbol 1}
\end{equation}
(here ${\boldsymbol 1}$\ is a vector of $k$\ ones). An edge indicator function
$1_{\boldx}$\ can be represented as a row vector $\boldz\in\Nset^k$, where 
$z_i$\ is the number of times $x_i$\ occurs in $\boldx$. Then $1_{\boldx}$\ can
be written as the row vector $\boldz\boldA$, and the conditions of Theorem~\ref{theo:graphcrit}
become: for all $\boldz,\boldz'\in\Nset^k$:
\begin{align}
  & \boldz\boldA=\boldz'\boldA\ \Rightarrow\ \boldz\cdot{\boldsymbol 1}=\boldz'\cdot{\boldsymbol 1},
  \label{eq:local302}\\
 & \boldz\boldA\leq\boldz'\boldA,\ \boldz\boldA\neq\boldz'\boldA \Rightarrow\ 
  \boldz\cdot{\boldsymbol 1}<\boldz'\cdot{\boldsymbol 1}.
  \label{eq:local303}
\end{align}
Subtracting right sides, this is equivalent to: for all $\boldz\in\Zset^k$:
\begin{align}
  & \boldz\boldA={\boldsymbol 0}\ \Rightarrow\ \boldz\cdot{\boldsymbol 1}={\boldsymbol 0},
  \label{eq:local304}\\
 & \boldz\boldA\leq{\boldsymbol 0},\ \boldz\boldA\neq{\boldsymbol 0} \Rightarrow\ 
  \boldz\cdot{\boldsymbol 1}<0.
  \label{eq:local305}
\end{align}
Using  Farkas's lemma (see e.g. \citeR[Section 7.3]{Schrijver86}), one 
now obtains that conditions (\ref{eq:local304}) and (\ref{eq:local305}) are necessary and 
sufficient for (\ref{eq:local301}). For the application of Farkas's lemma to our 
particular setting one has to observe that since $\boldA$\ and ${\boldsymbol 1}$\ are 
rational, it is sufficient to have (\ref{eq:local304}) and (\ref{eq:local305}) for
rational $\boldz$\ (cf. \citeR{Schrijver86}[p.85]). This, in turn, is equivalent to having 
 (\ref{eq:local304}) and (\ref{eq:local305}) for integer $\boldz$. 
The strict positivity of the solution $\boldnu$\ can be derived from conditions
(\ref{eq:local304}) and (\ref{eq:local305}) by analogous arguments as 
for Corollary 7.1k in \cite{Schrijver86}.
\end{proofenv}


\begin{examenv}
  From Example~\ref{ex:illuedgefunction} we immediately obtain that 
nested edges $x,x'$\ violate (\ref{eq:carcompcond2}), and hence we again
obtain Corollary~\ref{cor:nestededges}. Also the sequences 
$(x_1,x_2)$\ and $(x_3,x_4,x_5)$\ of the support hypergraph in 
Figure~\ref{fig:6nodessupphyp} violate (\ref{eq:carcompcond1}), so 
that we again obtain the \car-incompatibili\-ty of that hypergraph.
\end{examenv}

\begin{figure}[htbp]
\psfrag{ax}[c]{(a)}
\psfrag{bix}[c]{(b-i)}
\psfrag{biix}[c]{(b-ii)}
\psfrag{cx}[c]{(c)}
\psfrag{dx}[c]{(d)}
  \centering
  \includegraphics[scale=0.4]{\figurepath/allthreenodes.eps}
  \caption{\Car-compatible support hypergraphs with three nodes}
  \label{fig:allthreenodes}
\end{figure}
 
\begin{examenv}
\shortciteGH\ (Example 4.6) derive a complete 
characterization of \car-compatibility for the case that exactly three 
different observations can be made with positive probability. In our framework
this amounts to finding all support hypergraphs with three nodes that satisfy
the conditions of Theorem~\ref{theo:graphcrit}. The possible  solutions are
shown in Figure~\ref{fig:allthreenodes} (omitting equivalent solutions 
obtained by duplicating edges). The labeling (a)-(d) of the solutions  
corresponds to the case enumeration in \shortciteGH.
It is easy to verify that the shown support hypergraphs all satisfy 
(\ref{eq:carcompcond1}) and (\ref{eq:carcompcond2}). That these are the only
such hypergraphs follows from the facts that adding a new edge to any of the
shown hypergraphs either leads to a hypergraph already on our list
(only possible for the pair (b-i) and (b-ii)), or introduces a pair of nested 
edges. Similarly, deleting any edge either leads to a hypergraph already 
shown, or to an invalid hypergraph in which not all nodes are covered. 

\end{examenv}



\section{Procedural Models}
\label{sec:procmodels}

So far we have emphasized the distributional perspective on \car. We have tried
to identify \car\ from the joint distribution of complete and coarse data. From
this point of view coarsening variables are an artificial construct that is 
introduced to describe the joint distribution. 
In some cases, however, a coarsening variable can also model an actual 
physical, stochastic process that leads to the data coarsening. In such cases,
the analysis should obviously take this concrete model for the underlying
coarsening process into account. 
In this section we study $d$-\car\ distributions
in terms of such \emph{procedural models} for the data generating mechanism. 
Our results in this section extend previous investigations of \car\ \emph{mechanisms}
in \shortciteGLR\ and \shortciteGH. 
 


Our first goal in this section is to determine canonical procedural models for 
coarsening mechanisms leading to $d$-\car\ data. Such canonical models can be used
in practice for evaluating whether a $d$-\car\ assumption is warranted for a particular
data set under investigation by matching the (partially known or hypothesized) 
coarsening mechanism of the data against any of the canonical models. 
Our investigation will then focus on properties that one may expect 
reasonable or natural procedural models to possess. These properties will be 
captured in two formal conditions of \emph{honesty} and \emph{robustness}. 
The analysis of these conditions will provide new strong support for the $d$-\ccar\ assumption.

The following definition of a procedural
model is essentially a generalization of coarsening variables, obtained by
omitting condition (\ref{eq:defG2}), and by replacing the single variable
$G$\ with a (potentially infinite) sequence $\boldG$.


\begin{defenv}
\label{def:procmod}
Let $P$\ be a coarse data distribution on $\Omega(W)$. 
A {\em procedural model for $P$} is given by
\begin{itemize}
\item A random variable $X$\ distributed according to the marginal of 
$P$\ on $W$.
\item A finite or infinite sequence $\boldG=G_1,G_2,\ldots,$\ of random 
variables,  such that $G_i$\ takes values in a finite set $\Gamma_i$\ ($i\geq 1$).
\item A function $f: W\times \times_i \Gamma_i\ \rightarrow\ 2^W\setminus\emptyset$, such that
$(X,f(X,\boldG))$\ is distributed according to $P$. 
\end{itemize}
\end{defenv}

We also call a procedural model $(X,\boldG,f)$\ a \car\ model (\ccar\ model), if the coarse 
data distribution $P$\ it defines is $d$-\car\ ($d$-\ccar). 
In the following we denote $\times _i \Gamma_i$\ with $\boldGamma$. 

Some natural coarsening processes are modeled with real-valued coarsening
variables (e.g. censoring times,  \citeR{HeiRub91}). We can accommodate real-valued
variables $Z$\ in our framework by identifying 
$Z$\ with a sequence
of binary random variables $Z_i$ ($i\geq 1$) defining its binary representation.
A sequence $\boldG$\ containing a continuous $Z=G_i$\ can then be replaced with
a sequence $\boldG'$\ in which the original variables $G_j$ ($j\neq i$) 
are interleaved with the binary $Z_i$. 

In the following, we will not  discuss measurability issues in detail 
(only in Appendix~\ref{sec:proofs} will a small amount of measure 
theory be needed). It should be 
mentioned, however, that it is always assumed that $W$\ and the $\Gamma_i$\ 
are equipped with a $\sigma$-algebra equal to their powerset, that on 
$W\times\boldGamma$\ we have the generated product $\sigma$-algebra, 
and that $f^{-1}(U)$\ is measurable for all $U\subseteq W$. 

\begin{table}[htbp]
  \centering


    \begin{tabular}{c|ccc}
      $f_{\ref{ex:Monty1}}$ & $A$ & $B$ & $C$\\ \hline
      $h$ & $\{A,C\}$ & $\{A,B\}$ & $\{A,C\}$\\
      $t$ & $\{A,B\}$ & $\{A,B\}$ & $\{A,C\}$
    \end{tabular}
    \hspace{5mm}
    \begin{tabular}{c|ccc}
      $f_{\ref{ex:Monty2}}$ & $A$ & $B$ & $C$\\ \hline
      $h$ & $\{A,C\}$ & $\{B,C\}$ & $\{B,C\}$\\
      $t$ & $\{A,B\}$ & $\{A,B\}$ & $\{A,C\}$
    \end{tabular}
  \caption{Procedural models for Examples~\ref{ex:Monty1} and \ref{ex:Monty2}}
  \label{tab:procmodsMonty}
\end{table}

\begin{examenv}
 Natural procedural models for the coarse data distributions of Examples~\ref{ex:Monty1}
and \ref{ex:Monty2} are constructed by letting $\boldG=F$\ represent the coin flip 
that determines the door to be opened. Suppose that in both examples the host 
has the following rule for matching the result of the coin flip with potential doors
for opening: when the coin comes up heads, then the host opens the door that is
first in alphabetical order among all doors (two, at most) that his rules permit
him to open. If the coin comes up tails,  he opens the door last in alphabetical
order. This is formally represented by a procedural model in which $X$\ is
a $\{A,B,C\}$-valued, uniformly distributed random variable, 
$\boldG$\ consists of a single $\{h,t\}$-valued, uniformly distributed random variable 
$F$, and $X$\ and $F$\ are independent. 

Table~\ref{tab:procmodsMonty} completes the specification of the procedural 
models by defining the functions $f_{\ref{ex:Monty1}}$\ and $f_{\ref{ex:Monty2}}$\ for 
the respective examples. Note that neither 
$(F,f_{\ref{ex:Monty1}})$\ nor $(F,f_{\ref{ex:Monty2}})$\ are coarsening 
variables in the sense of Definition~\ref{def:coarseningvar}, as e.g.
$A\in f_{\ref{ex:Monty1}}(B,h)\neq f_{\ref{ex:Monty1}}(A,h)$, in 
violation of (\ref{eq:defG2}).  
\end{examenv}


The two procedures described in the preceding example appear quite similar,
yet one produces a $d$-\car\ distribution while the other does not. 
We are now interested in identifying classes of procedural models that are guaranteed
to induce $d$-\car\ ($d$-\ccar) distributions. Conversely, for any given $d$-\car\ 
distribution $P$, we would like to identify procedural models that might have
induced $P$. We begin with a class of procedural models that stands in a trivial
one-to-one correspondence with $d$-\car\ distributions. 




\begin{examenv}
\label{ex:directcar}
(\emph{Direct \car\ model})
  Let $X$\ be a $W$-valued random variable, and $\boldG= G_1$\ with $\Gamma_1=2^W\setminus\emptyset$. 
Let the joint distribution
of $X$\ and  $G_1$\ be such that $P(G_1=U\mid X=x)=0$\ when $x\not\in U$, and 
\begin{equation}
  \label{eq:directmodelcondition}
  P(G_1=U\mid X=x)\ \mbox{is constant on}\  \{x\mid P(X=x)>0, x\in U\}.  
\end{equation}
Define $f(x,U)=U$. 
Procedural models of this form are just the coarsening variable representations of 
$d$-\car\ distributions that we already encountered in Theorem~\ref{theo:dcarandGcar}. Hence,
a coarse data distribution $P$\ is $d$-\car\ iff it is induced by a direct \car\ model.
\end{examenv}


The direct \car\ models are not much more than a restatement of the $d$-\car\
definition. They do not help us very much in our endeavor to identify canonical observational
or data-generating processes that will lead to $d$-\car\ distributions, because the
condition (\ref{eq:directmodelcondition}) does not correspond to an easily
interpretable condition on an experimental setup. 

For $d$-\ccar\ the situation is quite different: here a direct encoding of the
$d$-\ccar\ condition leads to a rather natural class of procedural models. The 
class of models described next could be called, in analogy to Example~\ref{ex:directcar},
``direct \ccar\ models''. Since the models here described permit a more natural
interpretation, we give it a different name, however.

\begin{examenv}
  \label{ex:mgroupeddatamodel}
(\emph{Multiple grouped data model, MGD})
Let $X$\ be a $W$-valued random variable. 
Let $({\cal W}_1,\ldots,{\cal W}_k)$\ be a family of  partitions of $W$\
(cf. Theorem~\ref{theo:equivd-ccar}). Let $\boldG=G_1$, where $G_1$\ takes 
values in $\{1,\ldots,k\}$\ and is independent
of $X$. Define $f(x,i)$\ as that $U\in {\cal W}_i$\ that contains
$x$. Then $(X,G_1,f)$\ is \ccar. Conversely, every $d$-\ccar\ coarse data model
is induced by such a multiple grouped data model.
\end{examenv}

The multiple grouped data model corresponds exactly to the \cargen\ procedure
of \shortciteGH. It allows intuitive interpretations as representing procedures
where  one randomly selects one out of $k$\ different available 
sensors or tests, each of which will reveal the true value
of $X$\ only up to the accuracy represented by the set $U\in {\cal W}_i$\ 
containing $x$. In the special case $k=1$\ this corresponds to 
\emph{grouped} or \emph{censored} data~\cite{HeiRub91}. 
\shortciteGH\ introduced \cargen\ as a procedure that is guaranteed to 
produce $d$-\car\ distributions. They do not consider $d$-\ccar, and therefore do not
establish the exact correspondence between \cargen\ and $d$-\ccar. In a similar
vein, \shortciteGLR\ introduced a general procedure for 
generating $d$-\car\ distributions. The following example rephrases the
construction of \shortciteGLR\  in our terminology.

\begin{examenv}
 \label{ex:randmoncoars}
(\emph{Randomized monotone coarsening, RMC})
Let $X$\ be a $W$-valued random variable. Let 
$\boldG=H_1,S_1,H_2,S_2,\ldots,S_{n-1},H_n$, where the $H_i$\ take 
values in $2^W$, and the $S_i$\ are $\{0,1\}$-valued.
Define
\begin{displaymath}
  \bar{H}_i:= \left\{
  \begin{array}{ll}
    H_i & \mbox{if } X\in H_i \\
    W\setminus H_i & \mbox{if } X\not\in H_i. 
  \end{array}
  \right.
\end{displaymath}
Let the conditional distribution of $H_i$\ given 
$X$\ and $H_1,\ldots,H_{i-1}$\ be concentrated on
subsets of $\cap_{j=1}^{i-1}\bar{H}_j$.

This model represents a procedure where one successively refines a ``current''
coarse data set ${\cal A}_i:=\cap_{h=1}^{i-1} \bar{H_h}$\  by selecting 
a random subset $H_i$\ of  ${\cal A}_i$\ and checking whether 
$X\in H_i$\ or not, thus computing $\bar{H}_i$\ and ${\cal A}_{i+1}$. 
This process is continued until for the first time
$S_i=1$\ (i.e. the $S_i$\ represent stopping conditions). The result of the 
procedure, then is represented by the following function $f$:
\begin{displaymath}
  f(X,(H_1,S_1,\ldots,S_{n-1},H_n))= \cap_{i=1}^{\emph{min}\{k\mid S_k=1\}}\bar{H}_i.
\end{displaymath}

Finally, we impose the conditional independence condition that the distribution of 
the $H_i,S_i$\ depend on $X$\ only through $\bar{H}_1,\ldots,\bar{H}_{i-1}$, i.e.
\begin{displaymath}
  \begin{array}{l}
    P(H_i\mid X,H_1,\ldots,H_{i-1})=P(H_i\mid \bar{H}_1,\ldots,\bar{H}_{i-1})\\
    P(S_i\mid X,H_1,\ldots,H_{i-1})=P(S_i\mid \bar{H}_1,\ldots,\bar{H}_{i-1}).
  \end{array}
\end{displaymath}
\end{examenv}

As shown in \shortciteGLR, an \emph{RMC} model always generates a $d$-\car\ distribution,
but not every $d$-\car\ distribution can be obtained in this way. \shortciteGH\ state that
\emph{RMC} models are a special case of  \cargen\ models. As we will see below, 
\cargen\ and \emph{RMC} are actually equivalent, and thus, both correspond exactly to
$d$-\ccar\ distributions. The distribution of Example~\ref{ex:Monty2} is the standard example (already used 
in a slightly different form in \shortciteGLR) of a $d$-\car\ distribution that cannot be
generated by \emph{RMC} or \cargen. A question of considerable interest, then,
is whether there exist natural procedural models that correspond exactly to $d$-\car\ distributions.
\shortciteGLR\ state that they ``cannot conceive of a more general mechanism than
a randomized monotone coarsening scheme for constructing the \car\ mechanisms
which one would expect to meet with in practice,\ldots''(p.267). \shortciteGH, on
the other hand, generalize the \cargen\ models to a class of models termed 
\cargenstar, and show that these exactly comprise the models inducing $d$-\car\ distributions.

However, the exact extent to which \cargenstar\ is more natural or reasonable than the
trivial direct \car\ models has not been formally characterized. We will discuss this
issue below. First we present another class of procedural models. This is a rather intuitive
class  which contains models not equivalent to any \cargen/\emph{RMC} model.
 

\begin{examenv}
(\emph{Uniform noise model})
Let $X$\ be a $W$-valued random variable. 
Let $\boldG=N_1,H_1,N_2,H_2,\ldots$, where the $N_i$\ are 
$\{0,1\}$-valued, and the $H_i$\ are $W$-valued with
\begin{equation}
  \label{eq:uniformnoisecondition}
  P(H_i=x)=1/\cardinal{W}\hspace{3mm} (x\in W).
\end{equation}
Let $X,N_1,H_1,\ldots$\ be independent. Define for $h_i\in W, n_i\in\{0,1\}$:
\begin{equation}
  \label{eq:uniformnoisef}
  f(x,(n_1,h_1,\ldots))=\{x\}\cup\{h_i\mid i: n_i=1\}.
\end{equation}
This model describes a procedure where in several steps (perhaps infinitely many)
uniformly selected states from $W$\ are added as noise to the observation.
The random variables $N_i$\ represent events that cause additional noise to be added. 
The distributions generated by this procedure are $d$-\car, because for all 
$x,U$\ with $x\in U$:
\begin{displaymath}
  P(Y=U\mid X=x)=P(\{h_i\mid i: n_i=1\}=U)+P(\{h_i\mid i: n_i=1\}=U\setminus \{x\}).
\end{displaymath}
By  the uniformity condition (\ref{eq:uniformnoisecondition}), and the 
independence of the family $\{X,N_1,H_1,\ldots\}$, the last
probability term in this equation is constant for  $x\in U$. 

The uniform noise model can not  generate exactly the $d$-\car\ distribution
of Example~\ref{ex:Monty2}. However, it can generate the variant of that 
distribution that was originally given in \shortciteGLR. 
\end{examenv}

The uniform noise model is rather specialized, and far from being able to 
induce every possible $d$-\car\ distribution. As mentioned above, \shortciteGH\
have proposed a procedure called \cargenstar\ for generating exactly
all $d$-\car\ distributions. This procedure is described in \shortciteGH\ 
in the form of a randomized algorithm, but it can easily be recast in the
form of a procedural model in the sense of Definition~\ref{def:procmod}.
We shall not pursue this in detail, however, and instead present a procedure
that has the same essential properties as \cargenstar\ (especially with regard 
to the formal ``reasonableness conditions'' we shall introduce below), 
but is somewhat simpler and 
perhaps slightly more intuitive. 

\begin{examenv}
({\em  Propose and test model, P\&T)})
\label{ex:ptmodels}
Let $X$\ be a $W$-valued random variable. Let $\boldG=G_1,G_2,\ldots$\ be an infinite
sequence of random variables taking values in $2^W\setminus\emptyset$. 
Let $X,G_1,G_2,\ldots$\ be independent, and the $G_i$\ be identically
distributed, such that 
\begin{equation}
  \label{eq:pandtcondition}
  \sum_{U:x\in U}P(G_i=U)
  \hspace{3mm}\mbox{is constant on}\hspace{3mm}
  \{x\in W\mid P(X=x)>0\}.
\end{equation}
Define 
 \begin{displaymath}
   f(x,(U_1,U_2,\ldots):=
   \left\{
     \begin{array}{ll}
       U_i & \mbox{if}\ i=\min\{j\geq 1\mid x\in U_j\} \\
       W & \mbox{if} \ \{j\geq 1\mid x\in U_j\}=\emptyset
     \end{array}
     \right. .
 \end{displaymath}
\end{examenv}

The P\&T model describes a procedure where we randomly propose a set 
$U\subseteq W$, test whether $x\in U$, and return $U$\ if the result is 
positive (else continue). The condition (\ref{eq:pandtcondition}) can be 
understood as an unbiasedness condition, which ensures that for every
$x\in W$\ (with $P(X=x)>0$) we are equally likely to draw a positive test
for $x$. The following theorem is analogous to Theorem 4.9 in \shortciteGH; 
the proof is much simpler, however. 

\begin{theoenv}
  A coarse data distribution $P$\ is $d$-\car\ iff it can be induced by 
a P\&T model.
\end{theoenv}

\begin{proofenv}
  That every distribution induced by a P\&T model is $d$-\car\ follows immediately
from 
\begin{equation}
\label{eq:local400}
  P(Y=U\mid X=x)=P(G_i=U)/\sum_{U':x\in U'}P(G_i=U'). 
\end{equation}
By (\ref{eq:pandtcondition}) this is constant on $\{x\in U\mid P(X=x)>0\}$\
(note, too, that (\ref{eq:pandtcondition}) ensures that the sum in the 
denominator of (\ref{eq:local400}) is nonzero for all $x$, and that 
in the definition of $f$\ the case $\{j\geq 1\mid x\in U_j\}=\emptyset$\ 
only occurs with probability zero). 

Conversely, let $P$\ be a $d$-\car\ distribution on $\Omega(W)$. Define 
$c:=\sum_{U\in 2^W}P(Y=U\mid X\in U)$, and 
\begin{displaymath}
  P(G_i=U)=P(Y=U\mid X\in U)/c.
\end{displaymath}
Since $P(Y=U\mid X\in U)=P(Y=U\mid X=x)$\ for all $x\in U$\ with
$P(X=x)>0$, we have $\sum_{U:x\in U}P(Y=U\mid X\in U)=1$\ for all $x\in W$\ with
$P(X=x)>0$. It follows  that (\ref{eq:pandtcondition}) is satisfied 
with $1/c$\ being the constant. The resulting $P\&T$\ model
induces the original $P$: 
\begin{align*}
  P(f(X,\boldG)=U\mid X=x) & =
  (P(Y=U\mid X\in U)/c)/(\sum_{U':x\in U'}P(Y={U'}\mid X\in U')/c)\\
  & =P(Y=U\mid X\in U) = P(Y=U\mid X=x).
\end{align*}
\end{proofenv}

The P\&T model looks like a reasonable natural procedure. However, it violates 
a desideratum that \shortciteGLR\ have put forward for a natural coarsening
procedure:
\begin{quotation}
  \emph{(D)} In the coarsening procedure, no more information about the true value
of $X$\ should be used than is finally revealed by the coarse data variable 
$Y$ (\citeR[p.266]{GilvdLRob97}, paraphrased).
\end{quotation}
The P\&T model violates desideratum \emph{(D)}, because when we first unsuccessfully
test $U_1,\ldots,$ $U_k$, then we  require the information
$x\not\in \cup_{i=1}^k U_i$, which is not included in the final data 
$Y=U_{k+1}$. 
The observation generating process of Example~\ref{ex:Monty2}, too, appears to 
violate \emph{(D)}, as the host requires the precise value of $X$\ when
following his strategy.
Finally, the uniform noise model violates \emph{(D)}, because in the computation
(\ref{eq:uniformnoisef}) of the final coarse data output the exact value of 
$X$\ is required. 
 These  examples suggest that \emph{(D)}
is not a condition that one must necessarily expect every natural coarsening
procedure to possess. \emph{(D)} is most appropriate when coarse data is generated by an experimental 
process that is aimed at determining the true value of $X$, but may be unable
to do so precisely. 
In such a scenario,  \emph{(D)} corresponds to the assumption that all information
about the value of $X$\ that is collected in the experimental process also is 
reported in the final result. Apart from experimental procedures, also  'accidental'
processes corrupting complete data can generate $d$-\car\ data (as represented, e.g.,
by the uniform noise model). For such procedures \emph{(D)} 
is not immediately seen as a necessary feature. However, Theorem~\ref{theo:ccarchar}
below will lend additional support to \emph{(D)} also in these cases.


\shortciteGH\ argue that their class of \cargenstar\ procedures only contains
reasonable processes, because ``each step of the algorithm can depend only on
information available to the experimenter, where the 'information' is encoded 
in the observations made by the experimenter in the course of running the
algorithm''(\shortciteGH, p. 260). The same can be said about the P\&T procedure.
The direct \car\ model would not be reasonable in this sense,
because for the simulation of the variable $G$\ one would need to pick a distribution
dependent on the true value of $X$, which is not assumed to be available. However,
it is hard to make rigorous this distinction between direct \car\ models on the one
hand, and \cargenstar/P\&T  on the other hand, because the latter procedures
permit tests for the value of $X$\ (through checking $X\in U$\ for test sets 
$U$\ -- using singleton sets $U$\ one can even query the exact value of 
$X$), and the continuation of the simulation is dependent on the outcome of
these tests. 

We will now establish a more solid foundation for discussing reasonable vs.
unreasonable coarsening procedures by introducing two different rigorous 
conditions for natural or reasonable
\car\ procedures. One is a formalization of desideratum \emph{(D)}, while the other 
expresses an invariance of the \car\ property under numerical parameter changes.
We will then show that these conditions can only be satisfied when the generated
distribution is $d$-\ccar. For the purpose of this analysis it is helpful to 
restrict attention to a special type of procedural models.

\begin{defenv}
\label{def:bernoulli}
  A procedural model $(X,\boldG,f)$\ is a \emph{Bernoulli-model} if the
family $X,G_1,$ $G_2,\ldots$\ is independent.
\end{defenv}
 
The name Bernoulli model is not quite appropriate here, because the variables $X,G_i$\
are not necessarily binary. However, it is clear that one could also replace the
multinomial $X$\ and $G_i$\ with suitable sets of (independent) binary random variables. 
In essence, then, a Bernoulli model in the sense of Definition~\ref{def:bernoulli}
can be seen as an infinite sequence of independent coin tosses (with coins of
varying bias). Focusing on Bernoulli models is no real limitation:

\begin{theoenv}
\label{theo:existsBernoulli}
  Let $(X,\boldG,f)$\ be a procedural model. Then there exists a Bernoulli
model $(X,\boldG^*,f^*)$\ inducing the same coarse data distribution.
\end{theoenv}
 
The reader may notice that the statement of Theorem~\ref{theo:existsBernoulli}
really is quite trivial: the coarse data distribution induced by $(X,\boldG,f)$\ 
is just a distribution on the finite coarse data space $\Omega(W)$, and there 
are many simple, direct constructions of Bernoulli models for such a given 
distribution. The significance of Theorem~\ref{theo:existsBernoulli}, therefore,
lies essentially in the following proof, where we construct a Bernoulli model
$(X,\boldG^*,f^*)$\ that preserves all the essential procedural characteristics of 
the original model $(X,\boldG,f)$. In fact, the model $(X,\boldG^*,f^*)$\ can be 
understood as an implementation of the procedure $(X,\boldG,f)$\ using a 
generator for independent random numbers.

To understand the intuition of the construction,
consider a randomized algorithm for simulating the procedural model $(X,\boldG,f)$. 
The algorithm successively samples values for $X,G_1,G_2,\ldots$, and finally 
computes $f$\ (for most natural procedural models the value of $f$\ is already
determined by finitely many initial $G_i$-values, so that not infinitely many
$G_i$\ need be sampled, and the algorithm actually terminates; for our 
considerations, however, algorithms taking infinite time pose no conceptual
difficulties). The distribution used for sampling $G_i$\ may depend on the values
of previously sampled $G_1,\ldots,G_{i-1}$, which, in a computer implementation
of the algorithm are encoded in  the current program state. 

The set of all possible runs of the algorithm can be represented as a tree, where 
branching nodes correspond to sampling steps for the $G_i$.
A single execution of the algorithm generates one branch 
in this tree. One can now construct an equivalent algorithm that, instead, 
generates the whole tree breadth-first, and that labels each branching node
with a random value for the $G_i$\ associated with the node,  sampled according 
to the distribution determined by the  program state 
corresponding to that node. In this algorithm, sampling of random
values is independent. The labeling of all branching nodes identifies a unique
branch in the tree, and for each branch, the probability of being identified by
the labeling is equal to the probability of this branch representing the
execution of the original algorithm (a similar transformation by pre-computing
all random choices that might become relevant is described in 
by \citeR{GilRob01}[Section 7]). The following proof formalizes the preceding
informal description.
\\


\begin{proofofenv}{of Theorem~\ref{theo:existsBernoulli}}
  For each random variable $G_i$\ we introduce a sequence of random
variables $G^*_{i,1},\ldots,G^*_{i,K(i)}$, where 
$K(i)=\cardinal{W\times \times_{j=1}^{i-1}\Gamma_j}$\ is the size of the 
joint state space of $X,G_1,\ldots,G_{i-1}$.  The state space of 
the $G^*_{i,h}$\ is $\Gamma_i$\ (with regard to our informal explanation,
$G^*_{i,h}$\ corresponds
to the   node in the full computation tree that represent the 
sampling of $G_i$\  when the previous execution has resulted 
in the $h$th out of $K(i)$\ possible program states). We 
construct a joint distribution for $X$\ and the $G^*_{i,h}$\ by setting 
$P(G^*_{i,h}=v)=P(G_i=v\mid (X,G_1,\ldots,G_{i-1})=s_h)$\ 
($s_h$\  the $h$th state in an enumeration of $W\times \times_{j=1}^{i-1}\Gamma_j$),
and by taking $X$\ and the $G^*_{i,h}$\ to be independent. 

It is straightforward to define a mapping
\begin{displaymath}
  h^*:W\times \times_{i\geq 1}\Gamma_i^{K(i)}\rightarrow  \boldGamma
\end{displaymath}
such that $(X,h^*(X,\boldG^*))$\ is distributed as $(X,\boldG)$\ 
(the mapping $h^*$\ corresponds
to the extraction of the ``active'' branch in the full labeled computation
tree). Defining 
$f^*(x,\boldg^*):=f(x,h^*(x,\boldg^*)) $\ 
then completes the construction of the Bernoulli  model. 
\end{proofofenv}


\begin{defenv}
  The Bernoulli model $(X,\boldG^*,f^*)$\ obtained via the construction of the 
proof of Theorem~\ref{theo:existsBernoulli} is called the
\emph{Bernoulli transform} of $(X,\boldG,f)$.
\end{defenv}

\begin{examenv}
\label{ex:bernoullifordirect}
  For a direct \car\ model $(X,G,f)$\ we obtain the Bernoulli transform
$(X,(G^*_1,$ $\ldots,G^*_n),f^*)$, where 
\begin{displaymath}
\begin{array}{l}
  P(G_i^*=U)= P(G=U\mid X=x_i),\\
  h^*(x_i,U_1,\ldots,U_n)=(x_i,U_i),
\end{array}
\end{displaymath}
and so $f^*(x_i,U_1,\ldots,U_n)=U_i$.
\end{examenv}

When the coarsening procedure is a Bernoulli model, then no information
about $X$\ is used for sampling the variables $\boldG$. The only part
of the procedure where $X$\ influences the outcome is in the final 
computation of $Y=f(X,\boldG)$. The condition that in this computation
only as much knowledge of $X$\ should be required as finally revealed
by $Y$\ now is basically condition (\ref{eq:defG2}) for coarsening
variables. The state space $\boldGamma$\ for $\boldG$\ now being 
(potentially) uncountable, it is however more appropriate to replace the 
universal quantification ``for all $g$'' in (\ref{eq:defG2}) 
with ``for almost all $g$'' in 
the probabilistic sense. We thus define:

\begin{defenv}
  \label{def:honest}
A Bernoulli model is \emph{honest}, if for all $x,x'$ with 
$P(X=x)>0,P(X=x')>0$, and all $U\in 2^W\setminus\emptyset$:
\begin{equation}
  \label{eq:honestcond}
  P(\boldG\in\{\boldg\mid f(x,\boldg)=U,x'\in U \Rightarrow f(x',\boldg)=U\})=1.
\end{equation}
\end{defenv}

\begin{examenv}
The Bernoulli model of Example~\ref{ex:bernoullifordirect} is not honest, because
one can have for some $U_1,\ldots,U_n$\  with
$P(\boldG=(U_1,\ldots,U_n))>0$: $U_j\neq U_i$, and $x_i,x_j\in U_i$, such that
\begin{displaymath}
  f^*(x_i,U_1,\ldots,U_n)=U_i \neq U_j=f^*(x_j,U_1,\ldots,U_n).
\end{displaymath}
\end{examenv}
 
Honest Bernoulli models certainly satisfy \emph{(D)}. On the other hand, there
can be non-Bernoulli models that also seem to  satisfy \emph{(D)} 
(notably the RMC models, which were developed with \emph{(D)} in mind).
However, for non-Bernoulli models it appears hard to make precise the 
condition that the sampling of $\boldG$\ does not depend on $X$\ beyond
the fact that $X\in Y$
\footnote{The intuitive condition that $\boldG$\ must be independent of 
$X$\ given $Y$\ turns out to be inadequate.}.
The following theorem indicates that our formalization of 
\emph{(D)} in terms of Bernoulli models only  is not too narrow.


\begin{theoenv}
The Bernoulli transforms of MGD, \cargen\ and RMC models are honest.
\end{theoenv}

The proof for all three types of models are elementary, though partly tedious.
We omit  the details here.

We now turn to a second condition for reasonable procedures. For this we observe 
that the MGD/\cargen/RMC models are essentially defined in terms of the 
``mechanical procedure'' for generating the coarse data, whereas the direct \car,
the uniform noise, and the P\&T models (and in a similar way \cargenstar) rely on
the numerical conditions (\ref{eq:directmodelcondition}),(\ref{eq:uniformnoisecondition}),
respectively (\ref{eq:pandtcondition}), on distributional parameters. These 
procedures, therefore, are fragile in the sense that slight perturbations of the
parameters will destroy the $d$-\car\ property of the induced distribution. We would
like to distinguish robust \car\ procedures as those for which the $d$-\car\
property is guaranteed through the mechanics of the process alone (as determined
by the state spaces of the $G_i$, and the definition of $f$), and does not 
depend on parameter constraints for the $G_i$\ (which, in a more or less subtle
way, can be used  to mimic the brute force condition  (\ref{eq:directmodelcondition})).
Thus, we will essentially consider a \car\ procedure to be robust, if it stays
\car\ under changes of the parameter settings for the $G_i$. There are two points
to consider before we can state a formal definition of this idea. First,
we observe that our concept of robustness should again be based on Bernoulli
models, since in non-Bernoulli models even arbitrarily small parameter changes
can create or destroy independence relations between the variables 
$X,\boldG$, and such independence relations, arguably, reflect qualitative
rather than merely quantitative aspects of the coarsening mechanism. 

%Note, however, that even our prototypes  MGD/\cargen/RMC for reasonable processes 
%impose some distributional constraints in the form of independence conditions. 
%These independence conditions, however, will be taken care of in the
%corresponding Bernoulli model by the definition of $f$, and thus here become
%part of the mechanics of the procedure. For this reason it is useful to base the 
%following definition again on Bernoulli models.  

Secondly, we will want to limit permissible parameter changes to those that 
do not lead to such drastic quantitative changes that outcomes with previously 
nonzero probability become zero-probability events, or vice versa. This is in 
line with our perspective in Section~\ref{sec:carcond}, where  the set 
of support of a distribution on a finite state space was viewed as a basic qualitative property.
In our current context we are dealing with  distributions on uncountable state spaces,
and we need to replace the notion of identical support with the notion of 
absolute continuity: recall that two distributions $P,\tilde{P}$\ on a state space
$\Sigma$\  are called \emph{mutually absolutely continuous}, written $P\equiv\tilde{P}$,
if $P(S)=0\Leftrightarrow \tilde{P}(S)=0$\ for all measurable $S\subseteq\Sigma$. 

For a distribution $P(\boldG)$\ on $\boldGamma$, with $\boldG$\ an independent family,
we can obtain $\tilde{P}(\boldG)$\ with $P\equiv\tilde{P}$, for example, by 
changing for finitely many $i$\ parameter values $P(G_i=g)=r>0$\ to new values
$\tilde{P}(G_i=g)=\tilde{r}>0$. On the other hand, if e.g. $\Gamma_i=\{0,1\}$, 
$P(G_i=0)=1/2$, and $\tilde{P}(G_i=0)=1/2+\epsilon$ for all $i$\ and some
$\epsilon>0$, then $P(\boldGamma)\not\equiv \tilde{P}(\boldGamma)$.
For a distribution $P(X)$\ of $X$\ alone one has $P(X)\equiv\tilde{P}(X)$\ iff 
$P$\ and $\tilde{P}$\ have the same support.  


\begin{defenv}
  A Bernoulli model $(X,\boldG,f)$\ is \emph{robust} \car\  
(\emph{robust} \ccar), if it is \car\ (\ccar), and remains
\car\ (\ccar) if the distributions $P(X)$\  and 
$P(G_i)\ (i\geq 1)$\ are replaced with distributions  
$\tilde{P}(X)$\ and $\tilde{P}(G_i)$, such that $P(X)\equiv \tilde{P}(X)$\ and
$P(\boldG)\equiv \tilde{P}(\boldG)$. 
\end{defenv}

The Bernoulli transforms of MGD/\cargen\ are robust \ccar. Of the
class RMC we know, so far, that it is \car. The Bernoulli transform
of RMC can be seen to be robust \car. The Bernoulli transforms of 
\cargenstar/P\&T, on the other hand, are not robust (and neither is
the uniform noise model, which already is Bernoulli). We now come 
to the main result of this section, which basically identifies 
the existence of 'reasonable' procedural models with $d$-\ccar.

\begin{theoenv}
\label{theo:ccarchar}
  The following are equivalent for a distribution $P$\ on
$\Omega(W)$:
\begin{description}
\item[(i)] $P$\ is induced by a robust \car\ Bernoulli model.
\item[(ii)] $P$\ is induced by a robust \ccar\ Bernoulli model.
\item[(iii)] $P$\ is induced by an honest Bernoulli model.
\item[(iv)] $P$\ is $d$-\ccar.
\end{description}
\end{theoenv}

The proof is given in Appendix~\ref{sec:proofs}. Theorem~\ref{theo:ccarchar}
essentially identifies the existence of a natural procedural model for a 
$d$-\car\ distribution with the property of being $d$-\ccar, rather than merely
$d$-\car. This is a somewhat surprising result at first sight, given that 
$\boldM$-\mcar\ is usually considered an unrealistically strong assumption as compared
to $\boldM$-\mar. There is no real contradiction here, however, as we have seen before
that $d$-\ccar\ is weaker than $\boldM$-\mcar. Theorem~\ref{theo:ccarchar} 
indicates that in practice one may find many cases where $d$-\ccar\
holds, but $\boldM$-\mcar\ is not fulfilled.



\section{Conclusion}
\label{sec:conclusion}

We have reviewed several versions of \car\ conditions. They differ with respect to 
their formulation, which can be in terms of a coarsening variable, or 
in terms of a purely distributional constraint. 
The different versions are mostly non-equivalent.
Some care, therefore, is required in determining for a particular statistical or
probabilistic inference problem the appropriate \car\ condition that is both
sufficient to justify the intended form of inference, and the assumption of which
is warranted for the observational process at hand. We argue that the distributional forms
of \car\ are the more relevant ones: 
when the observations are fully described as subsets of $W$, then the coarse data
distribution is all that is required in the analysis, and the  introduction of an
artificial coarsening variable $G$\ can skew the analysis. 

Our main goal was to provide characterizations of coarse data distributions that
satisfy $d$-\car. We considered two types of such characterizations: the first
type is a ``static'' description of $d$-\car\ distributions in terms of their sets 
of support. Here we have derived a quite intuitive, complete characterization
by means of the support hypergraph of a coarse data distribution. 

The second type of characterizations is in terms of procedural models for the
observational process that generates the coarse data. We have considered several 
models for such observational processes, and found that the arguably most natural ones
are exactly those that generate observations which are $d$-\ccar, rather than only $d$-\car.
This is somewhat surprising at first, because $\boldM$-\ccar\ is typically an 
unrealistically strong assumption (cf. Example~\ref{ex:T1T2-3}). The distributional 
form, $d$-\ccar, on the contrary, turns out to be the perhaps most natural assumption.
The strongest support support for the $d$-\ccar\ assumption is provided by the
equivalence $(i)\Leftrightarrow (iv)$\ in Theorem~\ref{theo:ccarchar}: assuming 
$d$-\car, but not $d$-\ccar, means that we must be dealing with a fragile coarsening
mechanism that produces $d$-\car\ data only by virtue of some specific parameter 
settings. Since we usually do not know very much about the coarsening mechanism,
the assumption of such a special parameter-equilibrium (as exemplified by (\ref{eq:pandtcondition}))
will typically be unwarranted.

\section*{Acknowledgments}

The author would like to thank Ian Pratt for providing the initial motivation for
investigating the basis of probabilistic inference by conditioning. 
Richard Gill, Peter Gr\"unwald, and James Robins have provided valuable comments
to earlier versions of this paper. I am particularly indebted to Peter  Gr\"unwald
for suggestions on the organization of the material in Section~\ref{sec:defcar}, which
led to a great improvement in the presentation.  Richard Gill must be credited  for
the short proof of Theorem~\ref{theo:graphcrit}, which replaced a previous much more
laborious one.   



\appendix


\section{Proof of Theorem~\ref{theo:ccarchar}}
\label{sec:proofs}

%{\bf Theorem~\ref{theo:graphcrit}}
%  The support hypergraph $({\cal N},W')$\ is \car-compatible
%   iff for every two sequences $\boldx,\boldx'$\ of edges from 
%  $W'$\ we have
%  \begin{align*}
%    & 1_{\boldx} = 1_{\boldx'}\ \ \Rightarrow\ \ \cardinal{\boldx}= \cardinal{\boldx'}\ \mbox{and}\\
%    & 1_{\boldx} <  1_{\boldx'}\ \ \Rightarrow\ \ \cardinal{\boldx} < \cardinal{\boldx'}.
%  \end{align*}

% \begin{proofenv}
%  Define a set function $\mu_0$\ on $W'\subseteq 2^{\cal N}$\ by 
%  $\mu_0(x):\ 1/n$\ for all $x$. 
%  \begin{quotation}
%    \emph{Claim 1}: $({\cal N},W')$\ is \car-compatible
%  iff $\mu_0$\ can be extended to a strictly positive finite measure $\tilde{\mu}$\ on
%  $2^{\cal N}$
%  \end{quotation}
%  To verify claim 1, observe that if  $\tilde{\mu}$\ is such an extension we can define
%  $\nu(U):= n\tilde{\mu}(U)$, which satisfies the condition of 
%  Proposition~\ref{prop:existsvaluation}. Conversely, when $\nu$\ is as in 
%  Proposition~\ref{prop:existsvaluation}, then $\tilde{\mu}(U):=\nu(U)/n$\
%  defines a measure on ${\cal N}$\ with $\sum_{U:x\in U}\tilde{\mu_0}(U)=1/n$,
%  i.e. an extension of $\mu_0$. 

%  The remainder of this proof now closely follows a construction for extensions
%of set functions to finitely additive measures as described in~\cite[Section 3.2]{BhaBha83}.
%The construction of \cite{BhaBha83} here has to amended, however, in order to 
%ensure that the constructed measure is strictly positive. 

%  In the following we use $A,B,\ldots$\ to denote subsets of ${\cal N}$\ which may
%  or may not be of the form $A=x \in W'$. Extending Definition~\ref{def:edgefunction},
%  we associate with a sequence $\boldA=A_1,\ldots,A_k$\ of such subsets the function
%  $1_{\boldA}$\ defined on $W'$. 

%    \begin{quotation}
%      \emph{Claim 2}: Let $\tilde{\mu}$\ be some strictly positive set function on $2^{\cal N}$.
%      Then $\tilde{\mu}$\ is a measure iff for all sequences $\boldA,\boldB$\ in $2^{\cal N}$
%    \begin{eqnarray}
%      1_{\boldA}= 1_{\boldB}
%      & \Rightarrow &
%      \sum_{A\in \boldA}\tilde{\mu}(A) = \sum_{B\in \boldB}\tilde{\mu}(B)
%      \label{eq:firstineq} \\
%      1_{\boldA} < 1_{\boldB}
%      & \Rightarrow &
%      \sum_{A\in \boldA}\tilde{\mu}(A) < \sum_{B\in \boldB}\tilde{\mu}(B)
%      \label{eq:secondineq} 
%    \end{eqnarray}
%    \end{quotation}
   
%For the 'only if' part of claim 2 observe that $\tilde{\mu}(A)=\sum_{U\in A}\tilde{\mu}(\{U\})$\
%when $\tilde{\mu}$\ is a measure on $2^{\cal N}$. From this (\ref{eq:firstineq}) and
%(\ref{eq:secondineq}) directly follow.
%Conversely, if  $\tilde{\mu}$\ is some strictly positive 
%set function on $2^{\cal N}$\ that satisfies (\ref{eq:firstineq})
%for all sequences $\boldA,\boldB$, then $\tilde{\mu}$\ is a measure:
%if $A,B\in 2^{\cal N}$\ with $A\cap B=\emptyset$, then
%$1_A+1_B=1_{A\cup B}$, and $\tilde{\mu}(A)+\tilde{\mu}(B)=\tilde{\mu}(A\cup B)$\ 
%follows from (\ref{eq:firstineq}). Also, $\tilde{\mu}(\emptyset)=0$\ is guaranteed by
%(\ref{eq:firstineq}), because for any $A$: $1_A=1_A+1_{\emptyset}$, and hence
%$\tilde{\mu}(A)=\tilde{\mu}(A)+\tilde{\mu}(\emptyset)$.

%For our initial set function $\mu_0$, (\ref{eq:firstineq}) and
%(\ref{eq:secondineq}) are equivalent to (\ref{eq:carcompcond1}) and 
%(\ref{eq:carcompcond2}). Claims 1 and 2 thus imply the 'only if' direction
%of Theorem~\ref{theo:graphcrit}. For the 'if' direction we have to show that
%$\mu_0$\ can be extended to a strictly positive set function $\tilde{\mu}$\ 
%on  $2^{\cal N}$\ satisfying (\ref{eq:firstineq}) and
%(\ref{eq:secondineq}). 

%For this let $\mu$\ be a set function defined on some system $V\subset 2^{\cal N}$\ with
%$W\subseteq V$, and such that (\ref{eq:firstineq}) and (\ref{eq:secondineq}) hold
%for all sequences $\boldA,\boldB$\ of elements from $V$. Let $C\in 2^{\cal N}$\ with 
%$C\not\in V$. We show that $\mu$\ can be extended to a set function on 
%$V\cup \{ C\}$\ such that (\ref{eq:firstineq}) and (\ref{eq:secondineq}) continue to hold.
%For this define
%\begin{align}
%  & \mu_i(C)  :=  \itsup\{  (\sum_{A\in\boldA}\mu(A)-\sum_{B\in\boldB}\mu(B))/k\mid 
%    k\in\Nset,\ \boldA,\boldB\subset V: k1_C\geq 1_{\boldA}  - 1_{\boldB}\}
%   \label{eq:muidef} \\
%  & \mu_e(C)  :=   \itinf\{  (\sum_{A\in\boldA}\mu(A)-\sum_{B\in\boldB}\mu(B))/k\mid 
%    k\in\Nset,\ \boldA,\boldB\subset V: k1_C\leq 1_{\boldA}  - 1_{\boldB}\}
%   \label{eq:muedef}
%\end{align}

%We show the following:

%\begin{quotation}
%\emph{Claim 3}:
%The supremum and infimum in (\ref{eq:muidef}), respectively (\ref{eq:muedef}) are 
%taken over nonempty sets, and therefore are well-defined real numbers.
%\end{quotation}

%\begin{quotation}
%\emph{Claim 4}:
%$0\leq \mu_i(C)\leq\mu_e(C)$
%\end{quotation}



%\begin{quotation}
%\emph{Claim 5}:
%For all $k,\boldA,\boldB$:
%\begin{eqnarray}
%  k1_C=1_{\boldA} - 1_{\boldB} & \Rightarrow &  
%  \mu_i(C)=\mu_e(C)=(\sum_{A\in\boldA} \mu(A)-\sum_{B\in\boldB}\mu(B))/k \label{eq:claim-1}\\
%  k1_C<1_{\boldA} - 1_{\boldB} & \Rightarrow  & 
%  \mu_i(C)<(\sum_{A\in\boldA}  \mu(A)-\sum_{B\in\boldB} \mu(B))/k\label{eq:claim-2}\\
%  k1_C>1_{\boldA} - 1_{\boldB} & \Rightarrow &  
%  \mu_e(C)>(\sum_{A\in\boldA}  \mu(A)-\sum_{B\in\boldB} \mu(B))/k\label{eq:claim-3}
%\end{eqnarray}

%\begin{quotation}
%\emph{Claim 6}:
%$\mu_e(C)>0$
%\end{quotation}

%\end{quotation}



%To prove claim 3  observe that $1_C\geq 1_A-1_A$\ for an arbitrary $A\in V$, so that 
%the set in (\ref{eq:muidef}) contains 
%$0=(\mu(A)-\mu(A))/1$. For the definition of $\mu_e$\ observe that 
%$W\subseteq V$, and $\sum_{w\in W}1_w\geq 1_C$. Thus, 
%the set in (\ref{eq:muedef}) contains at least the value
%$(\sum_{w\in W} 1_w)/1$. 

%Claim 4: $\mu_i(C)\geq 0$\ already follows from our observation for claim 3. For the
%second inequality let $k,\boldA,\boldB,k',\boldA',\boldB'$\ be such that
%$k1_C\leq 1_{\boldA}- 1_{\boldB}$, $k' 1_C\geq 1_{\boldA'}-1_{\boldB'}$. 
%Then
%\begin{displaymath}
%  k(1_{\boldA'}-1_{\boldB'})\leq k'(1_{\boldA}-1_{\boldB})
%\end{displaymath}
%and hence
%\begin{displaymath}
%  k 1_{\boldA'} + k' 1_{\boldB} \leq k 1_{\boldB'}+ k' 1_{\boldA}.
%\end{displaymath}
%With (\ref{eq:firstineq}) then 
%\begin{displaymath}
%  k\sum_{A'\in\boldA'}\mu(A') + k'\sum_{B\in\boldB}\mu(B)
%  \leq 
%  k\sum_{B'\in\boldB'}\mu(B') + k'\sum_{A\in\boldA}\mu(A),
%\end{displaymath}
%and finally
%\begin{equation}
%\label{eq:claim4-1}
%  (\sum_{A'\in\boldA'}\mu(A') - \sum_{B'\in\boldB'}\mu(B'))/k'
%  \leq
%  (\sum_{A\in\boldA}\mu(A) - \sum_{B\in\boldB}\mu(B))/k,
%\end{equation}
% which proves $\mu_i(C)\leq \mu_e(C)$. 


%Claim 5: 
%Let $k1_C= 1_{\boldA}-1_{\boldB}$\ and $k'1_C\geq 1_{\boldA'}-1_{\boldB'}$. 
%Exactly as in the proof of claim 4 we obtain the inequality (\ref{eq:claim4-1}).
%Hence, the supremum in (\ref{eq:muidef}) is attained for $k,\boldA,\boldB$, i.e.
%$\mu_i(C)=(\sum_{A\in\boldA} \mu(A)-\sum_{B\in\boldB}\mu(B))/k$.
%The result for $\mu_e(C)$\ is shown similarly.

%To prove (\ref{eq:claim-2}) and (\ref{eq:claim-3}) we first need to show the
%following: there exist $\hat{k},\hat{\boldA},\hat{\boldB}$, such that 
%$\mu_i(C)=(\sum_{A\in\hat{\boldA}} \mu(A)-\sum_{B\in\hat{\boldB}}\mu(B))/\hat{k}$, i.e. the supremum
%in (\ref{eq:muidef}) is always attained (and similarly the infimum in
%(\ref{eq:muedef})). For this, we reformulate the definition of $\mu_i(C)$\ 
%as the solution to a fractional integer programming problem: 
%the sequences 
%$\boldA,\boldB$\ are equivalently described by assigning integer coefficient
%$z_E$\ to every $E\in V$: if $z_E>0$, then $E$\ occurs $z_E$\ times in $\boldA$; if
%$z_E<0$, then $E$\ occurs $z_E$\ times in $\boldB$. If $z_E=0$, then
%$E$\ does not occur in $\boldA$\ or $\boldB$\ (note that without loss of generality
%we can assume that no $E$\ occurs both in $\boldA$\ and $\boldB$, as such double 
%occurrences would cancel both in the value $\sum_{A\in\boldA}\mu(A) - \sum_{B\in\boldB}\mu(B)$\ 
%and in the function $1_{\boldA}-1_{\boldB}$). Thus, the definition of 
%$\mu_i(C)$\ is also given by the following optimization problem in
%the integer variables $z_E\ (E\in V)$\ and $k$:
%\begin{align}
%   \makebox[25mm][l]{maximize} & \frac{\sum_{E\in V}z_E\mu(E)}{k} \label{eq:intopt1}\\
%   \makebox[25mm][l]{subject to} & k\geq 1 \label{eq:intopt2}\\
%   & \sum_{U\in E} z_E \leq k \hspace{4mm} (U\in C)\label{eq:intopt3}\\
%   & \sum_{U\in E} z_E \leq 0 \hspace{4mm} (U\not\in C)\label{eq:intopt4}
%\end{align}
%The set of admissible $z_E,k$\ is nonempty (e.g. $k=1$, $z_E=0\ (E\in V)$\ 
%are admissible). The convex hull in $\Rset^{1+\cardinal{V}}$\ of all admissible integer
%vectors then is a nonempty polyhedron $P$\ \cite[Theorem 16.1]{Schrijver86}. 
%The fractional linear function (\ref{eq:intopt1}) is maximized over $P$\ by all 
%points of some face $F$\ of $P$. $F$\  must contain an integer vector 
%$(\hat{k},(\hat{z}_E)_{E\in V})$, which defines the desired optimal 
%$\hat{k},\hat{\boldA},\hat{\boldB}$.


%Now let $k1_C < 1_{\boldA}-1_{\boldB}$.
%Then 
%$k(1_{\hat{\boldA}}-1_{\hat{\boldB}})<\hat{k}(1_{\boldA}-1_{\boldB})$. Again, as in the proof of 
%claim 4, we obtain (\ref{eq:claim4-1}), now with strict inequality, which proves
%(\ref{eq:claim-2}).


%Claim 6: This follows immediately from (\ref{eq:claim-3}) using 
%$1_C> 1_A-1_A$\ for an arbitrary $A\in V$.

%Resuming the construction of $\tilde{\mu}$, we can now extend $\mu$\ to a set function
%$\mu'$\ on $V\cup \{C\}$\ by defining
%\begin{displaymath}
%  \mu'(C):=(\mu_i(C)+\mu_e(C))/2.
%\end{displaymath}
%By claims 3,4 and 6 $\mu'$\ is well-defined and strictly positive. We have to show
%(\ref{eq:firstineq}) and (\ref{eq:secondineq}) for $\mu'$.
%For (\ref{eq:firstineq}) let $\boldA,\boldB\subseteq V\cup \{C\}$\ with 
%$1_{\boldA}=1_{\boldB}$. Without loss of generality we may assume that 
%$1_{\boldB}=k 1_C + 1_{\boldB'}$, such that neither $\boldA$\ nor $\boldB'$\ contain
%$C$. Then $k 1_C = 1_{\boldA}-1_{\boldB'}$, and by
%(\ref{eq:claim-1}): $\mu'(C)=(\sum_{A\in\boldA} \mu(A')-\sum_{B'\in\boldB'}\mu(B'))/k$.
%Thus
%\begin{equation}
%  \label{eq:local10}
%  \sum_{A\in\boldA'}\mu'(A)=\sum_{A\in\boldA'}\mu(A)
%  = k\mu'(C)+\sum_{B'\in\boldB'}\mu(B')
%  = \sum_{B\in\boldB}\mu'(B).
%\end{equation}

%For (\ref{eq:secondineq}) let $1_{\boldA}<k 1_C + 1_{\boldB'}$\ with 
%$\boldA,\boldB'\subseteq V$. Then 
%$\mu_e(C)>(\sum_{A\in\boldA} \mu(A')-\sum_{B'\in\boldB'}\mu(B'))/k$\ by
%(\ref{eq:claim-3}), and 
%$\mu_e(C)\geq(\sum_{A\in\boldA} \mu(A')-\sum_{B'\in\boldB'}\mu(B'))/k$\ by
%definition. Hence $\mu'(C)>(\sum_{A\in\boldA} \mu(A')-\sum_{B'\in\boldB'}\mu(B'))/k$,
%and (\ref{eq:secondineq}) follows in analogy to (\ref{eq:local10}).

%The case $1_{\boldA}=k 1_C + 1_{\boldA'}$\ with $\boldA',\boldB$\ not containing
%$C$\ is treated similarly, using (\ref{eq:claim-2}).

%\end{proofenv}


{\bf Theorem~\ref{theo:ccarchar}}
  The following are equivalent for a distribution $P$\ on
$\Omega(W)$:
\begin{description}
\item[(i)] $P$\ is induced by a robust \car\ Bernoulli model.
\item[(ii)] $P$\ is induced by a robust \ccar\ Bernoulli model.
\item[(iii)] $P$\ is induced by an honest Bernoulli model.
\item[(iv)] $P$\ is $d$-\ccar.
\end{description}

We begin with some measure theoretic preliminaries. Let ${\cal A}$\ be the 
product $\sigma$-algebra on $\boldGamma$\ generated by the powersets
$2^{\Gamma_i}$. The joint distribution $P(X,\boldG)$\ then is defined 
on the  product of $2^W$\ and ${\cal A}$. The $\sigma$-algebra ${\cal A}$\ is
generated by the \emph{cylinder sets} 
$(g^*_{1},g^*_{2},\ldots,g^*_{k})\times \times_{j>k}\Gamma_j$\ 
($k\geq 0$, $g^*_{h}\in \Gamma_h$\ for $h=1,\ldots,k$). The cylinder sets also 
are the basis for a topology ${\cal O}$\ on $\boldGamma$. The space
$(\boldGamma,{\cal O})$\ is compact (this can be seen directly, or by an
application of Tikhonov's theorem). It follows that every probability distribution
$P$\ on ${\cal A}$\ is \emph{regular}, especially for all $A\in {\cal A}$:
\begin{displaymath}
  P(A)=\inf \{P(O)\mid A\subseteq O\in {\cal O}\}
\end{displaymath}
(see e.g. \citeR[Prop. 7.2.3]{Cohn93}). Here and in the following we use
interchangeably the notation $P(A)$\ and $P(\boldG\in A)$. The former 
notation is sufficient for reasoning about probability distributions on 
${\cal A}$, the latter emphasizes the fact that we are always dealing with
distributions induced by the family $\boldG$\ of random variables.

\begin{lemmaenv}
\label{lem:separation}
  Let $P(\boldG)$\ be the joint distribution on ${\cal A}$\ of an independent family
$\boldG$. Let $A_1,A_2\in{\cal A}$\ with
$A_1\cap A_2=\emptyset$\ and $P(\boldG\in A_1)=P(\boldG\in A_2)>0$. 
Then there exists a joint 
distribution $\tilde{P}(\boldG)$\ with $P(\boldG)\equiv\tilde{P}(\boldG)$\ and
$\tilde{P}(\boldG\in A_1)\neq \tilde{P}(\boldG\in A_2)$. 
\end{lemmaenv}

\begin{proofenv}
  Let $p:=P(A_1)$. Let $\epsilon=p/2$\ and $O\in{\cal O}$\ such that 
$A_1\subseteq O$\ and $P(O)<p+\epsilon$. Using the disjointness of 
$A_1$\ and $A_2$\ one  obtains $P(A_1\mid O)>P(A_2\mid O)$. Since the cylinder sets 
are a basis for ${\cal O}$, we have $O=\cup_{i\geq 0} Z_i$\ for a countable 
family of  cylinders $Z_i$. It follows that also for some cylinder set 
$Z=(g^*_{1},g^*_{2},\ldots,g^*_{k})\times \times_{j>k}\Gamma_j$\ with
$P(Z)>0$:
$P(A_1\mid Z)>P(A_2\mid Z)$. Now let $\delta>0$\ and define for $h=1,\ldots,k$:
\begin{displaymath}
  \tilde{P}(G_h=g^*_h):=1-\delta;\hspace{4mm}
  \tilde{P}(G_h=g):=\delta ({P}(G_h=g)/\sum_{g':g'\neq g^*_h}P(G_h=g'))
  \hspace{2mm} (g\neq g^*_h)
\end{displaymath}
For $h\geq k+1$: $\tilde{P}(G_h):={P}(G_h)$. 
Then $P(\boldG)\equiv\tilde{P}(\boldG)$,
$\tilde{P}(A_1\mid Z)={P}(A_1\mid Z)$, $\tilde{P}(A_2\mid Z)={P}(A_2\mid Z)$, 
and therefore:
\begin{displaymath}
  \tilde{P}(A_1)\geq(1-\delta)^k P(A_1\mid Z),\hspace{4mm}
  \tilde{P}(A_2)\leq(1-\delta)^k P(A_2\mid Z)+ 1-(1-\delta)^k.
\end{displaymath}
For sufficiently small $\delta$\ this gives $\tilde{P}(A_1)>\tilde{P}(A_2)$.  
\end{proofenv}

\begin{proofofenv}{of Theorem~\ref{theo:ccarchar}}
For simplification we may assume that $P(x)>0$\ for all $x\in W$. This is 
justified by the observation that none of the conditions (i)-(iv) are 
affected by adding or deleting states with zero probability from $W$. 

  The implication (iv)$\Rightarrow$(ii) follows from Example~\ref{ex:mgroupeddatamodel}
by the observation that MGD models are robust \emph{d-ccar} Bernoulli models.
(ii)$\Rightarrow$(i) is trivial. We will show (i)$\Rightarrow$(iii) and
(iii)$\Rightarrow$(iv).

First assume (i), and let $(X,\boldG,f)$\ be a robust \car\ Bernoulli model inducing $P$. 
%Let $q_i$\ denote the success probability of $X_i$\ ($i\geq 1$), and 
%$Q$\ the joint distribution of the $X_i$\ ($i\geq 1$). 
For $x\in W$\ and $U\subseteq W$\ denote 
\begin{displaymath}
  A(x,U):=\{\boldg\in\boldGamma\mid f(x,\boldg)=U\}.
\end{displaymath}
The \emph{d-car} property of $P$\ is equivalent to 
\begin{equation}
  \label{eq:local200}
  P(\boldG\in A(x,U))=P(\boldG\in A(x',U)).
\end{equation}
for all $x,x'\in U$. 

Condition (\ref{eq:honestcond}) is equivalent to the condition that
$P(\boldG\in A(x,U)\setminus A(x',U))=0$\ for $x,x'\in U$. 
Assume otherwise. Then for  $A_1:=A(x,U)\setminus A(x',U)$,
$A_2:=A(x',U)\setminus A(x,U)$: $0<P(\boldG\in  A_1)=P(\boldG\in A_2)$. 
Applying Lemma~\ref{lem:separation} we obtain a Bernoulli model
$\tilde{P}(X,\boldG)=P(X)\tilde{P}(\boldG)$\ with 
$\tilde{P}(X,\boldG)\equiv {P}(X,\boldG)$\ and
$\tilde{P}(\boldG\in A_1)\neq\tilde{P}(\boldG\in A_2)$. Then also
$\tilde{P}(\boldG\in A(x,U))\neq \tilde{P}(\boldG\in A(x',U))$, so that
$\tilde{P}(X,\boldG)$\ is not \emph{d-car}, contradicting (i). 



(iii)$\Rightarrow$(iv): 
Let 
\begin{displaymath}
  \boldGamma^* := \bigcap_{\begin{array}{c}\scriptstyle x,x'\in W, U\subseteq W:\\ \scriptstyle x,x'\in U\end{array}}
    \{\boldg\mid f(x,\boldg)=U,x'\in U \Rightarrow f(x',\boldg)=U\}.
\end{displaymath}
Since the intersection is only over finitely many $x,x',U$, we obtain from (iii) that
$P(\boldG\in \bold\Gamma^*)=1$. For $U\subseteq W$\ define 
$A(U):=A(x,U)\cap\bold\Gamma^*$, where $x\in U$\ is arbitrary. By the 
definition of $\bold\Gamma^*$\ the definition of $A(U)$\ is independent
of the particular choice of $x$. Define an equivalence
relation $\sim$\ on $\bold\Gamma^*$\ via
\begin{equation}
  \label{eq:local210}
  \boldg\sim\boldg'\hspace{3mm}\Leftrightarrow\hspace{3mm}
  \forall U\subseteq W:\ \boldg\in A(U)\Leftrightarrow\boldg'\in A(U).
\end{equation}

This equivalence relation partitions $\bold\Gamma^*$\ into finitely many
equivalence classes $\bold\Gamma^*_1,\ldots,\bold\Gamma^*_k$. We show that for each 
$\bold\Gamma^*_i$\ and $\boldg\in \bold\Gamma^*_i$\ the system
\begin{equation}
  \label{eq:local220}
  {\cal W}_i:=\{U\mid \exists x\in W:\ f(x,\boldg)=U\}
\end{equation}
is a partition of $W$, and that the definition of ${\cal W}_i$\ does not 
depend on the choice of $\boldg$. The latter claim is immediate from the fact 
that for $\boldg\in\bold\Gamma^*$
\begin{equation}
  \label{eq:local230}
  f(x,\boldg)=U
  \hspace{3mm}\Leftrightarrow\hspace{3mm}
  \boldg\in A(U)\ \mbox{and}\ x\in U.
\end{equation}
For the first claim assume that $f(x,\boldg)=U,f(x',\boldg)=U'$\ 
with $U\neq U'$. In particular, $\boldg\in A(U)\cap A(U')$. 
Assume there exists $x''\in U\cap U'$. Then by (\ref{eq:local230}) we would
obtain both $f(x'',\boldg)=U$\ and $f(x'',\boldg)=U'$, a contradiction.
Hence, the sets $U$\ in the ${\cal W}_i$\ are pairwise disjoint. 
They also are a cover of $W$, because for every $x\in W$\ there exists
$U$\ with $x\in U=f(x,\boldg)$. 

We thus obtain that the given Bernoulli model is equivalent to the
multiple grouped data model defined by the partitions
${\cal W}_i$\ and parameters $\lambda_i:= P(\boldG\in \boldGamma_i^*)$. 
\end{proofofenv}

\bibliography{ref,mypubs}


\end{document}
