Stats4Grads: Efficient algorithms for checking consistency of probability bounds.
11 May 2016 13:00 in CM105
In situations where we have little data or where we have little expert opinion, instead of stating probabilities which can lead to an erroneous conclusion, we can specify probability bounds. Lower previsions (Walley, 1991) provide a good way to do this, by bounding expectation. In this study, we explore more efficient algorithms for checking an important basic consistency principle for lower previsions, called "avoiding sure loss". The problem of checking avoiding sure loss can be written as a fully degenerate linear program. This linear program can be solved by standard methods such as the simplex method or the affine scaling method. We propose a new way of reducing the size of this linear program and for minimal introduction of artificial variables. Since the simplex method can be extremely inefficient for fully degenerate linear programs, we explore whether there is a benefit in using other methods, such as the affine scaling method. We propose a simple way to obtain an initial interior solution for our problem, which is required for starting the affine scaling method. We also identify a condition under which the algorithm can detect inconsistency much earlier compared to standard stopping criteria from the literature. In future, we plan to investigate which method is the best suited for checking whether a lower prevision avoids sure loss. We hope that this work will encourage people to use more efficient algorithms for checking avoiding sure loss, instead of standard methods such as the simplex method which are potentially very inefficient for this specific problem.
Contact firstname.lastname@example.org for more information
See the Stats4Grads page for more details about this series.