4
$\begingroup$

I am implementing code to compute the two-sided Fisher exact test of 2x2 contingency tables in C. I read that R's implementation is not the most efficient way to calculate the p-value for a two-sided test. My first question is, how is this implemented? Wikipedia states

"An approach used by the fisher.test function in R is to compute the p-value
 by summing the probabilities for all tables with probabilities less than or
 equal to that of the observed table."

But I do not understand where the other tables and probabilities come from.

Also, how could I implement this function in a more computationally effective way, assuming that the statement

"A simple, somewhat better computational approach relies on a gamma function
 or log-gamma function, but methods for accurate computation of
 hypergeometric and binomial probabilities remains an active research area."

is correct?

$\endgroup$

1 Answer 1

5
$\begingroup$

"An approach used by the fisher.test function in R is to compute the p-value by summing the probabilities for all tables with probabilities less than or equal to that of the observed table."

But I do not understand where the other tables and probabilities come from.

Fisher conditions on both margins. The other tables are all tables with the same margins. The probabilities come directly from the hypergeometric distribution.

(Both these pieces of information are already in the article you point to, by the way.)

The help on the R function you mention mentions an algorithm for getting the other tables, but in the 2x2 case it's pretty simple, because they correspond to taking one cell in the table through the range of its possible values (the range of values taken by the random variable in a hypergeometric distribution). Here's one example (y-axis is log-scaled, but the values on the axis are actual probabilities):

enter image description here

The red numbers represent the ranks of the probabilities from smallest to largest. This is the order you account for them in computing a two-tailed p-value until you hit the observed table.

"A simple, somewhat better computational approach relies on a gamma function or log-gamma function, but methods for accurate computation of hypergeometric and binomial probabilities remains an active research area."

This is simply referring to the calculation of a hypergeometric probability. When the margins take large (or even middling) values, the exact calculation can be problematic (the calculations involve $\binom{n}{r}$ terms that can get quite large). It's usual to work on the log-scale with functions that return the log of the gamma function of its arguments.

R, for example, provides the functions lgamma and lfactorial for such purposes.

exp(lfactorial(5))
[1] 120
> exp(lgamma(6))
[1] 120

Fast methods for exact tests are often based on the approach of Mehta and Patel (variations of the network algorithm, mentioned, again at the link you gave, though there were more papers than listed there). There have been more recent developments in this area, but I am not especially familiar with them; if you know how to search for academic research (which these days mostly means "can google efficiently") more recent work won't be hard to find.

If you look at the references at the bottom of the help for R's fisher.test, it includes references to Mehta and Patel and also to the more recent paper by Clarkson, Fan and Joe which is more efficient.

Page 17 of "Exact Inference for Categorical Data", 1997 by Mehta and Patel (on Cytel's website, here) mentions alternative approaches in passing (with references).

There's papers like

Requena, F., & N.M. Ciudad, (2006)
"A major improvement to the Network Algorithm for Fisher’s Exact Test in 2 × c contingency tables,"
Computational Statistics & Data Analysis, 51, 490–498.

that might be of some use.

$\endgroup$

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.