Fast Simulations of the Multi-Album Collector

Fast Simulations of the Multi-Album Collector | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Fast Simulations of the Multi-Album Collector Dina Barak-Pelleg, Daniel Berend This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3834325/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Our starting point is the coupon collector's problem. In this problem, there are $n$ coupons that are drawn uniformly randomly with replacement. The question is how many drawings on average are needed to collect at least one copy (or some other predetermined number $m$ of copies) of each coupon? The problem may be traced back to the $18$-th century, having been mentioned already by de Moivre. Numerous questions have been posed based on the problem since its inception, and it turned out to appear naturally in many applications. A naive simulation of the process is trivial to implement. However, the runtime of this algorithm makes it impractical for large values of $n$. We present here an alternative view of the coupon collecting process, for coupons with any probabilities, that allows us to increase the range of $n$-s (and $m$-s) for which the simulation may be run. For equiprobable coupons, we present additional improvements, making the simulation possible in a very short time practically for any $n$. More precisely, we show that the runtime of our algorithm is $\Theta(\max\{m,\log n\})$. We present theoretical results concerning some of the quantities relevant to our algorithms and conduct simulations to test the algorithms in practice. 2020 Mathematics Subject Classification. Primary 60C05; Secondary 00A72. Coupon Collector’s Problem Dixie Cup Problem Simulation Algorithm Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-3834325","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":265398188,"identity":"4b56e761-9ca9-4318-b5c9-c54bb171169b","order_by":0,"name":"Dina Barak-Pelleg","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABJElEQVRIiWNgGAWjYDCCw0DM2AAkeEC8AgsGBnYQz8CCWC0GEkDGASgDFziAoUUiAcTCrYXvOO/BD4w77PL5ew6wPfhgICEnH/n86oYfBRIM/O3dCdi0SB7mS5ZgPJNsOeNsA7vhDAMJY8PbOWU3e4DWSZw5uwGbFoPDPAYSjG3MBgznGdikgezEjbNz0m4AGUBH5uLSYvyDsa3eQB6k5Y+BRP3GmWfSbv7Br8UMaMthA4OzDWzSQGUJ8hLsx27js0USqMUi8cxxA8MzB9sNgV4w3MCTw3ZbxkCCB5df+M6fMb7xcUe1gdyZ5GMPflTYyMu3H392880fGzn+9l6sWsAgAUwytkGceoDHAETz4FSOBNjApHwD+wNiVI+CUTAKRsHIAQDvrl7TLYo2pQAAAABJRU5ErkJggg==","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":true,"prefix":"","firstName":"Dina","middleName":"","lastName":"Barak-Pelleg","suffix":""},{"id":265398189,"identity":"2d37b655-660d-4ae5-8c7f-099d44dd8a12","order_by":1,"name":"Daniel Berend","email":"","orcid":"","institution":"Ben-Gurion University of the Negev","correspondingAuthor":false,"prefix":"","firstName":"Daniel","middleName":"","lastName":"Berend","suffix":""}],"badges":[],"createdAt":"2024-01-04 10:44:09","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3834325/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3834325/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":50105071,"identity":"6b9553a4-174e-4b06-868a-d975479791d5","added_by":"auto","created_at":"2024-01-24 15:38:30","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":410380,"visible":true,"origin":"","legend":"","description":"","filename":"MultiAlbumCollector.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3834325/v1_covered_274bdaae-6d93-4cc7-b515-235b4065244e.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Fast Simulations of the Multi-Album Collector","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Coupon Collector’s Problem, Dixie Cup Problem, Simulation, Algorithm","lastPublishedDoi":"10.21203/rs.3.rs-3834325/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3834325/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eOur starting point is the coupon collector's problem. In this problem, there are $n$ coupons that are drawn uniformly randomly with replacement. The question is how many drawings on average are needed to collect at least one copy (or some other predetermined number $m$ of copies) of each coupon?\u003c/p\u003e\n\u003cp\u003eThe problem may be traced back to the $18$-th century, having been mentioned already by de Moivre. Numerous questions have been posed based on the problem since its inception, and it turned out to appear naturally in many applications.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eA naive simulation of the process is trivial to implement. However, the runtime of this algorithm makes it impractical for large values of $n$. We present here an\u0026nbsp; \u0026nbsp;alternative view of the coupon collecting process, for coupons with any probabilities, that allows us to increase the range of $n$-s (and $m$-s) for which the simulation may be run.\u0026nbsp; \u0026nbsp;For equiprobable coupons, we present additional improvements, making the simulation possible in a very short time practically for any $n$. More precisely,\u0026nbsp; we show that the runtime of our algorithm is $\\Theta(\\max\\{m,\\log n\\})$.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eWe present theoretical results concerning some of the quantities relevant to our algorithms and conduct simulations to test the algorithms in practice.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e2020 Mathematics Subject Classification. Primary 60C05; Secondary 00A72.\u003c/p\u003e","manuscriptTitle":"Fast Simulations of the Multi-Album Collector","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-01-08 06:55:25","doi":"10.21203/rs.3.rs-3834325/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"292a2306-9b67-4a0a-a18a-81849043bc81","owner":[],"postedDate":"January 8th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-01-24T15:30:20+00:00","versionOfRecord":[],"versionCreatedAt":"2024-01-08 06:55:25","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-3834325","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3834325","identity":"rs-3834325","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}