کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418944 | 681728 | 2008 | 17 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Formulas for approximating pseudo-Boolean random variables Formulas for approximating pseudo-Boolean random variables](/preview/png/418944.png)
We consider {0,1}n{0,1}n as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. We then derive explicit formulas for approximating a pseudo-Boolean random variable by a linear function if the measure is permutation-invariant, and by a function of degree at most k if the measure is a product measure. These formulas generalize results due to Hammer–Holzman and Grabisch–Marichal–Roubens. We also derive a formula for the best faithful linear approximation that extends a result due to Charnes–Golany–Keane–Rousseau concerning generalized Shapley values. We show that a theorem of Hammer–Holzman that states that a pseudo-Boolean function and its best approximation of degree at most k have the same derivatives up to order k does not generalize to this setting for arbitrary probability measures, but does generalize if the probability measure is a product measure.
Journal: Discrete Applied Mathematics - Volume 156, Issue 10, 28 May 2008, Pages 1581–1597