Total variation bounds on the expectation of periodic functions with applications to recourse approximations

Research paper by Ward Romeijnders, Maarten H. van der Vlerk, Willem K. Klein Haneveld

Indexed on: 30 Oct '14Published on: 30 Oct '14Published in: Mathematical Programming


We derive a lower and upper bound for the expectation of periodic functions, depending on the total variation of the probability density function of the underlying random variable. Using worst-case analysis we derive tighter bounds for functions that are periodically monotone. These bounds can be used to evaluate the performance of approximations for both continuous and integer recourse models. In this paper, we introduce a new convex approximation for totally unimodular recourse models, and we show that this convex approximation has the best worst-case error bound possible, improving previous bounds with a factor 2. Moreover, we use similar analysis to derive error bounds for two types of discrete approximations of continuous recourse models with continuous random variables. Furthermore, we derive a tractable Lipschitz constant for pure integer recourse models.