\documentstyle[IEEEtran]{article}

\bibliographystyle{unsrt}
\setlength{\floatsep}{1in}        
\setlength{\textfloatsep}{.5in}   
\setlength{\intextsep}{.25in}   
%\renewcommand{\topfraction}{1}   
%\renewcommand{\bottomfraction}{1}
%\renewcommand{\textfraction}{0}  
%\setlength{\topmargin}{-.5in}
%\setlength{\topmargin}{-.5in}
%\setlength{\textheight}{10in}
%\setlength{\evensidemargin}{0in}
%\setlength{\oddsidemargin}{0in}
%\setlength{\textwidth}{6.5in}
\newcommand{\comment}[1]{}
\newcommand{\op}[0]{\:\frame{$op$}\:}  
\newcommand{\OP}[0]{\:\frame{$OP$}\:}  
\newcommand{\xref}[1]{ \hspace*{\fill}\mbox{\sf [#1]}} %ForReferences
\newcommand{\C}[1]{\begin{tabular}{c}#1\end{tabular}}
\newcommand{\W}[0]{\begin{tabular}{@{}l}interval\\probability\end{tabular}}
\newcommand{\head}[0]{$\!\!\!>$}

 \author{Hang Cheng and Daniel Berleant}

 \title{A Software Tool for Automatically Verified Reasoning with
\\Intervals and Probability Distributions}

 \date{}
 
\begin{document}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ }



\maketitle

\input{psfig}

 \auffil{The authors are with the Dept. of Computer Systems
Engineering, University of Arkansas, Fayetteville, AR 72701. Contact:
djb@engr.uark.edu~.}

\sloppy

\begin{abstract}
This work reports a software tool for performing automatically
verified arithmetic operations on independent operands when these
operands are intervals, are probability distribution functions, or one
operand is an interval and the other is a distribution. Because our
histogram based representation can express both intervals and
distributions, the algorithms do not need to distinguish between
intervals and distributions in their operation. While our previous
work (Berleant 1993) discussed concepts and algorithms but did not
emphasize computer implementations, here we emphasize a PC-based
calculating tool that implements the algorithms, interacts with the
user via a graphical user interface, and saves, retrieves, and prints
the results of its calculations.
\end{abstract}
\fussy

 \section{Introduction to the Representation} 

We take an interval to be an incompletely specified description of
some value such that there is a probability of one that the actual but
unknown value falls within that interval. A probability distribution
function may be either a probability density function (PDF) or its
integral, a cumulative distribution function (CDF). Thus (excepting
nontypical cases, which we do not address) the same distribution
function can be described as either a PDF or a CDF, a CDF is the
integral of a corresponding PDF, and a PDF is the derivative of a
corresponding CDF. 

Since the interval representation of value does not assume any
particular distribution of probability mass within the interval, the
interval representation is consistent with any cumulative distribution
whose value is zero below the interval and one above it. To represent
the interval using CDF's, we determine upper and lower CDF's which
together bound the space of CDF's consistent with the interval. These
two most extreme CDF's are the CDF that rises faster than any other
CDF consistent with the interval, and the CDF that rises slower than
any other CDF consistent with the interval. The CDF that rises fastest
is obviously the one corresponding to the situation in which the
variable's value is certainly no higher than the interval's low bound
(and can't be lower than the interval's low bound because we assume it
lies within the interval with probability one). Likewise, the CDF that
rises slowest is obviously the one corresponding to the situation in
which the variable's value is certainly equal to the interval's high
bound. The interval is therefore representable as a family of CDF's
whose two bounding CDF's each have one ``step.'' Figure 1 shows the
interval $[0,1]$ and its representation as a bounded family of CDF's.

\centerline{ \psfig{figure=interval.ps,width=3in,silent=}}
\centerline{ \psfig{figure=cdf.ps,width=3in,silent=}}
Figure 1: An interval and its representation as two CDF's bounding a family of CDF's.\\
--------------------------------------------

Some other CDF's may be represented using multiple steps. A CDF
corresponding to a set of sample values, for example, would have one
step for each distinct sample value (Figure 2).\\

 \centerline{\psfig{figure=samples.ps,width=2in,silent=}}
Figure 2: A CDF corresponding to a set of sample values.\\
--------------------------------------------

 Many CDF's do not have a stepwise form. For example, many are smooth
curves. Our stepwise representation captures these CDF's correctly, by
bounding them from above and below with stepwise CDF's that we can
represent. Of course, while this method of representing non-stepwise
CDF's is correct in that it does not introduce incorrect
approximations, it does lose information due to its use of bounding
CDF's that are consistent with other CDF's besides the one they are
generated to represent. The user generates these CDF bounds
interactively, using a graphical histogram editor to edit a PDF-like
histogram which is automatically integrated into bounding CDF's: each
bar of the histogram consists of an interval and a corresponding
probability, and is treated analogously to the interval whose
integration was described previously. (Figure 3 shows a user-generated
histogram and its corresponding CDF bounds.)

 \centerline{\psfig{figure=hist.ps,width=3in,silent=}}
 \centerline{ \psfig{figure=histcdf.ps,width=3in,silent=}}
Figure 3: A histogram edited by a user and its corresponding CDF bounds.\\
--------------------------------------------

Berleant (1993) describes in more detail how a histogram can correctly
(although with information loss) represent a smooth PDF curve; the
integral of the histogram forms stepwise CDF's bounding the smooth CDF
corresponding to the smooth PDF.

Not all pairs of bounding stepwise CDF's can be used by our
algorithms. A pair of bounding CDF's must correspond to the integral
of a set of intervals, each of which is associated with its
probability.  While intervals in those sets can overlap or subsume one
another, the integrals are still generated analogously to the way a
single interval was integrated into single-step CDF bounds (Figure 1)
and a histogram was integrated into a multi-step CDF bounds (Figure
2).  The common approach to integrating intervals, histograms, and
sets of possibly overlapping intervals is due to the fact that each is
a set of intervals and associated probability masses.

\begin{quote}{\it the underlying representation of CDF bounds in our
system is a set of intervals and their associated probability
masses. This set of intervals we call an
\underline{intermediate distribution.}}
 \end{quote}

While a histogram generated by a user corresponds to a set of
non-overlapping intervals and their probability masses, the result of
an arithmetic operation often produces a set of intervals that
contains overlaps, and this set may in turn be used as an operand in
further arithmetic operations.

 An intermediate distribution represents stepwise CDF's that bound a
family of CDF's. Obviously other members of that family of CDF's need
not themselves be stepwise. Therefore, other than the fact that a CDF
to be provided with containing CDF bounds must have values of zero
below a known finite value and one above a known finite value,
arbitrary CDF's can be provided with stepwise bounds. The intermediate
distribution corresponding to these bounds therefore can represent
various CDF's in an automatically verified fashion, though usually
with information loss. Therefore they can also represent PDF's and
their histogram based discretizations correctly. Future work is needed
to extend the representation to handle CDF's whose curves reach zero
or one asymptotically.

\section{Introduction to Arithmetic Operations}

The algorithmic framework for performing an arithmetic operation on
operands that are intermediate distributions is exemplified in Figure
4.  A fuller description of the algorithms is given in Berleant
(1993). Related algorithms appeared beginning in 1968 (Ingram et al.),
however these algorithms were not automatically verifying. An approach
to using CDF bounds in computer systems administration appears in Post
and Diltz (1986) under the rubric of another related field called {\bf
stochastic dominance,} which recognizes the usefulness of bounded
families of CDF's. We have not been able to find work by others
discussing automatically verified operations where one operand is an
interval and the other is a CDF.  A fuller review of related work
appears in Berleant (1993).

\section{A Software Tool}

A personal computer based calculating tool for doing automatically
verified arithmetic operations on operands each of which may be either
an interval or a CDF has been written. The tool allows the user to
specify operands as histograms. These histograms, as well as the
results of operations, are represented internally as intermediate
distributions. Sets of exact numbers may be read in and are also
represented internally as intermediate distributions (whose intervals
have equal low and high bounds). All of these may be displayed
graphically as CDF families (note that sets of exact numbers
correspond to stepwise CDF's and hence can be bounded above and below
with the same stepwise CDF). All of these may also be displayed
graphically as histograms representing discretized PDF curves which
are in most cases approximate, when this is desired by the user for
intuition or convenience.  Tables of intervals and their associated
probabilities, coding intermediate distributions directly, may be
printed out on paper.

Addition, subtraction, multiplication, and division are currently
implemented. Several of these operations can be done in sequence using
a primitive batch command facility.

Our software is available at no charge (for non-commercial purposes)
from the authors.

\section{Conclusion}

Our previous work (Berleant 1993) described how automatically verified
arithmetic operations may be carried out on intervals and CDF's. The
present work reports a computer tool with graphical user interface
capabilities for allowing users to specify operands as intervals and
CDF's and allowing them to perform automatically verified arithmetic
operations on them. An important next stage in this research is to
find applications for the techniques in order to demonstrate practical
use of the tool and its underlying ideas.

\section{Acknowledgements}

We thank Dan Layne for originally suggesting the interval mathematics
forums.

\begin{thebibliography}{99}

 \bibitem{Berleant93}
 Berleant, D., Automatically Verified Reasoning with Both
Intervals and Probability Density Functions.  {\it Interval
Computations} 1993 No. 2, pp.~48--70.

\bibitem{Ingrametal68} G. E. Ingram, E. L. Welker, and C. R. Herrmann,
{\it Designing for Reliability Based on Probabilistic Modeling Using
Remote Access Computer Systems,} Proceedings 7th Reliability and
Maintainability Conference, American Society of Mechanical Engineers,
1968, pp.~492--500.

\bibitem{PostandDiltz86} G. V. Post and J. D. Diltz, {\it A
Stochastic Dominance Approach to Risk Analysis of Computer Systems,}
Management Information Systems Quarterly, Vol. 10, No. 4, Dec. 1986,
pp.~363--375.

\end{thebibliography}

\newpage\onecolumn

\centerline{ \psfig{figure=a.ps,width=3in,silent=} \psfig{figure=b.ps,width=3in,silent=}}
The left histogram $X$ corresponds to the intermediate distribution $\{p([1,2])=\frac{1}{2}, p([2,4])=\frac{1}{2}\}$\\
The right histogram $Y$ corresponds to the intermediate distribution $\{p([2,3])=\frac{1}{4},p([3,4])=\frac{1}{2},p([4,5])=\frac{1}{4}\}$\\
Multiplying their intermediate distributions leads to a Cartesion product:\\
 \begin{center}
{\small \begin{tabular}{c|l|c|c|c|}
\begin{tabular}{@{}c@{}}Cartesian\\product\\term \#\end{tabular}
              & \begin{tabular}{@{}c@{}} \end{tabular}
                            & \begin{tabular}{@{}c@{}}Operand 1\\$(X_i)$\end{tabular}
                                       & \begin{tabular}{@{}c@{}}Operand 2\\$(Y_j)$\end{tabular}
                                                 & \begin{tabular}{@{}c@{}}Resulting\\intermediate\\distribution\\elements\end{tabular}\\\hline
    \C{\#1}   & \W & \C{$[1,2]$\\$1/2$} & \C{$[2,3]$\\$1/4$} & \C{$[2,6]$\\$1/8$}  \\ \hline
    \C{\#2}   & \W & \C{$[1,2]$\\$1/2$} & \C{$[3,4]$\\$1/2$} & \C{$[3,8]$\\$1/4$}  \\ \hline
    \C{\#3}   & \W & \C{$[1,2]$\\$1/2$} & \C{$[4,5]$\\$1/4$} & \C{$[4,10]$\\$1/8$} \\ \hline
    \C{\#4}   & \W & \C{$[2,4]$\\$1/2$} & \C{$[2,3]$\\$1/4$} & \C{$[4,12]$\\$1/8$} \\ \hline
    \C{\#5}   & \W & \C{$[2,4]$\\$1/2$} & \C{$[3,4]$\\$1/2$} & \C{$[6,16]$\\$1/4$} \\ \hline
    \C{\#6}   & \W & \C{$[2,4]$\\$1/2$} & \C{$[4,5]$\\$1/4$} & \C{$[8,20]$\\$1/8$} \\ \hline
 \end{tabular}
} \end{center}
Integrating the resulting intermediate distribution above produces the curves below $(\downarrow)$.\\
\centerline{\psfig{figure=c.ps,width=3in,silent=}}\\
Figure 4: Multiplying two operands. At top, the user creates two
histograms $X$ and $Y$ using a graphical editor. The Cartesian product 
of the intermediate distributions corresponding to these histograms
is then used to calculate the members of the intermediate distribution of 
the answer, whose CDF bounds are shown at bottom.\\

\end{document}



