An analysis of the Rudvalis Shuffle

10/12/2021

In this thesis, we analyze a specific way to shuffle a finite number of cards. The shuffle consists of drawing the first card and flipping a coin: if it lands heads, we place the card at the last position of the deck, while if tails come out, the card is placed at the second-to-last position of the deck. This shuffle was introduced by Arunas Rudvalis, so we call it the Rudvalis shuffle. The dissertation is divided into two chapters. In the first chapter, we start by defining basic properties of Markov chains. Next, we study the Rudvalis shuffle, using Markov chains and the properties previously seen, such as the mixing time. The main goal of this chapter is to study the problem solved by Wilson, i.e., to estimate a lower bound (as a function of the number of cards in the deck) for the minimum number of times we have to shuffle the cards if we want the deck to be well shuffled. In the second chapter, we successively apply the Rudvalis shuffle and look at the configuration of the cards as a particle system (identifying the red cards as empty sites and the black cards as occupied sites), making use of continuous time Markov chains. The main result is the Hydrodynamic Limit, which characterizes the evolution of the particle density. In particular, we prove the existence of the weak solution of a partial differential equation, the transport equation on the torus.

Autores da comunidade :

• 

  D

  David Tadeu Lopes Moreira

  ist186585

Orientadores desta instituição:

• 

  A

  Ana Patrícia Carvalho Gonçalves

  ist426915

mathematics - Matemática

por - Português

Instituto Superior Técnico