Skip Navigation


Biometrika Advance Access originally published online on August 11, 2009
Biometrika 2009 96(3):635-644; doi:10.1093/biomet/asp036
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Kou, S. C.
Right arrow Articles by McCullagh, P.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© 2009 Biometrika Trust

Article

Approximating the {alpha}-permanent

S. C. Kou

Department of Statistics, Harvard University, Cambridge, Massachusetts 02138, U.S.A. kou{at}stat.harvard.edu

P. McCullagh

Department of Statistics, University of Chicago, 5734 University Avenue, Chicago 60637, U.S.A. pmcc{at}galton.uchicago.edu

Received for publication 1 May 2008. Revision received 1 December 2008.

The standard matrix permanent is the solution to a number of combinatorial and graph-theoretic problems, and the {alpha}-weighted permanent is the density function for a class of Cox processes called boson processes. The exact computation of the ordinary permanent is known to be #P-complete, and the same appears to be the case for the {alpha}-permanent for most values of {alpha}. At present, the lack of a satisfactory algorithm for approximating the {alpha}-permanent is a formidable obstacle to the use of boson processes in applied work. This paper proposes an importance-sampling estimator using nonuniform random permutations generated in a cycle format. Empirical investigation reveals that the estimator works well for the sorts of matrices that arise in point-process applications, involving up to a few hundred points. We conclude with a numerical illustration of the Bayes estimate of the intensity function of a boson point process, which is a ratio of {alpha}-permanents.

Key Words: Boson point process • Conditional intensity • Density estimation • Sequential importance sampling



References

    Beichl I., Sullivan F. Approximating the permanent via importance sampling with application to the dimer covering problem. In: J. Comp. Phys. (1999) 149:128–47.[CrossRef]

    Bezáková I., Stefankovic D., Vazirani V. V., Vigoda E. Accelerating simulated annealing for the permanent and combinatorial counting problems. In: Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithms (2006) New York: ACM. 900–7.

    Chen Y., Liu J. S. Sequential Monte Carlo methods for permutation tests on truncated data. In: Statist. Sinica (2007) 17:857–72.

    Daley D. J., Vere-Jones D. An Introduction to the Theory of Point Processes (2003) vol. 1: Elementary Theory and Methods, 2nd ed. New York: Springer.

    Diaconis P., Graham R. L., Holmes S. Statistical problems involving permutation with restricted positions. In: State of the Art in Probability and Statistics—de Gunst M., Klaassen C., Vaart A. Van der., eds. (2001) Hayward, CA: Institute of Mathematical Statistics. 195–222.

    Hough J., Krishnapur M., Peres Y., Virág B. Determinantal processes and independence. In: Prob. Surveys (2006) 3:206–29.[CrossRef]

    Jerrum M. R., Sinclair A., Vigoda E. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. In: J. Assoc. Comp. Mach. (2004) 51:671–97.

    Karmarkar N., Karp R., Lipton R., Lovász L., Luby M. A Monte Carlo algorithm for estimating the permanent. In: SIAM J. Comp. (1993) 22:284–93.[CrossRef]

    Kuznetsov N. Computing the permanent by importance sampling method. In: Cybern. Syst. Anal. (1996) 32:749–55.[CrossRef]

    Liu J. S. Monte Carlo Strategies in Scientific Computing (2001) New York: Springer.

    McCullagh P., Møller J. The permanental process. In: Adv. Appl. Prob. (2006) 38:873–88.[CrossRef]

    McCullagh P., Yang J. Stochastic classification models. In: Proc. Int. Cong. Math.—Sanz-Solé M., Soria J., Varona J. L., Verdera J., eds. (2006) 3. Zurich: European Mathematical Society. 669–86.

    Minc H. Permanents (1978) Encyclopedia of Mathematics and Its Applications 6. Reading, MA: Addison-Wesley.

    Shirai T. Remarks on the positivity of {alpha}-determinants. In: Kyushu J. Math. (2007) 61:169–89.[CrossRef]

    Shirai T., Takahashi Y. Random point fields associated with certain Fredholm determinants I: Fermion, Poisson and boson point processes. In: J. Funct. Anal. (2003) 205:414–63.[CrossRef]

    Sinkhorn R. A relationship between arbitrary positive matrices and doubly stochastic matrices. In: Ann. Math. Statist. (1964) 35:876–9.[CrossRef]

    Valiant L. G. The complexity of computing the permanent. In: Theor. Comp. Sci. (1979) 8:189–201.[CrossRef]

    van Lint J., Wilson R. A Course in Combinatorics (1992) Cambridge, UK: Cambridge University Press.

    Vere-Jones D. Alpha-permanents and their application to multivariate gamma, negative binomial and ordinary binomial distributions. In: New Zeal. J. Math. (1997) 26:125–49.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Kou, S. C.
Right arrow Articles by McCullagh, P.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?