A hypothesis test question Let $X_i$ (for all integer $i$)be Bernoulli random variables (which takes either value -1 or 1, with equal probability). Define a random variable $Y$ to be $Y=\sum_{i=1}^d{X_i}$, where $d$ is a hidden constant parameter. Given a constant $t$ and the ability to sample values ($y_1, y_2, \dots$) from $Y$, consider verifying the hypothesis $d<t$. 
Because $E[Y^2]=d$, so $\frac1n\sum_{i=1}^n{y_i^2}<t$ will be a good test for the hypothesis above. The question is, what would be a good alternative test that doesn't require any squaring? 
I intuitively considered the test ${\left|y_i\right|}<\sqrt{t}$. Interestingly, it appears not working as well as ${\left|y_i\right|}<0.5\sqrt{t}$, probably because the PDF of $|Y|$ is quite different from $Y^2$.
Any thoughts and pointers towards a more theoretical analysis of the problem are welcome!
 A: What are the "known" results about "best" tests and the conditions required to satisfy them? Is there any change of variable or other equivalent parameterizations of the above problem that matches "known" results about best-test concerning functions of sums of random variables?
A: For large $d$, $Y$ is approximately normal.
If $Y$ is normal with mean $0$ and variance $\sigma^2$,
$E||Y|] = \sqrt{2/\pi} \sigma$.  So if you want to test for $\sigma < \sqrt{t}$,
your test could be $$\dfrac{1}{n} \sum_{i=1}^n |y_i| < \sqrt{2 t/\pi}$$
Using the binomial distribution, while this is asymptotically correct, it turns out that $E[|Y|]$ is the same for $d=2k-1$ and $d=2k$, so this test won't distinguish between them.  However, note that $Y \equiv d \mod 2$, so you
can very easily determine whether $d$ is even or odd.
The exact value of $E[|Y|]$ using the binomial distribution, for $d = 2k$ or $2k-1$, is
$$2^{2-2k} k {2k-1 \choose k}$$
A: It is extremely unnatural and contrary to common sense to use any of the test statistics you suggested; the average is not at all what matters when you want make claims about $d$.
Say (for a sample of size $n=2$) you observe $y_1=4$, $y_2=0$, so $(1/2)(|y_1|+|y_2|)=2$, and your test would now commit the lunacy of accepting the null hypothesis $d<3$, even though you know for sure that it's false, having observed the value $Y=4$.
You could work with $T=\max |Y_j|$, and reject $d<t$ if $T$ gets too large relative to $t$, with the exact value depending on the desired significance. This isn't optimal either. In simpler examples of the same type (such as an urn with an unknown number of balls in it), the statistic $\max Y_j$ would typically be sufficient, and then there's a lot of theory available that makes precise claims about tests based on it being optimal, but this is not the case in your example, and it's in fact clear that no very simple function of the random sample will be sufficient.
You can read up some on this in lecture notes of mine that I put together recently. See here; tests are discussed in Chapter 6.
