# Guidelines for Experimental Algorithmics:
## 7 Evaluating Results with Statistical Analysis
### Bayesian Inference  
Bayesian statistics defines the probability of an experimental outcome as the _uncertainty of knowledge about it_. [PERSON]'s theorem gives a formal way to update probabilities on new observations. In its simplest form for discrete events and hypotheses, it can be given as:  
\[P\left(H_{1}|\text{A}\right)=\frac{P\left(\text{A}|H_{1}\right)P\left(H_{1} \right)}{P\left(\text{A}\right)} \tag{9}\]  
When observing outcome \(A\), the probability of hypothesis \(H_{1}\) is proportional to the probability of \(A\) conditioned on \(H_{1}\) multiplied by the _prior probability_\(P\left(H_{1}\right)\). The conditional probability \(P\left(A|H_{1}\right)\) of an outcome \(A\) given an hypothesis \(H_{1}\) is also called the _likelihood_ of \(H_{1}\). The prior probability reflects the estimation before making observations, based on background knowledge.  
Extended to continuous distributions, [PERSON]'s rule allows to combine a statistical model with a set of measurements and a _prior probability distribution_ over parameters to yield a _posterior probability distribution_ over parameters. This posterior distribution reflects both the uncertainty in measurements and possible prior knowledge about parameters. A thorough treatment is given by [PERSON] et al. (2011).  
For our example model introduced in Section 7.1, we model the running times of implementation B as a function of the time of implementation A, as done in Equation (8):  
\[\log(T_{A}(n))\sim\mathcal{N}(\log(\alpha_{A/B})+\beta_{A/B}\cdot\log(T_{B}(n) ),\sigma_{A/B}^{2})\]  
This defines the likelihood function as a Gaussian noise with variance \(\sigma^{2}\). Since this variance is unknown, we keep it as a model parameter. As we have no specific prior information about plausible values of \(\alpha\) and \(\beta\), we define the following vague prior distributions:  
\[\alpha_{A/B}\sim\text{Lognormal}(0,10),\ \beta_{A/B}\sim\mathcal{N}(1,10),\ \sigma_{A/B}\sim\text{InvGamma}(1,1)\]  
The first two distributions represent our initial--conservative--belief that the two implementations are equivalent in terms of scaling behavior and constants. We model the variance of the observation noise \(\sigma^{2}\) as an inverse gamma distribution instead of a normal distribution, since a variance cannot be negative.  
Figure 8 shows how to compute and trace the posterior distribution of these three parameters using SciPy ([PERSON] _et al._, 2012) and PyMC3 ([PERSON] _et al._, 2013). Results are listed in Table 4. The interval of _Highest Probability Density_ (HPD) is constructed to contain 95% of the probability mass of the respective posterior distribution. It is the Bayesian equivalent of the confidence interval (Section 7.3.2) and also called _credible interval_. The most probable values for \(\alpha_{A/B}\) and \(\beta_{A/B}\) are \(e^{-5.27}\approx 0.0051\) and \(1.04\), respectively. Taking measurement uncertainty into account, the true values are within the intervals \([0.0008,0.03]\) respective \([0.72,1.36]\) with 95% probability. This shows that KADABRA is more than two orders of magnitude faster on average, but results about the relative scaling behavior are inconclusive. While the average for \(\beta_{A/B}\) is 1.04 and suggests similar scaling, the interval \([0.72,1.36]\) neither excludes the hypothesis that KADABRA scales better, nor the hypothesis that it scales worse.  
Figure 8: Example listing for inference of parameters \(\alpha_{A/B}\), \(\beta_{A/B}\) and \(\sigma_{A/B}\).