Penney's game for permutations
Discrete Mathematics & Theoretical Computer Science · 08.07.2026 · vol. 28:1, Permutation... (Special issues)
DOI: 10.46298/dmtcs.16361 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 08.07.2026. Verfasst von Sergi Elizalde und 1 weiteren Autor:innen.
Abstract (Originalsprache)
We consider the permutation analogue of Penney's game for words. Two players, in order, each choose a permutation of length $k\ge3$; then a sequence of independent random values from a continuous distribution is generated, until the relative order of the last $k$ numbers coincides with one of the chosen permutations, making that player the winner. We compute the winning probabilities for all pairs of permutations of length 3 and some pairs of length 4, showing that, as in the original version for words, the game is non-transitive. Our proofs introduce new bijections for consecutive patterns in permutations. We also give some formulas to compute the winning probabilities more generally, and conjecture a winning strategy for the second player when $k$ is arbitrary.
Zitieren
APA
Elizalde, S., & Lin, Y. (2026). Penney's game for permutations. Discrete Mathematics & Theoretical Computer Science, vol. 28:1, Permutation...(Special issues). https://doi.org/10.46298/dmtcs.16361
Vancouver
Elizalde S, Lin Y. Penney's game for permutations. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:1, Permutation...(Special issues). doi:10.46298/dmtcs.16361
BibTeX
@article{Elizalde2026,
author = {Elizalde, Sergi and Lin, Yixin},
title = {Penney's game for permutations},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:1, Permutation...},
number = {Special issues},
doi = {10.46298/dmtcs.16361}
}
EUVIMED