摘要：In [LOO08], it was proposed that a concentration-of-measure inequality known as McDiarmid’s inequality [McD89] be used to provide upper bounds on the failure probabilityof a system of interest, the response of which depends on a collection of independentrandom inputs. McDiarmid’s inequality has the advantage of providing an upper boundin terms of only the mean response of the system, the failure threshold, and measures ofsystem spread known as the McDiarmid subdiameters. A disadvantage of McDiarmid’sinequality is that it that takes a global view of the response function: even if the responsefunction exhibits large plateaus of success with only small, localized regions of failure,McDiarmid’s inequality is unable to use this to any advantage. We propose a partitioning algorithm that uses McDiarmid diameters to generate “good” sequences of partitions,on which McDiarmid’s inequality can be applied to each partition element, yielding arbitrarily tight upper bounds. We also investigate some new concentration-of-measureinequalities that arise if mean performance is known only through sampling.
