Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 5 min ago
PreprintCC BY 4.0arXiv

GPU-Parallelization of Markov Chain Pool Decoding with Unbiased MCMC

  • Takato Ueno
  • Shuji Kijima
Open at sourcePDFDOICite

Abstract

Markov chain pool decoding (MCPD) devised by Knill et al. (1996) identifies likely positive clones from noisy pooled-test results. The standard MCPD estimates clone-wise posterior probabilities using Gibbs sampling, but it may allocate excessive computational effort to low-scoring clones. This paper focuses on parallelizing MCPD on GPU architectures. Whereas the standard MCPD employs systematic-scan updates, we propose a score-weighted update scheme that updates high-scoring clones more frequently. We prove that the stationary distribution of the proposed Markov chain coincides with the target posterior distribution. To enable efficient GPU parallelization, we further incorporate the unbiased MCMC framework of Jacob et al. (2020) and employ a slot-refilling technique based on the arguments by Glynn and Heidelberger (1991) about the coupling of Markov chains. Experiments involving 1,298 clones, 97 pools, and three true positives demonstrate improved recovery compared with uniform decoders, while maintaining high overlap under high-noise conditions.

Related

  1. Markov chain Monte Carlo for predictively oriented posteriors
    Yann McLatchie, Louis Sharrock, David T. Frazier +1
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. Geometric approximation for the number of returns of a transient Markov chain to its origin
    Fraser Daly, Seva Shneer
    arXivPreprintCC BY-NC-ND 4.0Full textProbabilityarXiv
  3. A Markov Chain Approach to Modeling Rugby Union
    Kenny Watts, Jonathan Pipping-Gamón
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  4. Markov Chain Convergence in Kernel-Induced Geometry
    Oleksii Kachaiev, Luc Brogat-Motte, Silvia Villa +1
    arXivPreprintCC BY 4.0Full textProbabilityStatisticsarXiv
  5. Deceptive Stochastic Patrolling via Markov Chain Lifting
    Yohan John, Gilberto Diaz-Garcia, Jason R. Marden +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{ueno2026gpuparallelization,
  title = {{GPU-Parallelization of Markov Chain Pool Decoding with Unbiased MCMC}},
  author = {Takato Ueno and Shuji Kijima},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.30239},
  eprint = {2608.30239},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.30239},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - GPU-Parallelization of Markov Chain Pool Decoding with Unbiased MCMC
AU  - Takato Ueno
AU  - Shuji Kijima
PY  - 2026
DA  - 2026/08/31
PB  - arXiv
DO  - 10.48550/arxiv.2608.30239
UR  - https://arxiv.org/abs/2608.30239
AB  - Markov chain pool decoding (MCPD) devised by Knill et al. (1996) identifies likely positive clones from noisy pooled-test results. The standard MCPD estimates clone-wise posterior probabilities using Gibbs sampling, but it may allocate excessive computational effort to low-scoring clones. This paper focuses on parallelizing MCPD on GPU architectures. Whereas the standard MCPD employs systematic-scan updates, we propose a score-weighted update scheme that updates high-scoring clones more frequently. We prove that the stationary distribution of the proposed Markov chain coincides with the target posterior distribution. To enable efficient GPU parallelization, we further incorporate the unbiased MCMC framework of Jacob et al. (2020) and employ a slot-refilling technique based on the arguments by Glynn and Heidelberger (1991) about the coupling of Markov chains. Experiments involving 1,298 clones, 97 pools, and three true positives demonstrate improved recovery compared with uniform decoders, while maintaining high overlap under high-noise conditions.
ER  -