Orbit-based conditional tests. A link between permutations and Markov bases

Algebraic sampling methods are a powerful tool to perform hypothesis testing for non-negative discrete exponential families, when the exact computation of the test statistic null distribution is computationally infeasible. We propose an improvement of the accelerated sampling described by Diaconis and Sturmfels (1998) based on permutations. We thus establish a link between standard permutation and algebraic-statistics-based sampling. We prove that the permutations-based sampling gives the lowest approximation errors and we validate our algorithm through a simulation study on three applications (data fitting, two sample tests and linear regression).