cleaning up more stuff

1 files changed, 18 insertions, 2 deletions

diff --git a/results.tex b/results.tex
index f90c72f..f4cea1a 100644
--- a/results.tex
+++ b/results.tex
@@ -203,9 +203,25 @@ $D-$learning $f$ approximately. Note that for every element $i \in \Omega$, and
 for a \emph{product} distribution $D$:
 \begin{displaymath}
   \mathbb{E}_{S \sim D}(f(S)|i \in S) - \mathbb{E}_{S \sim D}(f(S) | i \notin
-  S) = w_i
+  S) = \sum_{j \neq i \in \Omega} w_s \left(\mathbb{P}(j\in S|i \in S) -
+  \mathbb{P}(j \in S | i \notin S)\right) + w_i(1 - 0) = w_i
 \end{displaymath}
 
+Let $O$ be the collection of all sets $S$ for which we have observed $f(S)$ and
+let $O_i \equiv \{S \in O : i \in S\}$ and $O^c_i \equiv \{ S\in O: i \notin S
+\}$. If $O_i$ and $O^c_i$ are non-empty, define the following weight estimator:
+\begin{displaymath}
+  \hat W_i \equiv \frac{1}{|O_i|} \sum_{S \in O_i} f(S) - \frac{1}{|O_i^c|}
+  \sum_{S \in O_i^c} f(S)
+\end{displaymath}
+
+If $D$ is a product distribution such that $ \exists c > 0, \forall i,
+\mathbb{P}(i) \geq c$, it is
+easy to show that $\forall i \in
+\Omega,\ \hat W_i \rightarrow_{|O| \rightarrow +\infty} w_i$
+By using standard concentration bounds, we can hope to obtain within $poly(n, \frac{1}{\epsilon})$ observations:
+
+
 %For every node
 %$i$, we compute the \emph{average weight of every set containing element $i$}. Let $w_i$ be
 %the weight of element $i$, $w \equiv f(\Omega) = \sum_{i \in \Omega} w_i$ and
@@ -262,7 +278,7 @@ Let $G = (V, E)$ be a weighted directed graph. Without loss of generality, we
 can assign a weight $p_{u,v} \in [0,1]$ to every possible edge $(u,v) \in V^2$.
 Let $m$ be the number of non-zero edges of $G$. Let $\sigma_G(S, p)$ be the
 influence of the set $S \subseteq V$ in $G$ under the IC model with parameters
-$p$. 
+$p$.
 
 Recall from \cite{Kempe:03} that:
 \begin{equation}