most recent 30 from http://mathoverflow.net 2013-05-22T19:34:40Z http://mathoverflow.net/feeds/question/64708 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64708/expected-value-of-sum-of-fractions Steven 2011-05-11T23:06:40Z 2011-05-11T23:06:40Z

<p>Suppose $r$ is a set of attributes with probabilities while $p$ is a set of attributes without probabilities. For example, say that $r$ = {$a$:0.4, $b$:1.0} and $p$ = {$a$, $c$}. (Here, $a.prob = 0.4$ and $b.prob = 1.0$.) There are two possible worlds for $r$: {$a$, $b$} with probability 0.4*1 = 0.4 and {$b$} with probability (1-0.4)*1 = 0.6.</p> <p>I would like to efficiently compute the following equation: </p> <p>$F(r,p)$ = $\sum_{r' \in 2^r} (\Pi_{a \in r'} a.c)(\Pi_{a \in r-r'} 1 - a.c)\frac{|W(r')\cap p|}{|W(r')|}$</p> <p>where $W(r')$ strips off the probabilities from $r'$ (e.g., $W$({$b$:1.0}) = {$b$}). Hence, $F(r,p)$ = 0.4 * 1/2 + 0.6 * 0 = 0.2. </p> <p>The above equation is clearly inefficient to compute because of the exponential size of the power set $2^r$. The approximation </p> <p>$F'(r,p)$ = $\frac{\sum_{a \in r \cap p} a.prob}{\sum_{a \in r} a.prob}$ </p> <p>does not seem accurate because $F'(r,p)$ = 0.4 / 0.4+1 = 0.285 $\neq$ 0.2 = $F(r, p)$. </p> <p>Is $F'$ still an theoretically approximate result or is there some better way to efficiently compute $F$ (say in polynomial time)? What are the related math problems? </p>