{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:25:23Z","timestamp":1761294323841},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,1]]},"abstract":"Abstract<\/jats:title>Consider the following experiment: a deck with m<\/jats:italic> copies of n<\/jats:italic> different card types is randomly shuffled, and a guesser attempts to guess the cards sequentially as they are drawn. Each time a guess is made, some amount of \u2018feedback\u2019 is given. For example, one could tell the guesser the true identity of the card they just guessed (the complete feedback model) or they could be told nothing at all (the no feedback model). In this paper we explore a partial feedback model, where upon guessing a card, the guesser is only told whether or not their guess was correct. We show in this setting that, uniformly in n<\/jats:italic>, at most \n$m+O(m^{3\/4}\\log m)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> cards can be guessed correctly in expectation. This resolves a question of Diaconis and Graham from 1981, where even the \n$m=2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> case was open.<\/jats:p>","DOI":"10.1017\/s0963548321000134","type":"journal-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T11:17:45Z","timestamp":1623755865000},"page":"1-20","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Card guessing with partial feedback"],"prefix":"10.1017","volume":"31","author":[{"given":"Persi","family":"Diaconis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron","family":"Graham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyu","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam","family":"Spiro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"S0963548321000134_ref5","doi-asserted-by":"crossref","unstructured":"[5] Ciucu, M. (1998) No-feedback card guessing for dovetail shuffles. Ann. Appl. Prob. 8(4) 1251\u20131269.","DOI":"10.1214\/aoap\/1028903379"},{"key":"S0963548321000134_ref13","unstructured":"[13] Pehlivan, L. (2009) On top to random shuffles, no feedback card guessing, and fixed points of permutations. PhD dissertation, University of Southern California."},{"key":"S0963548321000134_ref9","doi-asserted-by":"crossref","unstructured":"[9] Diaconis, P. , Graham, R. and Spiro, S. (2020). Guessing about Guessing: Practical Strategies for Card Guessing with Feedback. arXiv preprint arXiv:2012.04019.","DOI":"10.1017\/S0963548321000134"},{"key":"S0963548321000134_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02294015"},{"key":"S0963548321000134_ref12","unstructured":"[12] Liu, P. (2019) Asymptotic analysis of card guessing with feedback. arXiv preprint arXiv:1908.07718."},{"key":"S0963548321000134_ref7","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345329"},{"key":"S0963548321000134_ref6","doi-asserted-by":"publisher","DOI":"10.1126\/science.663642"},{"key":"S0963548321000134_ref1","volume-title":"The Probabilistic Method","author":"Alon","year":"2004"},{"key":"S0963548321000134_ref11","unstructured":"[11] Gural, A. , Simper, M. and So, E. (2019) Information Theory in a Card-Guessing Game. https:\/\/theinformaticists.com\/wp-content\/uploads\/2019\/03\/Info_Theory_Project_Card_Guessing_Game.pdf"},{"key":"S0963548321000134_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(81)90001-4"},{"key":"S0963548321000134_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706973"},{"key":"S0963548321000134_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/lnms\/1215090070"},{"key":"S0963548321000134_ref3","doi-asserted-by":"publisher","DOI":"10.1111\/j.1541-0420.2005.00347.x"},{"key":"S0963548321000134_ref10","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/58.3.403"},{"key":"S0963548321000134_ref14","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176348144"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T10:39:08Z","timestamp":1639996748000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000134\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["S0963548321000134"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000134","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}