A Fast Algorithm for Computing Weighted V-Statistics in Resampling

• Activity Number: 38
• Type: Contributed
• Date/Time: Sunday, August 1, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Chunxiao Zhou*+ and Diane Damiano
• Companies: National Institutes of Health and National Institutes of Health
• Keywords: Weighted V-statistics ; Resampling ; group action ; combinatorial species ; bootstrap ; permutation tests

Abstract

Resampling methods are becoming increasingly popular in statistical inference due to their high flexibility and accuracy. One of the most important issues in resampling is how to compute high-order statistics. Traditionally, it is solved by random sampling since exhaustive examination of the resampling space is usually prohibitively expensive. There is a tradeoff between accuracy and computational cost of random sampling. In order to achieve high accuracy, it requires a large number of random samplings. In this work, we are proposing a novel and fast algorithm for computing weighted v-statistics in resampling. We linked this problem with group action and converted it into the problem of orbits counting and enumeration. We thus developed an efficient method to list all orbits by using combinatorial species theory. Applications in bootstrap and permutation tests are also demonstrated.