# Cutoff in the Bernoulli-Laplace Model With Unequal Colors and Urn Sizes

Thomas Griffin  Iowa State University  Bailey Hall  Westmont College  Jackson
Hebner  University of Connecticut  David Herzog  Iowa State University  Denis
Selyuzhitsky  The Michigan State University  Kevin Wong  University of
California, Los Angeles  John Wright  The Ohio State University

###### Abstract

We consider a generalization of the Bernoulli-Laplace model in which there are
two urns and $n$ total balls, of which $r$ are red and $n-r$ white, and where
the left urn holds $m$ balls. At each time increment, $k$ balls are chosen
uniformly at random from each urn and then swapped. This system can be used to
model phenomena such as gas particle interchange between containers or card
shuffling. Under a reasonable set of assumptions, we bound the mixing time of
the resulting Markov chain asymptotically in $n$ with cutoff at $\log{n}$ and
constant window. Among other techniques, we employ the spectral analysis of
[4] on the Markov transition kernel and the chain coupling tools of [1] and
[6].

###### Contents

  1. 1 Introduction
  2. 2 Lemmata
    1. 2.1 Spectral Lemmata
    2. 2.2 Hypergeometric Comparison Lemmata
  3. 3 Bounds under Assumption 1.1
    1. 3.1 Lower Bound
    2. 3.2 Upper Bound
  4. 4 Bounds when $\gamma=h(1-h)>0$
    1. 4.1 The Lower Bound
    2. 4.2 The Upper Bound
  5. 5 Conclusion
    1. 5.1 Generalizations
    2. 5.2 Numerical Results
  6. 6 Acknowledgements

##  1 Introduction

In the classical Bernoulli-Laplace model, there are a total of $n$ balls split
evenly between a left and a right urn. Of these balls, ${n\over 2}$ are red
and ${n\over 2}$ are white. At each time increment, $k$ balls are selected
uniformly at random without replacement from each urn and then swapped between
the urns.

We consider a generalization of this model where the left urn holds $m$ balls
and the right urn $n-m$ balls, and where $r$ of the balls are red and $n-r$ of
the balls are white. As in the classical case, $k$ balls are selected from
both urns uniformly and without replacement to swap. Note that implicitly,
$m,r,k$ are sequences in $n$ but we will suppress the reliance. We will let
$X_{t}$ denote the number of red balls in the left urn after $t$ swaps.
Transition probabilities for this process are given by

$p(x,y)=\mathbb{P}(x-H_{1}^{x}+H_{2}^{x}=y)$ (1)

where $H_{1}^{x}$ and $H_{2}^{x}$ are independent hypergeometric random
variables corresponding to the number of red balls moved out of the left urn
and into the left urn during the swap, respectively. More precisely,

$\displaystyle H_{1}^{x}\sim\mathrm{Hyp}(m,x,k)\hskip
14.22636pt\text{and}\hskip 14.22636ptH_{2}^{x}\sim\mathrm{Hyp}(n-m,r-x,k).$
(2)

This process is an irreducible, aperiodic Markov chain on the finite state
space

$\mathcal{X}=\\{\max(0,r+m-n),\max(0,r+m-n)+1,...,\min(m,r)\\}$

and so converges to a stationary distribution $\pi$. Given an initial
distribution $\mu$ for $X_{0}$, we define the total variation distance between
the law of $X_{t}$ and the stationary distribution by

$\|\mu P^{t}-\pi\|_{TV}=\sup_{A\subset\mathcal{X}}\left\lvert\mu
P^{t}(A)-\pi(A)\right\rvert,$

where $P$ is the Markov transition kernel corresponding to the chain. We may
then define the mixing time at $\varepsilon$ by

$t_{\mathrm{mix}}^{(n)}(\varepsilon)=\sup_{x\in\mathcal{X}}\inf\\{t:\|\delta_{x}P^{t}-\pi\|_{TV}\leq\varepsilon\\},$

where $\delta_{x}$ is the point distribution at $x$ (meaning the chain starts
at $X_{0}=x\in\mathcal{X}$).

We say a sequence of Markov chains exhibits cutoff in total variation if

$\lim_{n\to\infty}\frac{t^{(n)}_{\mathrm{mix}}(\varepsilon)}{t^{(n)}_{\mathrm{mix}}(1-\varepsilon)}=1\hskip
11.38109pt\text{ for all fixed }\hskip 11.38109pt\varepsilon\in(0,1).$

Further, we say a sequence $a_{n}$ is a cutoff window if there exists a
constant $c(\varepsilon)$ for each $\varepsilon\in(0,1)$ such that

$a_{n}=o\left(t^{(n)}_{\mathrm{mix}}\left({1\over 2}\right)\right)\hskip
14.22636pt\text{and}\hskip 14.22636pt\left\lvert
t^{(n)}_{\mathrm{mix}}(\varepsilon)-t^{(n)}_{\mathrm{mix}}(1-\varepsilon)\right\rvert\leq
c(\varepsilon)a_{n}\hskip 11.38109pt\text{ for all }\hskip 11.38109ptn.$

This paper analyzes the mixing times of sequences $\\{X_{t}^{(n)}\\}_{n}$ of
generalized Bernoulli-Laplace chains. To make this manageable, we introduce
the following assumption.

######  Assumption 1.1.

For each $n$, assume without loss of generality that $r,m\leq\frac{n}{2}$.
Suppose $\lim_{n\to\infty}{k\over n}=\gamma$, $\lim_{n\to\infty}{m\over n}=h$
and $\lim_{n\to\infty}{r\over n}=\eta$, and that

$\displaystyle 0<\gamma\leq h\leq\frac{1}{2},\hskip
11.38109pt0<\eta\leq{1\over 2},\hskip 11.38109pt\gamma\neq h(1-h),\hskip
14.22636pt\text{and}\hskip 14.22636pt\gamma\neq\frac{1}{2}\text{ if }h={1\over
2}.$

######  Remark 1.2.

When proving asymptotic results, Assumption 1.1 allows us to make the
following assumptions without loss of generality

$\displaystyle m,n-m\geq 2,\hskip 11.38109ptk\neq\frac{m(n-m)}{n},\hskip
14.22636pt\text{and}\hskip 14.22636pt\text{if }k=m\text{ then
}m\neq\frac{n}{2}.$

Further,

$\mathcal{X}=\\{0,\dots,\min(m,r)\\}.$

For completeness, we explicitly provide the stationary distributions of the
chains. The proof is simple and follows, for example, from the logic in [7].

######  Proposition 1.3.

The stationary distribution of $X_{t}^{(n)}$ is
$\pi^{(n)}\sim\mathrm{Hyp}(n,r,m)$, with probability mass function

$\pi^{(n)}(j)=\frac{{r\choose j}{n-r\choose m-j}}{{n\choose m}}.$

We now define for each $n$

$t_{n}:=\frac{-\log{n}}{2\log{\left\lvert
1-\frac{kn}{m(n-m)}\right\rvert}}=\frac{\log n}{2\left\lvert\log\left\lvert
1-\frac{kn}{m(n-m)}\right\rvert\right\rvert}.$ (3)

Notation. Let $a_{n}$ and $b_{n}$ be sequences in $\mathbb{R}$. We write
$a_{n}\lesssim b_{n}$ if there exists a constant $C\in\mathbb{R}$ such that
$\left\lvert a_{n}\right\rvert\leq C\left\lvert b_{n}\right\rvert$ for all $n$
large enough. If $\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=1$, we write $a_{n}\sim
b_{n}$. To denote the probability of transitioning from a state $x$ into a set
$S$ in $t$ steps, we write

$\displaystyle P_{t}(x,S):=\sum_{y\in S}p_{t}(x,y)=\mathbb{P}_{x}(X_{t}\in
S),$

where $\mathbb{P}_{x}$ denotes the probability measure induced by the Markov
chain starting from a state $X_{0}=x\in\cal X$. We may also sometimes write
$X_{t}^{x}$ to refer to a random variable induced by the same starting
criterion, especially in the context of two chains started at different
initial states.

Our main result bounds $t_{\mathrm{mix}}^{(n)}(\varepsilon)$ within a constant
distance of $t_{n}$ and is given below.

######  Theorem 1.4.

Let $\\{X_{t}^{(n)}\\}_{n}$ be a sequence of generalized Bernoulli-Laplace
chains satisfying Assumption 1.1. Then there exist constants $N_{1},N_{2},c$
and $C$, all depending on $\varepsilon,\gamma,\eta,h$, such that for all
$n\geq N_{1}$,

$t_{n}-c\leq t_{\mathrm{mix}}^{(n)}(\varepsilon),$

and for all $n\geq N_{2}$,

$t_{\mathrm{mix}}^{(n)}(\varepsilon)\leq t_{n}+C,$

with $t_{n}$ as in (3).

######  Remark 1.5.

By taking the maximums of a finite number of constants, Theorem 1.4 implies
that for any sequence $\\{X_{t}^{(n)}\\}_{n}$ of Bernoulli-Laplace chains
satisfying Assumption 1.1, there exists a constant $C^{\prime}$ such

$t_{n}-C^{\prime}\leq t_{\mathrm{mix}}^{(n)}(\varepsilon)\leq
t_{n}+C^{\prime}$

for all $n$. This further implies that $t_{\mathrm{mix}}^{(n)}(\varepsilon)$
exhibits cutoff at $t_{n}$ with constant window.

######  Remark 1.6.

If we assume further that

$\left\lvert\frac{1}{\log\left\lvert
1-\frac{\gamma}{\eta(1-\eta)}\right\rvert}-\frac{1}{\log\left\lvert
1-\frac{kn}{m(n-m)}\right\rvert}\right\rvert=O\left(\frac{1}{\log n}\right),$

then Theorem 1.4 implies (for possibly different $C^{\prime}$) that

$\frac{-\log{n}}{2\log\left\lvert
1-\frac{\gamma}{\eta(1-\eta)}\right\rvert}-C^{\prime}\leq
t_{\mathrm{mix}}^{(n)}(\varepsilon)\leq\frac{-\log{n}}{2\log\left\lvert
1-\frac{\gamma}{\eta(1-\eta)}\right\rvert}+C^{\prime},$ (4)

and so $t_{\mathrm{mix}}^{(n)}(\varepsilon)$ exhibits cutoff at order $\log n$
with constant window.

######  Remark 1.7.

Theorem 1.4 fails when $\gamma=h(1-h)$. In that case,
$t_{\mathrm{mix}}^{(n)}(\varepsilon)$ is usually a bounded sequence. For
details, see Section 4.

##  2 Lemmata

###  2.1 Spectral Lemmata

All of the eigenvalues and eigenfunctions for the Bernoulli-Laplace model are
known (see [4]), but here we only need the first two. This is similar to the
approach in [1].

######  Lemma 2.1.

The Markov transition has first two right eigenfunctions

$\displaystyle s_{1}(x)$ $\displaystyle=1-\frac{n}{rm}x$ (5) $\displaystyle
s_{2}(x)$
$\displaystyle=1-\frac{2(n-1)}{rm}x+\frac{(n-1)(n-2)}{r(r-1)m(m-1)}x(x-1)$ (6)

with respective eigenvalues

$\displaystyle\lambda_{1}$ $\displaystyle=1-\frac{nk}{m(n-m)}$ (7)
$\displaystyle\lambda_{2}$
$\displaystyle=1-\frac{2(n-1)k}{m(n-m)}+\frac{(n-1)(n-2)k(k-1)}{m(m-1)(n-m)(n-m-1)}.$
(8)

That is,

$\displaystyle\mathbb{E}_{x}[s_{1}(X_{1})]=\lambda_{1}s_{1}(x)\hskip
14.22636pt\text{and}\hskip
14.22636pt\mathbb{E}_{x}[s_{2}(X_{1})]=\lambda_{2}s_{2}(x).$

###### Proof.

This can be checked by a direct calculation. ∎

######  Corollary 2.2.

For all $t\geq 0,x\in\mathcal{X}$, we have

$\displaystyle\mathbb{E}_{x}[s_{1}(X_{t})]$
$\displaystyle=\lambda_{1}^{t}s_{1}(x)$
$\displaystyle\mathbb{E}_{x}[s_{2}(X_{t})]$
$\displaystyle=\lambda_{2}^{t}s_{2}(x)$

by the Markov property.

Doing some algebra, we find that

$\displaystyle s_{1}^{2}(x)=b_{0}+b_{1}s_{1}(x)+b_{2}s_{2}(x),$

where

$\displaystyle b_{0}={(n-m)(n-r)\over(n-1)rm},\hskip
14.22636ptb_{1}=-{(n-2r)(n-2m)\over(n-2)rm},\hskip
14.22636ptb_{2}={n^{2}(r-1)(m-1)\over(n-1)(n-2)rm}.$

######  Corollary 2.3.

For any $x,t,$ we have

$\mathbb{E}_{x}[s_{1}^{2}(x)]=b_{0}+b_{1}\lambda_{1}^{t}s_{1}(x)+b_{2}\lambda_{2}^{t}s_{2}(x).$

######  Lemma 2.4.

Let $\lambda_{1},\lambda_{2}$ be as above. Then
$\lambda_{1}^{2}-\lambda_{2}=O({1\over n}).$

###### Proof.

Observe that

$\displaystyle\lambda_{1}^{2}-\lambda_{2}$
$\displaystyle=\left(1-\frac{nk}{m(n-m)}\right)^{2}-\left(1-\frac{2(n-1)k}{m(n-m)}+\frac{(n-1)(n-2)k(k-1)}{m(m-1)(n-m)(n-m-1)}\right)$
$\displaystyle=\frac{2k}{m(n-m)}+\left({n^{2}k^{2}\over
m^{2}(n-m)^{2}}-{(n-2)(n-1)k(k-1)\over(n-m)(n-m-1)m(m-1)}\right).$

The claim follows. ∎

######  Lemma 2.5.

Let $\lambda_{2}$ be as above, $t_{n}$ as in (3), and suppose $\gamma\neq
h(1-h)$. Then $\lambda_{2}^{t_{n}}=O({1\over n})$.

###### Proof.

We first show that

$\lambda_{1}^{2}-\lambda_{2}=\frac{2k}{m(n-m)}+\left({n^{2}k^{2}\over
m^{2}(n-m)^{2}}-{(n-2)(n-1)k(k-1)\over(n-m)(n-m-1)m(m-1)}\right)\geq 0.$

Notice that for $n\geq 4$, we have

$\frac{4k^{2}}{m^{2}(n-m)^{2}}\leq\frac{2k}{m(n-m)}.$

It thus suffices to show that

$\displaystyle{(n^{2}+4)k^{2}\over
m^{2}(n-m)^{2}}-{(n-2)(n-1)k(k-1)\over(n-m)(n-m-1)m(m-1)}$ $\displaystyle\geq
0,$

which is equivalent to

$\frac{(n^{2}+4)k}{m(n-m)}-\frac{(n-2)(n-1)(k-1)}{(n-m-1)(m-1)}\geq 0.$

It is easy to check that the claim holds for $k=1$ and $k=m$. Since the left-
hand side is linear in $k$, this implies that the claim holds for all
$k\in\\{1,\dots,m\\}$.

The condition $\gamma\neq h(1-h)$ implies $\lim_{n\to\infty}\lambda_{2}>0$. We
may thus assume without loss of generality that
$\lambda_{2}=\left\lvert\lambda_{2}\right\rvert$. Therefore
$\log{(\lambda_{1}^{2})}-\log{\left\lvert\lambda_{2}\right\rvert}=:a_{n}\geq
0$, and so

$\displaystyle\left\lvert\lambda_{2}^{t_{n}}\right\rvert$
$\displaystyle=\exp\left(\log{\left\lvert\lambda_{2}\right\rvert}\frac{\log
n}{|\log(\lambda_{1}^{2})|}\right)$
$\displaystyle=\exp\left(\left[\log\left(\lambda_{1}^{2}\right)-a_{n}\right]\frac{\log
n}{\left\lvert\log(\lambda_{1}^{2})\right\rvert}\right)$
$\displaystyle=\exp\left(-\log n\right)\exp\left(\frac{-a_{n}\log
n}{\left\lvert\log(\lambda_{1}^{2})\right\rvert}\right)$
$\displaystyle\lesssim\frac{1}{n}.$

∎

###  2.2 Hypergeometric Comparison Lemmata

Denote the standard normal density by $\phi(x)$. For $l\in\mathcal{X}$, let

$p:=\frac{l}{m},\quad q:=1-p,\quad\sigma:=1\vee\sqrt{kpq\left(1-{k\over
n}\right)}.$ (9)

######  Definition 2.6.

We say $Z$ has a discrete normal distribution on $\mathcal{X}$ with parameters
$\zeta\in\mathbb{R}$ and $\xi>0$ if

$\displaystyle\mathbb{P}(Z=j)={1\over\xi\hskip
0.85358pt\mathcal{N}_{\zeta,\xi}}\phi\left({j-\zeta\over\xi}\right)\hskip
28.45274pt\textrm{where}\hskip
28.45274pt\mathcal{N}_{\zeta,\xi}:=\sum_{x\in\mathcal{X}_{k}}\frac{1}{\xi}\phi\left(x-\zeta\over\xi\right)$

for $j\in\mathcal{X}$, and denote $Z\sim\mathrm{dN}(\zeta,\xi)$.

Further, let $x_{j}:={j-kp\over\sigma}$ and
$\mathcal{N}:=\mathcal{N}_{kp,\sigma}$. Finally, we can give an important
technical lemma, the proof of which follows Lemma 5.2 from [1].

######  Lemma 2.7.

Given the above parameters, supposing Assumption 1.1 holds, letting
$l={rm\over n}+O(\sqrt{n})$, we have that

$\displaystyle\mathcal{N}=1+O\left(1\over\sqrt{n}\right).$

###### Proof.

Let $\mathcal{Z}$ be the standard normal distribution on $\mathbb{R}$. From
the proof of Lemma 5.2 from [1], we can obtain that

$\mathcal{N}\geq
1-\mathbb{P}\left(\mathcal{Z}\leq{-kp\over\sigma}\right)-\mathbb{P}\left(\mathcal{Z}\geq{kq\over\sigma}\right)-{2\over\sqrt{2\pi\sigma^{2}}}.$

Letting $l={rm\over n}+O(\sqrt{n})$, we have

$p={r\over n}+O\left({1\over\sqrt{n}}\right)\hskip 14.22636pt\text{and}\hskip
14.22636ptq={r\over n}+O\left({1\over\sqrt{n}}\right)\hskip
14.22636pt\text{and}\hskip
14.22636pt\sigma\sim\sqrt{\gamma(1-\gamma)n\eta(1-\eta)}.$

Applying Chebyshev’s inequality, we get

$\mathbb{P}\left(\mathcal{Z}\leq{-kp\over\sigma}\right)\leq{\sigma^{2}\over
k^{2}p^{2}}=O\left({1\over n}\right).$

Similarly, $\mathbb{P}\left(\mathcal{Z}={kq\over\sigma}\right)=O\left({1\over
n}\right)$. Of course,
${2\over\sqrt{2\pi\sigma^{2}}}=O\left({1\over\sqrt{n}}\right)$, and so the
claim follows. ∎

##  3 Bounds under Assumption 1.1

###  3.1 Lower Bound

In this section, we prove the lower bound of Theorem 1.4, which we restate
below.

######  Proposition 3.1.

Let $\\{X_{t}^{(n)}\\}_{n}$ be a sequence of generalized Bernoulli-Laplace
chains satisfying Assumption 1.1. Then there exist constants
$N_{1}:=N_{1}(\varepsilon,\gamma,\eta,h)$ and
$c:=c(\varepsilon,\gamma,\eta,h)$ such that for all $n\geq N_{1}$,

$t_{n}-c\leq t_{\mathrm{mix}}^{(n)}(\varepsilon).$

###### Proof.

We define

$\displaystyle s(x)=\sqrt{n-1}s_{1}(x)$

and calculate the mean and variance of $s(X_{t})$ both in the case where the
chain is started from $0$ and with respect to the stationary distribution. We
also let $t=t_{n}-c$, where $c$ is to be determined later.

Clearly, $\mathbb{E}_{\pi}[s(X_{t})]=0$ and

$\displaystyle\text{Var}_{\pi}(s(X_{t}))$ $\displaystyle=(n-1){n^{2}\over
r^{2}m^{2}}\text{Var}_{\pi}(X_{t})={(n-m)(n-r)\over
rm}\leq{(1-h)(1-\eta)\over\eta h}+2$

for sufficiently large $n$. Now,

$\displaystyle|\mathbb{E}_{0}[s(X_{t})]|$
$\displaystyle=|\sqrt{n-1}\lambda_{1}^{t}s_{1}(0)|$
$\displaystyle=\sqrt{n-1}|\lambda_{1}|^{t_{n}}|\lambda_{1}|^{-c}$
$\displaystyle=\sqrt{n-1\over n}|\lambda_{1}|^{-c}.$

To calculate

$\displaystyle\text{Var}_{0}[s(X_{t})]$
$\displaystyle=(n-1)\mathbb{E}_{0}[s_{1}(X_{t})^{2}]-\mathbb{E}_{0}[s(X_{t})]^{2},$

we first write

$\displaystyle\mathbb{E}_{0}[s_{1}(X_{t})^{2}]$
$\displaystyle=b_{0}+b_{1}\lambda_{1}^{t}+b_{2}\lambda_{2}^{t}$
$\displaystyle={(n-m)(n-r)\over(n-1)rm}-{(n-2m)(n-2r)\over(n-2)rm}\lambda_{1}^{t_{n}}\lambda_{1}^{-c}+{(m-1)(r-1)n^{2}\over
rm(n-1)(n-2)}\lambda_{2}^{t_{n}}\lambda_{2}^{-c}.$

By Lemma 2.5, $\lambda_{2}^{t_{n}}=O({1\over n})$. Now consider these three
terms in $(n-1)\mathbb{E}_{0}[s_{1}(X_{t})^{2}]$ in the limit as $n\to\infty$.
The first,

${(n-1)(n-m)(n-r)\over(n-1)rm}\to{(1-h)(1-\eta)\over h\eta}.$

The second vanishes, and the third is asymptotically bounded by $1$. It
follows that

$\text{Var}_{0}[s(X_{t})]\leq{(1-h)(1-\eta)\over h\eta}+2=:K$

for sufficiently large $n$. We now define the sets

$A_{\alpha}=\left\\{x\in\mathcal{X}:\left\lvert
s(x)\right\rvert\leq\alpha\sqrt{K}\right\\}$

and

$\displaystyle B_{d,c}$
$\displaystyle=\left\\{x:\min(|s(x)-\lambda_{1}^{-c}|,|s(x)+\lambda_{1}^{-c}|)\leq
d\sqrt{K}\right\\}$ $\displaystyle=\left\\{x:|s(x)-\lambda_{1}^{-c}|\leq
d\sqrt{K}\right\\}\cup\left\\{x:|s(x)+\lambda_{1}^{-c}|\leq
d\sqrt{K}\right\\}.$

The two sets reflect the two possibilities for the mean. Using Chebyshev’s
inequality, we calculate

$\displaystyle\pi_{n}(A_{\alpha})\geq 1-{1\over\alpha^{2}}$

For $B_{d,c}$, we have

$\displaystyle P_{t}(0,B_{d,c})$ $\displaystyle\geq
P_{t}\left(0,\left\\{\left\lvert s(X_{t})-\sqrt{n\over
n-1}\mathbb{E}_{0}[s(X_{t})]\right\rvert\leq d\sqrt{K}\right\\}\right)$
$\displaystyle=P_{t}\left(0,\left\\{\left\lvert
s(X_{t})-\mathbb{E}_{0}[s(X_{t})]\right\rvert\leq d\sqrt{K}\right\\}\right)$
$\displaystyle\qquad+P_{t}\left(0,\left\\{\mathbb{E}_{0}[s(X_{t})]-d\sqrt{K}\leq
s(X_{t})<\mathbb{E}_{0}[s(X_{t})]\sqrt{n\over n-1}-d\sqrt{K}\right\\}\right)$
$\displaystyle\qquad-
P_{t}\left(0,\left\\{\mathbb{E}_{0}[s(X_{t})]+d\sqrt{K}<s(X_{t})\leq\mathbb{E}_{0}[s(X_{t})]\sqrt{n\over
n-1}+d\sqrt{K}\right\\}\right)$ $\displaystyle\geq
P_{t}\left(0,\left\\{\left\lvert
s(X_{t})-\mathbb{E}_{0}[s(X_{t})]\right\rvert\leq d\sqrt{K}\right\\}\right)$
$\displaystyle\qquad-
P_{t}\left(0,\left\\{\mathbb{E}_{0}[s(X_{t})]+d\sqrt{K}<s(X_{t})\leq\mathbb{E}_{0}[s(X_{t})]\sqrt{n\over
n-1}+d\sqrt{K}\right\\}\right)$ $\displaystyle\geq 1-{1\over
d^{2}}-{\left\lvert\left(\sqrt{n\over
n-1}-1\right)\mathbb{E}_{0}[s(X_{t})]\right\rvert\over{n\sqrt{n-1}\over rm}}$
$\displaystyle\geq 1-{1\over d^{2}}-{K^{\prime}\over\sqrt{n}}$

eventually, where $K^{\prime}$ is a constant. Notice that if

$|\lambda_{1}|^{-c}-d\sqrt{K}\geq 2\alpha\sqrt{K}$ (10)

we have that $A_{\alpha}$ and $B_{d,c}$ are disjoint, implying that
$P_{t}(0,A_{\alpha})\leq{1\over d^{2}}+{K^{\prime}\over\sqrt{n}}$. Choosing
$\alpha$ and $d$ such that ${1\over\alpha^{2}}$ and ${1\over d^{2}}$ are less
than ${\varepsilon\over 3}$, and then $c$ such that (10) is satisfied, we have

$\displaystyle||P_{t}(0,\cdot)-\pi_{n}||_{TV}$
$\displaystyle\geq|P_{t}(0,A_{\alpha})-\pi_{n}(A_{\alpha})|$
$\displaystyle\geq 1-{1\over\alpha^{2}}-{1\over
d^{2}}-{K^{\prime}\over\sqrt{n}}$ $\displaystyle\geq 1-\varepsilon$

which gives the desired result.

Observe that equality is (asymptotically) achieved in (10) when

$c(\varepsilon,\gamma,\eta,h)={\log\left(2\alpha+d\right)+\log\sqrt{K}\over\left\lvert\log\left\lvert
1-{\gamma\over h(1-h)}\right\rvert\right\rvert}$

which does not depend on $n$. ∎

###  3.2 Upper Bound

We now begin the proof of the upper bound in Theorem 1.4.

######  Definition 3.2.

Define the following:

$\displaystyle\mathcal{I}_{n}(\kappa)$
$\displaystyle=\left\\{x\in\mathcal{X}:\left|x-\frac{rm}{n}\right|\leq\kappa\sqrt{n}\right\\}$
$\displaystyle F_{n}(\kappa)$
$\displaystyle=\left\\{(x,y)\in\mathcal{I}_{n}(\kappa)^{2}:\left\lvert
x-y\right\rvert\leq\frac{\sqrt{n}}{\kappa^{3}}\right\\}$
$\displaystyle\tau_{x,y}(\kappa)$
$\displaystyle=\min\\{t:(Y_{t}^{x},Y_{t}^{y})\in F_{n}(\kappa)\\}.$

####  3.2.1 Path Coupling Contraction

We use a generalization of the coupling introduced in [6]. Let $Y_{1,t}$ and
$Y_{2,t}$ be generalized Bernoulli-Laplace chains with parameters $m,r,n$. We
define a coupling between these chains as follows: In each chain, label the
balls in the left urn with $\\{1,\dots,m\\}$ and the balls in the right urn
with $\\{m+1,\dots,n\\}$ such that the red balls in any given urn have lower
indices than the white balls in the same urn. Now, choose subsets
$A\subset\\{1,\dots,m\\}$ and $B\subset\\{m+1,\dots,n\\}$ uniformly at random
such that $\left\lvert A\right\rvert=\left\lvert B\right\rvert=k$. Then, in
both chains, move the balls with labels in $A$ to the right urn and labels in
$B$ to the left urn. Relabel the balls and repeat.

This is a coupling because each individual chain, $Y_{1,t}$ or $Y_{2,t}$, has
the same behavior as $X_{t}$. However, there is a tendency for $Y_{1,t}$ and
$Y_{2,t}$ to approach one another because the same indices are being swapped
in each chain and indices are not independent of color. This is formalized
below.

######  Lemma 3.3.

Let $x,y\in\mathcal{X}$. Then for all $t\geq 0$,

$\mathbb{E}[|Y_{t}^{x}-Y_{t}^{y}|]\leq\left(1-\frac{k(n-2k)}{m(n-m)}\right)^{t}|x-y|.$

That is, each application of this path coupling’s Markov transition is a
strict contraction with coefficient

$1-\frac{k(n-2k)}{m(n-m)}\in(0,1).$

###### Proof.

The proof is very similar to that of Lemma 3.4 in [1]. We may assume without
loss of generality that $x>y$. By the Markov property, it suffices to prove
for $t=1$. Now consider the case when $x-y=1$. Then $Y_{1}^{x}-Y_{1}^{y}$ can
only takes values $-1,0,\text{ and }1$. We directly calculate that

$\mathbb{P}(Y_{1}^{x}-Y_{1}^{y}=-1)=\frac{k}{m}\left(\frac{k}{n-m}\right)$

and

$\mathbb{P}(Y_{1}^{x}-Y_{1}^{y}=1)=\left(\frac{m-k}{m}\right)\left(\frac{n-m-k}{n-m}\right).$

Thus

$\displaystyle\mathbb{E}[|Y_{1}^{x}-Y_{1}^{y}|]$
$\displaystyle=\frac{k}{m}\left(\frac{k}{n-m}\right)+\left(\frac{m-k}{m}\right)\left(\frac{n-m-k}{n-m}\right)$
$\displaystyle=1-\frac{k(n-2k)}{m(n-m)}.$

When $x-y>1$, we use the triangle inequality to get

$\mathbb{E}[|Y_{1}^{x}-Y_{1}^{y}|]\leq\sum_{i=0}^{x-y-1}\mathbb{E}[|Y_{1}^{y+i}-Y_{1}^{y+i+1}|]\leq(x-y)\left(1-\frac{k(n-2k)}{m(n-m)}\right).$

∎

Now we state the following:

######  Proposition 3.4.

Suppose Assumption 1.1 is satisfied. Then for any $\kappa\in\mathbb{N}$ such
that

$\displaystyle\kappa^{4}\left(1-{\gamma(1-2\gamma)\over
h(1-h)}\right)^{\kappa}\leq{1\over\kappa^{2}},$ (11)

we have

$\mathbb{P}(\tau_{x,y}(\kappa)>t_{n}+\kappa)=O\left(\frac{1}{\kappa^{2}}\right).$

###### Proof.

First observe that

$\displaystyle\mathbb{P}(\tau_{x,y}(\kappa)>t_{n}+\kappa)\leq\mathbb{P}(X_{t_{n}}^{x}\not\in\mathcal{I}_{n}(\kappa))+\mathbb{P}(X_{t_{n}}^{y}\not\in\mathcal{I}_{n}(\kappa))+\mathbb{P}(X_{t_{n}+\kappa}^{x}\not\in\mathcal{I}_{n}(\kappa))$
$\displaystyle+\mathbb{P}(X_{t_{n}+\kappa}^{y}\not\in\mathcal{I}_{n}(\kappa))+\mathbb{P}\left(Y_{t_{n}}^{x},Y_{t_{n}}^{y}\in\mathcal{I}_{n}(\kappa),\left\lvert
Y_{t_{n}+\kappa}^{x}-Y_{t_{n}+\kappa}^{y}\right\rvert>\frac{\sqrt{n}}{\kappa^{3}}\right),$

where we may use $X$ instead of $Y$ for the first four terms because $X$ and
$Y$ share the same distributions by the coupling. We now work to
asymptotically bound these terms by $\frac{1}{\kappa^{2}}$. For any constants
$t\geq 0$ and $z\in\mathcal{X}$, we have

$\displaystyle\mathbb{P}_{z}(X_{t}\not\in\mathcal{I}_{n}(\kappa))$
$\displaystyle=\mathbb{P}_{z}\left(\left|X_{t}-{rm\over
n}\right|>\kappa\sqrt{n}\right)$
$\displaystyle=\mathbb{P}_{z}\left(s_{1}^{2}(X_{t})>\kappa^{2}{n^{3}\over
r^{4}}\right)$ $\displaystyle\leq{1\over\kappa^{2}}{r^{4}\over
n^{3}}\mathbb{E}_{z}[s_{1}^{2}(X_{t})]$
$\displaystyle={1\over\kappa^{2}}{r^{4}\over
n^{3}}\left(b_{0}+b_{1}\lambda_{1}^{t}s_{1}(z)+b_{2}\lambda_{2}^{t}s_{2}(z)\right).$

Two of the terms involve $t=t_{n}$ and the other two $t=t_{n}+\kappa$. Since
$\left\lvert\lambda_{1}\right\rvert,\left\lvert\lambda_{2}\right\rvert\leq 1$,
it suffices to bound for $t=t_{n}$. As $\frac{r^{4}}{n^{3}}=O(n)$, we need
only show
$b_{0},b_{1}\lambda_{1}^{t_{n}}s_{1}(z),b_{2}\lambda_{2}^{t_{n}}s_{2}(z)=O({1\over
n})$. The first two follow easy because $b_{0},b_{1}=O({1\over n})$ and
$\lambda_{1}$ and $s_{1}(z)$ are bounded. For the final term, notice that
$b_{2}$ and $s_{2}(z)$ is bounded. It therefore suffices to show that
$\lambda_{2}^{t_{n}}=O({1\over n})$, and this follows from Lemma 2.5. Thus

$\mathbb{P}_{z}(X_{t}\not\in\mathcal{I}_{n}(\kappa))=O\left(\frac{1}{\kappa^{2}}\right).$

We now bound the last term. Observe that

$\displaystyle\mathbb{P}\left(Y_{t_{n}}^{x},Y_{t_{n}}^{y}\in\mathcal{I}_{n}(\kappa),\left|Y_{t_{n}+\kappa}^{x}-Y_{t_{n}+\kappa}^{y}\right|>{\sqrt{n}\over\kappa^{3}}\right)$
$\displaystyle\leq\max_{x,y\in\mathcal{I}_{n}(\kappa)}\mathbb{P}\left(\left|Y_{\kappa}^{x}-Y_{\kappa}^{y}\right|\geq{\sqrt{n}\over\kappa^{3}}\right)$
$\displaystyle\leq\max_{x,y\in\mathcal{I}_{n}(\kappa)}{\kappa^{3}\over\sqrt{n}}\mathbb{E}\left[|Y_{\kappa}^{x}-Y_{\kappa}^{y}|\right]$
$\displaystyle\leq 2\kappa^{4}\left(1-{k(n-2k)\over m(n-m)}\right)^{\kappa}$
$\displaystyle=O\left({1\over\kappa^{2}}\right).$

∎

####  3.2.2 Mixing Times for Chains Started Close Together

We now endeavor to prove the following:

######  Proposition 3.5.

Suppose that Assumption 1.1 is satisfied. Then,

$\displaystyle\max_{(x,y)\in
F_{n}(\kappa)}\|\delta_{x}P-\delta_{y}P\|_{TV}=O\left({1\over\kappa^{2}}\right).$

###### Proof.

Let $H_{1}^{x}$ and $H_{2}^{x}$ be hypergeometric random variables as in
Equation (2). First, let $Z_{a}^{b}\sim\mathrm{dN}_{k}(kp_{a}^{b},\sigma^{b})$
for $a\in\\{1,2\\}$ and $b\in\\{x,y\\}$, where

$\displaystyle p_{1}^{x}={x\over m},\hskip 8.5359ptp_{2}^{x}=q_{1}^{x},\hskip
8.5359ptp_{1}^{y}={y\over m},\hskip 8.5359ptp_{2}^{y}=q_{1}^{y},\hskip
14.22636pt\text{and}\hskip
14.22636pt\sigma^{b}=1\vee\sqrt{kp_{1}^{b}p_{2}^{b}\left(1-{k\over
n}\right)}.$

Now observe that

$\displaystyle\mu_{H_{2}^{x}-H_{1}^{x}+x}$
$\displaystyle-\mu_{H_{2}^{y}-H_{1}^{y}+y}$
$\displaystyle=(\mu_{H_{2}^{x}-H_{1}^{x}+x}-\mu_{H_{2}^{x}-Z_{1}^{x}+x})+(\mu_{H_{2}^{x}-Z_{1}^{x}+x}-\mu_{Z_{2}^{x}-Z_{1}^{x}+x})+(\mu_{Z_{2}^{x}-Z_{1}^{x}+x}-\mu_{Z_{2}^{x}-Z_{1}^{y}+x})$
$\displaystyle+(\mu_{Z_{2}^{x}-Z_{1}^{y}+x}-\mu_{Z_{2}^{y}-Z_{1}^{y}+y})+(\mu_{Z_{2}^{y}-Z_{1}^{y}+y}-\mu_{H_{2}^{y}-Z_{1}^{y}+y})+(\mu_{H_{2}^{y}-Z_{1}^{y}+y}-\mu_{H_{2}^{y}-H_{1}^{y}+y}).$

By the independence of all the hypergeometrics and discrete normals above, we
obtain

$\displaystyle\|\delta_{x}P-\delta_{y}P\|_{TV}$
$\displaystyle=\|\mu_{H_{2}^{x}-H_{1}^{x}+x}-\mu_{H_{2}^{y}-H_{1}^{y}+y}\|_{TV}$
$\displaystyle\leq\sum_{b\in\\{x,y\\}}\sum_{a=1}^{2}\|\mu_{H_{a}^{b}}-\mu_{Z_{a}^{b}}\|_{TV}+\|\mu_{Z_{2}^{x}+x-y}-\mu_{Z_{2}^{y}}\|_{TV}+\|\mu_{Z_{1}^{x}}-\mu_{Z_{1}^{y}}\|_{TV}.$

We now bound the first term by proving the following local limit theorem.

######  Proposition 3.6 (Local limit theorem).

Given Assumption 1.1 and using parameters in (9), if $l={rm\over
n}+O(\sqrt{n}),$ $H\sim\mathrm{Hyp}(m,l,k),$ and
$Z\sim\mathrm{dN}_{k}(kp,\sigma)$, then

$\|\mu_{H}-\mu_{Z}\|_{TV}=O\bigg{(}{1\over\sqrt{n}}\bigg{)}.$

###### Proof.

Let $L:=\sup\\{j\in\mathcal{X}:x_{j}\geq-\delta\sigma\\}$ and
$R:=\inf\\{j\in\mathcal{X}:x_{j}\leq\delta\sigma\\}$ for a fixed
$\delta\in(0,{1\over 2}]$. Observe that

$\displaystyle 2\|\mu_{H}-\mu_{Z}\|_{TV}$
$\displaystyle=\sum_{j=L}^{R}|\mathbb{P}(H=j)-\mathbb{P}(Z=j)|$
$\displaystyle\quad+\sum_{j=0}^{L-1}|\mathbb{P}(H=j)-\mathbb{P}(Z=j)|+\sum_{j=R+1}^{k}|\mathbb{P}(H=j)-\mathbb{P}(Z=j)|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad=:T_{1}+T_{2}+T_{3}\hskip
56.9055pt$

First, by triangle inequality,

$|\mathbb{P}(H=j)-\mathbb{P}(Z=j)|\leq\mathbb{P}(H=j)+\mathbb{P}(Z=j).$

and by applying Höffding’s inequality from [3], we obtain

$T_{2}+T_{3}\leq{(k+1)\exp\left({-{1\over
2}\delta^{2}\sigma^{2}}\right)\over\mathcal{N}\sigma\sqrt{2\pi}}+\mathbb{P}(H<L)+\mathbb{P}(H>R),$

where it is clear that

$\displaystyle{(k+1)\exp\left({-{1\over
2}\delta^{2}\sigma^{2}}\right)\over\mathcal{N}\sigma\sqrt{2\pi}}\to 0.$

For the other two terms, recall that any hypergeometric distribution is the
sum of $k$ independent Bernoulli random variables and $H$ has mean $kp$.
Therefore, again applying Höffding’s inequality,

$\displaystyle\mathbb{P}(H<L)+\mathbb{P}(H>R)$
$\displaystyle=\mathbb{P}(H-kp<L-kp)+\mathbb{P}(H-kp>R-kp)$ $\displaystyle\leq
2\exp\left(-2{(L-kp)^{2}\over k}\right)+2\exp\left(-2{(R-kp)^{2}\over
k}\right)$ $\displaystyle\leq 2\exp\left(-2{\delta\sigma^{2}\over
k}\right)+2\exp\left(-2{\delta\sigma^{2}\over k}\right)$ $\displaystyle\to 0$

where the last step occurs since $\sigma^{2}\sim\gamma(1-\gamma)n\eta(1-\eta)$
and $kp\sim\gamma n\eta$. Finally, for $T_{1}$, observe that

$\displaystyle T_{1}$
$\displaystyle\leq\sum_{j=L}^{R}\left|{\phi(x_{j})\over\sigma}-{\phi(x_{j})\over\mathcal{N}\sigma}\right|+\sum_{j=L}^{R}\left|\mathbb{P}(H=j)-{\phi(x_{j})\over\sigma}\right|$
$\displaystyle\leq\sum_{j=L}^{R}{\phi(x_{j})\over\sigma}\left\lvert
1-{1\over\mathcal{N}}\right\rvert+\sum_{j=L}^{R}\left|\mathbb{P}(H=j)-{\phi(x_{j})\over\sigma}\right|$
$\displaystyle\leq|\mathcal{N}-1|+\sum_{j=L}^{R}\left|\mathbb{P}(H=j)-{\phi(x_{j})\over\sigma}\right|.$

The left term is $O\left({1\over\sqrt{n}}\right)$ by Lemma 2.7. For the right
term, notice that

$\sum_{j=L}^{R}\left|\mathbb{P}(H=j)-{\phi(x_{j})\over\sigma}\right|\leq
2\sum_{j=L}^{\lfloor
kp\rfloor}\left|\mathbb{P}(H=j)-{\phi(x_{j})\over\sigma}\right|$

From Theorem 1 of [5], or in particular as Lemma 5.3 in [1], we have that

$2\sum_{j=L}^{\lfloor
kp\rfloor}\left|\mathbb{P}(H=j)-{\phi(x_{j})\over\sigma}\right|\leq{D\over\sigma}=O\left({1\over\sqrt{n}}\right)$

since $0<{k\over n}<1$ holds for all but finitely many $n$. This proves the
result. ∎

To complete the proof of Proposition 3.5, we must show that

$\|\mu_{Z_{2}^{x}+x-y}-\mu_{Z_{2}^{y}}\|_{TV}+\|\mu_{Z_{1}^{x}}-\mu_{Z_{1}^{y}}\|_{TV}=O\left({1\over\kappa^{2}}\right).$

We solve only
$\|\mu_{Z_{2}^{x}+x-y}-\mu_{Z_{2}^{y}}\|_{TV}\lesssim{1\over\kappa^{2}}$ since
the proof for $\|\mu_{Z_{1}^{x}}-\mu_{Z_{1}^{y}}\|_{TV}$ follows the same
method, but without a correction for $x-y$. First, without loss of generality
assume $x\geq y$. Then, let
$\mathcal{Y}:=\mathcal{X}\cap\\{\mathcal{X}+x-y\\}$,
$\mathcal{N}^{x}:=\mathcal{N}_{kp_{2}^{x},\sigma^{x}}$,
$\mathcal{N}^{y}:=\mathcal{N}_{kp_{2}^{y},\sigma^{y}}$,
$\overline{y_{j}}:={j-kp_{2}^{y}\over\sigma^{y}}$ and
$\overline{x_{j}}:={j-x+y-kp_{2}^{x}\over\sigma^{x}}$. Define $J_{n}:=[{k\over
2}-4\kappa\sqrt{n},{k\over 2}+4\kappa\sqrt{n}]$, then

$\displaystyle 2\|\mu_{Z_{2}^{x}+x-y}$
$\displaystyle-\mu_{Z_{2}^{y}}\|_{TV}\leq\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}\left|{\phi(\overline{x_{j}})\over\mathcal{N}^{x}\sigma^{x}}-{\phi(\overline{y_{j}})\over\mathcal{N}^{y}\sigma^{y}}\right|+\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}^{c}}{\phi(\overline{x_{j}})\over\mathcal{N}^{x}\sigma^{x}}$
$\displaystyle+\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}^{c}}{\phi(\overline{y_{j}})\over\mathcal{N}^{y}\sigma^{y}}+\sum_{\mathcal{X}\setminus(\mathcal{X}+x-y)}\mathbb{P}(Z_{2}^{y}=j)+\sum_{(\mathcal{X}+x-y)\setminus\mathcal{X}}\mathbb{P}(Z_{2}^{x}=j-x+y)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad=:\mathcal{T}_{1}+\mathcal{T}_{2}+\mathcal{T}_{3}+\mathcal{T}_{4}+\mathcal{T}_{5}.$

We now work backwards. $\mathcal{T}_{4}$ and $\mathcal{T}_{5}$ are bounded
analogously, as are $\mathcal{T}_{2}$ and $\mathcal{T}_{3}$.

For $\mathcal{T}_{4}$, observe that $x\geq y$, and by the space we are summing
over, $j\leq x-y-1$. Further,
$\sigma^{y}\sim\sqrt{\gamma(1-\gamma)n\eta(1-\eta)}$. Using Lemma 2.7 and
looking at large $n$, we obtain:

$\mathcal{T}_{4}\leq\sum_{j=0}^{x-y-1}\mathbb{P}(Z_{2}^{y}=j)\leq(x-y)\mathbb{P}(Z_{3}=x-y-1)={x-y\over\mathcal{N}^{y}\sigma^{y}}\phi\left({x-y-1-kp_{2}^{y}\over\sigma^{y}}\right)\leq
C_{0}e^{-c_{1}n}$

for constants $C_{0},c_{1}>0$ independent of $n$.

For $\mathcal{T}_{2}$, let $\mathcal{Z}$ be the standard normal distribution
over $\mathbb{R}$. Using the definition of $J_{n}$ with $\kappa\geq 0$, $n\geq
0$, $0<\gamma<{1\over 2}$, and $(x,y)\in F_{n}(\kappa)$, we have that
asymptotically,

${k\over 2}+4\kappa\sqrt{n}\geq\kappa\sqrt{n}+x-y+kp_{2}^{x}+1\hskip
14.22636pt\text{and}\hskip 14.22636pt{k\over
2}-4\kappa\sqrt{n}\leq-\kappa\sqrt{n}+x-y-1+kp_{2}^{x}.$

Therefore, we can use integral comparison, monotonicity of the standard normal
density away from the mean, and Lemma 2.7 to obtain

$\mathcal{T}_{3}\leq\sum_{j\in
J_{n}^{c}}{\phi(\overline{x_{j}})\over\mathcal{N}^{x}\sigma^{x}}\leq\int_{J_{n}^{c}}{\phi(\overline{x_{j}})\over\mathcal{N}^{x}\sigma^{x}}\hskip
1.42262ptdx\leq{2\over\mathcal{N}^{x}}\mathbb{P}\left(\mathcal{Z}\geq{\kappa\sqrt{n}\over\sigma^{x}}\right)\leq{2(\sigma^{x})^{2}\mathbb{E}[\mathcal{Z}^{2}]\over
n\mathcal{N}^{x}}{1\over\kappa^{2}}=O\left({1\over\kappa^{2}}\right),$

where we use that $\sigma^{x}\sim\sqrt{n\eta(1-\eta)\gamma(1-\gamma)}$.

Now, for $\mathcal{T}_{1}$, we can use the result of
$\left|{1\over\sigma^{x}}-{1\over\sigma^{y}}\right|=O({1\over n})$ from [1].
Using Lemma 2.7, observe:

$\displaystyle\mathcal{T}_{1}$ $\displaystyle=\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}\left|{\phi(\overline{x_{j}})\over\sigma^{x}}-{\phi({\overline{y_{j}}})\over\sigma^{y}}\right|+O\left({1\over\sqrt{n}}\right)$
$\displaystyle\leq\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}\left|{\phi(\overline{x_{j}})\over\sigma^{x}}-{\phi({\overline{y_{j}}})\over\sigma^{x}}\right|+\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}\phi(\overline{y_{j}})\left|{1\over\sigma^{x}}-{1\over\sigma^{y}}\right|+O\left({1\over\sqrt{n}}\right).$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad=:\mathscr{T}_{1}+\mathscr{T}_{2}+O\left({1\over\sqrt{n}}\right).$

It is easy to see that, since $\phi$ is bounded above by $1$,

$\mathscr{T}_{2}\leq 8\kappa\sqrt{n}\cdot O\left({1\over n}\right),$

which is also $O({1\over\sqrt{n}})$. For $\mathscr{T}_{1}$, first observe that
$\phi$ is Lipschitz, and let $K$ to be its Lipschitz constant. Then

$\displaystyle\mathscr{T}_{1}$
$\displaystyle\leq{K\over\sigma^{x}}\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}\left|\overline{y_{j}}-\overline{x_{j}}\right|$
$\displaystyle={K\over\sigma^{x}}\bigg{(}{1\over\sigma^{x}}\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}\left|j-kp_{2}^{y}-(j-x+y-kp_{2}^{x})\right|+\left|{1\over\sigma^{x}}-{1\over\sigma^{y}}\right|\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}|j-kp_{2}^{y}|\bigg{)}.$

It can be seen that $\left|j-kp_{2}^{y}-(j-x+y-kp_{2}^{x})\right|$ simplifies
to $|x-y+kp_{2}^{x}-kp_{2}^{y}|$, and using the triangle inequality and the
definitions of $p_{2}^{b}$, we obtain $|x-y|\left(1+{k\over m}\right)$, which
is less than or equal to ${\sqrt{n}\over\kappa^{3}}\left(1+{k\over m}\right)$
by definition of $F_{n}(\kappa)$. For the right term, observe that
$|j-kp_{2}^{y}|\leq 8\kappa\sqrt{n}$ by the definition of $J_{n}$, thus we now
have $O\left({1\over n}\right)\cdot O(n)$, and now distributing
${K\over\sigma^{x}}$ and recognizing that $\sigma^{x}\sim O(\sqrt{n})$
concludes that the right term is also $O\left({1\over\sqrt{n}}\right)$. Thus
we now have:

$\displaystyle\mathscr{T}_{1}$
$\displaystyle\leq{K\over(\sigma^{x})^{2}}\sum_{j\in\mathcal{Y}_{n}\cap
J_{n}}{\sqrt{n}\over\kappa^{3}}\left(1+{k\over m}\right)$
$\displaystyle\leq{Kn\over(\sigma^{x})^{2}}\left(1+{k\over
m}\right)\cdot{1\over\kappa^{2}}$
$\displaystyle=O\left({1\over\kappa^{2}}\right)$

as desired. ∎

####  3.2.3 Proof of Upper Bound

We now prove the upper bound in Theorem 1.4 using the results derived in the
previous two subsections.

######  Proposition 3.7.

Let $\\{X_{t}^{(n)}\\}_{n}$ be a sequence of generalized Bernoulli-Laplace
chains satisfying Assumption 1.1. Then there exist constants
$N_{2}:=N_{2}(\varepsilon,\gamma,\eta,h)$ and $C:=(\varepsilon,\gamma,\eta,h)$
such that for all $n\geq N_{2}$,

$t_{\mathrm{mix}}^{(n)}(\varepsilon)\leq t_{n}+C.$

###### Proof.

Let $x,y\in\mathcal{X}$ and $A\subset\mathcal{X}$. Select
$\kappa\in\mathbb{N}$ satisfying (11). Define $t:=t_{n}+\kappa+1$. Then by
Proposition 3.4 and the strong Markov property,

$\displaystyle|\mathbb{P}_{x}(X_{t}\in A)-\mathbb{P}_{y}(X_{t}\in A)|$
$\displaystyle\quad=|\mathbb{P}_{x}(Y_{t}\in A)-\mathbb{P}_{y}(Y_{t}\in A)|$
$\displaystyle\quad\leq
2\mathbb{P}(\tau_{x,y}(\kappa)>t-1)+|\mathbb{P}_{x}(Y_{t}\in
A,\tau_{x,y}(\kappa)\leq t-1)-\mathbb{P}_{y}(Y_{t}\in A,\tau_{x,y}(\kappa)\leq
t-1)|$ $\displaystyle\quad\leq
O\left({1\over\kappa^{2}}\right)+\max_{\begin{subarray}{c}z,w\in
F_{n}(\kappa)\\\ s\in\\{1,\dots,t\\}\end{subarray}}|\mathbb{P}_{z}(Y_{s}\in
A)-\mathbb{P}_{w}(Y_{s}\in A)|.$

Observe that for $s\in\\{1,\dots,t\\}$ and $z,w\in F_{n}(\kappa)$,

$\left\lvert\mathbb{P}_{z}(Y_{s}\in A)-\mathbb{P}_{w}(Y_{s}\in
A)\right\rvert\leq\|\delta_{z}P-\delta_{w}P\|_{TV}=O\left({1\over\kappa^{2}}\right),$

where we use Proposition 3.5. Thus,

$\max_{x\in\mathcal{X}}\|\delta_{x}P^{t}-\pi\|_{TV}\leq
2\max_{x,y\in\mathcal{X}}\|\delta_{x}P^{t}-\delta_{y}P^{t}\|_{TV}=2\max_{x,y\in\mathcal{X}}|\mathbb{P}_{x}(X_{t}\in
A)-\mathbb{P}_{y}(X_{t}\in A)|~{}=O\left({1\over\kappa^{2}}\right).$ (12)

Now let $C_{3}$ be the asymptotic bounding constant in (12). Then

$\max_{x\in\mathcal{X}}\|\delta_{x}P^{t}-\pi\|_{TV}\leq\frac{C_{3}}{\kappa^{2}}$

for $n$ large enough. If it is not already true, increase $\kappa$ so that
${C_{1}\over\kappa^{2}}\leq\varepsilon$ in addition to (11). Then $C=\kappa+1$
works as the constant referenced in the theorem statement, and this completes
the proof. ∎

##  4 Bounds when $\gamma=h(1-h)>0$

We now investigate the critical case when $\gamma=h(1-h)$. We will ultimately
show that the asymptotic behavior of $t_{\mathrm{mix}}^{(n)}(\varepsilon)$
differs.

######  Assumption 4.1.

For each $n$, assume without loss of generality that $r,m\leq\frac{n}{2}$.
Suppose $\lim_{n\to\infty}{k\over n}=\gamma$, $\lim_{n\to\infty}{m\over n}=h$
and $\lim_{n\to\infty}{r\over n}=\eta$, and that $\gamma=h(1-h).$ Assume
further that

$\left\lvert\lambda_{1}\right\rvert=\left\lvert
1-\frac{nk}{m(n-m)}\right\rvert\lesssim\frac{1}{\sqrt{n}}.$ (13)

######  Theorem 4.2.

Let $\\{X_{t}^{(n)}\\}_{n}$ be a sequence of Bernoulli-Laplace chains
satisfying Assumption 4.1. Then there exists constants
$N:=N(\varepsilon,\gamma,\eta,h)$ and $C:=C(\varepsilon,\gamma,\eta,h)$ such
that for all $n\geq N$,

$2\leq t_{\mathrm{mix}}^{(n)}(\varepsilon)\leq C.$ (14)

######  Remark 4.3.

Under Assumption 4.1, we no longer have cutoff at a multiple of $\log{n}$.

We split the proof of Theorem 4.2 across two subsections.

###  4.1 The Lower Bound

###### Proof.

We bound the total variation at time $t=1$:

$\displaystyle||\delta_{0}P-\pi^{(n)}||_{TV}$
$\displaystyle\geq|\delta_{0}P(\\{k\\})-\pi^{(n)}(\\{k\\})|$
$\displaystyle=1-\pi^{(n)}(\\{k\\})$ $\displaystyle=1-\frac{{r\choose
k}{n-r\choose m-k}}{{n\choose m}}$ $\displaystyle=1-{r!m!(n-m)!(r-m)!\over
k!n!(r-k)!(m-k)!(n-m-r+k)!}.$

Since $n,k,r,m$ are all of the same order, it is easy to see that the $n!$
term in the denominator dominates the fraction and send its limit to 0.
Therefore, for any $\varepsilon\in(0,1)$, we have for sufficiently large $n$
that

$||\delta_{0}P-\pi^{(n)}||_{TV}\geq\varepsilon.$

This implies $t_{\mathrm{mix}}^{(n)}(\varepsilon)\geq 2$. ∎

###  4.2 The Upper Bound

For this subsection, we introduce an alternative to $t_{n}$. Notice that the
definition given in (3) is invalid under Assumption 4.1.

######  Definition 4.4.

When $\lambda_{2}\neq 0$, let

$q_{n}=\frac{\log(n)}{|\log|\lambda_{2}||}=\frac{-\log(n)}{\log\left\lvert
1-\frac{2(n-1)}{m(n-m)}k+\frac{(n-1)(n-2)k(k-1)}{m(n-m)(m-1)(n-m-1)}\right\rvert}.$

When $\lambda_{2}=0$, let $q_{n}=1$.

We will now prove an analogue of Proposition 3.4 under Assumption 4.1.

######  Proposition 4.5.

Suppose Assumption 4.1 is satisfied. Then for any $\kappa\in\mathbb{N}$ such
that

$\displaystyle\kappa^{4}\left(1-{\gamma(1-2\gamma)\over
h(1-h)}\right)^{\kappa}\leq{1\over\kappa^{2}},$ (15)

we have

$\mathbb{P}(\tau_{x,y}(\kappa)>q_{n}+\kappa)=O\left(\frac{1}{\kappa^{2}}\right).$

###### Proof.

The the proof is identical to that of Proposition 3.4, except that we bound

$\mathbb{P}_{z}(X_{q_{n}}\not\in\mathcal{I}_{n}(\kappa))={1\over\kappa^{2}}{r^{4}\over
n^{3}}\left(b_{0}+b_{1}\lambda_{1}^{q_{n}}s_{1}(z)+b_{2}\lambda_{2}^{q_{n}}s_{2}(z)\right).$

We need that $\lambda_{2}^{q_{n}}=O\left({1\over n}\right)$. If
$\lambda_{2}=0$, then any asymptotic bound is trivially satisfied. If
$\lambda_{2}\neq 0$, then

$\displaystyle\lambda_{2}^{q_{n}}$ $\displaystyle\leq|\lambda_{2}|^{q_{n}}$
$\displaystyle=\exp\left(\log|\lambda_{2}|\frac{\log(n)}{|\log|\lambda_{2}||}\right)$
$\displaystyle=\frac{1}{n}.$

This proves the proposition. ∎

Following the argument of Section 3.2, we arrive at an analogue of Proposition
3.7.

######  Proposition 4.6.

Let $\\{X_{t}^{(n)}\\}_{n}$ be a sequence of generalized Bernoulli-Laplace
chains satisfying Assumption 4.1. Then there exist constants
$N:=N(\varepsilon,\gamma,\eta,h)$ and $C:=C(\varepsilon,\gamma,\eta,h)$ such
that for all $n\geq N$,

$t_{\mathrm{mix}}^{(n)}(\varepsilon)\leq q_{n}+C.$

We now employ this proposition with the rate of convergence assumption (13) to
prove the upper bound of Theorem 4.2.

###### Proof.

It suffices to show that $q_{n}$ is bounded when Assumption 4.1 holds. This is
trivially satisfied for all $n$ such that $\lambda_{2}=0$, so assume
$\left\lvert\lambda_{2}\right\rvert\neq 0$. Using Lemma 2.4, we see that

$\displaystyle\lambda_{2}$ $\displaystyle=\lambda_{1}^{2}+O\left({1\over
n}\right)$ $\displaystyle=O\left({1\over\sqrt{n}}\right)^{2}+O\left({1\over
n}\right)$ $\displaystyle=O\left({1\over n}\right).$

That is to say, there exists a $K$ such that
$\left\lvert\lambda_{2}\right\rvert\leq{K\over n}$. Thus

$\log\left\lvert\lambda_{2}\right\rvert\leq\log(K)-\log(n).$

Consider only $n$ large enough such that $\log(K)-\log(n)<0.$ Then

$\left\lvert\log|\lambda_{2}|\right\rvert\geq\log(n)-\log(K).$

This implies that

$q_{n}=\frac{\log(n)}{\left\lvert\log|\lambda_{2}|\right\rvert}\leq\frac{\log(n)}{\log(n)-\log(K)},$

which is clearly bounded. ∎

##  5 Conclusion

###  5.1 Generalizations

Theorem 1.4 generalizes pre-existing work on the two-color, two-urn Bernoulli-
Laplace model. In particular, we extend the work from [6] on the lower bound
and [1] on the upper bound to a model with uneven distributions of colors and
urn sizes. We also show that mixing time is bounded under certain conditions
in Theorem 4.2, which we believe to be a new result.

Another possible generalization comes from letting there be more than 2
colors. The complete spectrum of the Markov transition in this case is still
known (see [4]), but the more complicated state space is harder to work with,
and many proofs (e.g. that of Proposition 3.5) breaks down.

Another case still unproven (though analogous to [2]) is when $\gamma=0$. We
put forth the following conjecture, which is the analogue of the result in [6]
and notably lacks constant window.

######  Conjecture 5.1.

Let $\\{X_{t}^{(n)}\\}_{n}$ be a sequence of Bernoulli-Laplace chains. For
each $n$, assume without loss of generality that $r,m\leq\frac{n}{2}$. Suppose
$\lim_{n\to\infty}{k\over n}=0$, $\lim_{n\to\infty}{m\over n}=h$ and
$\lim_{n\to\infty}{r\over n}=\eta$. Then there exists constants
$N,c,c^{\prime},$ and $c^{\prime\prime}$ all depending on
$\varepsilon,\eta,\gamma,$ and $h$ such that for all $n\geq N$,

$\frac{n\log
n}{c(\varepsilon,\eta,\gamma,h)k}-\frac{k}{n}c^{\prime}(\varepsilon,\eta,\gamma,h)\leq
t_{mix}(\varepsilon)\leq
t_{n}+\frac{c^{\prime\prime}(\varepsilon,\eta,\gamma,h)n}{k}\log\log n.$

The last generalization we propose is to let $k$ and $r$ be random variables
such that convergence ${k\over n}\to\gamma$ and ${r\over n}\to\eta$ in
distribution. We are not aware of any previous literature on such a model.

###  5.2 Numerical Results

The asymptotic behavior proven in Theorems 1.4 and 4.2 is readily observed in
numeric data, which throughout this section is exact. The mixing times for two
sequences of Bernoulli-Laplace chains satisfying Assumption 1.1 are plotted in
Figures 1 and 2. Notice that they resemble a constant multiple of $\log n$.

Figure 3 displays the mixing times for a sequence of Bernoulli-Laplace chains
satisfying Assumption 4.1. Notice that they appear constant.

Figure 1: $t_{\mathrm{mix}}^{(n)}(0.01)$ when
$\frac{k}{n}=0.05,\frac{r}{n}=0.40,m=r$ Figure 2:
$t_{\mathrm{mix}}^{(n)}(0.01)$ when $\frac{k}{n}=0.10,\frac{r}{n}=0.40,m=r$
Figure 3: $t_{\mathrm{mix}}^{(n)}(0.01)$ when
$\frac{k}{n}=0.25,\frac{r}{n}=0.50,m=r$

In Tables 1 and 2, we vary ${k\over n}$ and ${r\over n}$, respectively, while
fixing $m=r$. In Table 3, we vary ${m\over n}$.

Notice in Table 1 that the mixing times appear to reach a minimum at ${k\over
n}={r\over n}(1-{r\over n})$. This makes sense in light of Theorems 1.4 and
4.2. For very low values of ${k\over n}$ (closer to $0$) and very high values
of ${k\over n}$ (closer to ${r\over n}$), the mixing times quickly increase.

However, as shown in Tables 2 and 3, mixing times increase monotonically in
${m\over n}$. This makes sense given the behavior of $t_{n}$ under the same
conditions. Tables 2 and 3 are so similar because the corresponding rows in
each table differ only by their values of $\eta$, and as Theorem 1.4 proves,
this allows for at most bounded difference in the mixing times. The data does
consistently show, though, that mixing occurs faster $\eta=0.50$ than
$\eta<0.50$.

(k/n, n) | $50$ | $100$ | $150$ | $200$ | $250$ | $300$ | $350$ | $400$ | $450$ | $500$ | $550$ | $600$ | $650$ | $700$ | $750$ | $800$ | $850$ | $900$ | $950$ | $1000$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$0.02$ | $68$ | $72$ | $75$ | $76$ | $78$ | $79$ | $80$ | $81$ | $81$ | $82$ | $83$ | $83$ | $84$ | $84$ | $84$ | $85$ | $85$ | $85$ | $86$ | $86$
$0.04$ | $33$ | $35$ | $36$ | $37$ | $37$ | $38$ | $38$ | $39$ | $39$ | $39$ | $40$ | $40$ | $40$ | $40$ | $41$ | $41$ | $41$ | $41$ | $41$ | $41$
$0.06$ | $21$ | $22$ | $23$ | $24$ | $24$ | $24$ | $25$ | $25$ | $25$ | $25$ | $25$ | $26$ | $26$ | $26$ | $26$ | $26$ | $26$ | $26$ | $26$ | $27$
$0.08$ | $15$ | $16$ | $17$ | $17$ | $17$ | $17$ | $18$ | $18$ | $18$ | $18$ | $18$ | $18$ | $18$ | $19$ | $19$ | $19$ | $19$ | $19$ | $19$ | $19$
$0.10$ | $12$ | $12$ | $13$ | $13$ | $13$ | $13$ | $13$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$
$0.12$ | $9$ | $10$ | $10$ | $10$ | $10$ | $10$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$
$0.14$ | $7$ | $8$ | $8$ | $8$ | $8$ | $8$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$
$0.16$ | $6$ | $6$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$
$0.18$ | $5$ | $5$ | $5$ | $5$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$
$0.20$ | $4$ | $4$ | $4$ | $4$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$
$0.22$ | $3$ | $3$ | $3$ | $3$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$
$0.24$ | $2$ | $2$ | $2$ | $2$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$
$0.26$ | $2$ | $2$ | $2$ | $2$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$ | $3$
$0.28$ | $3$ | $3$ | $3$ | $3$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$ | $4$
$0.30$ | $4$ | $4$ | $4$ | $4$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$ | $5$
$0.32$ | $5$ | $5$ | $5$ | $5$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$ | $6$
$0.34$ | $6$ | $6$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$
$0.36$ | $7$ | $8$ | $8$ | $8$ | $8$ | $8$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$ | $9$
$0.38$ | $9$ | $10$ | $10$ | $10$ | $10$ | $10$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$ | $11$
$0.40$ | $12$ | $12$ | $13$ | $13$ | $13$ | $13$ | $13$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$ | $14$
$0.42$ | $15$ | $16$ | $17$ | $17$ | $17$ | $17$ | $18$ | $18$ | $18$ | $18$ | $18$ | $18$ | $18$ | $19$ | $19$ | $19$ | $19$ | $19$ | $19$ | $19$
$0.44$ | $21$ | $22$ | $23$ | $24$ | $24$ | $24$ | $25$ | $25$ | $25$ | $25$ | $25$ | $26$ | $26$ | $26$ | $26$ | $26$ | $26$ | $26$ | $26$ | $27$
$0.46$ | $33$ | $35$ | $36$ | $37$ | $37$ | $38$ | $38$ | $39$ | $39$ | $39$ | $40$ | $40$ | $40$ | $40$ | $41$ | $41$ | $41$ | $41$ | $41$ | $41$
$0.48$ | $68$ | $72$ | $75$ | $76$ | $78$ | $79$ | $80$ | $81$ | $81$ | $82$ | $83$ | $83$ | $84$ | $84$ | $84$ | $85$ | $85$ | $85$ | $86$ | $86$
$0.50$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$

Table 1: $t_{\mathrm{mix}}^{(n)}(0.01)$ when
$\frac{k}{n}\in\\{0.02,0.04,\dots,0.48,0.50\\},\frac{r}{n}=0.50$, $m=r$

$({r\over n},n)$ | $50$ | $100$ | $150$ | $200$ | $250$ | $300$ | $350$ | $400$ | $450$ | $500$ | $550$ | $600$ | $650$ | $700$ | $750$ | $800$ | $850$ | $900$ | $950$ | $1000$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$0.02$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$
$0.04$ | $8$ | $8$ | $9$ | $9$ | $9$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$
$0.06$ | $13$ | $14$ | $15$ | $15$ | $15$ | $15$ | $16$ | $16$ | $16$ | $16$ | $16$ | $16$ | $16$ | $16$ | $16$ | $17$ | $17$ | $17$ | $17$ | $17$
$0.08$ | $19$ | $20$ | $20$ | $21$ | $21$ | $21$ | $21$ | $22$ | $22$ | $22$ | $22$ | $22$ | $22$ | $22$ | $23$ | $23$ | $23$ | $23$ | $23$ | $23$
$0.10$ | $23$ | $24$ | $25$ | $26$ | $26$ | $26$ | $27$ | $27$ | $27$ | $27$ | $28$ | $28$ | $28$ | $28$ | $28$ | $28$ | $29$ | $29$ | $29$ | $29$
$0.12$ | $28$ | $29$ | $30$ | $31$ | $31$ | $32$ | $32$ | $32$ | $33$ | $33$ | $33$ | $33$ | $33$ | $34$ | $34$ | $34$ | $34$ | $34$ | $34$ | $35$
$0.14$ | $31$ | $33$ | $34$ | $35$ | $36$ | $36$ | $37$ | $37$ | $38$ | $38$ | $38$ | $38$ | $39$ | $39$ | $39$ | $39$ | $39$ | $40$ | $40$ | $40$
$0.16$ | $36$ | $38$ | $39$ | $40$ | $41$ | $41$ | $41$ | $42$ | $42$ | $43$ | $43$ | $43$ | $43$ | $44$ | $44$ | $44$ | $44$ | $44$ | $45$ | $45$
$0.18$ | $39$ | $42$ | $43$ | $44$ | $45$ | $45$ | $46$ | $46$ | $47$ | $47$ | $47$ | $48$ | $48$ | $48$ | $49$ | $49$ | $49$ | $49$ | $49$ | $50$
$0.20$ | $42$ | $45$ | $47$ | $48$ | $49$ | $49$ | $50$ | $50$ | $51$ | $51$ | $52$ | $52$ | $52$ | $53$ | $53$ | $53$ | $53$ | $54$ | $54$ | $54$
$0.22$ | $46$ | $49$ | $50$ | $52$ | $52$ | $53$ | $54$ | $54$ | $55$ | $55$ | $56$ | $56$ | $56$ | $57$ | $57$ | $57$ | $57$ | $58$ | $58$ | $58$
$0.24$ | $49$ | $52$ | $54$ | $55$ | $56$ | $57$ | $57$ | $58$ | $58$ | $59$ | $59$ | $60$ | $60$ | $60$ | $61$ | $61$ | $61$ | $62$ | $62$ | $62$
$0.26$ | $52$ | $55$ | $57$ | $58$ | $59$ | $60$ | $61$ | $61$ | $62$ | $62$ | $63$ | $63$ | $64$ | $64$ | $64$ | $65$ | $65$ | $65$ | $65$ | $66$
$0.28$ | $54$ | $58$ | $60$ | $61$ | $62$ | $63$ | $64$ | $64$ | $65$ | $66$ | $66$ | $66$ | $67$ | $67$ | $67$ | $68$ | $68$ | $68$ | $69$ | $69$
$0.30$ | $57$ | $60$ | $62$ | $64$ | $65$ | $66$ | $67$ | $67$ | $68$ | $68$ | $69$ | $69$ | $70$ | $70$ | $70$ | $71$ | $71$ | $71$ | $72$ | $72$
$0.32$ | $59$ | $63$ | $65$ | $66$ | $67$ | $68$ | $69$ | $70$ | $70$ | $71$ | $71$ | $72$ | $72$ | $73$ | $73$ | $73$ | $74$ | $74$ | $74$ | $75$
$0.34$ | $61$ | $65$ | $67$ | $68$ | $69$ | $71$ | $71$ | $72$ | $73$ | $73$ | $74$ | $74$ | $75$ | $75$ | $75$ | $76$ | $76$ | $76$ | $77$ | $77$
$0.36$ | $63$ | $66$ | $69$ | $70$ | $72$ | $72$ | $73$ | $74$ | $75$ | $75$ | $76$ | $76$ | $77$ | $77$ | $78$ | $78$ | $78$ | $79$ | $79$ | $79$
$0.38$ | $64$ | $68$ | $70$ | $72$ | $73$ | $74$ | $75$ | $76$ | $76$ | $77$ | $78$ | $78$ | $79$ | $79$ | $79$ | $80$ | $80$ | $80$ | $81$ | $81$
$0.40$ | $65$ | $69$ | $72$ | $73$ | $75$ | $76$ | $76$ | $77$ | $78$ | $79$ | $79$ | $80$ | $80$ | $80$ | $81$ | $81$ | $82$ | $82$ | $82$ | $83$
$0.42$ | $66$ | $70$ | $73$ | $74$ | $76$ | $77$ | $78$ | $79$ | $79$ | $80$ | $80$ | $81$ | $81$ | $82$ | $82$ | $83$ | $83$ | $83$ | $84$ | $84$
$0.44$ | $67$ | $71$ | $74$ | $75$ | $77$ | $78$ | $79$ | $79$ | $80$ | $81$ | $81$ | $82$ | $82$ | $83$ | $83$ | $84$ | $84$ | $84$ | $85$ | $85$
$0.46$ | $68$ | $72$ | $74$ | $76$ | $77$ | $78$ | $79$ | $80$ | $81$ | $81$ | $82$ | $82$ | $83$ | $83$ | $84$ | $84$ | $85$ | $85$ | $85$ | $86$
$0.48$ | $68$ | $72$ | $75$ | $76$ | $78$ | $79$ | $80$ | $80$ | $81$ | $82$ | $82$ | $83$ | $83$ | $84$ | $84$ | $85$ | $85$ | $85$ | $86$ | $86$
$0.50$ | $68$ | $72$ | $75$ | $76$ | $78$ | $79$ | $80$ | $81$ | $81$ | $82$ | $83$ | $83$ | $84$ | $84$ | $84$ | $85$ | $85$ | $85$ | $86$ | $86$

Table 2: $t_{\mathrm{mix}}^{(n)}(0.01)$ when
$\frac{k}{n}=0.02,\frac{r}{n}\in\\{0.02,0.04,\dots,0.48,0.50\\}$, $m=r$

$({m\over n},n)$ | $50$ | $100$ | $150$ | $200$ | $250$ | $300$ | $350$ | $400$ | $450$ | $500$ | $550$ | $600$ | $650$ | $700$ | $750$ | $800$ | $850$ | $900$ | $950$ | $1000$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$0.02$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$
$0.04$ | $6$ | $6$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $7$ | $8$ | $8$ | $8$ | $8$ | $8$ | $8$ | $8$ | $8$ | $8$ | $8$ | $8$
$0.06$ | $10$ | $11$ | $12$ | $12$ | $12$ | $12$ | $12$ | $13$ | $13$ | $13$ | $13$ | $13$ | $13$ | $13$ | $13$ | $13$ | $13$ | $14$ | $14$ | $14$
$0.08$ | $14$ | $15$ | $16$ | $17$ | $17$ | $17$ | $17$ | $18$ | $18$ | $18$ | $18$ | $18$ | $18$ | $19$ | $19$ | $19$ | $19$ | $19$ | $19$ | $19$
$0.10$ | $19$ | $20$ | $21$ | $21$ | $22$ | $22$ | $22$ | $23$ | $23$ | $23$ | $23$ | $24$ | $24$ | $24$ | $24$ | $24$ | $24$ | $24$ | $24$ | $25$
$0.12$ | $22$ | $24$ | $25$ | $26$ | $26$ | $27$ | $27$ | $28$ | $28$ | $28$ | $28$ | $29$ | $29$ | $29$ | $29$ | $29$ | $29$ | $29$ | $30$ | $30$
$0.14$ | $27$ | $28$ | $30$ | $30$ | $31$ | $31$ | $32$ | $32$ | $33$ | $33$ | $33$ | $33$ | $34$ | $34$ | $34$ | $34$ | $34$ | $35$ | $35$ | $35$
$0.16$ | $30$ | $32$ | $34$ | $35$ | $35$ | $36$ | $36$ | $37$ | $37$ | $37$ | $38$ | $38$ | $38$ | $39$ | $39$ | $39$ | $39$ | $39$ | $39$ | $40$
$0.18$ | $34$ | $36$ | $38$ | $39$ | $40$ | $40$ | $41$ | $41$ | $42$ | $42$ | $42$ | $43$ | $43$ | $43$ | $43$ | $44$ | $44$ | $44$ | $44$ | $44$
$0.20$ | $37$ | $40$ | $42$ | $43$ | $44$ | $44$ | $45$ | $45$ | $46$ | $46$ | $47$ | $47$ | $47$ | $47$ | $48$ | $48$ | $48$ | $48$ | $49$ | $49$
$0.22$ | $41$ | $44$ | $45$ | $46$ | $47$ | $48$ | $49$ | $49$ | $50$ | $50$ | $51$ | $51$ | $51$ | $52$ | $52$ | $52$ | $52$ | $53$ | $53$ | $53$
$0.24$ | $44$ | $47$ | $49$ | $50$ | $51$ | $52$ | $52$ | $53$ | $54$ | $54$ | $54$ | $55$ | $55$ | $55$ | $56$ | $56$ | $56$ | $57$ | $57$ | $57$
$0.26$ | $47$ | $50$ | $52$ | $53$ | $54$ | $55$ | $56$ | $57$ | $57$ | $58$ | $58$ | $58$ | $59$ | $59$ | $59$ | $60$ | $60$ | $60$ | $61$ | $61$
$0.28$ | $50$ | $53$ | $55$ | $57$ | $58$ | $59$ | $59$ | $60$ | $60$ | $61$ | $61$ | $62$ | $62$ | $63$ | $63$ | $63$ | $64$ | $64$ | $64$ | $64$
$0.30$ | $53$ | $56$ | $58$ | $59$ | $61$ | $62$ | $62$ | $63$ | $64$ | $64$ | $65$ | $65$ | $65$ | $66$ | $66$ | $66$ | $67$ | $67$ | $67$ | $68$
$0.32$ | $55$ | $59$ | $61$ | $62$ | $63$ | $64$ | $65$ | $66$ | $66$ | $67$ | $68$ | $68$ | $68$ | $69$ | $69$ | $69$ | $70$ | $70$ | $70$ | $71$
$0.34$ | $57$ | $61$ | $63$ | $65$ | $66$ | $67$ | $68$ | $68$ | $69$ | $70$ | $70$ | $71$ | $71$ | $72$ | $72$ | $72$ | $73$ | $73$ | $73$ | $73$
$0.36$ | $59$ | $63$ | $65$ | $67$ | $68$ | $69$ | $70$ | $71$ | $72$ | $72$ | $73$ | $73$ | $74$ | $74$ | $74$ | $75$ | $75$ | $75$ | $76$ | $76$
$0.38$ | $61$ | $65$ | $68$ | $69$ | $70$ | $71$ | $72$ | $73$ | $74$ | $74$ | $75$ | $75$ | $76$ | $76$ | $77$ | $77$ | $77$ | $78$ | $78$ | $78$
$0.40$ | $63$ | $67$ | $69$ | $71$ | $72$ | $73$ | $74$ | $75$ | $76$ | $76$ | $77$ | $77$ | $78$ | $78$ | $79$ | $79$ | $79$ | $80$ | $80$ | $80$
$0.42$ | $65$ | $68$ | $71$ | $72$ | $74$ | $75$ | $76$ | $77$ | $77$ | $78$ | $78$ | $79$ | $79$ | $80$ | $80$ | $81$ | $81$ | $81$ | $82$ | $82$
$0.44$ | $65$ | $70$ | $72$ | $74$ | $75$ | $76$ | $77$ | $78$ | $79$ | $79$ | $80$ | $80$ | $81$ | $81$ | $82$ | $82$ | $82$ | $83$ | $83$ | $83$
$0.46$ | $67$ | $71$ | $73$ | $75$ | $76$ | $77$ | $78$ | $79$ | $80$ | $80$ | $81$ | $82$ | $82$ | $82$ | $83$ | $83$ | $84$ | $84$ | $84$ | $85$
$0.48$ | $67$ | $72$ | $74$ | $76$ | $77$ | $78$ | $79$ | $80$ | $81$ | $81$ | $82$ | $82$ | $83$ | $83$ | $84$ | $84$ | $85$ | $85$ | $85$ | $85$
$0.50$ | $68$ | $72$ | $75$ | $76$ | $78$ | $79$ | $80$ | $81$ | $81$ | $82$ | $83$ | $83$ | $84$ | $84$ | $84$ | $85$ | $85$ | $85$ | $86$ | $86$

Table 3: $t_{\mathrm{mix}}^{(n)}(0.01)$ when $\frac{k}{n}=0.02,{r\over
n}=0.50,\frac{m}{n}\in\\{0.02,0.04,\dots,0.48,0.50\\}$

##  6 Acknowledgements

All authors were supported by NSF grant 1950583 for work done during the 2023
Iowa State Mathematics REU.

## References

  * [1] Joseph S. Alameda et al.  “Cutoff in the Bernoulli-Laplace model with $O(n)$ swaps”, 2022  arXiv:2203.08647 [math.PR]
  * [2] Alexandros Eskenazis and Evita Nestoridi  “Cutoff for the Bernoulli–Laplace urn model with $o(n)$ swaps”  In _Annales de l’Institut Henri Poincaré, Probabilités et Statistiques_ 56.4 Institut Henri Poincaré, 2020, pp. 2621–2639  DOI: 10.1214/20-AIHP1052
  * [3] Wassily Höffding  “Probability inequalities for sums of bounded random variables”  In _The collected works of Wassily Höffding_ Springer, 1994, pp. 409–426
  * [4] Kshitij Khare and Hua Zhou  “Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions”  In _The Annals of Applied Probability_ 19.2 Institute of Mathematical Statistics, 2009, pp. 737–777  DOI: 10.1214/08-AAP562
  * [5] S.N. Lahiri, A. Chatterjee and T. Maiti  “Normal approximation to the hypergeometric distribution in nonstandard cases and a sub-Gaussian Berry–Esseen theorem” Special Issue: In Celebration of the Centennial of The Birth of Samarendra Nath Roy (1906-1964)  In _Journal of Statistical Planning and Inference_ 137.11, 2007, pp. 3570–3590  DOI: https://doi.org/10.1016/j.jspi.2007.03.033
  * [6] Evita Nestoridi and Graham White  “Shuffling Large Decks of Cards and the Bernoulli–Laplace Urn Model”  In _Journal of Theoretical Probability_ 32 Springer, 2019, pp. 417–446
  * [7] Djaouad Taïbi  “Une généralisation du modèle de diffusion de Bernoulli–Laplace”  In _Journal of Applied Probability_ 33.3 Cambridge University Press, 1996, pp. 688–697