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. 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.