Tenability and Computability of Generalized Pólya Urns Open Access
Downloadable ContentDownload PDF
Urn models have a storied part in the history of probability and have beenstudied extensively over the past century for their wide range of applications. Weanalyze a generalized class of urn models introduced in the past decade, the so-called"multiset" class, in which more than one ball is sampled at a time. We investigatesufficient conditions for a multiset urn process to be tenable, meaning the processcan continue indefinitely without getting stuck. We fully characterize the "stronglytenable" class of Pólya urn schemes, which is tenable under any starting conditionsthat allow the process to begin. We find several "weakly tenable" classes of Pólyaurn schemes that are tenable only under restricted starting conditions. We enumeratethe size of some of these tenable classes using combinatorics, probabilistically analyzethem, and provide an algorithm to assess the tenability of an arbitrary urn schemeusing breadth-first search. We further analyze the computational complexity of thetenability problem itself. By showing how to encode the Boolean satisfiability problemwithin a Pólya urn scheme, we find that the problem of determining whether amultiset urn scheme is untenable is in the complexity class NP-hard, and this placesconstraints on the kinds of tenability theorems we can hope to find. Finally, weanalyze a generalized “fault tolerant” urn model that can take action to avoid gettingstuck, and by showing that this model is Turing-equivalent, we show that thetenability problem for this model is undecidable.