Talks
Slides for a selection of my research talks
Shuffling cards via one-sided transpositions
Consider shuffling a deck of \(n\) cards as follows. Choose one card uniformly at random with your Right hand; choose a card uniformly at random with your Left hand, conditioned not to be above your Right hand’s choice; transpose the chosen cards.
How many of these shuffles does it take to randomise the deck? This can be answered using a mixture of representation theory of the symmetric group, and a variation of some classical probability arguments.
Omnithermal perfect simulation
Suppose that we want to sample from the equilibriun distribution of a Markov chain, which depends on some underlying parameter. In some situations it is possible to modify a perfect simulation algorithm so as to sample simultaneously from all distributions for which the corresponding parameter lies in a given range: we call this omnithermal simulation. Here we give an overview of a few of these algorithms.
Omnithermal perfect simulation for M/G/c queues
A number of perfect simulation algorithms allow the user to sample from the equilibrium distribution of the Kiefer-Wolfowitz workload vector for stable \(M/G/c\) and \(GI/GI/c\) queues. This talk looks at how some dominated Coupling From The Past algorithms may be modified to carry out this sampling simultaneously for a range of values of \(c\) (the number of servers).
Perfect simulation for M/G/c queues
This talk gives an overview of dominated Coupling From The Past, and then considers the problem of designing such an algorithm to obtain perfect samples from the equilibrium distribution of the workload vector of a multiserver (\(M/G/c\)) queue. Some careful coupling between “First-come first-served” and “Random assignment” service regimes leads to an implementable algorithm, whose properties are explored.
State-dependent Foster-Lyapunov criteria
Drift conditions are a theoretical tool for establishing the convergence rate of a Markov chain. Typically such a criterion only looks at a single step of the chain; here we explore what can be inferred if a geometric drift condition is known to hold for a subsampled chain, for which the subsampling rate is state-dependent. Applications of the results include perfect simulation algorithms, queueing theory and network stability.
Coupling: co-adapted vs. maximal
Suppose that we have two copies of a continuous-time random walk on the hypercube \(\mathbb{Z}_2^n\), and we wish to couple them so that they meet as quickly as possible. What’s the best way to do this, under the assumption that neither is allowed to “cheat” by looking ahead at what the other is going to do?
