Скачать или смотреть GOCC 04/10/2024 "Penney's Game for Permutations"

Speaker: Yixin (Kathy) Lin (Dartmouth)

Abstract: We consider the permutation analogue of Penney's game for words. Two players, in order, each choose a permutation of length k at least 3. 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. This makes the player who chose the permutation the winner.

We compute the winning probabilities for all pairs of permutations of length 3 and some pairs of length 4 and show that this game is non-transitive. This matches the original version for words. We give some formulas to compute the winning probabilities more generally, and conjecture a winning strategy for the second player when k is arbitrary.

We also consider a Markov chain variation of Penney's game for permutations.

We generate permutations of length k using a transition matrix that goes from one pattern to another with probability 1/k, if the relative order of the last k-1 numbers of the first pattern is the same as the first k-1 numbers of the second pattern. Here, k is the length of two patterns.

We give a formula to compute the expected time to see any permutations for the first time (hitting time), and discuss some conditions for two patterns to have the same hitting time.

We also compute the winning probabilities of all pairs of permutations of any length, and conjecture a non-losing strategy for the second player.

The Graduate Online Combinatorics Colloquium is an online combinatorics seminar organized for and run by graduate students.