\newsubfloat{figure}

% \newsubfloat{figure}

% \RequirePackage{caption}
\RequirePackage{subcaption}

    \chapter{Preliminaries}
    \input{ch2_preliminaries}

    \input{ch2_preliminaries}

@Article{DBLP:journals/scp/BagnaraHZ08,

@Article{bagnara2008socp,

  groups    = {Tools},

  groups    = {Tools, Polyhedra, Octagons, Boxes},

  groups  = {KoAT},

@Book{alma2011,

@Book{billingsley2011,

  groups     = {KoAT},

}
@Misc{kraaikamp2005modern,
  author    = {C. Kraaikamp and F.M. Dekking and H.P. Lopuhaä and L.E. Meester},
  title     = {A Modern Introduction to Probability and Statistics Understanding Why and How},
  year      = {2005},
  doi       = {https://doi.org/10.1007/1-84628-168-7},
  file      = {Full Book:/home/paradyx/MA/literatur/kraaikamp2005modern.pdf:PDF},
  groups    = {Probability},
  publisher = {springer publication},
}
@Book{vanderbei2020lp,
  author    = {Robert J. Vanderbei},
  publisher = {Springer},
  title     = {Linear Programming Foundations and Extensions},
  year      = {2020},
  edition   = {5},
  isbn      = {978-3-030-39414-1},
  series    = {International Series in Operations Research and Management Science},
  volume    = {285},
  doi       = {https://doi.org/10.1007/978-3-030-39415-8},
  file      = {Full Book:/home/paradyx/MA/literatur/vanderbei2020lp.pdf:PDF},
  groups    = {Linear Programming},
  timestamp = {Mon, 22 Jul 2019 16:40:55 +0200},
}
@Book{pan2023lpcomputation,
  author    = {Ping{-}Qi Pan},
  publisher = {Springer},
  title     = {Linear Programming Computation, Second Edition},
  year      = {2023},
  isbn      = {978-981-19-0146-1},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  biburl    = {https://dblp.org/rec/books/sp/Pan23.bib},
  doi       = {10.1007/978-981-19-0147-8},
  file      = {Full Book:/home/paradyx/MA/literatur/pan2023lpcomputation.pdf:PDF},
  groups    = {Linear Programming},
  timestamp = {Mon, 16 Jan 2023 12:10:53 +0100},
  url       = {https://doi.org/10.1007/978-981-19-0147-8},
}
@Article{bagnara2005convexpolyhedron,
  author    = {Roberto Bagnara and Patricia M. Hill and Enea Zaffanella},
  journal   = {Formal Aspects Comput.},
  title     = {Not necessarily closed convex polyhedra and the double description method},
  year      = {2005},
  number    = {2},
  pages     = {222--257},
  volume    = {17},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  biburl    = {https://dblp.org/rec/journals/fac/BagnaraHZ05.bib},
  doi       = {10.1007/s00165-005-0061-1},
  file      = {:/home/paradyx/MA/literatur/bagnara2005convexpolyhedron.pdf:PDF},
  groups    = {Polyhedra, Octagons, Boxes},
  timestamp = {Mon, 09 May 2022 16:20:12 +0200},
  url       = {https://doi.org/10.1007/s00165-005-0061-1},

@InProceedings{mine2001wcre,
  author    = {Antoine Min{\'{e}}},
  booktitle = {Proceedings of the Eighth Working Conference on Reverse Engineering, WCRE'01, Stuttgart, Germany, October 2-5, 2001},
  title     = {The Octagon Abstract Domain},
  year      = {2001},
  editor    = {Elizabeth Burd and Peter Aiken and Rainer Koschke},
  pages     = {310},
  publisher = {{IEEE} Computer Society},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  biburl    = {https://dblp.org/rec/conf/wcre/Mine01.bib},
  doi       = {10.1109/WCRE.2001.957836},
  file      = {:/home/paradyx/MA/literatur/mine2001wcre.pdf:PDF},
  groups    = {Polyhedra, Octagons, Boxes},
  timestamp = {Fri, 24 Mar 2023 00:04:44 +0100},
  url       = {https://doi.org/10.1109/WCRE.2001.957836},
}
@Article{mine2007arxiv,
  author     = {Antoine Min{\'{e}}},
  journal    = {CoRR},
  title      = {The Octagon Abstract Domain},
  year       = {2007},
  volume     = {abs/cs/0703084},
  bibsource  = {dblp computer science bibliography, https://dblp.org},
  biburl     = {https://dblp.org/rec/journals/corr/abs-cs-0703084.bib},
  eprint     = {cs/0703084},
  eprinttype = {arXiv},
  file       = {:/home/paradyx/MA/literatur/mine2007arxiv.pdf:PDF},
  groups     = {Polyhedra, Octagons, Boxes},
  timestamp  = {Mon, 13 Aug 2018 16:47:22 +0200},
  url        = {http://arxiv.org/abs/cs/0703084},
}
@Article{mine2006hosc,
  author    = {Antoine Min{\'{e}}},
  journal   = {High. Order Symb. Comput.},
  title     = {The octagon abstract domain},
  year      = {2006},
  number    = {1},
  pages     = {31--100},
  volume    = {19},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  biburl    = {https://dblp.org/rec/journals/lisp/Mine06.bib},
  doi       = {10.1007/s10990-006-8609-1},
  file      = {:/home/paradyx/MA/literatur/mine2006hosc.pdf:PDF},
  groups    = {Polyhedra, Octagons, Boxes},
  timestamp = {Thu, 05 Mar 2020 12:04:59 +0100},
  url       = {https://doi.org/10.1007/s10990-006-8609-1},
}
@InProceedings{truchet2010synacs,
  author    = {Charlotte Truchet and Marie Pelleau and Fr{\'{e}}d{\'{e}}ric Benhamou},
  booktitle = {12th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, {SYNASC} 2010, Timisoara, Romania, 23-26 September 2010},
  title     = {Abstract Domains for Constraint Programming, with the Example of Octagons},
  year      = {2010},
  editor    = {Tetsuo Ida and Viorel Negru and Tudor Jebelean and Dana Petcu and Stephen M. Watt and Daniela Zaharie},
  pages     = {72--79},
  publisher = {{IEEE} Computer Society},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  biburl    = {https://dblp.org/rec/conf/synasc/TruchetPB10.bib},
  doi       = {10.1109/SYNASC.2010.69},
  groups    = {Polyhedra, Octagons, Boxes},
  timestamp = {Fri, 24 Mar 2023 00:01:58 +0100},
  url       = {https://doi.org/10.1109/SYNASC.2010.69},
}

1 StaticGroup:Complexity Tools\;0\;1\;0xb3e6e6ff\;\;\;;

1 StaticGroup:Complexity Tools\;0\;1\;0xb3e6e6ff\;\;\;;

1 StaticGroup:Linear Programming\;0\;1\;0x8066ccff\;\;\;;

1 StaticGroup:Polyhedra, Octagons, Boxes\;0\;1\;0x8a8a8aff\;\;\;;

$latexoption = "-shell-escape"

$latexoption = "-shell-escape -halt-on-error"

% TeX root = ../main.tex
\begin{tikzpicture}[
        scale=0.4,
        declare function={unif(\k,\n)=1/\n;}
    ]
    \begin{axis}[
        axis lines = left,
        xlabel = {$k$},
        ylabel = {$P(X=k)$},
        x label style={at={(axis description cs:1,0.1)},anchor=north},
        y label style={at={(axis description cs:-0.15,1)},rotate = -90,
        anchor=north},
        yticklabel style={
            /pgf/number format/fixed,
            % /pgf/number format/fixed zerofill,
            /pgf/number format/precision=2
        },
        ymin=0,
        % ymax=0.3,
        xmin=-0.5,
        xmax=8.5,
        samples at={2,...,7},
        xtick={0,1,...,8},
        % xtick={0,1},
        % ytick={0,0.1,...,0.3},
        ybar=0pt,
        bar width=1,
        bar shift=0pt,
        % font=\tiny
    ]
        \addplot[fill=rwth-50] {unif(x,5)};
    \end{axis}
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[
        scale=0.4,
    ]
    \begin{axis}[
        axis lines = left,
        xlabel = {$k$},
        ylabel = {$P(X=k)$},
        x label style={at={(axis description cs:1,0.1)},anchor=north},
        y label style={at={(axis description cs:-0.15,1)},rotate = -90,
        anchor=north},
        yticklabel style={
            /pgf/number format/fixed,
            % /pgf/number format/fixed zerofill,
            /pgf/number format/precision=2
        },
        ymin=0,
        ymax=0.45,
        xmin=-0.5,
        xmax=6.5,
        xtick={0,1,...,6},
        % ytick={0,0.1,...,0.3},
        ybar=0pt,
        bar width=1,
        bar shift=0pt,
        % font=\tiny
    ]
        % Hypergeom N=12 K=8 n=5
        % [0.         0.01010101 0.14141414 0.42424242 0.35353535 0.07070707]
        \addplot[fill=rwth-50] coordinates{
            (0,0.0)
            (1,0.01010101)
            (2,0.14141414)
            (3,0.42424242)
            (4,0.35353535)
            (5,0.07070707)
        };
        % Hypergeom N=20 K=8 n=10
        % 0.00035723 0.00952608 0.07501786 0.24005716 0.35008335 0.24005716
        %  0.07501786 0.00952608 0.00035723 0.         0.        
        % \addplot[fill=rwth-50] coordinates{
        %     (0, 0.00035723)
        %     (1, 0.00952608)
        %     (2, 0.07501786)
        %     (3, 0.24005716)
        %     (4, 0.35008335)
        %     (5, 0.24005716)
        %     (6, 0.07501786)
        %     (7, 0.00952608)
        %     (8, 0.00035723)
        %     (9, 0        )
        %     (10, 0       )
        % };
    \end{axis}
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[scale=0.4]
    \begin{axis}[
        axis lines = left,
        xlabel = {$k$},
        ylabel = {$P(X=k)$},
        x label style={at={(axis description cs:1,0.1)},anchor=north},
        y label style={at={(axis description cs:-0.15,1)},rotate = -90,
        anchor=north},
        ymax=0.45,
        yticklabel style={
            /pgf/number format/fixed,
            % /pgf/number format/fixed zerofill,
            /pgf/number format/precision=2
        },
        ymin=0,
        xmin=-0.5,
        xmax=11.5,
        xtick={0,1,...,11},
        % ytick={0,0.25,...,1},
        ybar=0pt,
        bar width=1,
        bar shift=0pt,
        % font=\tiny
    ]
        % Geometric p=0.4, up to r=11
        % [0.4        0.24       0.144      0.0864     0.05184    0.031104
        % 0.0186624  0.01119744 0.00671846 0.00403108 0.00241865 0.00145119]
        \addplot[fill=rwth-50] coordinates {
            (0, 0.4)
            (1, 0.24)
            (2, 0.144)
            (3, 0.0864)
            (4, 0.05184)
            (5, 0.031104)
            (6, 0.0186624)
            (7, 0.01119744)
            (8, 0.00671846)
            (9, 0.00403108)
            (10, 0.00241865)
            (11, 0.00145119)
        };
    \end{axis}
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[
        scale=0.4,
    ]
    \begin{axis}[
        axis lines = left,
        xlabel = {$k$},
        ylabel = {$P(X=k)$},
        x label style={at={(axis description cs:1,0.1)},anchor=north},
        y label style={at={(axis description cs:-0.15,1)},rotate = -90,
        anchor=north},
        yticklabel style={
            /pgf/number format/fixed,
            % /pgf/number format/fixed zerofill,
            /pgf/number format/precision=2
        },
        ymin=0,
        xmin=-0.5,
        xmax=9,
        xtick={0,1,...,8},
        ymax=0.3,
        ybar=0pt,
        bar width=1,
        bar shift=0pt,
        % font=\tiny
    ]
        % Binomial n=8 p=0.4
        % [0.01679616 0.08957952 0.20901888 0.27869184 0.2322432  0.12386304
        %  0.04128768 0.00786432 0.00065536]
        \addplot[fill=rwth-50] coordinates {
            (0, 0.01679616)
            (1, 0.08957952)
            (2, 0.20901888)
            (3, 0.27869184)
            (4, 0.2322432)
            (5, 0.12386304)
            (6, 0.04128768)
            (7, 0.00786432)
            (8, 0.00065536)
        };
    \end{axis}
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[
        scale=0.4,
    ]
    \begin{axis}[
        axis lines = left,
        xlabel = {$k$},
        ylabel = {$P(X=k)$},
        x label style={at={(axis description cs:1,0.1)},anchor=north},
        y label style={at={(axis description cs:-0.15,1)},rotate = -90,
        anchor=north},
        xmax=1.7,
        ymax=1,
        yticklabel style={
            /pgf/number format/fixed,
            % /pgf/number format/fixed zerofill,
            /pgf/number format/precision=2
        },
        ymin=0,
        xmin=-0.5,
        xtick={0,1},
        ytick={0,0.25,...,1},
        ybar=0pt,
        bar width=1,
        bar shift=0pt,
        % font=\tiny
    ]
        \addplot[fill=rwth-50] coordinates {(0,0.75)(1,0.25)};
    \end{axis}
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[scale=0.5]
    \begin{axis}[
        axis lines = center,
        axis on top,
        xmin=-3.3,
        xmax=3.3,
        ymin=0,
        ymax=5.3,
        y=1cm,
        x=1cm,
        ytick={-0,...,5},
        xtick={-3,...,3},
        xlabel = x,
        ylabel = y,
        font=\tiny
    ]
        \addplot [ name path = A, thick ] {x + 4};
        \addplot [ name path = B, thick ] {x + 1};
        \addplot [ name path = C, thick ] {-x + 4};
        \addplot [ name path = D, thick ] {-x + 1};
        \addplot[name path=top,draw=none] {5.3};
        \addplot[name path=bottom,draw=none] {0};
        \addplot[pattern=north west lines,pattern color=blue!30] fill
        between[of=A and top];
        \addplot[pattern=north west lines,pattern color=blue!30] fill
        between[of=C and top];
        \addplot[pattern=north west lines,pattern color=blue!30] fill
        between[of=B and bottom];
        \addplot[pattern=north west lines,pattern color=blue!30] fill
        between[of=D and bottom];
        \addplot[only marks,mark=o] coordinates {
                    (0, 4) 
            (-1, 3) (0, 3) (1, 3)
            (-1, 2) (0, 2) (1, 2)
                    (0, 1) 
        };
        \addplot[fill=red,fill opacity=0.20] fill between [of=B and bottom,soft
        clip={domain=0:1.5}];
        \addplot[fill=red,fill opacity=0.20] fill between [of=D and bottom,soft
        clip={domain=-1.5:0}];
    \end{axis} 
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[scale=0.5]
    \begin{axis}[
        axis lines = center,
        axis on top,
        xmin=-3.3,
        xmax=3.3,
        ymin=-3.3,
        ymax=3.3,
        y=1cm,
        x=1cm,
        ytick={-3,...,3},
        xtick={-3,...,3},
        xlabel = x,
        ylabel = y,
        font=\tiny
    ]
        \addplot [
            % domain=-3:3,
            name path = A,
            thick,
            % pattern=north east lines,
        ] {0.5*x + 1};
        \addplot[name path=C,draw=none] {3.3};
        \addplot [
            % domain={-1.65:3},
            name path = B,
            thick,
            % pattern=north east lines,
        ] {0.5*x*x-2};
        \addplot[name path=D,draw=none] {-3.3};
        \addplot[pattern=north west lines,pattern color=blue!30] fill between[of=A and C];
        \addplot[pattern=north east lines,pattern color=red!30] fill between[of=B and D];
        \addplot[only marks,mark=o] coordinates {
                                                       (2,  2)
                                       (0,  1) (1,  1) (2,  1)        
                              (-1,  0) (0,  0) (1,  0)                
                              (-1, -1) (0, -1) (1, -1)                
        };
    \end{axis} 
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[scale=0.5]
    \begin{axis}[
        axis lines = center,
        axis on top,
        xmin=-3.3,
        xmax=3.3,
        ymin=-3.3,
        ymax=3.3,
        y=1cm,
        x=1cm,
        ytick={-3,...,3},
        xtick={-3,...,3},
        xlabel = x,
        ylabel = y,
        font=\tiny
    ]
        \addplot [
            % domain={-1.65:3},
            name path = B,
            thick,
            % pattern=north east lines,
        ] {0.5*x*x-2};
        \addplot[name path=D,draw=none] {-3.3};
        \addplot[pattern=north east lines,pattern color=red!30] fill between[of=B and D];
        \addplot[only marks,mark=o] coordinates {
            (-3,  3) (-2,  3) (-1,  3) (0,  3) (1,  3) (2,  3) (3,  3)
                     (-2,  2) (-1,  2) (0,  2) (1,  2) (2,  2)        
                     (-2,  1) (-1,  1) (0,  1) (1,  1) (2,  1)        
                     (-2,  1) (-1,  1) (0,  1) (1,  1) (2,  1)        
                              (-1,  0) (0,  0) (1,  0)                
                              (-1, -1) (0, -1) (1, -1)                
        };
    \end{axis} 
\end{tikzpicture}

% TeX root = ../main.tex
\begin{tikzpicture}[scale=0.5]
    \begin{axis}[
        axis lines = center,
        axis on top,
        xmin=-3.3,
        xmax=3.3,
        ymin=-3.3,
        ymax=3.3,
        y=1cm,
        x=1cm,
        ytick={-3,...,3},
        xtick={-3,...,3},
        xlabel = x,
        ylabel = y,
        font=\tiny
    ]
        \addplot [
            % domain=-3:3,
            name path = A,
            thick,
            % pattern=north east lines,
        ] {0.5*x + 1};
        \addplot[name path=C,draw=none] {3.3};
        \addplot[pattern=north west lines,pattern color=blue!30] fill between[of=A and C];
        \addplot[only marks,mark=o] coordinates {
                                                      (2,  2) (3,  2)
                                      (0,  1) (1,  1) (2,  1) (3,  1)
                    (-2, -0) (-1, -0) (0, -0) (1, -0) (2, -0) (3, -0)
            (-3,-1) (-2, -1) (-1, -1) (0, -1) (1, -1) (2, -1) (3, -1)
            (-3,-2) (-2, -2) (-1, -2) (0, -2) (1, -2) (2, -2) (3, -2)
            (-3,-3) (-2, -3) (-1, -3) (0, -3) (1, -3) (2, -3) (3, -3)
        };
        \addplot[only marks,mark=o,red!80] coordinates { (0, -2) };
    \end{axis} 
\end{tikzpicture}

        \subbottom[Program]{

        \begin{subcaptiongroup}
            \subcaptionlistentry{Program}

        }
        \subbottom[Extract of the evaluation tree]{

            \subcaptionlistentry{Extract of the evaluation tree}

        }

        \end{subcaptiongroup}
        % \subbottom[Program]{
        %     \input{figures/ch3_example1_program.tex}
        % }
        % \subbottom[Extract of the evaluation tree]{
        %     \input{figures/ch3_example1_tree.tex}
        % }

        \subbottom[Program]{

        \begin{subcaptiongroup}
            \subcaptionlistentry{Program}

        }
        \subbottom[Extract of the evaluation tree]{

            \subcaptionlistentry{Extract of the evaluation tree}

        }
        \caption{Foo}

        \end{subcaptiongroup}
        % \subbottom[Program]{
        %     \input{figures/ch3_example2_program.tex}
        % }
        % \subbottom[Extract of the evaluation tree]{
        %     \input{figures/ch3_example2_tree.tex}
        % }
        % \caption{Foo}

\label{ch:preliminaries}
\begin{comment}
    # Textbautsteine
    --- 
    For random program variables in this thesis, $\Omega$ will be the set of
    integers and $\mathcal{F}$ the maximal $\sigma$-field in $\Omega$, the
    power-set $2^\Omega$. However since the program variables are chosen at
    random, a specific path over a given program can also be considered a random
    event in the probability space and hence be considered as a ransom variable.
    In this case $\Omega$ is the set of all runs $\mathcal{Runs}$. The exact
    definition will be introduced later on in \Sref{}.
    ---
    \begin{definition}[Linear Constraints] 
        Let $V$ be a fixed set of integer
        Variables $\{x_1, x_2, \dots, n\} $. A linear constraint is defined as $\psi
        = a_0 + a_1 x_1 + \dots + a_n x_n \diamond 0$ where $a_i \in \mathbb{N}$ are
        integer coefficients, $x_i \in V$ are variables and $\diamond \in \{>, <, 
        \geq, \leq, =\}$. \end{definition}

\section{Preliminaries}\label{sec:preliminaries}

    \begin{definition}[Assignment] 
        An assignment $\sigma : V \mapsto \mathbb{Z}$ assigns an integer value to
        each variable in $V$. $\sigma$ is a solution for a linear constraint $\psi$
    \end{definition} \
    Common operations can be defined over probability distributions as well, which
    will be very handy in probabilistic integer programs. Given two probability
    distributions $p$, and $q$, the following operations are defined:
    \begin{equation*}
        p \diamond q (x) = \sum_{\substack{i,j \in \Z \\ i \diamond j = x}} p(i)
        \cdot q(i) \hspace{1cm} \with \diamond \in \{+, \cdot\}
    \end{equation*}
    \todo{more operators?}
    In the context of this thesis the discrete bounded distributions will be used to
    describe the possible values of a variable. They can be used as if they were
    non-probabilistic values, for exymple and 
    It can be used inside the 
    A note non-probabilistic (fixed) value $k$ is equivalent to a distribution which
    assignes the probability $1$ to this fixed value $k$ and $0$ to every other
    value.
    program itself during assignments when setting a new value to a variable or 
    during analysis to describe the possible values of the variables at a certain
    configuration. 
    \[
        p_k(x) = \begin{cases} 
            1, & x = k \\
            0, & \text{otherwise}
        \end{cases}
    \]
\end{comment}

\newcommand{\R}[0]{\mathbb{R}} % real numbers

\subsection{Constraints}

\section{Constraints}

        \subbottom[Formula $\varphi_1$]{
            \centering

        \begin{subcaptiongroup}
            \subcaptionlistentry{Formula $\varphi_1$}

        }
        \subbottom[Formula $\varphi_2$]{
            \centering

            \subcaptionlistentry{Formula $\varphi_2$}

        }
        \subbottom[Formula $\varphi_3 = \varphi_1 \land \varphi_2$]{
            \centering

            \subcaptionlistentry{Formula $\varphi_3 = \varphi_1 \land \varphi_2$}

        }

        \end{subcaptiongroup}
        % \subbottom[Formula $\varphi_1$]{
        %     \centering
        %     \input{figures/ch1_example1_phi1}
        % }
        % \subbottom[Formula $\varphi_2$]{
        %     \centering
        %     \input{figures/ch1_example1_phi2}
        % }
        % \subbottom[Formula $\varphi_3 = \varphi_1 \land \varphi_2$]{
        %     \centering
        %     \input{figures/ch1_example1_phi3}
        % }

\subsection{Convex Polyhedron}\label{sec:polyhedron}

% \subsection{Convex Polyhedron}\label{sec:polyhedron}

\subsection{Probability}

\section{Probability}

definitions from \cite{alma991005910089706448}. For additional information we
will refer to the literature. 

definitions from \cite{billingsley2011}. For additional information we
will refer to the literature.\cite{kraaikamp2005modern, billingsley2011}

\cite{alma991005910089706448}

% For random program variables in this thesis, $\Omega$ will be the set of
% integers and $\mathcal{F}$ the maximal $\sigma$-field in $\Omega$, the power-set
% $2^\Omega$. However since the program variables are chosen at random, a specific
% path over a given program can also be considered a random event in the
% probability space and hence be considered as a ransom variable. In this case
% $\Omega$ is the set of all runs $\mathcal{Runs}$. The exact definition will be
% introduced later on in \Sref{}.

The concept of random variables is not to be confused with program variables or
variables in formulas. Colloquially, a random variable maps the results of a
probabilistic event $\omega$ to a real value, or, the value of the random
variable depends on the outcome of a probabilistic event.

The concept of random variables is not to be confused with program
variables or variables in formulas. Random variables assign a probability
to an event of a probability space, whereas variables in formulas can be bound
to a value by an assignment or existentially quantified. 

    A random variable on a probability space $(\Omega, \F, \P)$ 

    A random variable on a probability space $(\Omega, \F, P)$ is a function $X
    : \Omega \rightarrow \R$ with $\set{\omega}{X(\omega) = x} \in \F$ for every
    $x \in \R$. 

In the following, we will only consider discrete random variables $X : \Omega
\rightarrow \Z$ with countably (but possibly infinitely) many possible results,
since only discrete random variables are relevant for this thesis.

A discrete bounded probability distribution gives a probability to every
possible integer and can be seen as a function $q: \Z \mapsto [0,1]$ where all 
values of $q$ add up to $1$, that is $\sum_{x\in\Z} q(x) = 1$.

The distribution of a variable is a way of describing a random variable and the
underlying probability space. In case of discrete random variables the are
sufficient to fully describe them. The underlying event space $\Omega$ becomes
irrelevant at this point, as the specific events and their probabilities are not
important to the outcome of the random variable, as long as the probability of
the outcome is fully defined.

\begin{definition}[Linear Constraints] 
    Let $V$ be a fixed set of integer
    Variables $\{x_1, x_2, \dots, n\} $. A linear constraint is defined as $\psi
    = a_0 + a_1 x_1 + \dots + a_n x_n \diamond 0$ where $a_i \in \mathbb{N}$ are
    integer coefficients, $x_i \in V$ are variables and $\diamond \in \{>, <, 
    \geq, \leq, =\}$. \end{definition}

\begin{definition}[Distribution of a random variable]
    Let $X$ be a discrete random variable. The distribution is describe by the
    probability measure $\mu: \Z \rightarrow \R$ with
    \begin{align}
        \mu(A) = P(\set{\omega \in \Omega}{X(\omega) \in A})
    \end{align}
\end{definition}

\begin{definition}[Assignment] 
    An assignment $\sigma : V \mapsto \mathbb{Z}$ assigns an integer value to
    each variable in $V$. $\sigma$ is a solution for a linear constraint $\psi$
\end{definition} \

The probability of a single value is well defined by the distribution as
follows: 
\begin{align}
    P(X=r) = \mu(\{r\}) = P(\set{\omega \in \Omega}{X(\omega) = r})
\end{align}

Common operations can be defined over probability distributions as well, which
will be very handy in probabilistic integer programs. Given two probability
distributions $p$, and $q$, the following operations are defined:
\begin{equation*}
    p \diamond q (x) = \sum_{\substack{i,j \in \Z \\ i \diamond j = x}} p(i)
    \cdot q(i) \hspace{1cm} \with \diamond \in \{+, \cdot\}
\end{equation*}
\todo{more operators?}

\begin{definition}[Support]
    For a random variable with a distribution $\mu$, the support is smallest
    Borel-set $S$ for which $\mu(S) = 1$. \todo{why borel set?} Discrete random
    variables have a countable support $S = \{S_1, S_2, \dots\}$.
    \begin{align}
        \text{supp}(\mu) = \set{x \in \N}{P(X = x) > 0}
    \end{align}
\end{definition}

In the context of this thesis the discrete bounded distributions will be used to
describe the possible values of a variable. They can be used as if they were
non-probabilistic values, for exymple and 
It can be used inside the 
A note non-probabilistic (fixed) value $k$ is equivalent to a distribution which
assignes the probability $1$ to this fixed value $k$ and $0$ to every other
value.

There are many common probability distributions. \gls{koat} uses five of them,
the Bernoulli, Uniform, Geometric, Hypergeometric and Binomial distributions.
They will be briefly introduced in this section, following the definitions
from \cite{kraaikamp2005modern}. Examples for the various probability
distributions are displayed in \fref{fig:distributions}.

program itself during assignments when setting a new value to a variable or 
during analysis to describe the possible values of the variables at a certain
configuration. 

\subsection{Bernoulli Distribution}\label{sec:bernoulli}
The Bernoulli distribution is a distribution with two possible outcomes: $1$ and $0$. For
example decided by a coin-flip. 
\begin{definition}[Bernoulli Distribution]
    A discrete random variable $X$ follows a \textit{Bernoulli distribution}
    parameterized by $p \in [0,1]$ if its probability is given by $P(X=1) = p$
    and $P(X=0) = 1-p$.
\end{definition}

\[
    p_k(x) = \begin{cases} 
        1, & x = k \\
        0, & \text{otherwise}

The support of a Bernoulli Distribution is as follows:
\begin{align}
    \text{supp}(\textsc{Bern}(p)) = \begin{cases}
        \{0\} & p = 0 \\
        \{0\} & p = 1 \\
        \{0, 1\} & \text{otherwise}

\]

\end{align}

The resulting 

\subsection{Uniform Distribution}\label{sec:uniform}
The uniform distribution is a distribution where every value in a certain range
has the same probability. 
\begin{definition}
    A discrete random variable $X$ follows a \textit{discrete uniform
    distribution} on the interval $[a, b]$, if its probability is given by 
    \begin{align}
        P(X=k) &= \begin{cases}
            \frac{1}{b-a} & \text{if} , a \leq k \leq b \\
            0 & \text{otherwise}
        \end{cases} & \text{for } k\in\N
    \end{align}
\end{definition}
The support of a uniform distribution is as follows: 
\begin{align}
    \text{supp}(\textsc{Unif}(a, b)) = \{a, a+1, \dots, b-1, b\}
\end{align}
\subsection{Geometric distribution}
The geometric distribution is related to the Bernoulli distribution. A series of
independent Bernoulli events is repeated until a false result is encountered.
The number of repetition is the result to the geometric distribution. 
\begin{definition}
    A discrete random variable $X$ follows a \textit{geometric distribution}
    parameterized by $p$ (the probability of the repeated Bernoulli event) with
    $0 < p \leq 1$, if its probability is given by 
    \begin{align}
        P(X=k)&=(1-p)^{k-1}p & \text{for } k = 1, 2, \dots
    \end{align}
\end{definition}
The support of a geometric distribution is as follows:
\begin{align}
    \text{supp}(\textsc{Geom}(p)) = \N^+
\end{align}
\subsection{Hypergeometric Distribution}
The hypergeometric distribution describes counting the number of successes when
sampling from population with a certain number of successes without putting
back. 
\begin{definition}[Hypergeometric Distribution]
    A discrete random variable $X$ follows a \textit{hypergeometric
    distribution} with a population of size $N$, $K < N$ successes therein, and
    $n < N$ samples, if its probability is given by
    \begin{align}
        P(X=k) &= \frac{\binom{K}{k} \binom{N-K}{n-k}}{\binom{N}{n}} & \text{for
        } k = 0, \dots, n
    \end{align}
\end{definition}

The support of a hypergeometric distribution is as follows: \todo{elaborate}
\begin{align}
    \text{supp}(\textsc{Hyper}(N, K, n)) = \{\max(0, n+K-N), \dots, \min (n, K)\}
\end{align}
\subsection{Binomial Distribution}
The binomial distribution similar to the geometric distribution except that the
number of successes of repeated independent Bernoulli events is counted. 
Or (\enquote{with putting back}). 
\begin{definition}[Binomial Distribution]
    A discrete random variable $X$ follows a \textit{binomial distribution} with
    $n$ Bernoulli events of a probability $p$, with $0 < p < 1$, if its
    probability is given by
    \begin{align}
        P(X=k)&=\binom{n}{k} p^k (1-p)^{n-k} & \text{for } k = 0,\dots,n
    \end{align}
\end{definition}
The support of a binomial distribution is as follows:
\begin{align}
    \text{supp}(\textsc{Binom}(n, p))=\{0,\dots,n\}
\end{align}
\begin{figure}
    \centering
    \begin{subcaptionblock}[t]{0.3\textwidth}
        \centering
        \input{figures/ch2_distributions_bern}
        \caption{Bernoulli $p = 0.25$}
    \end{subcaptionblock}
    \begin{subcaptionblock}[t]{.3\textwidth}
        \centering
        \input{figures/ch2_distributions_unif}
        \caption{Uniform $a = 2, b=6$}
    \end{subcaptionblock}
    \begin{subcaptionblock}[t]{.3\textwidth}
        \centering
        \input{figures/ch2_distributions_geom}
        \caption{Geometric $p = 0.4$}
    \end{subcaptionblock}
    \begin{subcaptionblock}[t]{.35\textwidth}
        \input{figures/ch2_distributions_hyper}
        \caption{Hypergeometric $N=12,$ \\$K=8, n=5$}
    \end{subcaptionblock}
    \begin{subcaptionblock}[t]{.35\textwidth}
        \centering
        \input{figures/ch2_distributions_bino}
        \caption{Binomial $p=0.4, n=8$}
    \end{subcaptionblock}
    \caption{Examples of common probability distributions. \label{fig:distributions}}
\end{figure}

\todo
\example{}

\todo{example}