pspp-dev
[Top][All Lists]

## Re: new algorithm for wilcoxon signed-rank test

 From: Jason Stover Subject: Re: new algorithm for wilcoxon signed-rank test Date: Fri, 6 Feb 2009 16:22:45 -0500 User-agent: Mutt/1.5.18 (2008-05-17)

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

```