Polynomial time perfect sampling algorithm for two‐rowed contingency tables | Zendy

Kijima Shuji | Zendy; Matsui Tomomi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Polynomial time perfect sampling algorithm for two‐rowed contingency tables

Author(s) -

Kijima Shuji,

Matsui Tomomi

Publication year - 2006

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.20087

Subject(s) - monotone polygon , time complexity , sampling (signal processing) , bounded function , mathematics , contingency table , polynomial , discrete mathematics , combinatorics , algorithm , computer science , statistics , mathematical analysis , geometry , filter (signal processing) , computer vision

This paper proposes a polynomial time perfect (exact) sampling algorithm for 2 × n contingency tables. The algorithm is based on monotone coupling from the past (monotone CFTP) algorithm. The expected running time is bounded by O( n 3 ln N ) where n is the number of columns and N is the total sum of all entries. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research