On the mixing time of the Diaconis-Gangolli random walk on contingency tables over Z/qZ

Evita Nestoridi; Oanh Nguyen

doi:10.1214/19-AIHP991

On the mixing time of the Diaconis-Gangolli random walk on contingency tables over Z/qZ

Evita Nestoridi, Oanh Nguyen

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

The Diaconis-Gangolli random walk is an algorithm that generates an almost uniform random graph with prescribed degrees. In this paper, we study the mixing time of the Diaconis-Gangolli random walk restricted on n × n contingency tables over Z/qZ. We prove that the random walk exhibits cutoff at (Equation presented) log n, when log (Equation presented).

Original language	English (US)
Pages (from-to)	983-1001
Number of pages	19
Journal	Annales de l'institut Henri Poincare (B) Probability and Statistics
Volume	56
Issue number	2
DOIs	https://doi.org/10.1214/19-AIHP991
State	Published - 2020

All Science Journal Classification (ASJC) codes

Statistics and Probability
Statistics, Probability and Uncertainty

Keywords

Contingency table
Cutoff
Mixing time
Random graphs

Access to Document

10.1214/19-AIHP991

Cite this

@article{5f6b9f2815224c6cad902a063621e229,

title = "On the mixing time of the Diaconis-Gangolli random walk on contingency tables over Z/qZ",

abstract = "The Diaconis-Gangolli random walk is an algorithm that generates an almost uniform random graph with prescribed degrees. In this paper, we study the mixing time of the Diaconis-Gangolli random walk restricted on n × n contingency tables over Z/qZ. We prove that the random walk exhibits cutoff at (Equation presented) log n, when log (Equation presented).",

keywords = "Contingency table, Cutoff, Mixing time, Random graphs",

author = "Evita Nestoridi and Oanh Nguyen",

note = "Publisher Copyright: {\textcopyright} Association des Publications de l'Institut Henri Poincar{\'e}, 2020.",

year = "2020",

doi = "10.1214/19-AIHP991",

language = "English (US)",

volume = "56",

pages = "983--1001",

journal = "Annales de l'institut Henri Poincare (B) Probability and Statistics",

issn = "0246-0203",

publisher = "Institute of Mathematical Statistics",

number = "2",

}

TY - JOUR

T1 - On the mixing time of the Diaconis-Gangolli random walk on contingency tables over Z/qZ

AU - Nestoridi, Evita

AU - Nguyen, Oanh

N1 - Publisher Copyright: © Association des Publications de l'Institut Henri Poincaré, 2020.

PY - 2020

Y1 - 2020

N2 - The Diaconis-Gangolli random walk is an algorithm that generates an almost uniform random graph with prescribed degrees. In this paper, we study the mixing time of the Diaconis-Gangolli random walk restricted on n × n contingency tables over Z/qZ. We prove that the random walk exhibits cutoff at (Equation presented) log n, when log (Equation presented).

AB - The Diaconis-Gangolli random walk is an algorithm that generates an almost uniform random graph with prescribed degrees. In this paper, we study the mixing time of the Diaconis-Gangolli random walk restricted on n × n contingency tables over Z/qZ. We prove that the random walk exhibits cutoff at (Equation presented) log n, when log (Equation presented).

KW - Contingency table

KW - Cutoff

KW - Mixing time

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=85082526201&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85082526201&partnerID=8YFLogxK

U2 - 10.1214/19-AIHP991

DO - 10.1214/19-AIHP991

M3 - Article

AN - SCOPUS:85082526201

SN - 0246-0203

VL - 56

SP - 983

EP - 1001

JO - Annales de l'institut Henri Poincare (B) Probability and Statistics

JF - Annales de l'institut Henri Poincare (B) Probability and Statistics

IS - 2

ER -

On the mixing time of the Diaconis-Gangolli random walk on contingency tables over Z/qZ

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this