# Pseudorandomness of the Sticky Random Walk

Emile Anand
Computing and Mathematical Sciences
California Institute of Technology
Pasadena, CA, 91125
<EMAIL_ADDRESS>
& Chris Umans
Computing and Mathematical Sciences
California Institute of Technology
Pasadena, CA, 91125
<EMAIL_ADDRESS>

###### Abstract

We extend the pseudorandomness of random walks on expander graphs using the
sticky random walk. Building on the works of [4] [10], [13] recently showed
that expander random walks can fool all symmetric functions in total variation
distance (TVD) upto an $O(\lambda(\frac{p}{\min f})^{O(p)})$ error, where
$\lambda$ is the second largest eigenvalue of the expander, $p$ is the size of
the arbitrary alphabet used to label the vertices, and $\min
f=\min_{b\in[p]}f_{b}$, where $f_{b}$ is the fraction of vertices labeled $b$
in the graph. [13] conjectures that the dependency on the $(\frac{p}{\min
f})^{O(p)}$ term is not tight. In this paper, we resolve the conjecture in the
affirmative for a family of expanders. We present a generalization of [10]’s
sticky random walk for which [13] predicts a TVD upper bound of $O(\lambda
p^{O(p)})$ using a Fourier-analytic approach. For this family of graphs, we
use a combinatorial approach involving the Krawtchouk functions used in [10]
to derive a strengthened TVD of $O(\lambda)$. Furthermore, we present
equivalencies between the generalized sticky random walk, and, using linear-
algebraic techniques, show that the generalized sticky random walk is an
infinite family of expander graphs.

_Keywords_ Sticky Random Walk $\cdot$ Expander Graphs $\cdot$ Pseudorandomness
$\cdot$ Derandomization

##  1 Introduction

Expander graphs are undirected spectral sparsifiers of the clique with high
expansion properties, and they are among the most useful combinatorial objects
in theoretical computer science due to their applications in pseudorandomness
and in error-correcting codes (see [15][22][26][23][18]). A $d$-regular graph
$G\\!=\\!(V\\!,\\!E)$ where $|V|\\!=\\!n$ is said to be an
$(n,d,\lambda)$-expander if (for eigenvalues
$\lambda_{1}\geq\lambda_{2}\geq\cdots\lambda_{n}=-1$ of its normalized
adjacency matrix $A$) the second largest magnitude of the eigenvalue of its
adjacency matrix $A$ is atmost $\lambda$. In other words, $\max_{i\neq
1}|\lambda_{i}|\leq\lambda$. It is a well-known fact that $\lambda\leq 1$
implies $G$ is connected; so, smaller values of $\lambda$ pertain to stronger
combinatorial connectivity properties (see [24]). There are several known
constructions [17][3][23][20] of optimal (Ramanujan) expander graphs that
saturate the Alon-Boppana bound [8] which characterizes “good” expanders. The
most useful fact about expander graphs in pseudorandomness arises from the
fact that random walks on them mix fast. Let $v_{0},...,v_{t-1}$ be a sequence
of vertices obtained by a $t$-step walk on an expander graph $G$ with second
largest eigenvalue atmost $\lambda$. Gilman’s [9] results uses the Chernoff
bound to characterize the rate of mixing (this has since been improved in [19]
and [13]).

_Expander-Walk Chernoff Bound (Gilman)_. For graph $G=(V,E)$, let
$v_{0},\dots,v_{t-1}$ denote a sequence of vertices obtained from a $t$-step
-walk on an expander graph $G$. For any function $f:[n]\to\\{0,1\\}$, let the
stationary distribution of $G$ be
$\pi(f):=\lim_{t\to\infty}\frac{1}{t}\sum_{i=0}^{t-1}f(v_{i})$. The expander-
walk Chernoff bound [9] states that $\forall\varepsilon>0$,

$\Pr\left[\left|\frac{1}{t}\sum_{i=0}^{t-1}f(X_{i})-\pi(f)\right|\geq\varepsilon\right]\leq
2e^{-\Omega((\lambda-\varepsilon)^{2}t)}$

For a proof of the expander walk Chernoff bound, we refer the reader to
[22][16][19]. An important direct consequence of the expander Chernoff bound
is that the mixing time of a $d$-regular expander graph on $n$ vertices is
atmost $O(\log n)$.

Expander graphs have (oftentimes, surprisingly) ubiquitous applications. They
were initially studied for the purpose of constructing fault-tolerant networks
in [14], where if a small number of channels (edges) broke down, the system
could be made to be still largely intact due to its good connectivity
properties if it were modeled as an expander. More recently, they have been
used in representation learning theoretic settings (see [7]) to create graph
neural networks that can propagate information to train models more
efficiently. In coding theory, expander codes (created from linear bipartite
expanders - see [1]) are the only known construction (see [23]) of
asymptotically good error-correcting codes which can be decoded in linear time
when a constant fraction of symbols are in error.

More recent works that combine ideas from combinatorial topology and algebraic
geometry have also led to the exciting study of high dimensional expanders
(HDX) which are pure simplicial complexes (hypergraphs that are downwards
closed under containment) where the $1$-skeletons are spectral expanders and
the links exhibit good expansion properties. We direct the reader to [5] and
[11].

One of the most important applications of expanders (which is the topic of
this thesis) is on derandomization and in pseudorandomness. Suppose that there
is a randomized algorithm for a language $L$ using $n$ bits such that: If a
string $x\in L$, then the algorithm accepts with probability $1$. If a string
$x\notin L$, then the algorithm rejects with probability atleast $1/2$. Our
goal is to reduce the error probability of the algorithm. If we repeat the
algorithm $t$ times then the error probability goes down to $1/2^{t}$, which
is ideal. However, the number of random bits used by the algorithm is then
equal to $nt$, which is very large. One work around is to “reuse the
randomness by weakening our independent choices to correlated choices on an
expander graph” [12]. If we start at a random vertex in $G$ (which is a random
number in $\\{0,\dots,n\\}$ which uses $\log n$ random bits) and pick random
neighbors of $v$, then since a good expander has degree $d=O(1)$ and since we
need $\log d=O(1)$ bits, we can continue this process till we pick $t$
vertices overall, and the overall number of random bits that we would need
would be equal to $\log n+O(t)$. Further, by the expander mixing lemma, for
$t\gg O(\log n)$ the sequence of vertices will still be extremely close to
uniformly random.

This makes expander graphs invaluable in the field of pseudorandomness.
Consider the $t$-step expander random walk which generates a sequence of
vertices $v_{0},\dots,v_{t-1}$. We are then interested in the degree to which
$(v_{0},\dots,v_{t-1})$ “fool” classes of test functions, where we say that a
test-function $T$ is $\epsilon$-fooled by a pseudorandom function
$g:X\to[\chi]$ if the statistical distance between distributions $T(g(X))$ and
$T(U)$ (here $U$ is the uniform distribution on $[\chi]$), is less than
$\epsilon$.

Ta-Shma’s breakthrough construction of optimal $\epsilon$-balanced codes [25]
which showed that expander random walk can fool the extremely sensitive parity
function led to an exciting series of results that showed the pseudorandomness
of expander random walks for increasingly many classes of test functions. [10]
introduces the ‘sticky random walk’, a canonical two-vertex expander which can
be thought of as a Markov chain on two states, where the probability of
switching between states is $\frac{1+\lambda}{2}$ and the probability of
staying at the same state is $\frac{1-\lambda}{2}$. [10] goes on to use the
discrete orthogonal Krawtchouk functions to show that the Hamming weight
distribution of the sticky random walk can fool any symmetric function with
error $O(\lambda)$, where $\lambda<0.16$. [6][4] then used Fourier analysis to
expand this result. Specifically, they showed that test functions computed by
$\mathrm{AC}^{0}$ circuits and symmetric functions are fooled by the random
walks on the full expander random walk, but only for balanced binary
labelings. These works culminate in [13] which establishes that random walks
on expanders where the vertices are labeled from an arbitrary alphabet can
fool symmetric functions (upto an $O(\lambda)$ error) and permutation
branching programs. Specifically, we are interested in the result concerning
symmetric functions (Theorem 2) which we restate below.

_Fooling symmetric functions (Corollary 4 of[13])_. For all integers $t\geq 1$
and $p\geq 2$, let $G=(G_{i})_{1\leq i\leq t-1}$ be a sequence of
$\lambda$-spectral expanders on a shared vertex set $V$ with labeling
$\mathrm{val}:V\to[p]$ that assigns each label $b\in[p]$ to $f_{b}$-fraction
of the vertices. Then, for any label $b$, we have that the total variation
distance between the number of $b$’s seen in the expander random walk and the
uniform distribution on $[p]$ has the following bound (where $[\Sigma(Z)_{b}]$
counts the number of occurrences of $b$ in $Z$):

$\mathrm{TVD}([\Sigma(\mathrm{RW}^{t}_{\mathcal{G}})]_{b},[\Sigma(U[d])]_{b})\leq
O\left(\left(\frac{p}{\min_{b\in[p]}f_{b}}\right)^{O(p)}\cdot\lambda\right)$

[13] asks whether the $(\frac{p}{\min_{b\in[p]}f_{b}})^{O(p)}$ dependence in
the upper bound of the total variation distance is tight. In this paper, we
answer in the negative for a family of graphs. Specifically, we present a
family of generalized sticky random walks (where the alphabet size can be
arbitrarily large), where in Theorem 5.3 we find that the optimal TVD is
$O(\lambda)$, for $\lambda<0.27$, whereas Corollary 4 in [13] predicts a bound
of $O(\lambda p^{2p})$, which provides evidence that the
$(\frac{p}{\min_{b\in[p]f_{b}}})^{O(p)}$ factor is not tight. [10] studied the
sticky random walk because it was an “essential step” to understanding the
full expander random walk - specifically, theorem $4$ in [10] shows that every
$\lambda$-parameterized sticky random walk is bijective with a corresponding
expander graph. We extend their result in Theorem 7.1 by showing that our
generalized sticky random walk (parameterized by $\lambda$ and $p$ also
correspond to expander graphs with a linearly-reduced spectral expansion of
$\lambda p$. We then show that our generalized sticky random walk reduces from
[10]’s two-vertex sticky random walk in Theorem 7.2. Finally, in Appendix B we
provide a novel alternate treatment of the Krawtchouk functions into the
complex domain which can be used to attain an $O(\lambda p^{p})$ bound on the
TVD.

##  2 Preliminaries: Notation and Conventions

This section describes the basic notation and problem setup that is used
throughout the paper.

For any $n\in\operatorname*{\mathbb{N}}$, let $[n]=\\{1,...,n\\}$ and
$\operatorname*{\mathbb{Z}}_{n}=\\{0,...,n-1\\}$. Next, let $[n]^{k}$ denote
$k$ copies of elements in $[n]$, and let $\operatorname*{\mathbb{Z}}_{n}^{k}$
denote $k$ copies of elements in $\operatorname*{\mathbb{Z}}_{n}$.
Furthermore, let $\genfrac{(}{)}{0.0pt}{1}{[n]}{k}$ denote the set of all
$k$-sized subsets of $[n]$, which has cardinality
$\genfrac{(}{)}{0.0pt}{1}{n}{k}$. For any $n$-bit string $s$, let $|s|$ denote
the Hamming weight (the Hamming distance from $0^{n}$) of $s$. Similarly, let
$|s|_{i}$ denote the number of $i$’s in $s$. We generalize the notion of
counting the number of occurrences of any character
$\chi\in\operatorname*{\mathbb{Z}}_{p}$ for $p\geq 2$ with the symmetric
function
$\Sigma(x):\operatorname*{\mathbb{Z}}_{p}^{n}\rightarrow\operatorname*{\mathbb{Z}}_{n}^{p}$,
where $\Sigma(x)$ is a vector that counts the number of occurrences of each
$\chi\in\operatorname*{\mathbb{Z}}_{p}$. Specifically, for all
$\chi\in\operatorname*{\mathbb{Z}}_{p}$ and for all
$x\in\operatorname*{\mathbb{Z}}_{p}^{n}$, we can write that
$[\Sigma(x)]_{\chi}=|\\{i\in x:x_{i}=\chi\\}|=|x|_{\chi}$.

Let $\mathrm{Ber}(q)$ denote the Bernoulli distribution on $\\{0,1\\}$, such
that if $X\sim\mathrm{Ber}(q)$, then $\Pr[X=1]=q$ and $\Pr[X=0]=1-q$. Next,
let $\mathrm{Bin}(n,1/2)$ denote the binomial distribution of
$\sum_{i=1}^{n}b_{i}$ with independent choices of $b_{i}\sim$ Ber($1/2$). Let
$\mathrm{U}_{p}^{n}=\mathrm{U}[\\{0,\dots,p-1\\}]^{n}$ denote $n$ samples of
the uniform distribution on $\operatorname*{\mathbb{Z}}_{p}$, where each
number is sampled with probability $1/p$. Then,
$[\Sigma(\mathrm{U}_{p}^{n})]_{0}$ reports the number of $0$’s in an $n$-bit
sample from the uniform distribution on $\operatorname*{\mathbb{Z}}_{p}$.
Furthermore, we write that $x\in A$ if $x$ is an element of $A$, and
$x\in_{U}A$ if $x$ is an element chosen uniformly randomly from $A$. Finally,
we use $\overline{C}$ to denote the complement of a set $C\subseteq\Omega$,
and for any two sets $A,B\subseteq\Omega$, we define their symmetric
difference $A\Delta B$ as $(A\cap\overline{B})\cup(B\cap\overline{A})$.

######  Definition 1 ($(n,d,\lambda)$-expanders).

_A $d$-regular graph $G=(V,E)$ where $|V|=n,|E|=m$ is said to be an
$(n,d,\lambda)$-expander if (for eigenvalues
$1=\lambda_{1}\geq\lambda_{2}\geq\cdots\lambda_{n}=-1$ of its degree-
normalized adjacency matrix $A$) the second largest magnitude of the
eigenvalue of its adjacency matrix $A$ is atmost $\lambda$. In other words,
$\max_{i\neq 1}|\lambda_{i}|\leq\lambda$. Intuitively, the spectrum
($\lambda_{1},...,\lambda_{n}$) of an expander graph approximates the spectrum
of the complete graph, which makes expanders a spectral sparsification of the
clique._

######  Definition 2 (Sticky Random Walk).

_The Sticky Random Walk (SRW) $S(n,\lambda)$ is a distribution on $n$-bit
strings that represent $n$-step walks on a Markov chain with states
$\\{0,1\\}$ such that for each $s\sim
S(n,\lambda),\Pr[s_{i+1}=b|s_{i}=b]=\frac{1+\lambda}{2}$, for $b\in\\{0,1\\}$,
and $s_{1}\sim$ Ber($1/2$) such that $\Pr[s_{1}=0]=\Pr[s_{1}=1]=1/2$. As
$\lambda\to 0$, the distribution of strings from the Markov chain converges to
the distribution of $n$ independent coin-flips._

Figure 1: The Markov chain of the sticky random walk $S(n,\lambda)$.

######  Definition 3 (Krawtchouk Functions).

_The Krawtchouk function
$K_{k}:\operatorname*{\mathbb{Z}}_{n+1}\rightarrow\operatorname*{\mathbb{R}}$
is defined, for $\ell\in\operatorname*{\mathbb{Z}}_{n+1}$ and an arbitrary
$n$-bit string $\alpha$ where $|\alpha|=\ell$, ($|\cdot|$ is the number of
$0$’s) such that:_

$K_{k}(\ell):=\sum_{\begin{subarray}{c}y\in\\{0,1\\}^{n}\\\
|y|=k\end{subarray}}(-1)^{\alpha\cdot
y}=\sum_{t=0}^{k}(-1)^{t}\genfrac{(}{)}{0.0pt}{0}{\ell}{t}\genfrac{(}{)}{0.0pt}{0}{n-\ell}{k-j}$

######  Lemma 2.1 (Krawtchouk orthogonality).

_The Krawtchouk function is orthogonal with respect to functions mapping
$[n]_{0}\to\operatorname*{\mathbb{R}}$ with respect to the inner product. The
proof of this is deferred to Appendix A. Specifically_:

$\langle
K_{r},K_{s}\rangle=\operatorname*{\mathbb{E}}_{b\sim\mathrm{Bin}(n,1/2)}[K_{r}(b)K_{s}(b)]=\begin{cases}0,&\text{if
}r\neq s\\\ \genfrac{(}{)}{0.0pt}{4}{n}{s},&\text{if }r=s\end{cases}$

######  Lemma 2.2 (Krawtchouk invariance).

_The Krawtchouk function is invariant against choices of $\alpha$ which
satisfy $|\alpha|=\ell$. This statement is proven in [21]. We formally state
this property below:_

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}|L|=k\\\ \mathrm{Fixed}\text{
}A\in\operatorname*{\mathbb{Z}}_{p}^{n}\\\
|A|=\ell\end{subarray}}[(-1)^{A\cdot
B}]=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}|L|=k\\\
\mathrm{Random}\text{ }A^{\prime}\in\operatorname*{\mathbb{Z}}_{p}^{n}\\\
|A^{\prime}|=\ell\end{subarray}}[(-1)^{A^{\prime}\cdot B}]$

######  Definition 4 (Total variation distance).

_Given a measure space $(\Omega,\mathcal{F},\mu)$ and a $\sigma$-algebra
$\mathcal{A}\subseteq\mathcal{F}$, the total variational distance
$d_{\text{TV}}(\mu_{1},\mu_{2})$ between probability measures
$\mu_{1},\mu_{2}:\mathcal{F}\rightarrow\operatorname*{\mathbb{R}}$ is_

$d_{\text{TV}}(\mu_{1},\mu_{2})=\sup_{A\in\mathcal{A}}|\mu_{1}(A)-\mu_{2}(A)|$

_Similarly, the $\ell_{1}$ distance between $\mu_{1}$ and $\mu_{2}$ is defined
as $d_{\ell_{1}}(\mu_{1},\mu_{2})=2d_{\text{TV}}(\mu_{1},\mu_{2})$.
Additionally, for countable $\Omega$ and $\mathcal{A}=2^{\Omega}$, we have
$d_{\ell_{1}}(\mu_{1},\mu_{2})=\sum_{x\in\Omega}|\mu_{1}(x)-\mu_{2}(x)|$.
Transitively,_

$d_{\text{TV}}(\mu_{1},\mu_{2})=\frac{1}{2}\sum\limits_{x\in\Omega}|\mu_{1}(x)-\mu_{2}(x)|$

######  Definition 5.

[Primitive root of unity] _For $p\geq 2$, let $\omega_{p}$ denote the $p^{th}$
primitive root of unity if it satisfies $(\omega_{p})^{p}=1$, and if there
does not exist $q\in\operatorname*{\mathbb{N}}$ where $q<p$ such that
$(\omega_{p})^{q}=1$. Specifically, the multiplicative order of the $p^{th}$
primitive root of unity must be $p$. Then, for $1\leq k<p$, we must have that_

$\sum\limits_{j=0}^{p-1}(\omega_{p})^{kj}=\omega_{p}^{k\cdot
0}+\omega_{p}^{k\cdot 1}+...+\omega_{p}^{k\cdot(p-1)}=0$

##  3 A Generalization of the Sticky Random Walk

We consider the case where the vertices of the sticky random walk (SRW) can be
labeled with an arbitrary alphabet $\operatorname*{\mathbb{Z}}_{p}$, since a
decomposition of the vertex-set $V=\\{0,\dots,p-1\\}=V_{1}\sqcup...\sqcup
V_{q}$ for $q\geq 2$, could allow us to model random walks where the
probability of transitioning between different states is asymmetric, while
allowing us to study the pseudorandomness of random walks on graphs with
vertices with more complex labelings which has already been explored in [13].
This section generalizes the sticky random walk on $p$ characters, and
provides the context for bounding the total variation distance between the
sticky random walk and $\mathrm{U}_{p}^{n}$.

######  Definition 6 (The generalized sticky random walk).

_The generalized sticky random walk $S(n,p,\lambda)$ is an $n$-step long,
$p$-symbol walk on a Markov chain with $p$ states
$\operatorname*{\mathbb{Z}}_{p}$ labeled as vertices on a complete graph with
self-loops $J_{p}$, where $s_{0}\in_{U}\operatorname*{\mathbb{Z}}_{p}$ and at
each subsequent step, we either stick to the same state with probability
$\frac{1}{p}+(p-1)\lambda$, or change to any other state with uniform
probability $\frac{1}{p}-\lambda$. So, for instance, comparing
$S(n,4,\lambda)$ to $S(n,4,0)=U_{4}^{n}$ (the uniform random walk on 4
vertices) yields the following Markov chain graphs:_

Figure 2:  Markov chains of the generalized sticky random walk on 4 states and
the uniform distribution on $4$ states. The figure on the left corresponds to
$S(n,4,\lambda)$, the $\lambda$-biased sticky random walk on four vertices,
and the figure on the right corresponds $S(n,4,0)=U_{4}^{n}$, the unbiased
random walk on four vertices.

######  Proposition 1 (Probability Invariance Under Permutations).

For any $x_{1},x_{2}\in\operatorname*{\mathbb{Z}}_{p}^{n}$, we have
$\text{Pr}[x_{1}]=\text{Pr}[x_{2}]$ iff $|({i,i+1})|$ such that
$(x_{1})_{i}=(x_{1})_{i+1}$ is equal to $|({j,j+1})|$ such that
$(x_{2})_{j}=(x_{2})_{j+1}$. This can be shown by considering the products of
conditional probabilities on each state. A slight weakening of this statement
is that for any permutation $\pi$ such that
$\pi:\operatorname*{\mathbb{Z}}_{p}\rightarrow\operatorname*{\mathbb{Z}}_{p}$,
we must have that
$\text{Pr}[x_{1}...x_{n}]=\text{Pr}[\pi(x_{1})...\pi(x_{n})]$. Consider the
case of $p=2$. Then, the lemma yields that $\text{Pr}(x)=\text{Pr}(\bar{x})$,
which says that inverting the labels of a string from the sticky random walk
does not change its probability. This proposition extends the same argument to
all $p\in\operatorname*{\mathbb{N}}$ for $p\geq 2$.

######  Proposition 2 (Krawtchouk Orthogonality).

_The orthogonality of the Krawtchouk function $K_{k}(\ell)$ implies that for
any function
$f:\operatorname*{\mathbb{Z}}_{n+1}\rightarrow\operatorname*{\mathbb{R}}$,
there exists a unique expansion
$f(\ell)=\sum\limits_{k=0}^{n}\hat{f}(k)K_{k}(\ell)$, where for $0\leq k\leq
n$,_

$\hat{f}(k)=\operatorname*{\mathbb{E}}\bigg{[}{{n}\choose{k}}f(b)K_{k}(b)\bigg{]}$

######  Definition 7 (Probability ratio).

_Let
$q:\operatorname*{\mathbb{Z}}_{n+1}\rightarrow\operatorname*{\mathbb{R}}$,
where $q(\ell)=\frac{\Pr\limits_{s\sim
S}[|s|_{0}=\ell]}{{n\choose\ell}(p-1)^{n-\ell}}p^{n}$. Intuitively, $q(\ell)$
is the ratio of the probability of getting a string with $\ell$ 0s from the
generalized sticky random walk $S(n,\lambda,p)$ to the probability of getting
a string with $\ell$ 0s from $\mathrm{U}_{p}^{n}$_.

######  Lemma 3.1.

[Krawtchouk coefficient of the probability ratio] _Expanding $q(\ell)$ through
the Krawtchouk function expansion in Proposition 3.2 yields that:_

$\hat{q}(k)=\frac{1}{{n\choose
k}(p-1)^{n-k}}\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})]$

###### Proof.

Writing the expected value of $K_{k}(|s|_{0})$ using $q(b)$ and $K_{k}(b)$, we
get:

$\displaystyle\hat{q}(k)$ $\displaystyle=\frac{1}{{n\choose
k}(p-1)^{n-k}}\sum\limits_{b=0}^{n}{n\choose
b}\frac{(p-1)^{n-b}}{p^{n}}q(b)K_{k}(b)$ $\displaystyle=\frac{1}{{n\choose
k}(p-1)^{n-k}}\sum\limits_{b=0}^{n}\Pr\limits_{s\sim
S(n,p,\lambda)}[|s|_{0}=b]K_{k}(b)\quad\text{(substituting $q(b)$)}$
$\displaystyle=\frac{1}{{n\choose
k}(p-1)^{n-k}}\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})]\quad\text{(by definition of
$\operatorname*{\mathbb{E}}\limits_{s\in
S(n,p,\lambda)}[K_{k}(|s|_{0})]$)}\qed$

######  Lemma 3.2.

_For $s\in S(n,p,\lambda)$, we have that
$\Pr[|s|_{0}=\ell]=\frac{1}{p^{n}}\sum\limits_{k=0}^{n}K_{\ell}(k)\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})].$_

###### Proof.

Writing out $\Pr[|s|_{0}=\ell]$ in terms of the probability ratio $q(\ell)$,
we get:

$\displaystyle\Pr[|s|_{0}=\ell]$
$\displaystyle=\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}q(\ell)$
$\displaystyle=\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\sum\limits_{k=0}^{n}\hat{q}(k)K_{k}(\ell)\quad\text{(Krawtchouk
expansion of $q(\ell)$)}$
$\displaystyle=\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\sum\limits_{k=0}^{n}\frac{K_{k}(\ell)}{{n\choose
k}(p-1)^{n-k}}\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]\quad(\text{Lemma
3.1})$
$\displaystyle=\frac{1}{p^{n}}\sum\limits_{k=0}^{n}\frac{{n\choose\ell}}{{n\choose
k}}\frac{(p-1)^{n-\ell}}{(p-1)^{n-k}}\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]K_{k}(\ell)$
$\displaystyle=\frac{1}{p^{n}}\sum\limits_{k=0}^{n}K_{\ell}(k)\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})]\quad\text{(By the reciprocity relation)}\qed$

Therefore, we observe that to compute $\Pr[|s|_{0}=\ell]$, it is imperative to
calculate the expected value of the Krawtchouk function. Section 4 is devoted
to computing $\operatorname*{\mathbb{E}}_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})]$.

##  4 Expectation of the Krawtchouk Function for the p-vertex Sticky Random
Walk

######  Definition 8 (Shift Function).

_Given any set $T\subseteq[n]$ such that $|T|=k$, let $a_{1}<...<a_{k}$ be the
elements of $T$ in increasing order. Then, for any
$c\in\operatorname*{\mathbb{Z}}_{p}$, let _

$\mathrm{shift}_{c}(T)=\sum\limits_{i=0}^{\lfloor|k-c|/p\rfloor}(a_{c+ip}-a_{c+ip-1})$

_Then, for any $c$ such that $k\mod p=-c$, and for any
$d\in\operatorname*{\mathbb{Z}}_{n+1}$, let $\phi_{c}(d)$ denote the number of
subsets of $[n]$ of size $k$ such that $\mathrm{shift}_{c}(T)=d$. Note that
for any $t\leq 0,a_{t}=0$_.

######  Lemma 4.1.

_The expected value of the Krawtchouk function is given by:_

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\begin{cases}(p-1)^{n-k}\sum\limits_{d=k}^{n-k}\phi_{0}(d)\lambda^{d},&\text{if
}c=k\\!\\!\\!\\!\mod p\equiv 0\\\ 0,&\text{ if }c=k\\!\\!\\!\\!\mod
p\not\equiv 0\end{cases}$

###### Proof.

By the formula of expected values, we have that:

$\displaystyle\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]$
$\displaystyle=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum_{\begin{subarray}{c}y\in\operatorname*{\mathbb{Z}}_{2}^{n}\\\
|y|_{0}=k\end{subarray}}(-1)^{y\cdot s}$ $\displaystyle=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum_{\begin{subarray}{c}y\in\operatorname*{\mathbb{Z}}_{2}^{n}\\\
|y|_{0}=k\end{subarray}}(-1)^{\sum\limits_{i=1}^{n}y_{i}\cdot s_{i}}$
$\displaystyle=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum_{\begin{subarray}{c}y\in\operatorname*{\mathbb{Z}}_{2}^{n}\\\
|y|_{0}=k\end{subarray}}\prod\limits_{i=1}^{n}(-1)^{y_{i}\cdot s_{i}}$

We note then that the dot-product on the exponent of $(-1)$ only takes the
summation of the element-wise product of $\alpha$ and $y$ for positions on $y$
that are strictly non-zero. Therefore, we can rewrite the summation by
considering the indices corresponding to locations of non-zeros in $y$, and
instead take the summation of the dot-product along these indices. So, for
$T=\\{a_{1}<...<a_{n-k}\\}$, we have that:

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum\limits_{T\in{{[n]}\choose{n-k}}}\prod\limits_{i\in
T}(-1)^{s_{i}}$

Further, choosing a $T\in{{[n]}\choose{n-k}}$ implies a choice of
$\overline{T}={{[n]}\choose k}=[n]\setminus T$. Hence, the summation reduces
to:

$\displaystyle\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]$
$\displaystyle=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum\limits_{T\in{{[n]}\choose
k}}\prod\limits_{i\in\overline{T}}(-1)^{s_{i}}$
$\displaystyle=\sum\limits_{T\in{{[n]}\choose
k}}\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}\bigg{[}\prod\limits_{i\in\overline{T}}(-1)^{s_{i}}\bigg{]}\quad\text{(definition
of expectations)}$

Next, observe that the sticky random walk is a Markov chain where
$(-1)^{s_{i}}=(-1)^{s_{i-1}}$ with probability $1/p+(p-1)\lambda)$. So, we can
instead model the transitions of strings from the sticky random walk as random
variables $u$, where $u_{1}$ is uniformly distributed in
$\operatorname*{\mathbb{Z}}_{p}$ and for $i\geq 2$, $u_{i}$ is uniformly
distributed on
$(1-\lambda)U[\operatorname*{\mathbb{Z}}_{p}]+\lambda\cdot\mathbbm{1}_{0}$. To
provide an intuition for this refactorization,
$(1-\lambda)U[\operatorname*{\mathbb{Z}}_{p}]$ is the ’base’ probability of
switching to any vertex and $\lambda$ is the additional probability of staying
on the same vertex.

Then, since $s_{i}=\sum_{i\in T}\sum_{j=1}^{i}u_{j}$, we write that:

$\displaystyle\operatorname*{\mathbb{E}}\limits_{s\in
S(n,p,\lambda)}\bigg{[}\prod\limits_{i\in\overline{T}}(-1)^{s_{i}}\bigg{]}$
$\displaystyle=\operatorname*{\mathbb{E}}\limits_{s\in
S(n,p,\lambda)}\bigg{[}(-1)^{\sum\limits_{i\in\overline{T}}\sum\limits_{j=1}^{i}u_{j}}\bigg{]}$
$\displaystyle=\prod\limits_{j=1}^{a_{n-k}}\operatorname*{\mathbb{E}}\limits_{s\in
S(n,p,\lambda)}\bigg{[}(-1)^{\sum\limits_{i\in\overline{T};i\geq
j}u_{j}}\bigg{]}\quad\text{(independence of $u_{j}$'s)}$

When $j=1$, we get that:

$\displaystyle\operatorname*{\mathbb{E}}\bigg{[}(-1)^{\sum\limits_{i\in\overline{T};i\geq
1}u_{1}}\bigg{]}$
$\displaystyle=\operatorname*{\mathbb{E}}[(-1)^{|\overline{T}|u_{1}}]$
$\displaystyle=\begin{cases}1,&\text{if }|\overline{T}|\mod p\equiv 0\\\
0,&\text{otherwise}\end{cases}$

Conversely, when $j\geq 2$, let $T_{j}=\\{i\in\overline{T};i\geq j\\}$. Then,

$\displaystyle\operatorname*{\mathbb{E}}\bigg{[}(-1)^{\sum\limits_{i\in\overline{T};i\geq
j}u_{j}}\bigg{]}$
$\displaystyle=\operatorname*{\mathbb{E}}[(-1)^{|T_{j}|u_{j}}]$
$\displaystyle=\begin{cases}1,&\text{if }|T_{j}|\mod p\equiv 0\\\
\operatorname*{\mathbb{E}}[(-1)^{u_{j}}],&\text{ otherwise}\\\ \end{cases}$

Next, observe that for $j\geq 2$,
$\operatorname*{\mathbb{E}}[(-1)^{u_{j}}]=\lambda$.

###### Proof.

To show this, we write the expression for $u_{j},j\geq 2$ in the exponent and
take the expected value of $(-1)^{u_{j}}$.

$\displaystyle\operatorname*{\mathbb{E}}[(-1)^{u_{j}}]$
$\displaystyle=\operatorname*{\mathbb{E}}[(-1)^{(1-\lambda)U[\mathbb{Z}_{p}]+\lambda\cdot\mathbbm{1}_{0}}]\quad\text{(since
$u_{j}\sim(1-\lambda)U[\mathbb{Z}_{p}]+\lambda\cdot\mathbbm{1}_{0}$)}$
$\displaystyle=\sum\limits_{k=0}^{p-1}(-1)^{k}\Pr[u_{j}=k]\quad\text{(definition
of expectation)}$
$\displaystyle=(-1)^{0}\Pr[u_{j}=0]+(-1)^{1}\Pr[u_{j}=1]+...+(-1)^{p-1}\Pr[u_{j}=p-1]$
$\displaystyle=\bigg{(}\frac{1}{p}+\lambda\bigg{(}\frac{p-1}{p}\bigg{)}\bigg{)}-\bigg{(}\frac{1}{p}-\frac{\lambda}{p}\bigg{)}+...+(-1)^{p-1}\bigg{(}\frac{1}{p}-\frac{\lambda}{p}\bigg{)}$
$\displaystyle=\frac{1}{p}\sum\limits_{k=0}^{p-1}(-1)^{k}-\frac{\lambda}{p}\sum\limits_{k=0}^{p-1}(-1)^{k}+\lambda(-1)^{0}$
$\displaystyle=\lambda\qed$

Then, for $k\mod p\equiv 0$, we have that:

$\begin{split}\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]&=\sum\limits_{T\in{[n]\choose
k}}\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}s\sim
S(n,p,\lambda)\end{subarray}}\bigg{[}\prod\limits_{i\in\overline{T}}(-1)^{s_{i}}\bigg{]}\\\
&=\sum\limits_{T\in{[n]\choose
k}}\prod\limits_{i\in\overline{T}}\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}s\sim
S(n,p,\lambda)\end{subarray}}[(-1)^{s_{i}}]\quad\text{(independence of
$(-1)^{s_{i}}$)}\\\ &=\sum\limits_{T\in{[n]\choose
k}}\prod\limits_{j=1}^{a_{n-k}}\lambda\quad\text{(since $|T|=a_{n-k}$)}\\\
&=\sum\limits_{T\in{[n]\choose k}}\lambda^{a_{n-k}}\end{split}$

We then parameterize the summation over every possible value of the shift of T
(for $k\\!\\!\mod p\equiv 0$), where the shift function is given in Definition
8.

$\displaystyle\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]$
$\displaystyle=\sum\limits_{d=k}^{n-k}\bigg{(}\sum_{\begin{subarray}{c}T\in{[n]\choose
k}\\\ \text{shift}_{0}\text{(T)=d}\end{subarray}}1\bigg{)}\lambda^{d}$
$\displaystyle=\sum\limits_{d=k}^{n-k}\phi_{0}(d)\lambda^{d}$

This yields the claim. ∎

######  Lemma 4.2.

_For $c\in\operatorname*{\mathbb{N}}$ where $0\leq c\leq p$, and for
$d\in\operatorname*{\mathbb{N}}$ where $k\leq d\leq n-k$, the number of
$k$-sized subsets of $[n]$ that satisfy $\text{shift}_{c}(T)=d$_ is:

$\phi_{c}(d)=\frac{1}{p^{k}}\sum_{\begin{subarray}{c}T\in{{[n]}\choose k}\\\
\text{shift}_{c}(T)=d\end{subarray}}1=\frac{1}{p^{k}}{{d-1}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor-1}}{{n-d}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor}}$

###### Proof.

To determine $\phi_{c}(d)$, we count the total number of ways to choose
$a_{1}\\!\\!<\\!\\!a_{2}\\!\\!<\\!\\!...\\!\\!<\\!\\!a_{k}$ such that the
lengths of the intervals
$(a_{c}-a_{c-1})+(a_{c+p}-a_{c+p-1})+(a_{c+2p}-a_{c+2p-1})+...=d$, where for
any $j\leq 0$, $a_{j}=0$. To do this, we combine each element-wise interval
$(a_{c+ip},a_{c+ip-1})$ to form a contiguous interval of length $d$ (starting
from $a_{c-1}=0$). The remaining contiguous region that excludes these
intervals must then have a length of $n-d$. We then abstract the number of
ways to count $a_{1}<...<a_{k}$ by counting the number of intervals that have
a length of $d$ when combined, such that the remaining intervals have a length
$n-d$. From a length of $d-1$ (accounting for $a_{0}=0$), we need to select
intervals that form a length of $\lfloor|k-c|/(p-1)\rfloor-1$ since they
represent the number of choices of elements of $T$ that are index-separated by
$p$. Similarly, from a length of $n-d$, we need to select intervals that form
a length of $\lfloor|k-c|/(p-1)\rfloor$ possible intervals, since they
represent every other element of $T$. This second constraint is to ensure that
the total length of the intervals chosen is exactly $n$. Finally, we divide by
the maximum number of repetitions to prevent duplicates, which is $p^{k}$.
Hence, we write that:

$\sum_{\begin{subarray}{c}T\in{{[n]}\choose k}\\\
\text{shift}_{c}(T)=d\end{subarray}}1={{d-1}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor-1}}{{n-d}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor}}$

Therefore,

$\phi_{c}(d)=\frac{1}{p^{k}}\sum_{\begin{subarray}{c}T\in{{[n]}\choose k}\\\
\text{shift}_{c}(T)=d\end{subarray}}1=\frac{1}{p^{k}}{{d-1}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor-1}}{{n-d}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor}}\qed$

######  Corollary 4.2.1.

_By combining the results from Lemmas 5.1 and 5.2, we have that the
expectation of the Krawtchouk function is:_

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\begin{cases}\frac{1}{p^{k}}\sum\limits_{d=k}^{n-k}{{d-1}\choose{\lfloor\frac{k}{p-1}\rfloor}-1}{{n-d}\choose{\lfloor\frac{k}{p-1}\rfloor}}\lambda^{d},&\text{
if }k\\!\\!\\!\\!\mod p\equiv 0\\\ 0,&\text{ if }k\\!\\!\\!\\!\mod p\not\equiv
0\end{cases}$

Thus, having computed $\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]$, we are now
prepared to upper-bound the total variation distance between
$[\Sigma(S(n,p,\lambda))]_{0}$ and $[\Sigma(\mathrm{U}_{p}^{n})]_{0}$. We
devote Section 5 to deriving an optimal upper bound of $O(\lambda)$.

##  5 Upper Bounds for the Total Variation Distance

######  Lemma 5.1.

_The total variational distance between the generalized sticky random walk on
$p$ vertices and the uniform distribution on $p$ states is given by:_

$\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{p}^{n})]_{0})=\frac{1}{2}\operatorname*{\mathbb{E}}\limits_{b\sim\mathrm{U}_{p}^{n}}[|q(b)-1|]$

###### Proof.

We write the expression of the total variation distance between the $n$-step
sticky random walk on $p$ states and $n$-samples from the uniform distribution
on $p$ states. This then yields:

$\displaystyle\operatorname{\text{TVD}}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{p}^{n})]_{0})$
$\displaystyle=\frac{1}{2}\sum\limits_{\ell=0}^{n}\bigg{|}\Pr[|s|_{0}=\ell]-\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\bigg{|}$
$\displaystyle=\frac{1}{2}\sum\limits_{\ell=0}^{n}\bigg{|}{n\choose\ell}q(\ell)\frac{(p-1)^{n-\ell}}{p^{n}}-\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\bigg{|}$
$\displaystyle=\frac{1}{2}\sum\limits_{\ell=0}^{n}\left|\frac{{n\choose\ell}}{p^{n}}(p-1)^{n-\ell}(q(\ell)-1)\right|$
$\displaystyle=\frac{1}{2}\sum\limits_{\ell=0}^{n}\left|\Pr[\ell](q(\ell)-1)\right|$
$\displaystyle=\frac{1}{2}\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[|q(b)-1|]\qed$

######  Corollary 5.1.1.

_The total variational distance between the generalized sticky random walk and
the uniform distribution on $p$ states has the following upper bound as a
result of convexity:_

$\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{p}^{n})]_{0})\leq\frac{1}{2}\sqrt{\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}}$

######  Lemma 5.2.

_For $k\leq n$ and for $b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}$, we have that_

$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}=\sum\limits_{k=1}^{n}\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}(p-1)^{n-k}}$

###### Proof.

Section 3 says that $q(b)$ has a unique Krawtchouk expansion, where the
coefficients on each Krawtchouk basis are given by Proposition 2, we observe
that:

$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}=\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}\bigg{[}\bigg{(}\sum\limits_{k=0}^{n}\hat{q}(k)K_{k}(b)-1\bigg{)}^{2}\bigg{]}$

Then, recall that
$\hat{q}(k)=\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]}{{n\choose
k}(p-1)^{n-k}}$. So,
$\hat{q}(0)=\frac{\operatorname*{\mathbb{E}}[K_{0}(|s|_{0})]}{(p-1)^{n}}=\frac{1}{(p-1)^{n}}$.
Similarly, by the definition of the Krawtchouk function and the reciprocity
relation $\frac{K_{k}(\ell)}{{n\choose
k}(p-1)^{n-k}}=\frac{K_{s}(\ell)}{{n\choose s}(p-1)^{n-s}}$, we have that
$K_{0}(b)=K_{n}(b)=(p\\!-\\!1)^{n}$. Therefore, $\hat{q}(0)K_{0}(b)=1$. Hence,
the above equation simplifies to:

$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}=\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}\bigg{[}\bigg{(}\sum\limits_{k=1}^{n}\hat{q}(k)K_{k}(b)\bigg{)}^{2}\bigg{]}$

Since the generalized Krawtchouk functions are orthogonal (as proven in Lemma
3.2), the product of the non-diagonal entries in the above term all evaluate
to $0$. Thus, counting the residuals, we have that the square of the summation
is just the summation of the squared terms that it contains. Thus, exploiting
the orthogonality of the generalized Krawtchouk functions and the linearity of
the expectations, we write that:

$\displaystyle\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}\bigg{[}\sum\limits_{k=1}^{n}\hat{q}(k)^{2}K_{k}(b)^{2}\bigg{]}$
$\displaystyle=\sum\limits_{k=1}^{n}\hat{q}(k)^{2}\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[K_{k}(b)^{2}]\quad\text{(linearity
of expectations)}$
$\displaystyle=\sum\limits_{k=1}^{n}\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}^{2}(p-1)^{2n-2k}}\cdot\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[K_{k}(b)^{2}]$

Finally, we use Lemma 3.2 to write
$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[K_{k}(b)^{2}]$
as $\langle K_{k},K_{k}\rangle={n\choose k}$.

$\displaystyle\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}$
$\displaystyle=\sum\limits_{k=1}^{n}\frac{{n\choose
k}\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}^{2}(p-1)^{2n-2k}}=\sum\limits_{k=1}^{n}\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}(p-1)^{2n-2k}}\qed$

######  Theorem 5.3.

_For $\lambda\leq 0.27$_,

$\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{p}^{n})]_{0})\leq
O(\lambda)$

###### Proof.

Substituting the result of Corollary 5.2 into the equation derived in Lemma
4.2.1, and scaling the indexes of the summation, we have that:

$\displaystyle\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}$
$\displaystyle=\sum\limits_{k=1}^{n/p}\frac{1}{{n\choose
pk}(p\\!-\\!1)^{2n-2pk}}\bigg{(}\sum\limits_{d=pk}^{n-pk}\frac{1}{p^{k}}{{d-1}\choose{\lfloor\frac{kp}{p-1}\rfloor}-1}{{n-d}\choose{\lfloor\frac{kp}{p-1}\rfloor}}\lambda^{d}\bigg{)}^{2}$
$\displaystyle=\frac{1}{p^{2k}}\sum\limits_{k=1}^{n/p}\frac{1}{{n\choose
pk}(p\\!-\\!1)^{2n-2pk}}\bigg{(}\sum\limits_{d=pk}^{n-pk}{{d-1}\choose{\lfloor\frac{k}{1-\frac{1}{p}}\rfloor}-1}{{n-d}\choose{\lfloor\frac{k}{1-\frac{1}{p}}\rfloor}}\lambda^{d}\bigg{)}^{2}$
$\displaystyle\leq\frac{1}{p^{2k}}\sum\limits_{k=1}^{n/p}\frac{{n\choose
k}^{2}}{{n\choose
pk}(p\\!-\\!1)^{2n-2pk}}\bigg{(}\sum\limits_{d=pk}^{n-pk}{{d-1}\choose{k-1}}\lambda^{d}\bigg{)}^{2}$
$\displaystyle\leq\frac{1}{p^{2k}}\sum\limits_{k=1}^{n/p}\frac{{n\choose
k}^{2}}{{n\choose
pk}}\bigg{(}\sum\limits_{d=pk}^{n-pk}{{d-1}\choose{k-1}}\lambda^{d}\bigg{)}^{2}$

Note the following generating function relation that
$(\frac{x}{1-x})^{k}=\sum\limits_{m\geq k}{{m-1}\choose{k-1}}x^{m}$. Then,

$\displaystyle\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}$
$\displaystyle\leq\frac{1}{p^{2k}}\sum\limits_{k=1}^{n/p}\frac{{n\choose
k}^{2}}{{n\choose pk}}\bigg{(}\frac{\lambda}{1-\lambda}\bigg{)}^{2k}$
$\displaystyle\leq\frac{1}{p^{2k}}\sum\limits_{k=1}^{n/p}\bigg{(}\frac{pk}{n}\bigg{)}^{pk}\bigg{(}\frac{en}{k}\bigg{)}^{2k}\bigg{(}\frac{\lambda}{1-\lambda}\bigg{)}^{2k}\quad\text{(From
Appendix \ref{claim: bound})}$
$\displaystyle=\sum\limits_{k=1}^{n/p}\bigg{(}\frac{pk}{n}\bigg{)}^{pk-2k}\bigg{(}\frac{e\lambda}{1-\lambda}\bigg{)}^{2k}$
$\displaystyle\leq\sum\limits_{k=1}^{n/p}\bigg{(}\frac{e\lambda}{1-\lambda}\bigg{)}^{2k}$
$\displaystyle\leq O(\lambda^{2}),\quad\text{(for $\lambda\leq\frac{1}{1+e}$
by geometric sums)}$

Therefore, for $\lambda\leq\frac{1}{1+e}\approx 0.27$, we have that TVD
$\leq\sqrt{\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[p(b)-1]^{2}}\leq
O(\lambda)$. ∎

##  6 Proof Strengths and Limitations

When $\lambda>0.27$, our proof method fails to provide the desired
$O(\lambda)$ total variation distance since
$\sum_{k=1}^{n/p}(\frac{e\lambda}{1-\lambda})^{2k}$ does not converge and goes
to $\infty$. We do, however, reach a higher lower-bound on the radius of
convergence ($\lambda\leq 0.27$) than [10]’s $\lambda\leq 0.16$ and [13]’s
more general result but which is only valid for $\lambda<0.01$ and a fixed $p$
in their interpretation of their $O(\lambda p^{O(p)})$ result, whereas our
methodology allows us to remove the dependency of $p$ in the total variation
distance (though only for the generalized sticky random walk). We conjecture
that $\lambda\leq 0.27$ is not the optimal radius of convergence for the
generalized sticky random walk and leave this as an open problem for future
research directions in this topic to resolve.

##  7 Reductions

######  Theorem 7.1.

_Let $p$ be the number of vertices in the generalized sticky random walk.
Then, for all $p\mod k\equiv 0$, $S(n,p,\lambda)$ reduces from
$S(n,k,p\lambda(1-\frac{1}{k}))$._

###### Proof.

Consider a generalized sticky random walk which details an irreducible
homogeneous Markov chain on $p$ states where the probability of staying at the
same state is $\frac{1}{p}+(p-1)\lambda$ and the probability of switching
states is $\frac{1}{p}-\lambda$. Then, consider a ’grouped’ random-walk, for a
grouping of states $V=[p]=V_{0}\sqcap\dots\sqcap V_{k-1}$, where $V_{i}$
contains an arbitrary selection of $p/k$ vertices and where $p\mod k\equiv 0$.
Then, $S(n,p,\lambda)$ details an $n$-step long random walk on the generalized
sticky random walk. Then, we note that the probability that the current state
of the grouped random walk stays at itself must be
$(\frac{1}{k}+(p-1)\lambda)+(\frac{1}{p}-\lambda)(\frac{p}{k}-1)=\frac{1}{k}+p\lambda(1-\frac{1}{k})$.
Here, the first term comes from the probability of any state $E$ in the sticky
random walk staying at itself, and the second term comes from the probability
that any other vertex in the same group as $E$ transitions to $E$. Since this
is true for any of the grouped vertex, we conclude that our grouping of the
random walk yields a sticky random walk on $k$ vertices and bias
$p\lambda(1-\frac{1}{k})$, which completes the reduction. ∎

######  Theorem 7.2.

_Every generalized sticky random walk $S(n,p,\lambda)$ corresponds to a
$n$-step long random walk on a $p\lambda$-spectral expander with $p$
vertices._

###### Proof.

We first extend Definition 45 of the sticky random walk matrix in [13]. For
subsets $A,B\in[p]$, let $J_{A,B}\in\operatorname*{\mathbb{R}}^{A\times B}$
denote the matrix with all entries equal to $\frac{1}{|A|}$. Then, for
$\lambda\in[0,1]$, let $G_{\lambda,p}\in\operatorname*{\mathbb{R}}^{p\times
p}$ denote the generalized sticky random walk matrix. Then, by definition, we
write that:

$G_{\lambda,p}=(1-\lambda)\mathrm{J}_{V,V}+p\lambda\mathrm{I}_{\\{n\times
n\\}}$

Then, note that $\|I_{n\times n}\|_{2}$ is $1$, as it acts as $J$ on the
orthogonal subspaces $\operatorname*{\mathbb{R}}$ of
$\operatorname*{\mathbb{R}}^{p}$. Therefore, $\lambda(G_{\lambda,p})\leq
p\lambda$ since the eigenvector of $G_{\lambda,p}$ is orthogonal to $J_{V,V}$
and so $G_{\lambda,p}\nu=((1-\lambda)\mathrm{J}_{v,v}+p\lambda I_{\\{n\times
n\\}})\nu=(1-\lambda)\mathrm{J}_{v,v}\nu+p\lambda I_{\\{n\times
n\\}}\nu=p\lambda\nu$. The opposite inequality comes from the fact that
$\frac{n-1}{n}\vec{\mathbbm{1}}_{\\{c_{0}\\}}-\frac{1}{n}\sum_{i=1}^{p-1}\vec{\mathbbm{1}}_{\\{c_{i}\\}}\in\vec{\mathbbm{1}}^{\perp}$
is an eigenvector of $G_{\lambda,p}$ with eigenvalue $p\lambda$, which proves
the theorem.∎

##  8 Acknowledgements

This work was done as part of a Caltech undergraduate thesis, and this
preprint submission has been reformatted from the thesis submission [2]. EA
thanks Professor Chris Umans for his mentorship during this project, and Elia
Gorokhovsky and David Hou for helpful suggestions over the course of this
work.

## References

  * Alo [86] Noga Alon.  Eigenvalues and expanders, 1986.
  * Ana [23] Emile Anand.  Pseudorandomness of the sticky random walk.  Caltech Thesis Archive, doi:0.7907/ze1k-6v37, Senior Thesis (Major), https://resolver.caltech.edu/CaltechTHESIS:06142023-102020321, 2023.
  * BATS [11] Avraham Ben-Aroya and Amnon Ta-Shma.  A combinatorial construction of almost-ramanujan graphs using the zig-zag product.  SIAM Journal on Computing, 40(2):267–290, 2011.
  * CMP+ [22] Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma.  Expander Random Walks: The General Case and Limitations.  In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:18, Dagstuhl, Germany, 2022\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * Con [19] David Conlon.  Hypergraph expanders from cayley graphs, 2019.
  * CPTS [21] Gil Cohen, Noam Peri, and Amnon Ta-Shma.  Expander random walks: A fourier-analytic approach.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1643–1655, New York, NY, USA, 2021. Association for Computing Machinery.
  * DLV [22] Andrea Deac, Marc Lackenby, and Petar Veličković.  Expander graph propagation, 2022.
  * Fri [03] Joel Friedman.  Relative expanders or weakly relatively Ramanujan graphs.  Duke Mathematical Journal, 118(1):19 – 35, 2003.
  * Gil [98] David Gillman.  A chernoff bound for random walks on expander graphs.  SIAM Journal on Computing, 27(4):1203–1220, 1998.
  * GK [21] Venkatesan Guruswami and Vinayak M. Kumar.  Pseudobinomiality of the Sticky Random Walk.  In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * GK [23] Roy Gotlib and Tali Kaufman.  No where to go but high: A perspective on high dimensional expanders, 2023\.
  * Gur [22] Venkatesan Guruswami.  Great theoretical ideas in computer science.  https://csd.cmu.edu/course-profiles/15-251-Great-Theoretical-Ideas-in-Computer-Science, 2022\.
  * GV [22] Louis Golowich and Salil Vadhan.  Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs.  In Shachar Lovett, editor, 37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:13, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * INW [94] Russell Impagliazzo, Noam Nisan, and Avi Wigderson.  Pseudorandomness for network algorithms.  In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94, page 356–364, New York, NY, USA, 1994. Association for Computing Machinery.
  * Kow [13] Emmanuel Kowalski.  Expander graphs–their applications and construction.  Available at https://people.math.ethz.ch/k̃owalski/expander-graphs.pdf, 2013.
  * KSSS [02] J. Komlós, Ali Shokoufandeh, Miklós Simonovits, and Endre Szemerédi.  The regularity lemma and its applications in graph theory, 2002.
  * Lub [17] Alexander Lubotzky.  Ramanujan graphs, 2017.
  * Rei [05] Omer Reingold.  Undirected st-connectivity in log-space.  In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 376–385, New York, NY, USA, 2005. Association for Computing Machinery.
  * RR [17] Shravas Rao and Oded Regev.  A Sharp Tail Bound for the Expander Random Sampler.  arXiv e-prints, page arXiv:1703.10205, March 2017.
  * RVW [04] Omer Reingold, Salil Vadhan, and Avi Wigderson.  Entropy waves, the zig-zag graph product, and new constant-degree, Jun 2004.
  * Sam [98] Alex Samorodnitsky.  On the optimum of delsarte’s linear program.  J. Combinatorial Theory, Ser. A, 96, 1998.
  * SH [06] Avi Wigderson Shlomo Hoory, Nathan Linial.  Expander graphs and their applications.  Bulletin of the American Mathematical Society, 43(4):439–561, 2006\.
  * SS [96] M. Sipser and D.A. Spielman.  Expander codes.  IEEE Transactions on Information Theory, 42(6):1710–1722, 1996\.
  * Tre [11] Luca Trevisan.  Graph partitioning and expanders.  https://lucatrevisan.github.io/teaching/cs359g-11/lecture01.pdf, 2011.
  * TS [17] Amnon Ta-Shma.  Explicit, almost optimal, epsilon-balanced codes.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 238–251, New York, NY, USA, 2017. Association for Computing Machinery.
  * Vad [13] Salil Vadhan.  Pseudorandomness.  Book On Demand Ltd, 2013.

##  Appendix A Appendix: Technical Lemmas

The following technical lemmas are used at various points in the paper.

######  Claim.

_For $1\leq k\leq\frac{n}{p}$, we can bound $\frac{{n\choose
k}^{2}}{{n\choose{pk}}}\leq(\frac{ne}{k})^{2k}\cdot(\frac{pk}{n})^{pk}$._

###### Proof.

We use the bound that $(\frac{n}{k})^{k}\leq{n\choose k}<(\frac{ne}{k})^{k}$.
This gives us that $\frac{{n\choose
k}^{2}}{{n\choose{pk}}}\leq\frac{(\frac{ne}{k})^{2k}}{(\frac{n}{pk})^{pk}}$.
Simplifying it yields that $(\frac{ne}{k})^{2k}\cdot(\frac{pk}{n})^{pk}$,
which proves the claim. ∎

######  Definition 9.

_For $p\geq 2$, let $\omega_{p}$ denote the $p^{th}$ primitive root of unity
if it satisfies $(\omega_{p})^{p}=1$, and if there does not exist
$q\in\operatorname*{\mathbb{N}}$ where $q<p$ such that $(\omega_{p})^{q}=1$.
Specifically, the multiplicative order of the $p^{th}$ primitive root of unity
must be $p$. Then, for $1\leq k<p$, we must have that_

$\sum\limits_{j=0}^{p-1}(\omega_{p})^{kj}=\omega_{p}^{k\cdot
0}+\omega_{p}^{k\cdot 1}+...+\omega_{p}^{k\cdot(p-1)}=0$

###### Proof.

Given $\omega_{p}^{p}=1$, it is clear that for $k<p$,
$(\omega_{p}^{k})^{p}=1$. Thus,
$(\omega_{p}^{k})p-1=0=(\omega_{p}^{k}-1)(\omega_{p}^{k\cdot
0}+\omega_{p}^{k\cdot 1}+...+\omega_{p}^{k\cdot(p-1)})$. Since
$\omega_{p}^{k}\neq 1$ as $\omega_{p}$ is a primitive root of unity, we must
have that $\omega_{p}^{k\cdot 0}+\omega_{p}^{k\cdot
1}+...+\omega_{p}^{k\cdot(p-1)}=0$, which proves the claim. ∎

######  Lemma A.1.

_Orthogonality of the Krawtchouk functions:_

$\langle
K_{r},K_{s}\rangle=\operatorname*{\mathbb{E}}_{b\sim\text{Bin}(n,\frac{1}{2})}[K_{r}(b)K_{s}(b)]=\begin{cases}0\quad\text{if
}r\neq s\\\ \genfrac{(}{)}{0.0pt}{1}{n}{s}\quad\text{if }r=s\end{cases}$

###### Proof.

We provide a probabilistic interpretation of the Krawtchouk function as
demonstrated in [21]. Fix $A\in\genfrac{(}{)}{0.0pt}{1}{[n]}{\ell}$,
$B\in_{U}\genfrac{(}{)}{0.0pt}{1}{[n]}{s}$, and choose
$C\in_{U}\genfrac{(}{)}{0.0pt}{1}{[n]}{r}$. Then,

$K_{s}(\ell)=\genfrac{(}{)}{0.0pt}{0}{n}{s}\operatorname*{\mathbb{E}}[(-1)^{|A\cap
B|}],\quad
K_{r}(\ell)=\genfrac{(}{)}{0.0pt}{0}{n}{r}\operatorname*{\mathbb{E}}[(-1)^{|A\cap
C|}]$

The inner product of $K_{r}$ and $K_{s}$ is then:

$\begin{split}\langle
K_{r},K_{s}\rangle&=\genfrac{(}{)}{0.0pt}{0}{n}{r}\genfrac{(}{)}{0.0pt}{0}{n}{s}\operatorname*{\mathbb{E}}[(-1)^{|A\cap
B|}]\operatorname*{\mathbb{E}}[(-1)^{|A\cap C|}]\\\
&=\genfrac{(}{)}{0.0pt}{0}{n}{r}\genfrac{(}{)}{0.0pt}{0}{n}{s}\operatorname*{\mathbb{E}}[(-1)^{|A\cap
B|}(-1)^{|A\cap C|}]\quad\text{(A, B, and C are independent)}\end{split}$

If $B\neq C$, then $\operatorname*{\mathbb{E}}[(-1)^{|A\cap B|}(-1)^{|A\cap
C|}|B\neq C]=0$, since for each $x\in B\Delta C$, we could either have $x\in
A$ or $x\notin A$, which contributes a +1 or -1 (or vice versa) (respectively)
to the expectation. So, the expected value must be 0. Conversely, if $B=C$,
then it must be the case that $r=s$, which occurs with probability
$\frac{1}{\genfrac{(}{)}{0.0pt}{1}{n}{s}}$. So,
$\operatorname*{\mathbb{E}}[(-1)^{|A\cap B|}(-1)^{|A\cap
C|}]=\operatorname*{\mathbb{E}}[(-1)^{2|A\cap B|}]=\frac{1}{{n\choose s}}$.
This yields that

$\langle K_{r},K_{s}\rangle=\begin{cases}0\quad\text{if }r\neq s\\\
\genfrac{(}{)}{0.0pt}{1}{n}{s}\quad\text{if }r=s\end{cases}\qed$

##  Appendix B Appendix: Generalizing the Krawtchouk Functions into the
Complex Domain

In this section of the Appendix, we also present a generalization of the
Krawtchouk polynomials into the complex domain that yields an elegant method
of analysis for bounding the total variation distance of
$[\Sigma(S(n,p,\lambda))]_{0}$ and $[\Sigma(\mathrm{U}_{n}^{p})]_{0}$, but
only for when $p$ is a prime number. For the generalized sticky random walk,
this method yields an upper-bound on
TVD$([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{n}^{p})]_{0})$ of
$O(\lambda p^{O(p)})$, which matches the upper-bound derived in Corollary 4 of
[13] through Fourier-analytic means, which the body of our paper shows to be
suboptimal when the size of the alphabet used is allow to increase
asymptotically. Nonetheless, we include a proof of this generalization to
present our novel treatment of the Krawtchouk function.

######  Definition 10.

_Given any set $S_{k}\subseteq[n]$ with cardinality $|S_{k}|=k$, let
$v_{S_{k}}$ denote a bit-string in $\\{0,1\\}^{n}$ such that for each $i\in
S_{k}$, $(v_{S_{k}})_{i}=0$ and for each $i\in[n]\setminus S_{k}$,
$(v_{S_{k}})_{i}=1$. Similarly, given the context of a prior prime number $p$,
let $w_{S_{k}}$ denote a string in $\operatorname*{\mathbb{Z}}_{p}^{n}$ where
for each $i\in{S_{k}}$, $(w_{S_{k}})_{i}=0$, and for each $i\in[n]\setminus
S_{k}$, $(w_{S_{k}})_{i}\in[p-1]$_.

######  Definition 11.

_Let $D$ denote the ‘zero distribution’ where for any $\ell\in[n]$,
$\Pr[\ell]$ denotes the probability that a string
$s\in\operatorname*{\mathbb{Z}}_{p}^{n}$ has $\ell$ zeros. Specifically,
$\Pr[\ell]=\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}$, since there are
${n\choose\ell}$ ways to select the locations for the $\ell$ 0s in a string of
length $n$, and $(p-1)^{n-\ell}$ to populate the other $n-k$ locations with
characters from $[p-1]$._

######  Definition 12.

_For all $p\in\operatorname*{\mathbb{N}}$, consider $\omega_{p}$, the p-th
principal root of unity. Then, the generalized Krawtchouk function
$K_{k}(\ell)$, for any $\alpha$ where $\alpha$ has $\ell$ 0s and $n-\ell$ 1s,
is defined as:_

$K_{k}(\ell)=\sum_{\begin{subarray}{c}y\in\operatorname*{\mathbb{Z}}_{p}^{n}\\\
\ |y|_{0}=k\end{subarray}}(\omega_{p})^{\alpha\cdot y}$

######  Lemma B.1.

_Orthogonality of the generalized Krawtchouk function: The generalized
Krawtchouk functions form an orthogonal basis of the functions mapping
$\operatorname*{\mathbb{Z}}_{n+1}\rightarrow\operatorname*{\mathbb{R}}$ (for
the distribution $D$ as described in Definition 11) with respect to the inner
product $\langle f,g\rangle=\operatorname*{\mathbb{E}}\limits_{b\sim
D}[f(b)g(b)]$._

$\langle K_{r},K_{s}\rangle=\begin{cases}0,&\text{if }r\neq s\\\ {n\choose
r}(p-1)^{n-r},&\text{if }r=s\end{cases}$

###### Proof.

In a similar vein to the proof of Lemma 9.1 in Appendix A, we start by
providing a probabilistic interpretation of the generalized Krawtchouk
function. Fix $A\in\genfrac{(}{)}{0.0pt}{1}{[n]}{\ell}$, and choose
$B\in_{U}\genfrac{(}{)}{0.0pt}{1}{[n]}{r}$ and
$C\in_{U}\genfrac{(}{)}{0.0pt}{1}{[n]}{s}$. This is equivalent to fixing a
string $v_{A_{\ell}}\in\operatorname*{\mathbb{Z}}_{p}^{n}$ where
$|v_{A_{\ell}}|_{0}=\ell$ and $(v_{A_{\ell}})_{t}=0$ for all $t\in A$, and
randomly choosing $w_{B_{r}},w_{C_{s}}\in\operatorname*{\mathbb{Z}}_{p}^{n}$
where $|w_{B_{r}}|_{0}=r$ and $|w_{C_{s}}|_{0}=s$. Then,

$K_{s}(\ell)=\genfrac{(}{)}{0.0pt}{0}{n}{s}(p-1)^{n-s}\mathbb{E}_{B_{r}}[\omega_{p}^{\langle
v_{A_{\ell}},w_{B_{r}}\rangle}],\quad
K_{r}(\ell)=\genfrac{(}{)}{0.0pt}{0}{n}{r}(p-1)^{n-r}\operatorname*{\mathbb{E}}_{C_{s}}[\omega_{p}^{\langle
v_{A_{\ell}},w_{C_{s}}\rangle}]$

The inner product of $K_{r}$ and $K_{s}$ (with respect to the probability
distribution $D$) is then:

$\displaystyle\langle K_{r},K_{s}\rangle$
$\displaystyle=\sum\limits_{\ell=0}^{n}\Pr[\ell]K_{r}(\ell)\overline{K_{s}(\ell)}$
$\displaystyle=\sum\limits_{\ell=0}^{n}\genfrac{(}{)}{0.0pt}{0}{n}{\ell}\genfrac{(}{)}{0.0pt}{0}{n}{r}\genfrac{(}{)}{0.0pt}{0}{n}{s}\frac{(p-1)^{n-\ell}}{p^{n}}(p-1)^{2n-s-r}\operatorname*{\mathbb{E}}\limits_{B_{r}}[\omega_{p}^{\langle
v_{A_{\ell}},w_{B_{r}}\rangle}]\operatorname*{\mathbb{E}}\limits_{C_{s}}[\overline{\omega}_{p}^{\langle
v_{A_{\ell}},w_{C_{s}}\rangle}]$
$\displaystyle=\genfrac{(}{)}{0.0pt}{0}{n}{r}\genfrac{(}{)}{0.0pt}{0}{n}{s}\frac{(p-1)^{2n-s-r}}{p^{n}}\sum\limits_{\ell=0}^{n}\genfrac{(}{)}{0.0pt}{0}{n}{\ell}(p-1)^{n-\ell}\operatorname*{\mathbb{E}}\limits_{B_{r},C_{s}}[\omega_{p}^{\langle
v_{A_{\ell}},w_{B_{r}}\rangle-\langle
v_{A_{\ell}},w_{C_{s}}\rangle}]\quad\text{(A, B, and C are independent)}$
$\displaystyle=\genfrac{(}{)}{0.0pt}{0}{n}{r}\genfrac{(}{)}{0.0pt}{0}{n}{s}\frac{(p-1)^{2n-s-r}}{p^{n}}\sum\limits_{\ell=0}^{n}\genfrac{(}{)}{0.0pt}{0}{n}{\ell}(p-1)^{n-\ell}\operatorname*{\mathbb{E}}\limits_{B_{r},C_{s}}[\omega_{p}^{\langle
v_{A_{\ell}},w_{B_{r}}-w_{C_{s}}\rangle\mod p}]$

The last line in the derivation follows by the bilinearity of the inner
product. If $r\neq s$, then $B_{r}\neq C_{s}$ and
$\operatorname*{\mathbb{E}}[\omega_{p}^{\langle
v_{A_{\ell}},w_{B_{r}}-w_{C_{s}}\rangle\mod
p}]=\operatorname*{\mathbb{E}}[\omega_{p}^{\langle
v_{A_{\ell}},w_{B_{r}}\rangle\mod p}]$ since the distribution of $B-C$ is
uniformly random (as are the distributions of $B$ and $C$). Therefore, the
distribution of $B-C$ must be indistinguishable from the distribution of $B$
under the expectation operator. Additionally,
$\operatorname*{\mathbb{E}}[\omega_{p}^{\langle A,B\rangle\mod
p}]=\sum_{j=0}^{p}\omega_{p}^{kj}=0$. If $B=C$, (which is only when $r=s$),
the associated probability of it occurring must be $\frac{1}{{n\choose
r}(p-1)^{n-r}}$.

In this case, $\langle K_{r},K_{s}\rangle={n\choose s}{n\choose
r}(p-1)^{2n-r-s}\operatorname*{\mathbb{E}}[\omega^{\langle
A,0\rangle}]={n\choose s}(p-1)^{n-r}$.

$\operatorname*{\mathbb{E}}\limits_{b\sim
D}[K_{r}(b)K_{s}(b)]=\begin{cases}0,&\text{if }r\neq s\\\ {n\choose
r}(p-1)^{n-r},&\text{if }r=s\end{cases}\qed$

######  Lemma B.2.

_The generalized Krawtchouk function $K_{k}(\ell)$ is invariant against
choices of $\alpha\in\\{0,1\\}^{n}$, where $|\alpha|_{0}=\ell$. Specifically,
we have that for a fixed $B\in\operatorname*{\mathbb{Z}}_{p}^{n}$ where
$|B|_{0}=k$, that_

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\text{Fixed
}A\in\operatorname*{\mathbb{Z}}_{2}^{n}\\\
|A|_{0}=\ell\end{subarray}}[\omega_{p}^{\langle
A,B\rangle}]=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\text{Random
}A^{\prime}\in\operatorname*{\mathbb{Z}}_{2}^{n}\\\
|A^{\prime}|_{0}=\ell\end{subarray}}[\omega_{p}^{\langle
A^{\prime},B\rangle}]$

###### Proof.

The problem is equivalent to showing that

$\omega_{p}^{\langle
A,B\rangle}\cdot\frac{1}{\operatorname*{\mathbb{E}}\limits_{A^{\prime}}[\omega_{p}^{\langle
A^{\prime},B\rangle}]}=\omega_{p}^{\langle
A,B\rangle}\cdot\operatorname*{\mathbb{E}}\limits_{A^{\prime}}\bigg{[}\frac{1}{\omega_{p}^{\langle
A^{\prime},B\rangle}}\bigg{]}\overset{?}{=}1$

By the independence of $A,A^{\prime}$, and $B$, the problem reduces to showing
that

$\operatorname*{\mathbb{E}}\limits_{A^{\prime}}\bigg{[}\frac{\omega_{p}^{\langle
A,B\rangle}}{\omega_{p}^{\langle
A^{\prime},B\rangle}}\bigg{]}=\operatorname*{\mathbb{E}}\limits_{A^{\prime}}[\omega_{p}^{\langle
A-A^{\prime},B\rangle}]\overset{?}{=}1$

Since $A^{\prime}$ is uniformly random in
$\operatorname*{\mathbb{Z}}_{2}^{n}$, $A-A^{\prime}$ must also be uniformly
random for a fixed $A$. So, the problem reduces further to showing (under the
same conditions of $B$ and $A^{\prime}$) that
$\operatorname*{\mathbb{E}}[\omega_{p}^{\langle
A^{\prime},B\rangle}]\overset{?}{=}1$. Since $\sum_{j=0}^{p}\omega_{p}^{kj}=0$
from definition 2.5, we must have that $\sum_{j=0}^{p-1}\omega_{p}^{kj}=1$.
Thus, $\operatorname*{\mathbb{E}}[\omega_{p}^{\langle
A^{\prime},B\rangle}]=\sum_{j=0}^{p-1}\omega_{p}^{kj}=1$, which proves the
claim. ∎

######  Corollary B.2.1.

_The orthogonality of the generalized Krawtchouk function implies a
reciprocity relation:_

$\frac{K_{k}(\ell)}{{n\choose k}(p-1)^{n-k}}=\frac{K_{s}(\ell)}{{n\choose
s}(p-1)^{n-s}}$

We now provide a brief calculation for the expectation of the generalized
Krawtchouk function, since it is necessary for bounding the total variational
distance between $[\Sigma(S(n,p,\lambda))]_{0}$ and $[\Sigma(U_{p}^{n})]_{0}$.

######  Definition 13.

_Given any set $T\subseteq[n]$ such that $|T|=k$, let $a_{1}<...<a_{k}$ be the
elements of $T$ in increasing order. Then, for any
$c\in\operatorname*{\mathbb{Z}}_{p}$, let_

$\mathrm{shift}_{c}(T)=\sum\limits_{i=0}^{\lfloor|k-c|/p\rfloor}(a_{c+ip}-a_{c+ip-1})$

_Then, for any $c$ such that $k\mod p=-c$, and for any
$d\in\operatorname*{\mathbb{Z}}_{n+1}$, let $\phi_{c}(d)$ denote the number of
subsets of $[n]$ of size $k$ such that $\mathrm{shift}_{c}(T)=d$. Note that
for any $t\leq 0,a_{t}=0$._

######  Lemma B.3.

_The expectation of the Krawtchouk function is_ :

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\begin{cases}(p-1)^{n-k}\sum\limits_{d=k}^{n-k}\phi_{0}(d)\lambda^{d},&c=k\\!\\!\\!\\!\mod
p\equiv 0\\\ 0,&c=k\\!\\!\\!\\!\mod p\not\equiv 0\end{cases}$

###### Proof.

$\displaystyle\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum_{\begin{subarray}{c}y\in\operatorname*{\mathbb{Z}}_{p}^{n}\\\
|y|_{0}=k\end{subarray}}\omega_{p}^{y\cdot s}=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum_{\begin{subarray}{c}y\in\operatorname*{\mathbb{Z}}_{p}^{n}\\\
|y|_{0}=k\end{subarray}}\omega_{p}^{\sum\limits_{i=1}^{n}y_{i}\cdot
s_{i}}=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum_{\begin{subarray}{c}y\in\operatorname*{\mathbb{Z}}_{p}^{n}\\\
|y|_{0}=k\end{subarray}}\prod\limits_{i=1}^{n}\omega_{p}^{y_{i}\cdot s_{i}}$

The dot-product on the exponent of $\omega$ only takes the summation of the
element-wise product of $\alpha$ and $y$ for positions on $y$ that are non-
zero. We can rewrite this summation by considering the location of non-zero
terms in $y$. So, for $T=\\{a_{1}<...<a_{n-k}\\}$:

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum\limits_{T\in{{[n]}\choose{n-k}}}\sum\limits_{\beta\in[p-1]^{n-k}}\prod\limits_{i\in
T}\omega_{p}^{\beta_{i}s_{i}}$

Further, choosing a $T\in{{[n]}\choose{n-k}}$ implies a choice of
$\overline{T}={{[n]}\choose k}=[n]\setminus T$. Hence, the summation reduces
to:

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\sum\limits_{s\sim
S(n,p,\lambda)}\Pr[s]\sum\limits_{T\in{{[n]}\choose
k}}\sum\limits_{\beta\in[p-1]^{n-k}}\prod\limits_{i\in\overline{T}}\omega_{p}^{\beta_{i}s_{i}}=\sum\limits_{T\in{{[n]}\choose
k}}\sum\limits_{\beta\in[p-1]^{n-k}}\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}\bigg{[}\prod\limits_{i\in\overline{T}}\omega_{p}^{\beta_{i}s_{i}}\bigg{]}$

Next, observe that the sticky random walk is a Markov chain where
$\omega_{p}^{s_{i}}=\omega_{p}^{s_{i-1}}$ with probability
$\frac{1}{p}+(p-1)\lambda$. We can instead model the transitions of strings
from the sticky random walk as random variables $u$, where $u_{1}$ is
uniformly distributed in $\operatorname*{\mathbb{Z}}_{p}$ and for $i\geq 2$,
$u_{i}$ is uniformly distributed on
$(1-\lambda)U[\operatorname*{\mathbb{Z}}_{p}]+\lambda\cdot\mathbbm{1}_{0}$.
Intuitively, $\lambda$ is the additional probability of staying on the same
vertex. So, for each $s\\!\sim\\!S$, we refactor $s$ to
$\tilde{s}=\\{\tilde{s}_{1},...,\tilde{s}_{n}\\}$, where
$\tilde{s}_{i}=\mathbbm{1}\\{s_{i}\neq 0\\}$. Note then that since $\beta_{i}$
is uniformly random in $[p-1]$, that $\beta_{i}s_{i}\mod p$, and therefore
$\beta_{i}\tilde{s}_{i}\mod p$ must also be uniformly random in $[p-1]$.
Therefore, $\beta_{i}\tilde{s}_{i}$ and $\beta_{i}s_{i}$ are both uniformly
random in $[p-1]$ and have the same distributions. Hence, we write that:

$\begin{split}\operatorname*{\mathbb{E}}\limits_{\beta,s}\bigg{[}\prod\limits_{i\in\overline{T}}\omega_{p}^{\beta_{i}s_{i}}\bigg{]}=\operatorname*{\mathbb{E}}\limits_{\beta,s}\bigg{[}\prod\limits_{i\in\overline{T}}\omega_{p}^{\beta_{i}\tilde{s}_{i}}\bigg{]}&=\operatorname*{\mathbb{E}}\limits_{\beta,s}\bigg{[}\omega_{p}^{\sum\limits_{i\in\overline{T}}\beta_{i}\sum\limits_{j=1}^{i}u_{j}}\bigg{]}=\prod\limits_{j=1}^{a_{n-k}}\operatorname*{\mathbb{E}}\limits_{\beta,s}\bigg{[}\omega_{p}^{\sum\limits_{i\in\overline{T};i\geq
j}\beta_{i}u_{j}}\bigg{]}\end{split}$

Since $u_{j}$ is random, the distribution of $\beta_{i}u_{j}\mod p$ must also
be random, and therefore indistinguishable from the distribution of $u_{j}$.
Therefore, $\beta_{i}u_{j}\\!\\!\mod p$ and $u_{j}\\!\\!\mod p$ are invariant
under the expectation operation of its exponentiation under $\omega_{p}$. So,

$\begin{split}\operatorname*{\mathbb{E}}\limits_{\beta,s}\bigg{[}\prod\limits_{i\in\overline{T}}\omega_{p}^{\beta_{i}s_{i}}\bigg{]}&=\prod\limits_{j=1}^{a_{n-k}}\operatorname*{\mathbb{E}}\bigg{[}\omega_{p}^{\sum\limits_{i\in\overline{T};i\geq
j}u_{j}}\bigg{]}\end{split}$

When $j=1$, the above definition directly implies that:

$\operatorname*{\mathbb{E}}\bigg{[}\omega_{p}^{\sum\limits_{i\in\overline{T};i\geq
1}u_{1}}\bigg{]}=\operatorname*{\mathbb{E}}[\omega_{p}^{|\overline{T}|u_{1}}]=\begin{cases}1,\quad\text{if
}|\overline{T}|\mod p\equiv 0\\\ 0,\quad\text{otherwise}\end{cases}$

Conversely, when $j\geq 2$, let $T_{j}=\\{i\in\overline{T};i\geq j\\}$. Then,

$\operatorname*{\mathbb{E}}\bigg{[}\omega_{p}^{\sum\limits_{i\in\overline{T};i\geq
j}u_{j}}\bigg{]}=\operatorname*{\mathbb{E}}[\omega_{p}^{|T_{j}|u_{j}}]=\begin{cases}1,\quad\quad\quad\text{if
}|T_{j}|\mod p\equiv 0\\\
\operatorname*{\mathbb{E}}[\omega_{p}^{u_{j}}],\quad\text{otherwise}\\\
\end{cases}$

Next, observe that for $j\geq 2$,
$\operatorname*{\mathbb{E}}[\omega_{p}^{u_{j}}]=\lambda$.

###### Proof.

We write $u_{j}$ in terms of our refactoring (similarly to Section 4) and take
the expectation:

$\displaystyle\operatorname*{\mathbb{E}}[\omega_{p}^{u_{j}}]$
$\displaystyle=\operatorname*{\mathbb{E}}[\omega_{p}^{(1-\lambda)U[\operatorname*{\mathbb{Z}}_{p}]+\lambda\cdot\mathbbm{1}_{0}}]=\sum\limits_{k=0}^{p-1}\omega_{p}^{k}\Pr[u_{j}=k]$
$\displaystyle=\omega_{p}^{0}\Pr[u_{j}=0]+\omega_{p}^{1}\Pr[u_{j}=1]+...+\omega_{p}^{p-1}\Pr[u_{j}=p-1]$
$\displaystyle=\omega_{p}^{0}\bigg{(}\frac{1}{p}+\lambda\bigg{(}\frac{p-1}{p}\bigg{)}\bigg{)}+\omega_{p}^{1}\bigg{(}\frac{1}{p}-\frac{\lambda}{p}\bigg{)}+...+\omega_{p}^{p-1}\bigg{(}\frac{1}{p}-\frac{\lambda}{p}\bigg{)}$
$\displaystyle=\frac{1}{p}\sum\limits_{k=0}^{p-1}\omega_{p}^{k}-\frac{\lambda}{p}\sum\limits_{k=0}^{p-1}\omega_{p}^{k}+\lambda\omega_{p}^{0}$
$\displaystyle=\lambda\qed$

Then, for $k\mod p\equiv 0$, we have that

$\begin{split}\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]&=\sum\limits_{T\in{[n]\choose
k}}\sum\limits_{\beta\in[p-1]^{n-k}}\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}s\sim
S\end{subarray}}\bigg{[}\prod\limits_{i\in\overline{T}}\omega_{p}^{\beta_{i}s_{i}}\bigg{]}\\\
&=(p\\!-\\!1)^{n-k}\\!\\!\\!\sum\limits_{T\in{[n]\choose
k}}\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}s\sim S\\\
\beta\in[p-1]^{n-k}\end{subarray}}\bigg{[}\prod\limits_{i\in\overline{T}}\omega_{p}^{\beta_{i}s_{i}}\bigg{]}\\\
&=\\!(p\\!-\\!1)^{n-k}\\!\\!\\!\sum\limits_{T\in{[n]\choose
k}}\prod\limits_{j=1}^{a_{n-k}}\lambda\\\
&=(p\\!-\\!1)^{n-k}\\!\\!\\!\sum\limits_{T\in{[n]\choose
k}}\lambda^{a_{n-k}}\end{split}$

We then parameterize the summation over every possible value of the shift of T
(for $k\\!\\!\mod p\equiv 0$):

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=(p\\!-\\!1)^{n-k}\sum\limits_{d=k}^{n-k}\bigg{(}\sum_{\begin{subarray}{c}T\in{[n]\choose
k}\\\
\text{shift}_{0}\text{(T)=d}\end{subarray}}1\bigg{)}\lambda^{d}=(p\\!-\\!1)^{n-k}\sum\limits_{d=k}^{n-k}\phi_{0}(d)\lambda^{d}$

This yields the claim.
∎

######  Lemma B.4.

_For $c\in\operatorname*{\mathbb{N}}$ where $0\leq c\leq p$, and for
$d\in\operatorname*{\mathbb{N}}$ where $k\leq d\leq n-k$, the number of
$k$-sized subsets of $[n]$ that satisfy $\mathrm{shift}_{c}(T)=d$ is:_

$\phi_{c}(d)=\sum_{\begin{subarray}{c}T\in{{[n]}\choose k}\\\
\mathrm{shift}_{c}(T)=d\end{subarray}}1={{d-1}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor-1}}{{n-d}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor}}$

###### Proof.

To determine $\phi_{c}(d)$, we count the total number of ways to choose
$a_{1}<a_{2}<...<a_{k}$ such that
$(a_{c}-a_{c-1})+(a_{c+p}-a_{c+p-1})+(a_{c+2p}-a_{c+2p-1})+...=d$, where for
any $j\leq 0$, $a_{j}=0$. To do this, we combine each element-wise interval
$(a_{c+ip},a_{c+ip-1})$ to form a contiguous interval of length $d$ (starting
from $a_{c-1}=0$). The remaining contiguous region that excludes these
intervals must then have a length of $n-d$. We then abstract the number of
ways to count $a_{1}<...<a_{k}$ by counting the number of intervals that have
a length of $d$ when combined, such that the remaining intervals have a length
$n-d$.

From a length of $d-1$ (accounting for $a_{0}=0$), we need to select intervals
that form a length of $\lfloor|k-c|/(p-1)\rfloor-1$ since they represent the
number of choices of elements of $T$ that are index-separated by $p$.
Similarly, from a length of $n-d$, we need to select intervals that form a
length of $\lfloor|k-c|/(p-1)\rfloor$ possible intervals, since they represent
every other element of $T$. This second constraint is to ensure that the total
length of the intervals chosen is exactly $n$. Hence, we write that:

$\phi_{c}(d)=\sum_{\begin{subarray}{c}T\in{{[n]}\choose k}\\\
\text{shift}_{c}(T)=d\end{subarray}}1={{d-1}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor-1}}{{n-d}\choose{\lfloor\frac{|k-c|}{p-1}\rfloor}}\qed$

######  Corollary B.4.1.

_By combining the results from Lemmas 5.1 and 5.2, we have that the
expectation of the Krawtchouk function is_ :

$\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]=\begin{cases}(p-1)^{n-k}\sum\limits_{d=k}^{n-k}{{d-1}\choose{\lfloor\frac{k}{p-1}\rfloor}-1}{{n-d}\choose{\lfloor\frac{k}{p-1}\rfloor}}\lambda^{d},&k\\!\\!\\!\\!\mod
p\equiv 0\\\ 0,&k\\!\\!\\!\\!\mod p\not\equiv 0\end{cases}$

######  Proposition 3.

_The orthogonality of the generalized Krawtchouk function $K_{k}(\ell)$
implies that for any function
$f:\operatorname*{\mathbb{Z}}_{n+1}\rightarrow\operatorname*{\mathbb{R}}$,
there exists a unique expansion
$f(\ell)=\sum\limits_{k=0}^{n}\hat{f}(k)K_{k}(\ell)$, where for $0\leq k\leq
n$_,

$\hat{f}(k)=\frac{\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[f(b)K_{k}(b)]}{{n\choose
k}(p-1)^{n-k}}$

######  Definition 14.

_Let
$q:\operatorname*{\mathbb{Z}}_{n+1}\rightarrow\operatorname*{\mathbb{R}}$,
where $q(\ell)=\frac{\Pr\limits_{s\sim
S(n,p,\lambda)}[|s|_{0}=\ell]}{{n\choose\ell}(p-1)^{n-\ell}}p^{n}$_.
Intuitively, $q(\ell)$ is the ratio of the probability of getting a string
with $\ell$ 0s from the sticky random walk $S(n,\lambda,p)$ to the probability
of getting a string with $\ell$ 0s from the uniformly random distribution.

Lemma 3.4: _Expanding $q(\ell)$ through the generalized Krawtchouk function
yields that:_

$\hat{q}(k)=\frac{1}{{n\choose
k}(p-1)^{n-k}}\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})]$

###### Proof.

$\displaystyle\hat{q}(k)$ $\displaystyle=\frac{1}{{n\choose
k}(p-1)^{n-k}}\sum\limits_{b=0}^{n}{n\choose
b}\frac{(p-1)^{n-b}}{p^{n}}q(b)K_{k}(b)$ $\displaystyle=\frac{1}{{n\choose
k}(p-1)^{n-k}}\sum\limits_{b=0}^{n}\Pr\limits_{s\sim
S(n,p,\lambda)}[|s|_{0}=b]K_{k}(b)$ $\displaystyle=\frac{1}{{n\choose
k}(p-1)^{n-k}}\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})]\qed$

Lemma 3.5: _For $s\in S(n,p,\lambda)$, we have that
$\Pr[|s|_{0}=\ell]=\frac{1}{p^{n}}\sum\limits_{k=0}^{n}K_{\ell}(k)\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})].$_

###### Proof.

$\displaystyle\Pr[|s|_{0}=\ell]$
$\displaystyle=\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}q(\ell)$
$\displaystyle=\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\sum\limits_{k=0}^{n}\hat{q}(k)K_{k}(\ell)$
$\displaystyle=\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\sum\limits_{k=0}^{n}\frac{K_{k}(\ell)}{{n\choose
k}(p-1)^{n-k}}\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]$
$\displaystyle=\frac{1}{p^{n}}\sum\limits_{k=0}^{n}\frac{{n\choose\ell}}{{n\choose
k}}\frac{(p-1)^{n-\ell}}{(p-1)^{n-k}}\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]K_{k}(\ell)$
$\displaystyle=\frac{1}{p^{n}}\sum\limits_{k=0}^{n}K_{\ell}(k)\operatorname*{\mathbb{E}}\limits_{s\sim
S(n,p,\lambda)}[K_{k}(|s|_{0})]\quad\text{(By the reciprocity relation in
Corollary 9.3.1)}\qed$

######  Lemma B.5.

_The total variational distance between the $n$-step generalized sticky random
walk on $p$ vertices and the $n$-round uniform distribution on $p$ states is
given by_

$\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(U_{p}^{n})]_{0})=\frac{1}{2}\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[|p(b)-1|]$

###### Proof.

$\begin{split}\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(U_{p}^{n})]_{0})&=\frac{1}{2}\sum\limits_{\ell=0}^{n}\bigg{|}\Pr[|s|_{0}=\ell]-\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\bigg{|}\\\
&=\frac{1}{2}\sum\limits_{\ell=0}^{n}\bigg{|}{n\choose\ell}q(\ell)\frac{(p-1)^{n-\ell}}{p^{n}}-\frac{{n\choose\ell}(p-1)^{n-\ell}}{p^{n}}\bigg{|}\\\
&=\frac{1}{2}\sum\limits_{\ell=0}^{n}\bigg{|}\frac{{n\choose\ell}}{p^{n}}(p-1)^{n-\ell}(q(\ell)-1)\bigg{|}\\\
&=\frac{1}{2}\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[|q(b)-1|]\qed\end{split}$

######  Claim.

_The total variational distance between the generalized sticky random walk and
the multinomial distribution has the following upper bound as a result of
convexity:_

$\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{p}^{n})]_{0})\leq\frac{1}{2}\sqrt{\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(\mathrm{U}_{p}^{n})]_{0}}[q(b)-1]^{2}}$

######  Lemma B.6.

_For $k\leq n$ and for $b\sim[\Sigma(U_{p}^{n})]_{0}$, we have that_

$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}=\sum\limits_{k=1}^{n}\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}(p-1)^{n-k}}$

###### Proof.

$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}=\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}\bigg{[}\bigg{(}\sum\limits_{k=0}^{n}\hat{q}(k)K_{k}(b)-1\bigg{)}^{2}\bigg{]}$

Recall that
$\hat{q}(k)=\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]}{{n\choose
k}(p-1)^{n-k}}$. So,
$\hat{q}(0)=\frac{\operatorname*{\mathbb{E}}[K_{0}(|s|_{0})]}{(p-1)^{n}}=\frac{1}{(p-1)^{n}}$.
Similarly, by the definition of the Krawtchouk function and the reciprocity
relation $\frac{K_{k}(\ell)}{{n\choose
k}(p-1)^{n-k}}=\frac{K_{s}(\ell)}{{n\choose s}(p-1)^{n-s}}$, we have that
$K_{0}(b)=K_{n}(b)=(p\\!-\\!1)^{n}$. Therefore, $\hat{q}(0)K_{0}(b)=1$. Thus,
the above equation simplifies to:

$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}=\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}\bigg{[}\bigg{(}\sum\limits_{k=1}^{n}\hat{q}(k)K_{k}(b)\bigg{)}^{2}\bigg{]}$

Since the generalized Krawtchouk functions are orthogonal (as proven in Lemma
9.2), the non-diagonal products evaluate to 0. So, the square of the summation
is just the summation of the squared terms that it contains. Thus, exploiting
the orthogonality of the generalized Krawtchouk functions and the linearity of
the expectations, we write:

$\begin{split}\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}&=\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}\bigg{[}\sum\limits_{k=1}^{n}\hat{q}(k)^{2}K_{k}(b)^{2}\bigg{]}\\\
&=\sum\limits_{k=1}^{n}\hat{q}(k)^{2}\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[K_{k}(b)^{2}]\\\
&=\sum\limits_{k=1}^{n}\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}^{2}(p-1)^{2n-2k}}\cdot\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[K_{k}(b)^{2}]\end{split}$

Finally, we use Lemma 9.2 to write
$\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[K_{k}(b)^{2}]$
as $\langle K_{k},K_{k}\rangle={n\choose k}(p-1)^{n-k}$.

$\begin{split}\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}&=\sum\limits_{k=1}^{n}\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}^{2}(p-1)^{2n-2k}}{n\choose k}(p-1)^{n-k}\\\
&=\sum\limits_{k=1}^{n}\frac{\operatorname*{\mathbb{E}}[K_{k}(|s|_{0})]^{2}}{{n\choose
k}(p-1)^{n-k}}\qed\end{split}$

######  Theorem B.7.

For $\lambda\leq\frac{1}{1+e}$,

$\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{p}^{n})]_{0})\leq\sqrt{\operatorname*{\mathbb{E}}\limits_{b\sim
M}[p(b)-1]^{2}}\leq O(\lambda p^{p})$

###### Proof.

Substituting the result of Corollary 5.1 into the equation derived in Lemma
6.2, and scaling the indexes of the summation, we have that:

$\displaystyle\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}$
$\displaystyle=\sum\limits_{k=1}^{n/p}\frac{1}{{n\choose
pk}(p\\!-\\!1)^{n-pk}}\bigg{(}(p\\!-\\!1)^{n-pk}\sum\limits_{d=pk}^{n-pk}{{d-1}\choose{\lfloor\frac{kp}{p-1}\rfloor}-1}{{n-d}\choose{\lfloor\frac{kp}{p-1}\rfloor}}\lambda^{d}\bigg{)}^{2}$
$\displaystyle=\sum\limits_{k=1}^{n/p}\frac{(p\\!-\\!1)^{n-pk}}{{n\choose
pk}}\bigg{(}\sum\limits_{d=pk}^{n-pk}{{d-1}\choose{\lfloor\frac{k}{1-\frac{1}{p}}\rfloor}-1}{{n-d}\choose{\lfloor\frac{k}{1-\frac{1}{p}}\rfloor}}\lambda^{d}\bigg{)}^{2}$
$\displaystyle\leq\sum\limits_{k=1}^{n/p}(p\\!-\\!1)^{n-pk}\frac{{n\choose
k}^{2}}{{n\choose
pk}}\bigg{(}\sum\limits_{d=pk}^{n-pk}{{d-1}\choose{k-1}}\lambda^{d}\bigg{)}^{2}$

Note the following generating function relation that
$(\frac{x}{1-x})^{k}=\sum\limits_{m\geq k}{{m-1}\choose{k-1}}x^{m}$. Then,

$\displaystyle\operatorname*{\mathbb{E}}\limits_{b\sim[\Sigma(U_{p}^{n})]_{0}}[q(b)-1]^{2}$
$\displaystyle\leq\sum\limits_{k=1}^{n/p}(p-1)^{n-pk}\frac{{n\choose
k}^{2}}{{n\choose pk}}\bigg{(}\frac{\lambda}{1-\lambda}\bigg{)}^{2k}$
$\displaystyle\leq\sum\limits_{k=1}^{n/p}(p\\!-\\!1)^{n-pk}\bigg{(}\frac{pk}{n}\bigg{)}^{pk}\bigg{(}\frac{en}{k}\bigg{)}^{2k}\bigg{(}\frac{\lambda}{1-\lambda}\bigg{)}^{2k}\quad\text{(From
claim 6.1)}$
$\displaystyle=\sum\limits_{k=1}^{n/p}(p\\!-\\!1)^{n-pk}\bigg{(}\frac{pk}{n}\bigg{)}^{pk-2k}\bigg{(}\frac{pe\lambda}{1-\lambda}\bigg{)}^{2k}$
$\displaystyle\leq
p^{2p}\sum\limits_{k=1}^{n/p}\bigg{(}\frac{e\lambda}{1-\lambda}\bigg{)}^{2k}$
$\displaystyle\leq p^{2p}O(\lambda^{2}),\quad\text{for
}\lambda\leq\frac{1}{1+e}$

Therefore, for $\lambda\leq\frac{1}{1+e}$, we have that
$\mathrm{TVD}([\Sigma(S(n,p,\lambda))]_{0},[\Sigma(\mathrm{U}_{p}^{n})]_{0})\leq\sqrt{\operatorname*{\mathbb{E}}\limits_{b\sim
M}[p(b)-1]^{2}}\leq O(\lambda p^{O(p)})$. ∎

This method shows that the total variation distance between the $n$-step
generalized sticky random walk on $p$ vertices and the $n$-ary samples from
the Uniform distribution on $\operatorname*{\mathbb{Z}}_{p}$ is $O(\lambda
p^{O(p)})$, which matches the more general result predicted in [13].