The increasing amount of PV (photo-voltaic) power plants comes along with an increased instability in the power grid due to the high uncertainty of the PV power production. As a stabilizing measure, grid operators introduce regulations on the injected power profiles comprising the obligation to declare in advance the predicted power production as well as penalties which apply in case these previously declared production profiles were not respected. In order to meet these regulations power plant owners are forced to invest into expensive storage capacities. In this work an algorithm is proposed which allows to determine the optimal battery size that maximizes the to-be-expected revenue of such an installation for a given regulative framework. Moreover the scheme explicitly takes into account the uncertainty in the PV power production and it provides guaranteed lower bounds on the to-be-expected revenue at a configurable probability. The underlying method allowing to achieve these objectives is a randomized algorithm. The principle of this method is to compute probabilistic guarantees for respecting a binary constraint, considering only a limited number of uncertainty scenarios. (C) 2017 Elsevier Ltd. All rights reserved.