Matem Atica e Embaralhamento de Cartas
Matem Atica e Embaralhamento de Cartas
Matem Atica e Embaralhamento de Cartas
Departamento de Matemática
Apoio: Capes
Belo Horizonte - MG
2016
Para Sérgio e Maria,
meus pais.
i
Agradecimentos
Gostaria de agradecer primeiramente à minha mãe, Maria, por ter me ensinado a gostar
de Matemática, acreditado em mim, me apoiado durante toda a minha vida acadêmica
e por todo o esforço para que eu alcançasse os meus sonhos.
Agradeço ao meu pai, Sérgio, e à minha irmã, Renata, pela paciência, pelo enco-
rajamento e por torcerem tanto por mim.
Agradeço ao meu marido, Tiago, por me apoiar, por estar sempre disposto a me
ajudar e por todo o companheirismo.
Agradeço a todos os meus amigos, por tornarem esta jornada tão mais prazerosa.
Em especial agradeço ao meu amigo Marcos, por estar ao meu lado desde a graduação,
me ajudando nos momentos de dificuldades e me incentivando sempre.
Agradeço ao meu orientador, Bernardo, pela paciência, por ter acreditado em mim
e por ter me guiado, me dando a oportunidade de ir além do que eu imaginava. Serei
eternamente grata.
Agradeço à Fump, por ter me mantido durante a graduação, e agradeço à Capes
pelo apoio financeiro durante o mestrado.
Por fim, agradeço a Deus por ter colocado cada uma dessas pessoas na minha
vida, sem elas eu não teria chegado até aqui.
ii
Resumo
iii
Abstract
This work aims to study the mathematical model of Riffle Shuffle, that we will denote
by canonical shuffle. The mathematical model for the canonical shuffle is called Gilbert-
Shannon-Reeds (GSR) model, in honor of the mathematicians who developed it.
Based on an analysis of a magic, we will introduce the concept of rising sequence,
which is closely linked to the GSR model. With this concept we will be able to calcu-
late the probability of getting a specific permutation of cards, after performing several
canonical shuffles.
The remaining of this work will be dedicated to find the number of consecutive
canonical shuffles that approaches the GSR distribution from the uniform distribution.
We will develop a study of Markov Chains, relating them with the canonical shuffle.
KEYWORDS: GSR Model, Magic, Markov Chains, Riffle Shuffle.
iv
Sumário
Lista de Figuras vi
Introdução 1
Apêndice 54
Referências Bibliográficas 55
v
Lista de Figuras
vi
Lista de Tabelas
vii
Introdução
O ponto de partida para responder estas duas questões será a análise de uma
mágica, conhecida como Premo. As referências principais para todo o texto serão o
artigo de Bayer e Diaconis, Trailing the Dovetail Shuffle to its Lair [1], o texto de
Hilário e Oliveira, A Matemática de Embaralhar Cartas [4], e o Capı́tulo 8 do livro
Markov Chains and Mixing Times [6], de Lewin, Peres e Wilmer.
No Capı́tulo 1 apresentaremos as primeiras definições que serão utilizadas constan-
temente ao longo deste texto, dentre elas o modelo GSR e as Sequências Levantadoras.
Em seguida, analisaremos a mágica Premo e faremos uma breve biografia de Charles
Thornton Jordan, o criador da mágica inspiradora para o desenvolvimento da mágica
Premo, tendo como referência os livros Magical Mathematics: The mathematical ideas
1
that animate great magical tricks [2], de Diaconis e Graham, e Mathematics, magic
and mystery [3], de Gardner. Com o objetivo de responder à primeira pergunta citada
acima, apresentaremos uma generalização para o modelo GSR, e vamos oferecer quatro
descrições alternativas deste modelo a fim de poder analisar vários embaralhamentos
canônicos consecutivos. As principais referências para este capı́tulo serão [1] e [4].
O Capı́tulo 2 será dedicado a responder à segunda pergunta citada acima, para
isso desenvolviremos um estudo sobre Cadeias de Markov. Inicialmente apresentare-
mos vários conceitos referentes às Cadeias de Markov, como distribuição estacionária
e irredutibilidade, e mostraremos como estes conceitos se relacionam tanto com o em-
baralhamento canônico quanto com o embaralhamento canônico inverso. Em seguida
definiremos uma maneira de medirmos a distância entre duas distribuições de proba-
bilidade e, no final da Seção 2, mostraremos que podemos analisar o embaralhamento
canônico inverso ao invés do embaralhamento canônico. Finalizamos este trabalho ofe-
recendo uma cota superior e uma cota inferior para o número de embaralhamentos
canônicos consecutivos que embaralham bem um baralho. As referências para este
capı́tulo serão [4] e [6].
2
Capı́tulo 1
O modelo de
Gilbert-Shannon-Reeds (GSR)
3
Neste texto iremos considerar pilhas ordenadas, ou seja, quando o baralho estiver
em uma pilha, dizemos que a carta do topo está na primeira posição, a carta logo abaixo
da carta do topo está na segunda posição, e assim sucessivamente, terminando com a
última carta, que está no fundo da pilha e vamos dizer que esta carta está na n-ésima
posição. Representaremos uma pilha por
b = (b1 , b2 , ..., bn ),
Definição 2 (Corte reto). Consiste em separar uma pilha em dois montes, dividindo
a pilha em duas partes simplesmente separando uma quantidade do topo e deixando as
demais cartas na pilha. Se a pilha é representada por (b1 , b2 , ..., bn ), o corte reto irá
formar dois montes (b1 , ..., bk ) e (bk+1 , ..., bn ), com 0 ≤ k ≤ n, k ∈ N.
4
denotaremos por σ(bi ), com 1 ≤ σ(bi ) ≤ n. Assim, um embaralhamento qualquer leva
uma pilha b = (b1 , · · · , bn ), em outra pilha c = (c1 , · · · , cn ), sendo que para cada carta
bi , i ∈ {1, · · · , n}, existe um j ∈ {1, · · · , n} tal que σ(bi ) = j, ou seja, a carta que
está na j- ésima posição na pilha c, representada cj , correspode a carta bi da pilha b.
Desta forma, é natural associar embaralhamentos a permutações, mais detalhes desta
associação podem ser vistos em [4].
A partir da associação embaralhamento-permutação, temos que o conjunto de
todos os embaralhamentos possı́veis de um baralho de tamanho n é o conjunto de
permutações de n elementos, ou seja, o grupo simétrico, conhecido como Sn , que possui
n! elementos. Optamos por usar a mesma notação utilizada em [1]: dado um baralho
de tamanho n = 8, suponhamos que o baralho esteja disposto na pilha identidade
id = (1, 2, 3, 4, 5, 6, 7, 8).
c = (3, 7, 1, 2, 8, 5, 4, 6),
5
1 2 ··· n
ρ= .
b1 b2 · · · bn
Desta forma, além de denotar embaralhamentos por permutações, também pode-
mos denotar cada pilha pela permutação que a gera a partir da pilha identidade. Neste
caso, por exemplo, podemos denotar b por ρ. Portanto, constatamos que tanto pilhas
quanto embaralhamentos podem ser vistos como elementos de Sn . Com isso, podemos
apresentar uma definição mais formal de um embaralhamento qualquer.
6
Um modelo matemático preciso para o embaralhamento canônico foi introduzido
pelos matemáticos Edgar N. Gilbert e Claude Shannon em 1955, e independentemente
por Jim Reeds em 1981. De acordo com [1], temos a seguinte definição:
7
Figura 1.2: Intercalando os montes
8
Figura 1.5: Pilha resultante a partir do embaralhamento canônico inverso
1.2.1 A performance
9
e finalizar com um corte. O mágico pega o baralho e abre a pilha em uma mesa, com
as faces das cartas viradas para cima. Para a surpresa da audiência, ele rapidamente
encontra a carta que o voluntário memorizou.
Começaremos a análise da mágica pelo baralho. Para a realização desta mágica não
importa a quantidade exata de cartas, a numeração das cartas ou os naipes a serem
utilizados, o único fator importante é a ordenaração inicial das cartas, ou seja, a pilha
inicial. Para facilitar a análise, consideremos que o baralho esteja inicialmente na pilha
identidade (1, 2, · · · , n).
Antes de considerarmos a mágica completa, vamos investigar o efeito que um em-
baralhamento canônico produz na ordem das cartas. Pela Definição 5, para a realização
de um embaralhamento canônico primeiramente devemos efetuar um corte reto na pi-
lha, e assim dividimos o baralho em dois: um monte composto pelas cartas 1, 2, ..., k,
e outro compostos pelas cartas k + 1, k + 2, ..., n, com 0 ≤ k ≤ n, k ∈ N. Ao interca-
larmos esses dois montes obtemos uma nova pilha, mas observe que as cartas 1, 2, ..., k
permanecem na mesma ordem relativa na pilha, assim como as cartas k + 1, k + 2, ..., n,
reveja a Figura 1.3, o que nos leva a seguinte definição.
b = (5, 1, 3, 8, 2, 4, 9, 10, 6, 7) .
Para esse arranjo de cartas temos 4 sequências levantadoras, que são (5, 6, 7), (1, 2),
(3, 4) e (8, 9, 10).
10
sequências levantadoras, com r ∈ {1, 2, · · · , n}. A permutação que possui r = 1 é a
permutação identidade, e a permutação com r = n é a permutação (n, n−1, · · · , 3, 2, 1).
Fixada uma pilha, notamos que duas sequências levantadoras desta pilha não se
intersectam, e, sendo assim, podemos representar uma pilha qualquer de Sn como a
união das suas sequências levantadoras de maneira única, porém, a união de sequências
levantadoras não determinam uma única pilha. Ilustramos esta afirmação com o Exem-
plo 2, não é possı́vel representarmos a pilha b a partir de suas sequências levantado-
ras de uma maneira distinta de {(A, 2), (3, 4), (5, 6, 7), (8, 9, 10)}, a menos de ordem.
Porém, observe que {(A, 2), (3, 4), (5, 6, 7), (8, 9, 10)} também pode expressar a pilha
c = (A, 5, 3, 2, 8, 4, 9, 6, 10, 7), sendo que b 6= c.
Como para a mágica consideramos a pilha inicial sendo a pilha identidade, inicial-
mente temos apenas uma sequência levantadora. Após a realização de um embaralha-
mento canônico, a nova pilha poderá apresentar uma ou duas sequências levantadoras.
No corte reto que compõe o embaralhamento canônico, escolhendo k = 0 ou k = n
não há como intercalarmos as cartas e portanto o baralho irá manter sua ordenação
inicial, (1, 2, ..., n), e a nova pilha permanecerá com apenas uma sequência levantadora.
Entretanto, caso 1 ≤ k ≤ n − 1, o corte reto irá quebrar a sequência levantadora em
duas partes, uma parte com as cartas de 1 a k, e a outra com as cartas de k + 1 a n. Se
ao intercalar apenas sobrepormos as cartas, obtemos novamente a pilha identidade, e
portanto uma sequência levantadora, mas ao intercalarmos de outras maneiras obtemos
pilhas com duas sequências levantadoras, uma vez que as cartas 1, 2, ..., k permanecerão
na mesma ordem relativa na nova pilha, assim como as cartas k + 1, k + 2, ..., n.
Esse processo irá se repetir a cada nova realização de um embaralhamento canônico,
o corte reto poderá quebrar cada sequências levantadora da pilha em duas e, ao inter-
calarmos as cartas, teremos no máximo o dobro do número de sequências levantadoras
que tinhamos anteriormente. Sendo assim, após a realização de t embaralhamentos
canônicos partindo da pilha identidade, a pilha resultante terá no máximo 2t sequências
levantadoras.
De volta a análise da mágica, suponhamos que o baralho não seja cortado e que a
carta do topo seja movida somente após o último embaralhamento canônico. Após três
11
embaralhamentos canônicos o baralho terá no máximo oito sequências levantadoras, e ao
movermos a carta do topo para o meio do baralho criamos mais uma dessas sequências,
consistindo apenas da carta movida. Assim, quando o mágico abre o baralho com as
faces das cartas viradas para cima, ele buscará uma carta que está em uma sequência
levantadora composta apenas por uma única carta, ou seja, a carta que se encontra
após o seu sucessor e antes do seu antecessor.
Agora vamos observar o efeito que um corte produz na ordem das cartas. Supondo
que o baralho esteja inicialmente na pilha identidade, ao efetuarmos um corte a nova
ordem será (k+1, ..., n, 1, 2, ..., k−1, k), com k ∈ {1, 2, ..., n}, ou seja, se considerarmos a
carta 1 como a sucessora da carta n, podemos ver o baralho arranjado em um loop e com
um corte estamos apenas rotacionando o loop. De volta a mágica, quando o espectador
corta o baralho uma vez o mágico passa a não saber mais o inı́cio do loop, mas ainda
assim, após um embaralhamento canônico teremos as sequências levantadoras, a saber
uma começando com k + 1 e a outra terminando com k, que é o que realmente interessa
para a realização desta mágica. Os demais cortes irão rotacionar o loop novamente
e também poderão criar e modificar as sequências levantadoras, tornando assim mais
difı́cil a tarefa do mágico de encontar a carta que o espectador moveu.
Como mencionado anteriormente, uma maneira de verificar qual carta foi movida
pelo voluntário é procurar pela carta que está antes de sua antecessora e depois de sua
sucessora, e isto pode ser feito atribuindo um contador a cada carta.
Em [1], o seguinte contador é apresentado: seja σ(i) a posição da carta i, denota-
mos por d(i, j) o menor inteiro positivo obtido por σ(j) − σ(i) (mod n), e a cada carta
i associamos o contador
Idealmente a carta movida será a única com o contador maior ou igual a n. Este
fato é apenas brevemente mencionado em [1], por completude, apresentamos o seguinte
teorema no qual provamos que idealmente o contador da carta movida será maior ou
igual a n, porém o contador das demais cartas pode variar de acordo com a sequência
levantadora a qual cada carta pertence.
Teorema 1. Considere a mágica Premo descrita na Seção 1.2.1 . Seja i a carta movida
12
pelo voluntário durante a mágica, temos que:
a) c(i) ≥ n;
b) c(j) pode ser maior, menor ou igual a n, para toda carta j 6= i.
Demonstração. a) Seja σ(i) = y. Observe que se i está antes de seu antecessor e depois
do seu sucessor, temos que σ(i − 1) = y + z e σ(i + 1) = y − x, com x > 0 e z > 0. Uma
vez que o baralho possui n cartas, temos que
x + z + 1 ≤ n. (1.1)
d(i − 1, i) ≡ y − y − z ≡ −z ≡ n − z
e
d(i, i + 1) ≡ y − x − y ≡ −x ≡ n − x,
d(j − 1, j) = y − y + x ≡ x
e
d(j, j + 1) = y + z − y ≡ z,
13
e portanto, c(j) = x + z − 1 = (x + z + 1) − 2 ≤ n − 2 < n, onde a primeira desigualdade
também segue da Desigualdade 1.1. Ou seja, para estas cartas o contador é estritamente
menor que n.
Caso 2: As cartas j − 1 e j pertencem à mesma sequência levantadora, mas a
carta j + 1 não. Neste caso consideremos dois subcasos.
2.1) A carta j + 1 está antes de j − 1. Sejam σ(j) = y, σ(j − 1) = y − x e
σ(j + 1) = y − z, com 0 < x < z. Logo,
d(j − 1, j) = y − y + x ≡ x
e
d(j, j + 1) = y − z − y ≡ −z ≡ n − z.
Portanto, c(j) = x + n − z − 1 < n − 1 < n, visto que x < z. Logo, para estas cartas o
contador é estritamente menor que n.
2.2) A carta j + 1 está entre as cartas j − 1 e j. Suponhamos que σ(j) = y,
σ(j − 1) = y − z e σ(j + 1) = y − x, com 0 < x < z. Logo,
d(j − 1, j) ≡ y − y + z ≡ z
e
d(j, j + 1) ≡ y − x − y ≡ −x ≡ n − x,
d(j − 1, j) ≡ y − y − x ≡ −x ≡ n − x
e
d(j, j + 1) = y + z − y ≡ z.
14
3.2) A carta j − 1 está depois da carta j + 1. Sejam σ(j) = y, σ(j − 1) = y + z e
σ(j + 1) = y + x, com 0 < x < z. Portanto,
d(j − 1, j) ≡ y − y − z ≡ −z ≡ n − z
e
d(j, j + 1) ≡ y + x − y ≡ x.
Logo, c(j) = n−z +x−1 < n, uma vez que x < z. Ou seja, para estas cartas o contador
é estritamente menor que n. Assim finalizamos a última parte do teorema.
Pelo teorema acima, notamos que este truque pode falhar, pois podemos ter mais
de uma carta com o contador maior ou igual a n, e portanto, mais de uma opção para
a carta movida. Além disso, quando o voluntário move a carta do topo ele pode não
retirá-la de sua sequência levantadora, ou também pode retirá-la de uma sequência
levantadora, mas colocá-la em outra sequência levantadora, e portanto o seu contador
também poderá ser menor ou igual a n.
Bayer e Diaconis em [1] realizaram vários experimentos de Monte Carlo que apon-
taram que o truque é realizado com maior sucesso quando a carta é movida após o último
embaralhamento canônico. Eles programaram um computador para embaralhar as car-
tas t vezes, t ∈ N, de acordo com o modelo GSR, cortar o baralho segundo a distribuição
uniforme, mover a carta do topo para uma posição escolhida segundo a distribuição bi-
nomial e, por fim, cortar novamente. O computador calculava o contador de cada carta
e selecionava a carta com o contador mais alto. Caso houvesse mais de uma carta com
o maior contador, o computador selecionava uma delas de modo equiprovável.
A seguir apresentamos uma tabela extraı́da de [1] referente ao experimento citado
acima. A tabela é baseada em 1.000.000 de experimentos de Monte Carlo, e cada entrada
(i, j) expressa a probabilidade de com j embaralhamentos o mágico dizer corretamente
a carta movida, sendo permitidas i tentativas.
Na Tabela 1.1 as colunas indicam o número t de embaralhamentos canônicos con-
secutivos, com 2 ≤ t ≤ 12, e cada linha representa a quantidade de tentativas de acerto
que são permitidadas. Segundo a Tabela 1.1, notamos que com três embaralhamentos
canônicos temos uma probabilidade de 0,839 de acertar a carta movida com apenas
15
t 2 3 4 5 6 7 8 9 10 11 12
1 0,997 0,839 0,228 0,088 0,042 0,028 0,023 0,021 0,020 0,020 0,019
2 1,000 0,943 0,471 0,168 0,083 0,057 0,047 0,042 0,040 0,039 0,039
3 1,000 0,965 0,590 0,238 0,123 0,085 0,070 0,063 0,061 0,059 0,058
13 1,000 0,998 0,884 0,617 0,427 0,334 0,290 0,270 0,260 0,254 0,252
26 1,000 0,999 0,975 0,835 0,688 0,596 0,548 0,524 0,513 0,505 0,503
uma tentativa, e essa probabilidade aumenta para 0,943 se são permitidas duas tenta-
tivas. Uma observação interessante é que mesmo com oito embaralhamentos canônicos
consecutivos, após 26 tentativas ainda temos uma probabilidade de acerto considerável
maior que 21 .
O fator que torna importante a mágica Premo é que ela nos mostra que com
poucos embaralhamentos canônicos o baralho ainda guarda memória de sua ordenação
inicial, possibilitando assim que o mágico consiga “adivinhar” qual carta foi movida
pelo voluntário. O objetivo do Capı́tulo 2 será encontrar o número de embaralhamentos
canônicos necessários para que o baralho não seja mais capaz de guardar a memória da
sua ordem inicial, ou seja para que o baralho esteja bem embaralhado.
Charles Thornton Jordan nasceu no final do Século XIX em Berkeley, Califórnia. Além
de ser um construtor de rádios habilidoso e criador de galinhas, ele tinha como hobby
inventar mágicas e participar de desafios publicados em jornais. Participando destes
desafios, Jordan ganhou diversos prêmios e com o passar do tempo foi proibido de
envolver-se neste tipo de concurso, mas isso não o impediu de concorrer. Jordan e sua
equipe contrataram um mágico da época, Blackledge, para se apresentar durante os
desafios no lugar deles, mas Jordan e sua equipe forneciam as respostas para Blackledge.
Jordan foi o primeiro grande inventor de truques matemáticos com cartas e também
o primeiro mágico a usar o princı́pio por trás das sequências de de Bruijn. Porém, ele
era muito tı́mido para fazer performaces em público, o que o levou a criar mágicas para
16
vendê-las a outros mágicos. Um dos mais celebrados truques de Jordan é o Leitor de
mentes a longa distância, esse truque foi anunciado na principal revista de mágicas da
época, Sphinix, em maio de 1916 e o truque estava sendo vendido por uma quantia de
25 vezes o valor da revista.
A performace desta mágica é descrita em [3], como se segue: O mágico envia por
correio um baralho comum de cartas, em forma de pilha, a uma pessoa, solicitando-
lhe que realize algumas operações com o baralho. Primeiramente a pessoa deve cortar o
baralho quantas vezes desejar, realizar um embaralhamento canônico e cortar novamente
quantas vezes desejar. Em seguida a pessoa deve dar um corte reto dividindo o baralho
em dois montes, selecionar uma carta no centro de um dos montes, memorizá-la, e
coloca-lá no centro do outro monte. A pessoa escolhe um dos dois montes, realiza mais
um embaralhamento canônico e retorna este monte ao mágico, sem revelar se nele está
ou não contida a carta memorizada. Em seguida, o mágico envia-lhe o nome correto
da carta que a pessoa havia escolhido.
O truque Leitor de mentes a longa distância foi a base para a mágica Premo,
pois em sua realização também se utiliza o conceito de sequências levantadoras. Será a
partir deste conceito que na próxima seção responderemos à seguinte questão: qual a
probabilidade de obtermos o baralho em uma pilha desejada, após um certo número de
embaralhamentos canônicos?
17
1.3.1 Sequências levantadoras e o modelo GSR
18
assim teriamos um monte vazio e outro com n cartas, dessa forma a única maneira de
intercalar os dois montes seria retomando a configuração inicial. Cada um desses dois
1
casos tem probabilidade igual a 2n
. Outra maneira seria dividir a pilha em montes de
k e n − k cartas, com k ∈ {1, 2, · · · , n}, e depois apenas sobrepor o monte com k cartas
(n)
sobre o monte com n − k cartas. Escolhemos k com probabilidade 2kn e em seguida
devemos sobrepor os dois montes.
Segundo a Definição 5, ao intecalar os dois montes adicionamos a cada vez uma
carta vinda do monte 1 ou do monte 2 com probabilidade proporcional ao número de
cartas em cada monte, assim, como no primeiro monte temos k cartas e no segundo
monte temos n − k cartas, para toda intercalação possı́vel teremos a probabilidade
−1
k(k − 1) · · · 1(n − k)(n − k − 1) · · · 1 k!(n − k)! n
= = .
n(n − 1) · · · (n − k) · · · 1 n! k
Portanto, após o corte reto, a probabilidade de intercalar montes com tamanhos k e
−1
n − k de maneira a formar uma configuração especı́fica é nk .
Ou seja, para essa maneira, a probabilidade de retornar a configuração inicial é
n −1
k n 1
n
= n,
2 k 2
e observe que temos n − 1 opções para k. Portanto, a probabilidade de um emba-
ralhamento canônico gerar uma configuração com apenas uma sequência levantadora
é:
n−1
1 1 X 1 1
n
+ n
+ n
= (n + 1) n .
2 2 k=1
2 2
Suponhamos agora que após um embaralhamento canônico o baralho apresente
uma permutação fixa que possua duas sequências levantadoras, uma com as cartas de
1 a k e a outra com as cartas de k + 1 a n. Neste caso o baralho foi cortado na k-
(n)
ésima carta, o que ocorre com probabilidade 2kn . Após o corte temos que intercalar as
cartas de maneira a formar a configuração apresentada pelo baralho, e, como mostrado
−1
anteriormente, isso acontece com probabilidade nk .
Portanto, a probabilidade de que um embaralhamento canônico gere uma per-
mutação especı́fica com duas sequências levantadoras é
n −1
k n 1
= .
2n k 2n
19
O Teorema 2 afirma que a probabilidade de obtermos as configurações σ e ρ a
partir da realização de um embaralhamento canônico são as mesmas, se σ e ρ possuem
o mesmo número de sequências levantadoras. Além disso, este teorema diz que fixado
o tamanho do baralho, a probabilidade de obtermos uma permutação ρ especı́fica de
Sn após a realização de um embaralhamento canônico depende apenas do número de
sequências levantadoras de ρ.
f : [0, 1] → [0, 1] ,
20
b) Descrição da máxima entropia: todas as possı́veis maneiras de cortar um bara-
lho em a montes e intercalá-los são igualmente prováveis, permitindo que haja montes
vazios inclusive, ou seja, formados por nenhuma carta.
c) Descrição inversa: considerando um baralho embaralhado, todas as possı́veis
maneiras de colocá-lo separadamente em a montes são igualmente prováveis, permitindo
que haja montes vazios.
Uma maneira de realizarmos um a-embaralhamento inverso é a seguinte: dado
um baralho de tamanho n em uma pilha, retiramos as cartas uma a uma, virando-
as de modo a ficar com a face voltada para cima e em seguida escolhemos um dos a
montes, dispostos lado a lado, para colocá-la de modo uniforme e independente. Após
distribuirmos todas as cartas, sobrepomos os a montes da esquerda para a direita e o
baralho, completo mais uma vez, é virado de modo a ficar com as faces voltadas para
baixo novamente.
d) Descrição sequencial: escolhemos inteiros ji , com 0 ≤ ji ≤ n e 1 ≤ i ≤ a, de
acordo com a distribuição multinomial
n
j1 ,...,ja
P (j1 , ..., ja ) = ,
an
a
X
sendo ji = n.
i=1
Escolhidos os ji0 s, cortamos as j1 primeiras cartas do baralho, em seguida cortamos
as j2 próximas cartas, e assim por diante, produzindo assim a montes, cada um deles
com ji cartas, com i = 1, 2, · · · , a . Embaralhamos os montes de tamanho j1 e j2
segundo o modelo GSR de modo a formar um único monte, em seguida embaralhamos
o monte resultante com o monte que possui j3 cartas, e assim sucessivamente até obter
uma pilha de tamanho n. Esse procedimento é equivalente a embaralhar todos os a
montes juntamente de uma só vez.
O método apresentado na descrição sequencial é comum e eficaz para embara-
lharmos muitas cartas. Por exemplo, em cassinos nos jogos em que são utilizados dois
baralhos, 104 cartas, é comum dividir o baralho em quatro montes, A, B, C e D, e emba-
ralhar os montes A e B juntamente, e os montes C e D juntamente e depois embaralhar
os dois montes resultantes.
21
O seguinte teorema relaciona as quatro descrições alternativas para o modelo GSR
apresentadas acima. Esse teorema é originalmente apresentado em [1].
Demonstração. Mostraremos que cada uma das descrições resulta em um número mul-
tinomial de cartas em cada monte, e já sabemos que isto é por definição a descrição
sequencial.
Considere a descrição inversa, para cada uma das n cartas devemos escolher inde-
1
pendentemente um dos a montes para colocá-la com probabilidade a
para cada monte.
Denotando por Xi o número de cartas do monte i, com 1 ≤ i ≤ a, temos que,
P (X1 = j1 ; X2 = j2 ; · · · ; Xa = ja ) =
n 1 n − j1 1 n − j1 − j2 − · · · − ja−1 1
× j1 × × j2 × · · · × × ja =
j1 a j2 a ja a
n 1
.
j1 , ..., ja an
Para a descrição geométrica, o tamanho dos montes é determinado pelo número
de pontos em cada intervalo i−1 , ai , com i ∈ {1, 2, · · · , a}. Novamente, temos n pontos
a
para distribuir de maneira independente e com distribuição uniforme no intervalo [0, 1],
e portanto temos que a probabilidade de cada ponto cair em um intervalo i−1 i
1
a
, a
é a .
De maneira análoga à descrição inversa, encontramos a distribuição multinomial para
o número de cartas de cada monte.
Considerando agora a descrição da máxima entropia, o número de possı́veis inter-
calações a partir de um dado corte é multinomial, existe uma bijeção com as maneiras
de se dividir o baralho em a montes com o tamanho do monte correspondente. Isto
mostra a primeira parte.
Dado os tamanhos dos montes, a descrição da máxima entropia assegura que
todas as formas de intercalar são igualmente prováveis, assim como na descrição inversa.
Consideremos a descrição sequencial, quando embaralhamos os dois primeiros montes,
22
de tamanhos j1 e j2 , a probabilidade de aparecer qualquer sequência especı́fica da
esquerda para a direita é
−1
j1 (j1 − 1) · · · 1 · j2 (j2 − 1) · · · 1 j1 + j2
= .
(j1 + j2 )(j1 + j2 − 1) · · · 1 j1
Quando essas cartas são embaralhadas com o terceiro monte, de tamanho j3 , analo-
−1
gamente ao feito acima, temos que todas as j1 +jj32 +j3 posições para as cartas são
igualmente prováveis, e esse processo continua para cada monte sucessivo.
Pelo já mostrado, a regra do produto para uma sequência de embaralhamentos
vale em cada um desses modelos uma vez que vale para um deles. Isso sai facilmente
da descrição inversa: primeiramente dividimos o baralho, carta a carta, em a montes e
depois empilhamos estes montes de forma que o primeiro monte fica sobre o segundo
monte e assim por diante até terminar com o a-ésimo monte, o último. Em seguida
dividimos o baralho novamente, carta a carta, mas desta vez em b montes, então as
cartas que estavam no primeiro monte serão divididas em b montes, as cartas que
estavam no segundo monte serão divididas em b montes, e assim por diante, até finalizar
com as cartas do a-ésimo monte, o que é equivalente a produzir ab montes. A Figura
1.6 ilustra um ab-embaralhamento.
23
Figura 1.6: ab-embaralhamento inverso
24
n + 1 espaçamentos onde a − r cortes podem ser alocados arbitrariamente, mas observe
que esse processo equivale a termos n + a − r objetos, n do tipo 1 (cartas) e a − r do
tipo 2 (cortes) e escolhermos a − r posições para colocar os objetos do tipo 2, e sabemos
que existem a+n−r
n
maneiras de se fazer isso.
Portanto, o número de maneiras de cortar o baralho em a montes de modo que ϕ
seja uma intercalação possı́vel é a+n−r
n
. Como existem an possı́veis a−embaralhamentos
para um baralho de tamanho n, temos que a probabilidade de se obter a permutação
ϕ com um a-embaralhamento é
a+n−r
n
.
an
25
O Corolário 2 generaliza o Teorema 2, pois mostra que, fixado o tamanho do
baralho, a probabilidade de obtermos uma permutação especı́fica de Sn a partir de con-
secutivos embaralhamentos canônicos também depende apenas do número de sequências
levantadoras da permutação resultante. Relembrando a primeira pergunta, “qual a pro-
babilidade de obtermos o baralho em uma ordem desejada após um certo número de
embaralhamentos?”, o Corolário 2 é a melhor resposta, pois reflete a maneira mais
usual de se embaralhar, através de embaralhamentos canônicos. Respondida à primeira
pergunta, no próximo capı́tulo vamos apresentar as ferramentas necessárias para se res-
ponder a próxima questão a ser abordada neste trabalho: como embaralhar bem um
baralho?
26
Capı́tulo 2
Cadeias de Markov e
embaralhamentos
27
Markov, baseado em [6], que irá nos possibilitar relacionar Cadeias de Markov com o
embaralhamento canônico, e seguindo a estratégia usada em [4] e [6], mostraremos que
para analisar o embaralhamento canônico basta analisar o embaralhamento canônico
inverso.
A fim de evitar ambiguidades nas definições que faremos sobre Cadeias de Markov,
passaremos a denotar elementos de Sn por letras do nosso alfabeto ao invés de letras
do alfabeto grego. Também passaremos a omitir o sinal de composição entre duas
permutações, sempre que estiver claro a operação que desejamos realizar.
28
ou iguais a zero e
X
P (x, y) = 1 ∀x ∈ Ω.
y∈Ω
Definição 10 (Passeios aleatórios em grupos). Seja (G, ◦) um grupo finito. Dada uma
distribuição de probabilidade µ em G, definimos o passeio aleatório em G como uma
Cadeia de Markov cujo espaço de estados é G e que move do seu estado atual para o
próximo compondo o estado atual pela esquerda por um elemento de G de acordo com
µ. Isto é, a matriz de transição P para essa cadeia tem entradas
P (g, h) = µ(h ◦ g −1 ).
29
Seja (X0 , X1 , · · · ) uma Cadeia de Markov finita com espaço de estados Ω e matriz
de transição P, e seja µt a distribuição de Xt , ou seja,
µt (x) = P (Xt = x) ∀x ∈ Ω.
µt = µ0 P t (2.2)
30
Definição 12 (Cadeia de Markov Aperiódica). Considere uma Cadeia de Markov com
espaço de estados Ω. Se x ∈ Ω, definimos T (x) = t ≥ 1; Pt (x, x) > 0 como o conjunto
dos tempos em que é possı́vel que a Cadeia retorne ao estado x. O perı́odo do estado x
é o maior divisor comum de T (x). Dizemos que a Cadeia é aperiódica quando o perı́odo
de todo x ∈ Ω é igual a um.
É fácil ver que o passeio aleatório em Sn é uma cadeia aperiódica, pois para todo
x ∈ Sn temos que P (x, x) > 0. Este fato foi provado na demonstração do Teorema 2
ao calcularmos como obter a mesma pilha após um embaralhamento canônico. Sendo
assim, 1 ∈ T (x) ∀ x ∈ Sn .
Pelo Teorema 2, temos que para todo x ∈ Sn , tal que x possui uma ou duas sequências
levantadoras, P(id, x) > 0, sendo assim, já provamos que para as permutações de Sn
com uma ou duas sequências levantadoras existe t tal que Pt (id, x) > 0, neste caso
t = 1.
Agora consideremos uma permutação com r sequências levantadoras. Pelo Co-
rolário 2, tomando t tal que
2t +n−r
n
> 0,
2tn
ou seja, 2t − r ≥ 0, temos então que Pt (id, x) > 0. Ou seja, se x possui r sequências
levantadoras, tomando t ≥ log2 r, t ∈ N, temos Pt (id, x) > 0. Sendo assim, para toda
permutação x ∈ Sn podemos encontrar um t tal que Pt (id, x) > 0, ou seja, o passeio
aleatório em Sn é uma Cadeia de Markov irredutı́vel.
31
Definição 13 (Distribuição Estacionária). Seja (X1 , X2 , · · · ) uma Cadeia de Markov
com matriz de transição P. Uma distribuição de probabilidade ν em Ω é uma distri-
buição estacionária de P se ν satisfaz ν = νP.
Observe que se ν é a distribuição estacionária para uma Cadeia de Markov com matriz
de transição P e µ0 = ν, então, pela Equação 2.2, µt = ν para todo t ≥ 0.
Relembrando a distribuição uniforme definida no ı́nicio deste capı́tulo, o teorema
a seguir assegura que a distribuição uniforme é a distribuição estacionária para um
passeio aleatório em um grupo, em particular, temos que a distribuição uniforme é a
distribuição estacionária para o passeio aleatório em Sn .
X X 1
π(h)P(h, g) = P(h, g)
h∈G h∈G
|G|
1 X
= P(k −1 g, g)
|G| k∈G
1 X
= µ(k)
|G| k∈G
1
=
|G|
= π(g),
32
Finalizamos esta seção com um resultado originalmente apresentado em [1] que
relaciona sequências levantadoras e Cadeias de Markov. Não apresentaremos a demons-
tração deste teorema pois durante a sua prova não utilizamos resultados relevantes ao
estudo realizado nesta dissertação. A base da demostração é o Lema 1 da referência
[7].
33
Mostraremos que essa distribuição é coerente com o embaralhamento canônico
inverso, ou seja, que a distribuição de probabilidade induzida pelo embaralhamento
canônico inverso a partir da permutação identidade é dada por Q∗ (x) = Q(x−1 ):
(n + 1) 21n , se x−1 apresenta uma sequência levantadora
Q∗ (x) = 1
2n
, se x−1 apresenta duas sequências levantadoras
0, caso contrário.
W1 = 0, W2 = 0, · · · , Wj = 0, Wj+1 = 1, · · · , Wn = 1, (2.3)
n+1
com j = 0, 1, · · · , n. Portanto, temos probabilidade de 2n
de obtermos a permutação
identidade após a realização de um embaralhamento canônico inverso.
Para as sequências distintas das do tipo apresentado na Expressão 2.3, após asso-
ciarmos à cada carta i a variável aleatória Wi e colocarmos as cartas com Wi = 0 por
cima das cartas com Wi = 1, a pilha resultante será dada por uma permutação x ∈ Sn ,
x 6= id. Observe que a posição das cartas que são associadas à variável aleatória
Wi = 0 formam uma sequência levantadora em x−1 , enquanto a posição das cartas
que são associadas à variável aleatória Wj = 1 formam outra sequência levantadora na
permutação x−1 , uma vez que preservamos a ordenação entre as cartas associadas às
variáveis aleatórias de mesmo valor.
34
nas posições 3, 5, 6 e 8 formam uma sequência levantadora em x−1 , enquanto as cartas
nas posições 1, 2, 4 e 7 formam outra sequência levantadora.
P∗ (x, y) = µ∗ (yx−1 ).
35
Pela definição de distribuição inversa, temos que µ∗ (yx−1 ) = µ(xy −1 ), e juntamente
com a definição da matriz de transição P, temos que
T
P2 = PT PT = P∗ P∗ = P∗2
ν(y)P(y, x)
Pr (x, y) = .
ν(x)
36
Como a distribuição estacionária para um passeio aleatório em um grupo G é a
1
distribuição uniforme π, onde ∀x ∈ G temos π(x) = |G|
, então pelo Teorema 8
1
∗ |G|
P(y, x) π(y)P(y, x)
P (x, y) = P(y, x) = 1 = = Pr (x, y).
|G|
π(x)
Observe que o passeio aleatório inverso também é uma Cadeia aperiódica, De-
finição 12, pois para todo x ∈ Sn , ao associarmos x à qualquer sequência do tipo 2.3
obtemos a pilha x novamente. Assim 1 ∈ T (x) ∀ x ∈ Sn , e portanto o passeio aleatório
inverso é uma Cadeia aperiódica.
O próximo resultado mostra que o passeio aleatório em Sn e o passeio inverso
compartilham a mesma distribuição estacionária, a distribuição uniforme.
Teorema 9. Sejam (Xt ) uma Cadeia de Markov irredutı́vel com matriz de transição P
e distribuição estacionária ν, e (Xt∗ ) a cadeia de tempo reverso com matriz de transição
P∗ . Sendo assim, ν é distribuição estacionária de P∗ e para x0 , · · · , xt ∈ Ω temos que
37
Como P∗ é a matriz de transição da cadeia do tempo reverso da matriz P, para
cada i temos
ν(xi )P∗ (xi , xi−1 )
P(xi−1 , xi ) = .
ν(xi−1 )
Logo,
Com todo o estudo desenvolvido durante esta seção, criamos um paralelo entre o
passeio aleatório induzido pelo embaralhamento canônico e o passeio aleatório inverso,
induzido pelo embaralhamento canônico inverso, que pode ser sintetizado na tabela a
seguir.
distribuição incremento Q Q∗
matriz de transição P(x, y) P∗ (x, y) = P(y, x)
irredutı́vel sim sim
distribuição estacionária distribuição uniforme distribuição uniforme
O objetivo deste capı́tulo é ver o quão perto podemos chegar da distribuição uni-
forme a partir da distribuição GSR. Com o paralelo entre o passeio aleatório e o passeio
inverso em Sn , provaremos mais adiante que para alcançar o nosso objetivo podemos
passar a analisar o embaralhamento canônico inverso, mas antes será necessário intro-
duzir uma maneira de medir a distância entre duas distribuições.
38
Em particular, se P é uma matriz de transição e ν sua distribuição estacionária, defi-
nimos
d(t) = max
P t (x, .) − ν
V T
x∈Ω
X X
µ(A) − ν(A) = µ(x) − ν(x)
x∈A x∈A
! !
X X X X
= µ(x) + µ(x) − ν(x) + ν(x)
x∈A∩B x∈A∩B c x∈A∩B x∈A∩B c
! !
X X X X
= µ(x) − ν(x) + µ(x) − ν(x) .
x∈A∩B x∈A∩B x∈A∩B c x∈A∩B c
39
Figura 2.1: Diferença entre duas distribuições
X X
µ(B) − ν(B) = µ(x) − ν(x)
x∈B x∈B
! !
X X X X
= µ(x) + µ(x) − ν(x) + ν(x)
x∈A∩B x∈Ac ∩B x∈A∩B x∈Ac ∩B
! !
X X X X
= µ(x) − ν(x) + µ(x) − ν(x) .
x∈A∩B x∈A∩B x∈Ac ∩B x∈Ac ∩B
A partir das Equações 2.5 e 2.6, concluimos então que µ(A) − ν(A) ≤ µ(B) − ν(B),
para todo evento A ⊂ Ω.
Pelo mesmo raciocı́nio acima podemos mostrar que
Observamos na Figura 2.1, extraı́da de [6], que a região I tem área µ(B) − ν(B)
e a região II, ν(B c ) − µ(B c ). Como as áreas totais abaixo de µ e ν têm valor 1, temos
que as regiões I e II possuem a mesma área. Logo, a cota superior para µ(B) − ν(B) e
40
ν(B c ) − µ(B c ) é a mesma, e portanto,
1
kµ − νkV T = [µ(B) − ν(B) + ν(B c ) − µ(B c )]
2
1X
= |µ(x) − ν(x)|.
2 x∈Ω
P (id, .) − π
=
P ∗t (id, .) − π
.
t
VT VT
P (id, .) − π
= 1
X
P t (id, a) − |G|−1 ,
t
VT 2 a∈G
mas, pelo Teorema 8 temos que P (x, y) = P ∗ (y, x), ∀x, y ∈ G. Logo P t (x, y) =
P ∗t (y, x), e portanto
P (id, .) − π
= 1
X
P ∗t (a, id) − |G|−1 .
t
VT
(2.8)
2 a∈G
P ∗ (a, id) = µ∗ (id ◦ a−1 ) = µ∗ (a−1 ) = µ∗ (a−1 ◦ id−1 ) = P ∗ (id, a−1 ). (2.9)
41
Pelas Equações 2.8 e 2.9, concluimos que
P (id, .) − π
= 1
X
P t (id, a) − |G|−1
t
VT 2 a∈G
1 X ∗t
P (id, a−1 ) − |G|−1 .
=
2 a∈G
P (id, .) − π
= 1
X
P ∗t (id, a) − |G|−1
t
VT 2 a∈G
=
P ∗t (id, .) − π
V T ,
lembrando que d(t) = maxx∈Ω kP t (x, .) − µkV T . Denotamos por tmix = tmix ( 14 ).
42
aleatórias com valores 0 ou 1, sendo que as cartas associadas à variável aleatória Wi = 0
serão posicionadas por cima das cartas associadas à variável aleatória Wi = 1. Para
o segundo embaralhamento, a cada carta i será associada uma variável aleatória Zi
tomando valores 0 ou 1, assim cada carta será associada a uma sequência de dois dı́gitos,
cada um deles podendo ser zero ou um. Observe que as cartas associadas à sequência
00 estarão por cima das associadas à 10, que estarão por cima das com sequência 01 e
por fim as associadas à sequência 11.
Após t embaralhamentos canônicos inversos consecutivos, cada carta estará asso-
ciada a uma sequência de t dı́gitos, cada um dos dı́gitos sendo zero ou um. Seja i uma
carta qualquer do baralho de tamanho n, denotaremos por
1. s(i) = s(j) e i < j, ou seja i já estava a frente da carta j na pilha original.
2. s(i) 6= s(j) e existe u ∈ {1, 2, · · · , t} tal que su (i) = 0 e su (j) = 1, sendo que
sv (i) = sv (j) ∀v ∈ {u + 1, · · · , t}.
43
ser alcançadas, a saber, aquelas nas quais as cartas que possuem a mesma sequência
aparecem em ordem decrescente. Sendo assim, a distribuição uniforme só poderá ser
alcançada a partir do momento em que todas as cartas estejam associadas a sequências
distintas. Dessa forma, é interessante saber qual é a probabilidade de se obter sequências
distintas para cada carta após um número qualquer de embaralhamentos canônicos in-
versos consecutivos. O teorema abaixo é a resposta para esta questão.
maneiras de atribuirmos sequências a todas as cartas sem que haja repetição. Logo,
a probabilidade de que com t embaralhamentos canônicos inversos cada carta possua
uma sequência distinta é
Na próxima seção iremos encontrar o valor t para o qual todas as cartas possuam
sequências distintas com alta probabilidade.
44
2.3 A distância da uniformidade
O principal objetivo desta seção é encontrar cotas para o tempo de mistura do embara-
lhamento canônico inverso, e, pelo Corolário 4, também do embaralhamento canônico.
A cota superior é dada pelo teorema a seguir.
Teorema 13. Considere um baralho de tamanho n, vale a seguinte cota superior para
o tempo de mistura do embaralhamento canônico
4n
tmix ≤ 2 log2 ,
3
para n suficientemente grande.
Definição 19. Considere uma Cadeia de Markov finita no espaço de estados Ω, com
matriz de transição P. Um mapa de representação aleatória da matriz de transição P
é uma função f : Ω × Λ −→ Ω, juntamente com uma variável aleatória Z que toma
valores em Λ, satisfazendo
Teorema 14. Toda matriz de transição em um espaço de estados finito possui um mapa
de representação aleatória.
45
Observe que se Z1 , Z2 , · · · são variáveis aleatórias i.i.d. com a mesma distribuição
que a variável aleatória Z definida na Definição 19 e X0 com distribuição µ, µ(x) =
P (X0 = x), então a sequência (X0 , X1 , · · · ) definida por
Xn = f (Xn−1 , Zn ),
= P (f (xt , Z) = xt+1 )
= P(xt , xt+1 ).
a sequência (Xt )∞
t=0 definida indutivamente por X0 = x e Xt = f (Xt−1 , Zt ) seja uma
{0, 1, 2, · · · , ∞} é um tempo de parada para (Xt ) se, para cada t ∈ {0, 1, · · · }, existe
um conjunto Bt ⊂ Ωt+1 tal que {τ = t} = {(X0 , · · · , Xt ) ∈ Bt }. Um tempo de parada
aleatório para uma Cadeia de Markov é o tempo de parada para a sequência (Zt ) definida
acima.
46
1
2n
, se y pode ser obtido ao associarmos a x uma sequência de zeros e uns
P(x, y) = n+1
2n
, se y = x
0, caso contrário.
uma vez que cada sequências em {0, 1}n , distintas daquelas como na Expressão ??, pro-
duz uma permutação distinta ao ser aplicada a x, e as sequências do tipo ?? produzem
a permutação x novamente.
Seja (Zt ) uma sequência de variáveis aleatórias independentes e uniformes em
{0, 1}n . Se o estado atual do passeio é x, denotando por x ◦ z o embaralhamento
canônico inverso regido pela sequência z ∈ {0, 1}n a partir da permutação x, temos que
P (x ◦ Z = y) = P(x, y).
o primeiro tempo em que cada carta i possui uma sequência binária s(i) distinta.
Observe que τ não é uma função do passeio aleatório (Xt ), mas da sequência (Zt )
de zeros e uns atribuida em cada tempo t. A partir da Definição 20, podemos agora
definir um Tempo Estacionário Forte.
Px (τ = t, Xτ = y) = Px (τ = t)ν(y).
47
Podemos relacionar os conceitos definidos acima com o embaralhamento canônico
inverso, como mostra o teorema a seguir.
Teorema 15. Seja τ como definido na Definição 21, então τ é um tempo estacionário
forte para o passeio aleatório inverso em Sn .
Lema 1. Seja (Xt ) uma Cadeia de Markov irredutı́vel com distribuição estacionária ν.
Se τ é um tempo estacionário forte para (Xt ), então para todo t ≥ 0,
Px (τ ≤ t, Xt = y) = Px (τ ≤ t)ν(y).
Pela definição de tempo estacionário forte, τ é um tempo de parada para (Zt ), logo
o evento {τ = q} é da forma {(Z1 , · · · , Zq ) ∈ B} para algum B ⊂ Ωq . Também, para
inteiros q, u ≥ 0, existe uma função fu : Ωu+1 → Ω, tal que
48
Uma vez que os vetores (Z1 , · · · , Zq ) e (Zq+1 , · · · , Zt ) são independentes, temos que
Px (τ = q, Xq = z) = Px (τ = q)ν(z), (2.11)
Como ν é a distribuição estacionária para esta Cadeia, temos que ν satisfaz ν = νP t−q .
Portanto, o lado direito da equação acima é igual a ν(y)Px (τ = q). Sendo assim,
X
Px (τ ≤ t, Xt = y) = Px (τ = q, Xt = y)
q≤t
X
= ν(y)Px (τ = q)
q≤t
X
= ν(y) Px (τ = q)
q≤t
= ν(y)Px (τ ≤ t).
49
X
d(t) =
P t (x, .) − ν
V T = ν(y) − P t (x, y)
y∈Ω; P t (x,y)<ν(y)
P t (x, y)
X
= ν(y) 1 −
ν(y)
y∈Ω; P t (x,y)<ν(y)
P t (x, y)
≤ max 1 − .
y ν(y)
Agora observe que para todo y ∈ Ω temos
P t (x, y) Px (Xt = y) Px (Xt = y, τ ≤ t)
1− =1− ≤1− .
ν(y) ν(y) ν(y)
Pelo Lema 1, sabemos que Px (Xt = y, τ ≤ t) = ν(y)Px (τ ≤ t), logo
P t (x, y) ν(y)Px (τ ≤ t)
1− ≤1− = Px (τ > t).
ν(y) ν(y)
Sendo assim,
P t (x, y)
t
d(t) = P (x, .) − ν V T ≤ max 1 −
y ν(y)
≤ max Px (τ > t).
x∈Ω
n2
a notação. Temos então que t = 2 log2 ( nc ), logo 2t = c2
, assim temos
50
n−1
Y n−1
i X i
log 1− t = log 1 − t
i=0
2 i=0
2
n−1
( 2 )
X c2 i i
=− 2
+O 2
i=1
n n
c2 n(n − 1)
3
n
=− 2
+O
2n n4
c2
1
=− +O .
2 n
Logo, como tanto c quanto P (τ ≤ t) são funções em n, tirando o limite quando n tende
a infinito,
P (τ ≤ t)
lim c2
= 1,
n→∞
e− 2
obtemos um valor assintótico para P (τ ≤ t).
O Teorema 16 nos diz que d(t) ≤ maxx∈Ω Px (τ > t), pelo o que fizemos até o
momento, temos então que
c2
d(t) ≤ 1 − e− 2 .
Como tmix = min t, d(t) ≤ 41 , tomando qualquer valor de c tal que c seja menor que
q
2 log( 34 ), teremos uma cota para o tmix . Um valor conveniente é c = 34 , e como
definimos acima que t = 2 log2 ( nc ), temos o resultado.
Lema 2. Seja (Xt ) uma Cadeia de Markov irredutı́vel e aperiódica, com espaço de
estados Ω, e suponha que π, a distribuição uniforme, seja a distribuição estacionária
51
para esta Cadeia. Denotamos por dout (x) = |{y; P(x, y) > 0}| o número de estados
acessı́veis por x com apenas um passo e Ωxt o conjunto dos estados que podem ser
alcançados a partir de x com t passos e seja ∆ = maxx∈Ω dout (x). Se ∆t < (1 − ) |Ω|,
então
log |Ω| (1 − )
tmix () ≥ .
log ∆
Demonstração. Observe que |Ωxt | ≤ ∆t . Como ∆t < (1 − ) |Ω|, pela definição de
Distância de Variação Total temos que
∆t
d(t) =
Pt (x, .) − π
V T ≥ Pt (x, Ωxt ) − π(Ωxt ) ≥ 1 − > .
|Ω|
Portanto,
log [|Ω| (1 − )]
tmix () ≥ .
log ∆
temos
52
−
Seja 0 < δ < 1, observe que para n suficientemente grande temos o(1) ≥ 2
, e o mesmo
log2 (1−)
ocorre para n log2 n
. Logo
log2 (1 − )
− o(1) + ≤ δ.
n log2 n
53
Apêndice
No artigo [1] os autores apresentam uma estratégia diferente para fazer a aproximação
da distribuição uniforme. A partir do Corolário 2 e da Equação 2.7, a terceira caracte-
rização de Distância de Variação Total, eles encontram
X 2t + n − r 1
−tn
d(t) = 2 − αr ,
n∈X
n n!
t 1 2 3 4 5 6 7 8 9 10
d(t) 1,000 1,000 1,000 1,000 0,924 0,614 0,334 0,167 0,085 0,043
54
Referências Bibliográficas
[1] Bayer, D.; Diaconis, P., Trailing the Dovetail Shuffle to its Lair, The
Annals of Applied Probability , Vol.2, No. 2, 294-313, 1992.
[6] Levin, D. A.; Peres, Y.; Wilmer, E. L.,Markov Chains and Mixing
Times, American Mathematical Society, 2008.
55