# Expected value of sum of fractions

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.

I would like to efficiently compute the following equation:

$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')|}$

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.

The above equation is clearly inefficient to compute because of the exponential size of the power set $2^r$. The approximation

$F'(r,p)$ = $\frac{\sum_{a \in r \cap p} a.prob}{\sum_{a \in r} a.prob}$

does not seem accurate because $F'(r,p)$ = 0.4 / 0.4+1 = 0.285 $\neq$ 0.2 = $F(r, 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?

-
How do evaluate that when $|W(r')|=0$? Also, is this notation standard anywhere? Is it ok to change it? –  Douglas Zare May 11 '11 at 23:36
Good point, I only want to use non-empty r' values. The notation is not standard and can be changed. Thanks. –  Steven May 12 '11 at 3:47
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.925483763217926, "perplexity": 579.3592734384973}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-52/segments/1418802775225.37/warc/CC-MAIN-20141217075255-00039-ip-10-231-17-201.ec2.internal.warc.gz"}