Re: new algorithm for wilcoxon signed-rank test

[Jason Stover]

On Wed, Feb 04, 2009 at 10:15:26PM -0800, Ben Pfaff wrote:
> Here's an explanation.
...
> Notably, these trivial cases include all values of W for N = 1.
> 
> Now consider the remaining, nontrivial cases, that is, N > 1 and
> 1 <= W <= N*(N+1)/2.  In this case, apply the following identity:
> 
>         S(N,W) = S(N-1, W) + S(N-1, W-N).
> 
> The first term on the right hand is the number of subsets that do
> not include N that sum to at least W; the second term is the
> number of subsets that do include N that sum to at least W.
> 
> Then we repeatedly apply the identity to the result, reducing the
> value of N by 1 each time until we reach N=1.  Some expansions
> yield trivial cases, e.g. if W - N <= 0 (in which case we add a
> 2**N term to the final result) or if W is greater than the new N.

Simple and clever. I think you should publish this. I'm not surprised
it hasn't been used in statistical software before. Most people in the
field of non-parametric statistics don't think about algorithms from
discrete math.

It's a good result, especially for a sleepless night's work.

-Jason