# Decide probabilistically whether leaf labels in a decision tree sum to zero?

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.

-
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

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.