Search for: All records

Abstract Let G be a finite group. Let $H, K$ be subgroups of G and $$H \backslash G / K$$ the double coset space. If Q is a probability on G which is constant on conjugacy classes ( $$Q(s^{-1} t s) = Q(t)$$ ), then the random walk driven by Q on G projects to a Markov chain on $$H \backslash G /K$$ . This allows analysis of the lumped chain using the representation theory of G . Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on $$GL_n(q)$$ onto a Markov chain on $$S_n$$ via the Bruhat decomposition. The chain on $$S_n$$ has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets, which describes the Markov chain as a mixture of Metropolis chains. Some extensions and examples of double coset Markov chains with G a compact group are discussed. 

A parameter free version of classical models for contingency tables is developed along the lines of de Finetti’s notions of partial exchangeability. 

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.