12
$\begingroup$

It's often claimed that the jackknife is less computationally intensive. How is that the case?

My understanding is that the jackknife involves the following steps:

  1. Remove 1 data point
  2. Estimate the statistic of interest (e.g. sample mean) on the remaining point
  3. Repeat step 1) and 2) to get a sampling distribution of the statistic of interest.

The bootstrap involves the following steps:

  1. Generate a bootstrap sample (sample with replacement)
  2. Estimate the statistic of interest (e.g. sample mean) on the bootstrap sample
  3. Repeat step 1) and 2) to get a sampling distribution of the statistic of interest.

It seems to me that Step 2 is the much more computationally intensive part, and is exactly the same between the jackknife and the bootstrap. If so, then how is the jackknife less computationally intensive?

$\endgroup$
  • 1
    $\begingroup$ For many of the classic ("older") statistical models there exists a simple/efficient closed-form for the jackknife estimate. $\endgroup$ – Jim Apr 22 at 20:53
30
$\begingroup$

The jackknife is not necessarily or intrinsically faster, as Cliff AB points out, but two factors sometimes make the it faster than the boostrap in practice.

  1. Convention During a jackknife, the estimation step is always done exactly $n$ times, since one data point is omitted from each estimate. If you had a dataset of $n=50$ points, you'd therefore run the estimation procedure 50 times. Bootstraps, by comparison, are almost run "a large number of times" (~1000); bootstrapping with $n=50$ is virtually unheard of and people rarely compute jackknife estimates from absolutely massive samples ($n=10^9$).

  2. Optimization Since the entire bootstrap sample is drawn anew on each iteration, each bootstrap samples can be totally different from the others, and so the statistic needs to be computed from scratch. Each jackknife sample, however, is almost identical to the one before it, with the exception of two data points: the one removed during the last iteration (and now added back) and the one removed for the current iteration (which was previously present). This opens the door to some computational optimizations.

    For example you want to estimate the mean. For the bootstrap, you're stuck adding all $n$ values together each time; $bn$ additions are required for $b$ bootstrap iterations. For the jackknife estimate, you can instead add all $n$ numbers once to find $S=\sum x$. Next, compute the mean for the sample where the $i$th data point is removed as $\frac{S-x_i}{n-1}$. This requires only $2n$ additions/subtractions for the whole jackknife. Similar tricks exist for other statistics.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ (+1) It's probably worth noting that while there are special cases in which jackknife can be much faster, it's not generically true, especially for large datasets. I think this was implied in your answer but worth stating explicitly. $\endgroup$ – Cliff AB Apr 22 at 6:29
  • $\begingroup$ Agreed! I made a quick edit, but if you want to add more (or get some rep), I'd be happy to accept another one from you too. $\endgroup$ – Matt Krause Apr 22 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.