Mixing time of the torus shuffle Article Swipe

PDF

Olena Blumberg , Ben Morris , Alto Senda ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2411.06006

We prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only triplets of cards. Then we use it to analyze a classic model of card shuffling. In 1988, Diaconis introduced the following Markov chain. Cards are arranged in an $n$ by $n$ grid. Each step, choose a row or column, uniformly at random, and cyclically rotate it by one unit in a random direction. He conjectured that the mixing time is ${\rm O}(n^3 \log n)$. We obtain a bound that is within a poly log factor of the conjecture.

Related Topics

Concepts

Torus Mixing (physics) Mathematics Geometry Physics Combinatorics Quantum mechanics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2411.06006
PDF: https://arxiv.org/pdf/2411.06006
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4404390827

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4404390827

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2411.06006

Digital Object Identifier
Title: Mixing time of the torus shuffle

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-11-08

Full publication date if available
Authors: Olena Blumberg, Ben Morris, Alto Senda

List of authors in order
Landing page: https://arxiv.org/abs/2411.06006

Publisher landing page
PDF URL: https://arxiv.org/pdf/2411.06006

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2411.06006

Direct OA link when available
Concepts: Torus, Mixing (physics), Mathematics, Geometry, Physics, Combinatorics, Quantum mechanics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4404390827
doi	https://doi.org/10.48550/arxiv.2411.06006
ids.doi	https://doi.org/10.48550/arxiv.2411.06006
ids.openalex	https://openalex.org/W4404390827
fwci
type	preprint
title	Mixing time of the torus shuffle
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T12250
topics[0].field.id	https://openalex.org/fields/31
topics[0].field.display_name	Physics and Astronomy
topics[0].score	0.6876999735832214
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/3109
topics[0].subfield.display_name	Statistical and Nonlinear Physics
topics[0].display_name	Experimental and Theoretical Physics Studies
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C9767117
concepts[0].level	2
concepts[0].score	0.8139930367469788
concepts[0].wikidata	https://www.wikidata.org/wiki/Q12510
concepts[0].display_name	Torus
concepts[1].id	https://openalex.org/C138777275
concepts[1].level	2
concepts[1].score	0.7711704969406128
concepts[1].wikidata	https://www.wikidata.org/wiki/Q6884054
concepts[1].display_name	Mixing (physics)
concepts[2].id	https://openalex.org/C33923547
concepts[2].level	0
concepts[2].score	0.39992332458496094
concepts[2].wikidata	https://www.wikidata.org/wiki/Q395
concepts[2].display_name	Mathematics
concepts[3].id	https://openalex.org/C2524010
concepts[3].level	1
concepts[3].score	0.36225903034210205
concepts[3].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[3].display_name	Geometry
concepts[4].id	https://openalex.org/C121332964
concepts[4].level	0
concepts[4].score	0.3405710756778717
concepts[4].wikidata	https://www.wikidata.org/wiki/Q413
concepts[4].display_name	Physics
concepts[5].id	https://openalex.org/C114614502
concepts[5].level	1
concepts[5].score	0.3233642578125
concepts[5].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[5].display_name	Combinatorics
concepts[6].id	https://openalex.org/C62520636
concepts[6].level	1
concepts[6].score	0.0
concepts[6].wikidata	https://www.wikidata.org/wiki/Q944
concepts[6].display_name	Quantum mechanics
keywords[0].id	https://openalex.org/keywords/torus
keywords[0].score	0.8139930367469788
keywords[0].display_name	Torus
keywords[1].id	https://openalex.org/keywords/mixing
keywords[1].score	0.7711704969406128
keywords[1].display_name	Mixing (physics)
keywords[2].id	https://openalex.org/keywords/mathematics
keywords[2].score	0.39992332458496094
keywords[2].display_name	Mathematics
keywords[3].id	https://openalex.org/keywords/geometry
keywords[3].score	0.36225903034210205
keywords[3].display_name	Geometry
keywords[4].id	https://openalex.org/keywords/physics
keywords[4].score	0.3405710756778717
keywords[4].display_name	Physics
keywords[5].id	https://openalex.org/keywords/combinatorics
keywords[5].score	0.3233642578125
keywords[5].display_name	Combinatorics
language	en
locations[0].id	pmh:oai:arXiv.org:2411.06006
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2411.06006
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2411.06006
locations[1].id	doi:10.48550/arxiv.2411.06006
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2411.06006
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5082562712
authorships[0].author.orcid
authorships[0].author.display_name	Olena Blumberg
authorships[0].author_position	first
authorships[0].raw_author_name	Blumberg, Olena
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5044639892
authorships[1].author.orcid	https://orcid.org/0000-0002-9850-6071
authorships[1].author.display_name	Ben Morris
authorships[1].author_position	middle
authorships[1].raw_author_name	Morris, Ben
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5114654013
authorships[2].author.orcid
authorships[2].author.display_name	Alto Senda
authorships[2].author_position	last
authorships[2].raw_author_name	Senda, Alto
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2411.06006
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Mixing time of the torus shuffle
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T12250
primary_topic.field.id	https://openalex.org/fields/31
primary_topic.field.display_name	Physics and Astronomy
primary_topic.score	0.6876999735832214
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/3109
primary_topic.subfield.display_name	Statistical and Nonlinear Physics
primary_topic.display_name	Experimental and Theoretical Physics Studies
related_works	https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2167530280, https://openalex.org/W3124916295, https://openalex.org/W2142036596, https://openalex.org/W2022411416
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2411.06006
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2411.06006
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2411.06006
primary_location.id	pmh:oai:arXiv.org:2411.06006
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2411.06006
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2411.06006
publication_date	2024-11-08
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	2, 11, 16, 30, 56, 71, 87, 92
abstract_inverted_index.He	74
abstract_inverted_index.In	36
abstract_inverted_index.We	0, 85
abstract_inverted_index.an	48
abstract_inverted_index.at	61
abstract_inverted_index.by	50, 67
abstract_inverted_index.in	47, 70
abstract_inverted_index.is	80, 90
abstract_inverted_index.it	27, 66
abstract_inverted_index.of	10, 22, 33, 96
abstract_inverted_index.or	58
abstract_inverted_index.to	14, 28
abstract_inverted_index.we	25
abstract_inverted_index.$n$	49, 51
abstract_inverted_index.and	63
abstract_inverted_index.are	45
abstract_inverted_index.log	94
abstract_inverted_index.one	68
abstract_inverted_index.row	57
abstract_inverted_index.the	7, 40, 77, 97
abstract_inverted_index.use	26
abstract_inverted_index.Each	53
abstract_inverted_index.Then	24
abstract_inverted_index.\log	83
abstract_inverted_index.card	12, 34
abstract_inverted_index.n)$.	84
abstract_inverted_index.only	20
abstract_inverted_index.poly	93
abstract_inverted_index.that	4, 18, 76, 89
abstract_inverted_index.time	9, 79
abstract_inverted_index.unit	69
abstract_inverted_index.${\rm	81
abstract_inverted_index.1988,	37
abstract_inverted_index.Cards	44
abstract_inverted_index.bound	88
abstract_inverted_index.grid.	52
abstract_inverted_index.model	32
abstract_inverted_index.prove	1
abstract_inverted_index.step,	54
abstract_inverted_index.Markov	42
abstract_inverted_index.O}(n^3	82
abstract_inverted_index.cards.	23
abstract_inverted_index.chain.	43
abstract_inverted_index.choose	55
abstract_inverted_index.factor	95
abstract_inverted_index.mixing	8, 78
abstract_inverted_index.obtain	86
abstract_inverted_index.random	72
abstract_inverted_index.rotate	65
abstract_inverted_index.within	91
abstract_inverted_index.analyze	29
abstract_inverted_index.classic	31
abstract_inverted_index.column,	59
abstract_inverted_index.random,	62
abstract_inverted_index.reduces	5
abstract_inverted_index.shuffle	13
abstract_inverted_index.theorem	3
abstract_inverted_index.Diaconis	38
abstract_inverted_index.arranged	46
abstract_inverted_index.bounding	6
abstract_inverted_index.involves	19
abstract_inverted_index.triplets	21
abstract_inverted_index.condition	17
abstract_inverted_index.following	41
abstract_inverted_index.uniformly	60
abstract_inverted_index.verifying	15
abstract_inverted_index.cyclically	64
abstract_inverted_index.direction.	73
abstract_inverted_index.introduced	39
abstract_inverted_index.shuffling.	35
abstract_inverted_index.conjecture.	98
abstract_inverted_index.conjectured	75
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile