| Popis: |
In [LOO08], it was proposed that a concentration-of-measure inequality known as Mc-Diarmid’s inequality [McD89] be used to provide upper bounds on the failure probability of a system of interest, the response of which depends on a collection of independent random inputs. McDiarmid’s inequality has the advantage of providing an upper bound in terms of only the mean response of the system, the failure threshold, and measures of system spread known as the McDiarmid subdiameters. A disadvantage of McDiarmid’s inequality is that it that takes a global view of the response function: even if the response function 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-measure inequalities that arise if mean performance is known only through sampling. |
