Card guessing with partial feedback. (15th January 2022)
- Record Type:
- Journal Article
- Title:
- Card guessing with partial feedback. (15th January 2022)
- Main Title:
- Card guessing with partial feedback
- Authors:
- Diaconis, Persi
Graham, Ron
He, Xiaoyu
Spiro, Sam - Abstract:
- Abstract: Consider the following experiment: a deck with m copies of n 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 'feedback' 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, at most $m+O(m^{3/4}\log m)$ cards can be guessed correctly in expectation. This resolves a question of Diaconis and Graham from 1981, where even the $m=2$ case was open.
- Is Part Of:
- Combinatorics, probability and computing. Volume 31:Number 1(2022)
- Journal:
- Combinatorics, probability and computing
- Issue:
- Volume 31:Number 1(2022)
- Issue Display:
- Volume 31, Issue 1 (2022)
- Year:
- 2022
- Volume:
- 31
- Issue:
- 1
- Issue Sort Value:
- 2022-0031-0001-0000
- Page Start:
- 1
- Page End:
- 20
- Publication Date:
- 2022-01-15
- Subjects:
- Card Guessing -- Shuffling -- Games
60C05
Combinatorial analysis -- Periodicals
Probabilities -- Periodicals
Computer science -- Mathematics -- Periodicals
511.6 - Journal URLs:
- http://journals.cambridge.org/action/displayJournal?jid=CPC ↗
- DOI:
- 10.1017/S0963548321000134 ↗
- Languages:
- English
- ISSNs:
- 0963-5483
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library STI - ELD Digital Store
- Ingest File:
- 21748.xml