Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following problem, which might or might not be very easy to answer for someone with even a light background in statistics - but I don't even know where to start. Hence, I will give it a shot and post it here:

Terminology

By a decision tree I will mean a directed, acyclic graph $G=(V,E)$ where each vertex $v\in V$ has indegree $0$ or $1$, and there is precisely one vertex with indegree zero, called the root.

For each vertex $v\in V$, let $\newcommand{\out}{\mathrm{out}}\delta_\out(v)=\{ e\in E \mid \exists w\in V: e=(v,w)\}$ be the set of outgoing edges.

For each edge $e=(v,w)\in E$, let $$p(e):=\frac{1}{\sharp\delta_\out(v)}$$ be the probability of this edge. For each leaf $v\in V_0:=\{ v\in V \mid \sharp\delta_\out(v)=0\}$, there is a unique path from the root to $v$. Let $e_1,\ldots,e_r\in E$ be the edges of this path. Then, we write $$p(v):=\prod_{i=1}^r p(e_i)$$ and call it the probability of this leaf.

Problem Description

Let $a,b\in\newcommand{\Z}{\mathbb{Z}}\Z$ with $a<0<b$. Consider a decision tree $(V,E)$ whose leaves are labelled with integer values from the interval $[a,b]$. In other words, we have a function $\ell: V_0 \to \Z\cap[a,b]$.

Question: Is the sum over all leaf labels equal to zero or not?

i.e. decide whether $$\sum_{v\in V_0} \ell(v) = 0$$ or not.

Now in my case there are a lot of leaves, way too many to compute $\sum_{v\in V_0} \ell(v)$ explicitly. However, traversing a path from the root to some leaf $v$ and thereby computing $p(v)$ is easy.

Now, I was wondering: Is there a method to probabilistically answer the question from a smaller number of samples $v\in V_0$ together with the values $p(v)$ and $\ell(v)$? Unfortunately, I do not know anything about the distribution of the values along the leaves.

share|improve this question
    
Unless there’s some relationship between the $p(v)$ and the function $\ell$, it seems unlikely that the ability to calculate former easily will help much. –  Brian M. Scott Oct 25 '12 at 12:19
add comment

1 Answer

up vote 2 down vote accepted

Yes, you can do this by sampling leaves according to $p$ and averaging $\ell/p$. Its expected value is

$$ \sum_{v\in V_0}p(v)\frac{\ell(v)}{p(v)}=\sum_{v\in V_0}\ell(v) $$

as desired. You can use the Chebyshev inequality for finite samples to obtain an upper bound on the probability that the actual sample would have been obtained if the sum were zero, or you could assume an approximately normal distribution and do a standard $z$-test.

share|improve this answer
    
Perfect, this looks to be exactly what I am looking for. Thanks a bunch! –  Jesko Hüttenhain Oct 26 '12 at 6:59
    
@rattle: You're welcome! –  joriki Oct 26 '12 at 10:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.