Estimator for sum of independent and identically distributed (iid) variables This is a repost of a question at math.stackexchange, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot.

Consider the Chernoff bound described in Theorem 1 of this paper:


  Theorem 1. Let $X_1,\ldots,X_n$ be discrete, independent random variables such that $E[X_i] = 0$ and $|X_i|&lt;1$ for all $i$. Let $X:=\sum_{i=1}^n X_i$ and $\sigma^2$ be the variance of $X$. Then,
  $$\Pr\left[|X|\ge \lambda\sigma\right] \le 2e^{-\lambda^2/4}$$
  for any $0\le\lambda\le 2\sigma$.


I want to apply this estimator for a computation, but the variance of the variables $X_i$ is unknown to me. Apart from that, my variables satisfy all the conditions of Theorem 1. In fact, my variables are independent and identically distributed (iid).

On the other hand, there is Chebyshev's inequality for finite samples which does not require knowledge of the variance (or mean) of a given random variable and replaces it with the corresponding values of my given sample.
 However, the estimator is not good enough for my application and I was wondering if there is an estimator similar to Theorem 1 but not featuring the variance of the distribution itself. 

Intuitively speaking, it would be nice to have the best of both worlds: If that is not possible, then what is the best bound I can achieve for a sum of iid variables, without any knowledge about their variance?

Edit. I will explain the application in greater detail. I have a tree, at its leaves $v$ are labels $\ell(v)$ with values from the interval $[-1,1]$. I want to know whether these values sum to zero, but summing them up would take too long, because there are too many of them. However, I can easily do a random walk from the root to a leaf. Viewing the tree as a decision tree this way, let $p(v)$ be the probability of each leaf $v$. I then sample a couple of leaves $v_1,\ldots,v_n$ and compute the values $\tfrac{\ell(v_i)}{P\cdot p(v_i)}$, where $P$ is an upper bound for $\tfrac{1}{p(v)}$. Under the null hypthesis that the leaf lables sum to zero, the expected value of a random variable sampling this fraction is 
$$\sum_v p(v) \cdot \frac{\ell(v)}{Pp(v)} = \frac{1}{P} \sum_v \ell(v) = 0.$$
Hence, I am in the situation of Theorem 1. I compute 
$$t=\sum_{i=1}^n \frac{\ell(v_i)}{P\cdot p(v_i)\cdot\sigma}$$
and by Theorem 1, $2e^{-t^2/4}$ is an upper bound for the probability that this sample was obtained under the assumption of the null hypothesis. Now, this works very well for small test instances when I compute $\sigma$ - which actually requires me to search the entire tree. For larger instances, that's exactly what I am trying to avoid, so I need something different. It would be less of a problem to use the mean or the standard deviation of my sample, for instance.

Note that 
$$\textstyle
\sigma^2 = E(X^2)- E(X)^2 = E(X^2) = E(\sum_{i=1}^n X_i^2) + E(\sum_{i\ne j} X_i X_j).$$
Since $X_i$ and $X_j$ are independent, this means $\sigma^2 = n E(X_1^2)$. In my application, the expected value of $X_1^2$ is so small that reasonably large sample sizes cannot negate the effect that $\sigma^2$ is very small.
You need McDiarmid's inequality, or in particular the Hoeffding inequality, which is a simplification: 

Given $n$ independent $X_i$ with the property that $X_i \in [a_i, b_i]$, and $X = (1/n)\sum X_i$, then 

$$ \text{Pr}(|X - EX| \ge t) \le 2 \exp(\frac{2t^2n^2}{\sum (b_i - a_i)^2}) $$