# Fine Grained Analysis of High Dimensional Random Walks

Roy Gotlib 111Department of Computer Science, Bar-Ilan University,
<EMAIL_ADDRESS>research supported by ERC and ISF.  Tali Kaufman
222Department of Computer Science, Bar-Ilan University<EMAIL_ADDRESS>research supported by ERC and ISF.

###### Abstract

One of the most important properties of high dimensional expanders is that
high dimensional random walks converge rapidly. This property has proven to be
extremely useful in a variety of fields in the theory of computer science from
agreement testing to sampling, coding theory and more. In this paper we
present a state of the art result in a line of works analyzing the convergence
of high dimensional random walks [KM17, DK17, KO18, AL20], by presenting a
_structured_ version of the result of [AL20]. While previous works examined
the expansion in the viewpoint of the worst possible eigenvalue, in this work
we relate the expansion of a function to the entire spectrum of the random
walk operator using the structure of the function; We call such a theorem a
Fine Grained High Order Random Walk Theorem. In sufficiently structured cases
the fine grained result that we present here can be much better than the worst
case while in the worst case our result is equivalent to [AL20].

In order to prove the Fine Grained High Order Random Walk Theorem we introduce
a way to bootstrap the expansion of random walks on the vertices of a complex
into a fine grained understanding of higher order random walks, provided that
the expansion is good enough.

In addition, our _single_ bootstrapping theorem can simultaneously yield our
Fine Grained High Order Random Walk Theorem as well as the well known
Trickling down Theorem. Prior to this work, High order Random walks theorems
and Tricking down Theorem have been obtained from different proof methods.

##  1 Introduction

In recent years much attention has been given to the field of high dimensional
expanders which are high dimensioanl analogues of expander graphs. One
extremely useful property of high dimensional expanders is that higher
dimensional random walks (which are higher dimensional analogues of random
walks on graphs) converge rapidly to their stationary distribution (For
example, this property was used in [DK17, KM20, ALGV18, DHK+19] and more).
Consequently there has been some work studying the convergence of higher
dimensional random walks [DK17, KM17, KO18, AL20]. In this paper we improve
upon these convergence results by relating the structure of the function to
its expansion. Specifically we present the following improvements:

##### Fine grained analysis of random walk

Prior to this paper, the state of the art analysis of high dimensional random
walks was done by Alev and Lau in [AL20] following [DK17, KM17, KO18]. Their
work analyzed the eigenvalues of an important random walk called the _down-up
random walk_. Their result, however, was only useful for the worst case
analysis as it did not relate the structure of the function to its expansion
and thus was forced to consider the worst possible function. In this paper we
present an improvement upon Alev and Lau’s result by finding a connection
between the structure of a function and how well it expands and can therefore
yield better results on cochains that posses a “nice” structure.

In two-sided spectral expanders a fine grained analysis of high dimensional
random walks was already proven, based on Fourier analysis in high dimensional
expanders [DDFH18, KO18]. In the two sided case even stronger results
following from hypercontractivity are known [BHKL20, BHKL21, GLL22] and more.
Our result is, importantly, about _one-sided_ spectral expanders as there are
cases when the use of one-sided high dimensional expansion is crucial - for
example in Anari et al’s breakthrough proof of the fast convergence of the
basis exchange walk [ALGV18] and thus showed an algorithm that samples a basis
of a matroid. This result started a wave of sampling results that use high
dimensional expanders [CLV21, ALG20, AJK+22] to name a few examples. This
result relies heavily on fast convergence of high dimensional random walks on
one-sided expanders (As they show that that the basis exchange corresponds to
a down-up walk on the top dimension of a one-sided high dimensional expander).
In this work we present, to our knowledge, the first result to show a fine
grained analysis of the random walk operator in one-sided local spectral
expanders.

##### Replacing eigendecomposition

Previous fine grained analysis of high dimensional random walks relied on
finding approximate eigendecomposition of the high dimensional random walk. We
present a new approach to finding a fine grained understanding of the high
dimensioanl random walks: bootstrapping an understanding of the expansion of
random walks on the vertices of the complex. We show that, if the expansion of
these random walks beat the expansion of high dimensional random walks on the
vertices of local structures333Specifically, high dimensional random walks on
the vertices of the links of vertices., we can bootstrap it into a _fine
grained_ understanding of higher dimensional random walks.

##### Unification of the High order random walk theorem and the Tricking down
theorem

In order to perform our fine grained analysis of the higher dimensional random
walk operators we develop a new bootstrapping framework. This new framework is
fairly generic and seems to be of independent interest as it can be used to
prove another central theorem in the theory of high dimensional expansion,
namely the trickling down theorem [Opp17]. We comment that prior to this work
these two important theorems were obtained by different proof techniques.

Before we can state our results more formally, we have to define the high
dimensional analogs of expander graphs as graphs do not posses high
dimensions. This high dimensional object is called a “simplicial complex” and
is defined as:

######  Definition 1.1 (Simplicial complex).

A set $X$ is a _simplicial complex_ if it is closed downwards meaning that if
${\sigma}\in X$ and ${\tau}\subseteq{\sigma}$ then ${\tau}\in X$. We call
members of $X$ the _faces_ of $X$.

Simplicial complexes can be thought of as hyper-graphs with closure property
(i.e. every subset of a hyper-edge is a hyper-edge). We are interested in
higher dimensions and therefore it would be useful to define the dimension of
these higher dimensional objects:

######  Definition 1.2 (Dimension).

Let $X$ be a simplicial complex and let ${\sigma}\in X$ be a face of $X$.
Define the dimension of ${\sigma}$ to be:

$\dim{\left({\sigma}\right)}=\left|{\sigma}\right|-1$

Denote the set of all faces of dimension $i$ in $X$ as $X(i)$. Also define the
dimension of the complex $X$ as:

$\dim{\left(X\right)}=\max_{{\sigma}\in
X}{\left\\{\dim{\left({\sigma}\right)}\right\\}}$

Note that there is a single $(-1)$-dimensional face - the empty face.

Of particular interest are simplicial complexes whose maximal faces are of the
same dimension, defined below:

######  Definition 1.3 (Pure simplicial complex).

A simplicial complex $X$ is a _pure simplicial complex_ if every face
${\sigma}\in X$ is contained in some
$\left(\dim{\left(X\right)}\right)$-dimensional face.

Throughout this paper we will assume that every simplicial complex is pure. In
most cases we will be interested in weighted pure simplicial complexes. In
weighted pure simplicial complexes the top dimensional faces are weighted and
the weight of the rest of the faces follows from there as described here:

######  Definition 1.4 (Weight).

Let $X$ be a pure $d$-dimensional simplicial complex. Define its weight
function $\operatorname{w}:X\rightarrow\left[0,1\right]$ to be a function such
that:

  * •

$\sum_{{\sigma}\in X(d)}{\operatorname{w}\left(X\right)}=1$

  * •

For every face ${\tau}$ of dimension $i<d$ it holds that:

$\operatorname{w}\left({\tau}\right)=\frac{1}{\binom{d+1}{i+1}}\sum_{\begin{subarray}{c}{\sigma}\in
X(d)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\operatorname{w}\left({\sigma}\right)}$

It is important to note that we think of unweighted complex as complexes that
satisfy $\forall{\sigma}\in
X(d):\operatorname{w}\left({\sigma}\right)=\frac{1}{\left|X(d)\right|}$. While
the top dimensional faces of unweighted complexes all have the same weight,
the same cannot be said for lower dimensional faces.

It is also important to note that the sum of weights in every dimension is
exactly $1$ and therefore for every $k$ the weight function can, and at times
will, be thought of as a distribution on $X(k)$.

One key property of high dimensional expanders is that they exhibit _local to
global_ phenomena. These phenomena are at the main interest of this paper. It
is therefore useful to consider local views of the simplicial complex which we
define as follows:

######  Definition 1.5 (Link).

Let $X$ be a simplicial complex and ${\sigma}\in X$ be a face of $X$. Define
the _link_ of ${\sigma}$ in $X$ as:

$X_{{\sigma}}=\left\\{{\tau}\setminus{\sigma}\middle|{\sigma}\subseteq{\tau}\right\\}$

It is easy to see that the link of any face is a simplicial complex.

The weight of faces in the links is induced by the weights of the faces in the
original complex. Specifically, we denote by $\operatorname{w}_{{\sigma}}$ the
weight function in the link of ${\sigma}\in X(i)$ and it holds that:

$\forall{\tau}\in
X_{{\sigma}}(j):\operatorname{w}_{{\sigma}}\left({\tau}\right)=\frac{\operatorname{w}\left({\tau}\cup{\sigma}\right)missing}{\binom{i+j+2}{i+1}\operatorname{w}\left({\sigma}\right)missing}$

Generally speaking, the local to global phenomena are ways to derive
properties of the entire complex by only looking at local views (i.e. links).

Another important substructure of a simplicial complex is its skeletons

######  Definition 1.6 (Skeleton).

Let $\left(X,\operatorname{w}\right)$ be a weighted pure $d$-dimensional
simplicial complex and let $i\leq d$. Define the $i$-skeleton of $X$ as the
following weighted simplicial complex:

$X^{\left(i\right)}=\left\\{{\sigma}\in X\middle|\dim{{\sigma}}\leq
i\right\\}$

With the original weight function.

In many cases we will think of the $1$-skeleton of a simplicial complex as a
graph. In addition, it is important to note that even if the original complex
is unweighted, the skeletons of said complex might still be weighted.

We are now ready to define a high dimensional expander444There is no singular
definition of high dimensional expander but for the majority of this paper we
only use the algebraic definition - local spectral expansion..

######  Definition 1.7 (Local spectral expander).

A pure $d$-dimensional simplicial complex $X$ is a $\lambda$-local spectral
expander555Much like one dimensional expanders, in high dimensions there is
also notion of one-sided vs. two-sided local spectral expansion. The
definition we use throughout the paper is that of _one_ -sided local spectral
expander. The difference being that in two-sided local spectral expander the
underlying graph of every link is a two-sided expander rather than a one-sided
expander. if for every face ${\sigma}$ of dimension at most $d-2$ it holds
that $X_{{\sigma}}^{\left(1\right)}$ is a $\lambda$-spectral expander666The
complexes are weighted and therefore their expansion property is defined as
the second largest eigenvalue of the non-lazy random walk. A random walk that
walks from a face to one of its neighbours with probability equal to the
proportion between the weight of the edge that connects them and the sum of
the weights of the edges that include said vertex.. Note that this includes
${\sigma}=\emptyset$, i.e. the entire complex.

Much like graphs, simplicial complexes also support random walks. In graphs,
the random walks are of the form vertex-edge-vertex - the walk might move
between two vertices if they are connected by an edge. The high dimensional
analogue of these random walks travel between two $k$-dimensional faces if
they are part of a common $(k+1)$-dimensional face. Our particular random walk
of interest is the higher dimensional analogue of the non-lazy random walk,
defined as follows:

######  Definition 1.8 (Non-lazy up-down operator informal, for formal see
4.1).

Define the $k$-dimensional non-lazy up-down random walk,
$\left(M^{\prime}\right)^{+}_{k}$ as the $k$ dimensional analogue of the non-
lazy random walk on the vertices of a graph: A walk that moves between two
$k$-dimensional faces if they are contained in a $(k+1)$-dimensional face and
never stays in place.

We are going to improve our understanding of how these higher dimensional
random walks apply to structured states. These states correspond to another
natural structure on high dimensional expanders called cochains that is
defined as follows:

######  Definition 1.9 (Cochains).

Let $X$ be a pure $d$-dimensional simplicial complex. For $-1\leq k\leq d$
define a $k$-dimensional cochain ${F}$ to be any function from $X(k)$ to
$\mathbbm{R}$. We also denote by $C^{k}\left(X;\mathbbm{R}\right)$ the set of
all $k$-dimensional cochains.

We are going to be interested in ways of viewing the cochains in the links of
the complex. For now we will only introduce one such way. Namely localization:

######  Definition 1.10 (Localization).

Let $X$ be a pure $d$-dimensional simplicial complex, $k,i$ be dimensions such
that $i<k$ and ${F}\in C^{k}\left(X;\mathbbm{R}\right)$. Also let ${\sigma}\in
X(i)$. Define the localization of ${F}$ to ${\sigma}$ to be:

${F}_{{\sigma}}({\tau})={F}({\sigma}\cup{\tau})$

We note that there is a very natural inner product defined on the cochains of
a simplicial complex, defined as follows:

######  Definition 1.11 (Inner product).

Let $X$ be a pure $d$-dimensional simplicial complex and let ${F},{G}\in
C^{k}\left(X;\mathbbm{R}\right)$. Define the inner product of ${F}$ and ${G}$
to be:

$\left<{F},{G}\right>=\sum_{{\sigma}\in
X(k)}{\operatorname{w}\left({\sigma}\right){F}({\sigma}){G}({\sigma})}$

###  1.1 Main Results

In this paper we present a state of the art analysis the high dimensional
analogue of the non-lazy random walk. We are specifically interested in going
beyond Alev and Lau’s worst case result [AL20, Theorem 1.5] and relate the
structure of the cochain to its expansion. Specifically, we define:

######  Definition 1.12 ($i$-level cochain, informal. For formal see
Definition 5.3).

A cochain ${F}$ is an $i$-level cochain with respect to localization if for
every ${\sigma}\in X(i-1)$ it holds that
$\left<{F}_{{\sigma}},\mathbbm{1}\right>=0$.777We note that every
$j$-dimensional $i$-level cochain corresponds to a cochain in the $i$th
dimension that has been “lifted” up to the $j$th dimension. A more formal
version of this statement can be found in Lemma 7.8.

Previously the best analysis of high dimensional random walk was due to Alev
and Lau [AL20, Theorem 1.5] who showed that:

######  Theorem 1.13 (Alev and Lau [AL20], restated).

Let $X$ be a pure $d$-dimensioanl high dimensional expander. Define
$\gamma_{i}=\max_{{\sigma}\in
X(i)}{\left\\{\lambda_{2}(X_{{\sigma}})\right\\}}$. For any dimension $k$ and
any $k$-dimensional $0$-level cochain ${F}$ it holds that:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>\leq\left(1-\frac{1}{k+1}\prod_{j=-1}^{k-2}{(1-\gamma_{i})}\right)\left\|{F}\right\|^{2}$

We show that this result can be vastly improved for structured cochains.
Specifically, we show the following decomposition of the high dimensional
random walks:

######  Theorem 1.14 (Fine grained analysis of high dimensional random walks,
Informal. For formal see Theorem 7.9).

Let ${F}\in C^{k}\left(X;\mathbbm{R}\right)$ and let ${F}_{0},\cdots,{F}_{k}$
be an orthogonal decomposition of ${F}$ such that ${F}_{i}$ is an $i$-level
cochain and ${F}=\sum_{i=0}^{k}{{F}_{i}}$. In addition, let
$\gamma_{i}=\max_{{\sigma}\in
X(i)}{\left\\{\lambda_{2}(X_{{\sigma}})\right\\}}$ (Where
$\lambda_{2}(X_{{\sigma}})$ is the second largest eigenvalue of the underlying
graph of $X_{{\sigma}}$) then:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>\leq\sum_{i=0}^{k}{\left(1-\frac{1}{k-i+1}\prod_{j=i-1}^{k-1}{(1-\gamma_{j})}\right)\left\|{F}_{i}\right\|^{2}}$

##### Cases where we improve upon previous results

In the worst case (i.e. no assumption is made on the structure of ${F}$) our
result matches that of Alev and Lau. In cases where the cochain is structured,
however, our Theorem yields strictly better results than what was previously
known. We also give some examples of families of structured cochains on which
our result is _strictly better_ than the result of Alev and Lau -
Specifically, we show two families of cochains that are highly structured: The
first is a set of cochains associated with a different form of high
dimensional expansion, the minimal cochains and the second is the indicator
function of a balanced set of faces (for more information, see Subsection
7.3).

##### Comparison with other known decompositions

Similar decompositions of the high dimensional random walks were already known
for two-sided high dimensional expanders [DDFH18, KO18]. These decomposition
relied on finding approximate eigenspaces of the walk operator. Unlike the
case in two-sided high dimensional expanders, in one-sided high dimensional
expanders the eigenspaces of the high dimensional random walks are not
currently understood, even approximately. We do, however, understand the
expansion of key random walks on the $0$-dimensional cochains. We follow this
by showing that if this expansion is strong enough (i.e. these random walks
converge fast enough) we can boost it to all levels and get a decomposition
theorem without eigendecomposition. In order to apply our bootstrapping method
we have to show that the expansion of the aforementioned $0$-dimensional
cochains “beats” the expansion of cochains of higher levels. Note that the
decomposition achieved by our bootstrapping theorem differs from the
decomposition known in two-sided expanders in one _crucial_ way: In our
decomposition the level functions are _not_ approximate eigenfunctions.
Moreover, applying the non-lazy up-down random walk operator to any one of
them yields a cochain that is _not_ orthogonal to many of the other
${F}_{j}$s. This allows us to sidestep a major technical barrier in previous
works as we do not rely on the existence of an eigendecomposition of the walk
operator (or even an approximate decomposition of that operator). Note that
many results that use local spectral expanders, such as their usage in proving
the existence of cosystolic expanders, agreement testing, locally testable
codes and more only require one application of the walk operator and thus we
believe that our result will prove to be influential with regards to these
fields.

Our main tool for proving the decomposition of high dimensional random walks
is a bootstrapping theorem that reduces decomposition of higher dimensional
random walk to an understanding of highly structured cochains (for example
cochains that correlate with $0$-dimensional cochains). The bootstrapping
theorem is fairly general and thus we bring a special case of it here:

######  Theorem 1.15 (Bootstrapping theorem, informal. For formal see Theorem
5.8).

Let $X$ be a simplicial complex and $k$ be a dimension. Every ${F}\in
C^{k}\left(X;\mathbbm{R}\right)$ that is orthogonal to the constant functions
can be decomposed into ${F}=\sum_{i=0}^{k}{{F}_{i}}$ such that the cochains
${F}_{i}$ are both:

  1. 1.

_$i$ -level cochains with respect to localization_.

  2. 2.

_Orthogonal:_ For every $i\neq j$ it holds that ${F}_{i}$ is orthogonal to
${F}_{j}$.

We can use a solution of some recursive formula on $0$-level cochains and
values $\left\\{\lambda_{i}\right\\}_{i=0}^{k}$ in order to bootstrap a
decomposition of the following form:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>=\sum_{i=0}^{k}{\lambda_{i}\left\|{F}_{i}\right\|^{2}}$

Solving the recursive formula in the bootstrapping theorem requires us to gain
some “advantage” for highly structured cochains in the complex. We can
therefore view this Theorem as a tool that allows us to bootstrap an advantage
we have to a decomposition of the non-lazy random walks.

As we said, our bootstrapping theorem is fairly generic and can also yield the
celebrated Oppenheim’s trickling down theorem [Opp17, Theorem 4.1]:

######  Theorem 1.16 (Trickling Down, [Opp17]).

Let $X$ be a pure $d$-dimensional simplicial complex. If it holds that:

  * •

For every vertex ${v}$: $X_{{v}}^{\left(1\right)}$ is a $\lambda$ spectral
expander.

  * •

$X$ is connected.

Then it holds that $X^{\left(1\right)}$ is a $\frac{\lambda}{1-\lambda}$
spectral expander.

In order to prove the trickling down we use Theorem 1.15 while defining the
$i$-level cochains differently. For more detail, see Section 6.

###  1.2 Proof Layout

As we mentioned before, we analyze the _non-lazy up-down random walk_ \- a
high dimensional analogue of the non-lazy random walk in graphs. We would like
to get a decomposition of the non-lazy random walk operator. In order to do
that we decompose the space of cochains to spaces which we term level
cochains. Our proof is then comprised of two steps: A bootstrapping Lemma that
reduces the problem of decomposing the non-lazy up-down random walk operator
to a simple recursive condition about the $0$-level cochains and an advantage
that allows us to solve said recursive condition. We note that solving the
recursive condition is considerably simpler than proving the decomposition
directly as the $0$-level cochains are very structured objects.

##### Link viewers

Local-to-global arguments are typically structured by taking a global cochain,
decomposing it to local cochains (i.e. cochains on the links of the vertices
of the complex) and then using a property of the cochains in the links in
order to argue about the original cochain. Two extremely useful ways of
decomposing a global cochain to cochains in the links are _restriction_ and
_localization_. These two methods share many properties, for example:

  * •

They preserve constant functions - Any global constant function is constant
locally.

  * •

They are linear - The local view of sum of any two global cochains is the sum
of the local views.

  * •

They interact well with the inner product - The expected value of the local
inner products of two cochains is their inner product.

We start by identifying these properties and defining a general object that
satisfy them called a _link viewer_. A link viewer $\Lambda$ defines the local
view of a cochain ${F}$ in the link of ${\sigma}$ which we denote by
$\Lambda_{{\sigma}}{F}$. For the rest of this section, unless stated
otherwise, we will think of the _localization link viewer_ defined as
$\Lambda^{\ell}_{{\sigma}}{F}={F}_{{\sigma}}$.

##### Level cochains

Any link viewer decomposes the space of cochains to subspaces called _$i$
-level cochains_. These spaces are the set of cochains whose expected value is
$0$ when viewed from any $i$-dimensional face. We think of these cochains as
not correlated with any $i$-dimensional face. For example, under the
localization link viewer the $i$-level cochains are cochains ${G}$ that
satisfy: $\forall{\sigma}\in X(i):\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(k-i-1)}{\left[\Lambda^{\ell}_{{\sigma}}{G}({\tau})\right]}=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(k-i-1)}{\left[{G}_{{\sigma}}({\tau})\right]}=0$. Note that any
$i$-level cochain is also an $(i-1)$-level cochain and that of ${F}$ is an
$i$-level cochain then $\Lambda_{{v}}{F}$ is an $(i-1)$-level cochain in the
link of every vertex ${v}$. It is therefore useful to define _proper level
cochains_ as well - a proper $i$-level cochain is an $i$-level cochain that is
orthogonal to every $(i-1)$-level cohain. Every cochain ${F}$ can be
decomposed to ${F}=\sum_{i=-1}^{p}{{F}_{i}}$ such that every ${F}_{i}$ is a
proper $i$-level cochain. This decomposition plays a key role in our proof.

##### The bootstrapping argument

We can now present our proof for the bootstrapping argument. We assume that
the non-lazy up-down random walk expands locally and show that this yields
that the non-lazy up-down random walk expands globally. We restrict our
attention only to $0$-level cochains (which are not necessarily proper) as
$(-1)$-level cochains correspond to the trivial eigenvalue in which we are not
interested. Let ${F}=\sum_{i=0}^{p}{{F}_{i}}$ be a $0$-level cochain. Consider
its localization to the links of vertices
$\Lambda_{{v}}{F}=\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}}$. Note that
$\sum_{i=1}^{p}{\Lambda_{{v}}{F}_{i}}$ is a $0$-level cochain in $X_{{v}}$(as
the localization to links of vertices of $i$-level cochains is an
$(i-1)$-level cochain). Note that $\Lambda_{{v}}{F}_{0}$ is _not_ a $0$-level
cochain. We can, however, apply our decomposition theorem to some part of
$\Lambda_{{v}}{F}_{0}$ by decomposing it to two parts:

  * •

A $0$-level cochain -
$\Lambda_{{v}}{F}_{0}-\operatorname{\mathbbm{E}}{\left[\Lambda_{{v}}{F}_{0}\right]}$

  * •

A remainder - $\operatorname{\mathbbm{E}}{\left[\Lambda_{{v}}{F}_{0}\right]}$.

We can therefore apply our decomposition theorem to
$\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}}-\operatorname{\mathbbm{E}}{\left[\Lambda_{{v}}{F}_{0}\right]}$.
Note that a key step in this decomposition is that despite the fact that these
new localized cochains are _not_ orthogonal to each other, they are _all_
orthogonal to the constants. This allows us to separate them from the constant
part of every localization. All we have left to do is to compensate for the
remainder. This is done using the advantage step which we will describe next.

##### The Advantage

In the advantage step we try to bound the remainder we have left in the
bootstrapping stage. The advantage required in order to achieve the random
walk decomposition Theorem is done by considering the localization link viewer
that showing the following observations:

  1. 1.

Any $0$-level function ${F}_{0}$ is, in a sense, a high dimensional
description of some other $0$-dimensional cochain ${G}\in
C^{0}\left(X;\mathbbm{R}\right)$. This is true in the sense that
$\left\|{F}_{0}\right\|=\left\|{G}\right\|$ and
$\operatorname{\mathbbm{E}}{\left[\Lambda^{\ell}_{{v}}{F}_{0}\right]}=\left\|M^{+{k}}_{0}{G}\right\|$
where $M^{+{k}}_{0}$ is the random walk the applied the up step $k$ times
followed by applying the down step $k$ times.

  2. 2.

There is a connection between the random walk on the underlying graph of the
complex and $M^{+{k}}$. The key claim we use is that once the random walk has
performed its first up step _it can already “see” all the vertices it will
ever see_ (this is due to the structure of simplicial complexes - if two
vertices share a $k$-dimensional face then by the closure property they also
share an edge). Going further up only decreases the probability of staying in
place. Therefore $M^{+{k}}$ is a weighted sum of the underlying graph’s non-
lazy random walk transition matrix and a lazy component (which corresponds to
staying in place). We note that this observation can be generalized to any
random walk on $k$-dimensional faces that “walks through” faces of dimension
higher than $2k$.

Using these observations as well as our understanding of the $0$-dimensional
random walk we obtain the advantage we seek.

##  2 The Signless Differential and Its Adjoint Operator

One of the key operators induced by any simplicial complex is its _signless
differential operator_. The signless differential operator is an averaging
operator that accepts a $k$-dimensional cochain and returns a
$(k+1)$-dimensional cochain. We adopt the terminology of [KO18] and consider
repeated application of the signless differential and its adjoint operator.

######  Definition 2.1 (Signless differential).

The signless differential operator
$d_{k}:C^{k}\left(X;\mathbbm{R}\right)\rightarrow
C^{k+1}\left(X;\mathbbm{R}\right)$ in the following way:

$d_{k}{F}({\sigma})=\operatorname{\mathbbm{E}}_{{\tau}\in
X(k)}{\left[{F}({\tau})\middle|{\tau}\subseteq{\sigma}\right]}=\sum_{{\tau}\in\binom{{\sigma}}{k+1}}{\frac{1}{k+2}{F}\left({\tau}\right)}$

When the dimension is clear from context it will be omitted from the notation.
Also define
$d_{k}^{*}:C^{k+1}\left(X;\mathbbm{R}\right)\rightarrow
C^{k}\left(X;\mathbbm{R}\right)$ to be the adjoint operator of $d_{k}$.

######  Note.

The signless differential does not meet the definition of a differential as
$d_{k}d_{k-1}\neq 0$.

######  Lemma 2.2 ([KO18, Lemma 3.6], [DDFH18]).

It holds that:

$d_{k}^{*}{F}({\tau})=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(k+1)}{\left[{F}({\sigma})\middle|{\tau}\subseteq{\sigma}\right]}=\operatorname{\mathbbm{E}}_{{\sigma}\in
X_{{\tau}}(0)}{\left[{F}_{{\tau}}({\sigma})\right]}$

###### Proof.

Consider, now, the following:

$\displaystyle\left<d{F},{G}\right>$ $\displaystyle=\sum_{{\sigma}\in
X(k+1)}{\operatorname{w}\left({\sigma}\right)d{F}({\sigma}){G}({\sigma})}=\sum_{{\sigma}\in
X(k+1)}{\operatorname{w}\left({\sigma}\right)\operatorname{\mathbbm{E}}_{{\tau}\in
X(k)}{\left[{F}({\tau})\middle|{\tau}\subseteq{\sigma}\right]}{G}({\sigma})}=$
$\displaystyle=\sum_{{\sigma}\in
X(k+1)}{\operatorname{w}\left({\sigma}\right)\left(\sum_{\begin{subarray}{c}{\tau}\in
X(k)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\frac{1}{k+2}{F}({\tau})}\right){G}({\sigma})}=$
$\displaystyle=\sum_{{\sigma}\in X(k+1)}{\sum_{\begin{subarray}{c}{\tau}\in
X(k)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\frac{\operatorname{w}\left({\sigma}\right)missing}{k+2}{F}({\tau}){G}({\sigma})}}=$
$\displaystyle=\sum_{{\tau}\in X(k)}{\sum_{\begin{subarray}{c}{\sigma}\in
X(k+1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\frac{\operatorname{w}\left({\sigma}\right)missing}{(k+2)\operatorname{w}\left({\tau}\right)missing}\operatorname{w}\left({\tau}\right){F}({\tau}){G}({\sigma})}}=$
$\displaystyle=\sum_{{\tau}\in
X(k)}{\operatorname{w}\left({\tau}\right){F}({\tau})\sum_{\begin{subarray}{c}{\sigma}\in
X(k+1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\frac{\operatorname{w}\left({\sigma}\right)missing}{(k+2)\operatorname{w}\left({\tau}\right)missing}{G}({\sigma})}}=$
$\displaystyle=\sum_{{\tau}\in
X(k)}{\operatorname{w}\left({\tau}\right){F}({\tau})\sum_{\begin{subarray}{c}{\sigma}\in
X(k+1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\sigma}\right){G}({\sigma})}}=$
$\displaystyle=\sum_{{\tau}\in
X(k)}{\operatorname{w}\left({\tau}\right){F}({\tau})\operatorname{\mathbbm{E}}_{{\sigma}\in
X(k+1)}{\left[{G}({\sigma})\middle|{\tau}\subseteq{\sigma}\right]}}$

∎

We will be interested in repeated application of the signless differential and
its adjoint operator. To that effect it will be useful to present them
explicitly. Lemmas 2.3 and 2.5 will present repeated applications of these
operators explicitly.

######  Lemma 2.3.

Let ${F}$ be an $i$-dimensional cochain. Then:

$d_{j-1}\cdots d_{i}{F}({\sigma})=\operatorname{\mathbbm{E}}_{{\tau}\in
X\left(i\right)}{\left[{F}({\tau})\middle|{\tau}\subseteq{\sigma}\right]}$

###### Proof.

By induction, the case of $j=i+1$ follows from the definition of $d_{i}$.

Induction step:

$\displaystyle d_{j}\cdots d_{i}{F}({\sigma})$
$\displaystyle=\operatorname{\mathbbm{E}}_{{\tau}\in X(j)}{\left[d_{j}\cdots
d_{i}{F}({\tau})\middle|{\tau}\subseteq{\sigma}\right]}=\operatorname{\mathbbm{E}}_{{\tau}\in
X(j)}{\left[\operatorname{\mathbbm{E}}_{{\tau}^{\prime}\in
X\left(i\right)}{\left[{F}({\tau}^{\prime})\middle|{\tau}^{\prime}\subseteq{\tau}\right]}\middle|{\tau}\subseteq{\sigma}\right]}$
$\displaystyle=\sum_{{\tau}\in\binom{{\sigma}}{j+1}}{\frac{1}{j+2}\sum_{{\tau}^{\prime}\in\binom{{\tau}}{i+1}}{\frac{1}{\binom{j+1}{i+1}}{F}({\tau}^{\prime})}}=\sum_{{\tau}\in\binom{{\sigma}}{j+1}}{\frac{1}{j+2}\sum_{{\tau}^{\prime}\in\binom{{\tau}}{i+1}}{\frac{(j-i)!(i+1)!}{(j+1)!}{F}({\tau}^{\prime})}}$
$\displaystyle=\sum_{{\tau}\in\binom{{\sigma}}{j+1}}{\sum_{{\tau}^{\prime}\in\binom{{\tau}}{i+1}}{\frac{(j-i)!(i+1)!}{(j+2)!}{F}({\tau}^{\prime})}}=\sum_{{\tau}\in\binom{{\sigma}}{i+1}}{(j-i+1)\frac{(j-i)!(i+1)!}{(j+2)!}{F}({\tau})}$
$\displaystyle=\sum_{{\tau}\in\binom{{\sigma}}{i+1}}{\frac{(j-i+1)!(i+1)!}{(j+2)!}{F}({\tau})}=\sum_{{\tau}\in\binom{{\sigma}}{i+1}}{\frac{1}{\binom{j+2}{i+1}}{F}({\tau})}$
$\displaystyle=\operatorname{\mathbbm{E}}_{{\tau}\in
X\left(i\right)}{\left[{F}({\tau})\middle|{\tau}\subseteq{\sigma}\right]}$

∎

We turn our attention to showing that the adjoint operator of the signless
differential localizes to the links in the following way:

######  Lemma 2.4.

For every cochain ${F}$ and every face ${\tau}$ it holds that:

$d_{{\tau}}^{*}{F}_{{\tau}}=(d^{*}{F})_{{\tau}}$

###### Proof.

The Lemma holds due to:

$d_{{\tau}}^{*}{F}_{{\tau}}({\sigma})=\operatorname{\mathbbm{E}}_{{\tau}^{\prime}\in\left(X_{{\tau}}\right)_{{\sigma}}(0)}{\left[\left({F}_{{\tau}}\right)_{{\sigma}}({\tau}^{\prime})\right]}=\operatorname{\mathbbm{E}}_{{\tau}^{\prime}\in
X_{{\tau}{\sigma}}(0)}{\left[{F}_{{\tau}{\sigma}}({\tau}^{\prime})\right]}=d^{*}{F}({\sigma}{\tau})=(d^{*}{F})_{{\tau}}({\sigma})$

∎

######  Lemma 2.5.

Let ${F}$ be an $i$-dimensional cochain. Then:

$d^{*}_{i}\cdots
d^{*}_{j-1}{F}({\sigma})=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(j-i-1)}{\left[{F}_{{\sigma}}({\tau})\right]}$

###### Proof.

By induction, the case where $j=i+1$ holds due to Lemma 2.2. The induction
step follows the following argument:

$\displaystyle d^{*}_{i}\cdots d^{*}_{j}{F}({\sigma})$
$\displaystyle=\operatorname{\mathbbm{E}}_{{v}\in
X_{{\sigma}}(0)}{\left[\left(d^{*}_{i+1}\cdots
d^{*}_{j}{F}\right)_{{\sigma}}({v})\right]}=\operatorname{\mathbbm{E}}_{{v}\in
X_{{\sigma}}(0)}{\left[d^{*}_{{\sigma},i}\cdots
d^{*}_{{\sigma},j-1}{F}_{{\sigma}}({v})\right]}$
$\displaystyle=\operatorname{\mathbbm{E}}_{{v}\in
X_{{\sigma}}(0)}{\left[\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}{v}}(j-i-1)}{\left[{F}_{{\sigma}{v}}({\tau})\right]}\right]}=\sum_{{v}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({v}\right)\sum_{{\tau}\in
X_{{\sigma}{v}}(j-i-1)}{\operatorname{w}_{{\sigma}{v}}\left({\tau}\right){F}_{{\sigma}{v}}({\tau})}}$
$\displaystyle=\sum_{{v}\in X_{{\sigma}}(0)}{\sum_{{\tau}\in
X_{{\sigma}{v}}(j-i-1)}{\operatorname{w}_{{\sigma}}\left({v}\right)\operatorname{w}_{{\sigma}{v}}\left({\tau}\right){F}_{{\sigma}}({\tau}{v})}}$
$\displaystyle=\sum_{{v}\in X_{{\sigma}}(0)}{\sum_{{\tau}\in
X_{{\sigma}{v}}(j-i-1)}{\frac{\operatorname{w}_{{\sigma}}\left({\tau}{v}\right)}{\binom{\left|{\tau}{v}\right|}{\left|{v}\right|}}{F}_{{\sigma}}({\tau}{v})}}$
$\displaystyle=\sum_{{\tau}^{\prime}\in
X_{{\sigma}}(j-i)}{\operatorname{w}_{{\sigma}}\left({\tau}^{\prime}\right){F}_{{\sigma}}({\tau}^{\prime})}$
$\displaystyle=\operatorname{\mathbbm{E}}_{{\tau}^{\prime}\in
X_{{\sigma}}(j-i)}{\left[{F}_{{\sigma}}({\tau}^{\prime})\right]}$

The second equality is due to Lemma 2.4. ∎

##  3 Up-Down and Down-Up Operators

In this section we will present two objects of interest - the up-down and
down-up walks. These are natural operators that result from considering a
standard walk on the $k$-dimensional faces of a simplicial complex using the
following two steps: A _down step_ where, given a $k$-dimensional face, the
walk moves to a $(k-1)$-dimensional face that is contained in it with equal
probability. And an _up step_ in which, given a $k$-dimensional face, the walk
moves to a $(k+1)$-dimensional face with probability proportional to its
weight. Applying the up step followed by the down step yields the up-down walk
while applying the down step followed by the up step yields the down-up walk.

######  Definition 3.1 (Up-down and down-up operators).

Let $X$ be a simplicial complex. Then define the up-down random walk to be:

$\left[M^{+}_{k}\right]_{{\sigma},{\tau}}=\begin{cases}\frac{1}{k+2}&{\sigma}={\tau}\\\
\frac{\operatorname{w}_{{\sigma}}\left({\tau}\setminus{\sigma}\right)}{k+2}&{\sigma}\cup{\tau}\in
X(k+1)\\\ 0&\text{Otherwise}\end{cases}$

And the down-up random walk to be:

$\left[M^{-}_{k}\right]_{{\sigma},{\tau}}=\begin{cases}\frac{1}{k+1}\sum_{{\tau}^{\prime}\in\binom{{\sigma}}{k}}{\operatorname{w}_{{\tau}^{\prime}}\left({\sigma}\setminus{\tau}^{\prime}\right)}&{\sigma}={\tau}\\\
\frac{1}{k+1}\operatorname{w}_{{\sigma}\cap{\tau}}\left({\tau}\setminus{\sigma}\right)&{\sigma}\cap{\tau}\in
X(k-1)\\\ 0&\text{Otherwise}\end{cases}$

We would now like to present characterization the up-down random walk and the
down-up random walk using the signless differential (this characterization had
appeared in [KO18, Corollary 3.7] and is given here for completeness). In
order to do that, consider the following Lemma:

######  Lemma 3.2.

Let $X$ be a simplicial complex, it holds that:

$M^{+}_{k}=d^{*}_{k}d_{k}\qquad\qquad M^{-}_{k}=d_{k-1}d^{*}_{k-1}$

###### Proof.

Let ${F}\in C^{k}\left(X;\mathbbm{R}\right)$ and ${\sigma}\in X(k)$, then:

$\displaystyle d^{*}d{F}({\sigma})$
$\displaystyle=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(0)}{\left[\left(d{F}\right)_{{\sigma}}({\tau})\right]}=\sum_{{\tau}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({\tau}\right)\left(d{F}\right)_{{\sigma}}({\tau})}=\sum_{{\tau}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({\tau}\right)d{F}({\tau}\cup{\sigma})}$
$\displaystyle=\sum_{{\tau}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({\tau}\right)\frac{1}{k+2}\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X(k)\\\
{\tau}^{\prime}\subseteq{\sigma}\cup{\tau}\end{subarray}}{{F}({\tau}^{\prime})}}$
$\displaystyle=\frac{1}{k+2}\sum_{{\tau}\in
X_{{\sigma}}(0)}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in X(k)\\\
{\tau}^{\prime}\subseteq{\sigma}\cup{\tau}\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\right){F}({\tau}^{\prime})}}$
$\displaystyle=\frac{1}{k+2}\sum_{{\tau}\in
X_{{\sigma}}(0)}{\left(\operatorname{w}_{{\sigma}}\left({\tau}\right){F}({\sigma})+\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X(k)\\\ {\tau}^{\prime}\subseteq{\sigma}\cup{\tau}\\\
{\tau}^{\prime}\neq{\sigma}\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\right){F}({\tau}^{\prime})}\right)}$
$\displaystyle=\frac{1}{k+2}\left(\sum_{{\tau}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({\tau}\right){F}({\sigma})}+\sum_{{\tau}\in
X_{{\sigma}}(0)}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in X(k)\\\
{\tau}^{\prime}\subseteq{\sigma}\cup{\tau}\\\
{\tau}^{\prime}\neq{\sigma}\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\right){F}({\tau}^{\prime})}}\right)$
$\displaystyle=\frac{1}{k+2}\left({F}({\sigma})+\sum_{{\tau}\in
X_{{\sigma}}(0)}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in X(k)\\\
{\sigma}\cup{\tau}^{\prime}={\sigma}\cup{\tau}\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}^{\prime}\setminus{\sigma}\right){F}({\tau}^{\prime})}}\right)$
$\displaystyle=\frac{1}{k+2}\left({F}({\sigma})+\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X(k)\\\ {\sigma}\cup{\tau}^{\prime}\in
X(k+1)\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}^{\prime}\setminus{\sigma}\right){F}({\tau}^{\prime})}\right)$
$\displaystyle=M^{+}_{k}{F}$

In addition:

$\displaystyle dd^{*}{F}({\sigma})$
$\displaystyle=\frac{1}{k+1}\sum_{\begin{subarray}{c}{\tau}\in X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{d^{*}{F}({\tau})}=\frac{1}{k+1}\sum_{\begin{subarray}{c}{\tau}\in
X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\operatorname{\mathbbm{E}}_{{\tau}^{\prime}\in
X_{{\tau}}(0)}{\left[{F}_{{\tau}}({\tau}^{\prime})\right]}}$
$\displaystyle=\frac{1}{k+1}\sum_{\begin{subarray}{c}{\tau}\in X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\sum_{{\tau}^{\prime}\in
X_{{\tau}}(0)}{\operatorname{w}_{{\tau}}\left({\tau}^{\prime}\right){F}_{{\tau}}({\tau}^{\prime})}}$
$\displaystyle=\frac{1}{k+1}\left(\sum_{\begin{subarray}{c}{\tau}\in X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\sigma}\right){F}_{{\tau}}({\sigma}\setminus{\tau})}+\sum_{\begin{subarray}{c}{\tau}\in
X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X_{{\tau}}(0)\\\
{\tau}\cup{\tau}^{\prime}\neq{\sigma}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\tau}^{\prime}\right){F}_{{\tau}}({\tau}^{\prime})}}\right)$
$\displaystyle=\frac{1}{k+1}\left(\sum_{\begin{subarray}{c}{\tau}\in X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\sigma}\right){F}({\sigma})}+\sum_{\begin{subarray}{c}{\tau}\in
X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\sum_{\begin{subarray}{c}{\tau}^{\prime\prime}\in
X(k)\\\ {\tau}^{\prime\prime}\neq{\sigma}\\\
{\tau}^{\prime\prime}\cap{\sigma}={\tau}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\tau}^{\prime\prime}\setminus{\tau}\right){F}_{{\tau}}({\tau}^{\prime\prime}\setminus{\tau})}}\right)$
$\displaystyle=\frac{1}{k+1}\left(\sum_{\begin{subarray}{c}{\tau}\in X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\sigma}\right){F}({\sigma})}+\sum_{\begin{subarray}{c}{\tau}\in
X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\sum_{\begin{subarray}{c}{\tau}^{\prime\prime}\in
X(k)\\\
{\tau}^{\prime\prime}\cap{\sigma}={\tau}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\tau}^{\prime\prime}\setminus{\tau}\right){F}({\tau}^{\prime\prime})}}\right)$
$\displaystyle=\frac{1}{k+1}\left(\sum_{\begin{subarray}{c}{\tau}\in X(k-1)\\\
{\tau}\subseteq{\sigma}\end{subarray}}{\operatorname{w}_{{\tau}}\left({\sigma}\right){F}({\sigma})}+\sum_{\begin{subarray}{c}{\tau}^{\prime\prime}\in
X(k)\\\ {\tau}^{\prime\prime}\cap{\sigma}\in
X(k-1)\end{subarray}}{\operatorname{w}_{{\tau}^{\prime\prime}\cap{\sigma}}\left({\tau}^{\prime\prime}\setminus{\sigma}\right){F}({\tau}^{\prime\prime})}\right)$
$\displaystyle=M^{-}_{k}{F}$

∎

We are also going to be interested in applying the signless differential and
its adjoint operator multiple times in a row. We will therefore define the
$k$-dimensional $i$-up-down operator and the $k$-dimensional $i$-down-up
operator in the following way:

######  Definition 3.3.

Let $M^{+{i}}_{k}$ be the $k$-dimensional $i$-up-down operator and
$M^{-{i}}_{k}$ be the $k$-dimensional $i$-down-up operator defined as follows:

$M^{+{i}}_{k}=d^{*}_{k}\cdots d^{*}_{k+i-1}d_{k+i-1}\cdots d_{k}\qquad\qquad
M^{-{i}}_{k}=d_{k-1}\cdots d_{k-i-1}d^{*}_{k-i-1}\cdots d^{*}_{k-1}$

Recall that the $i$-up-down operator and the $i$-down-up operators can be
presented explicitly using Lemma 2.3 and Lemma 2.5. In addition, note that the
$i$-up-down operator corresponds to applying the up step $i$ times and then
applying the down step $i$ times. Likewise the $i$-down-up operator
corresponds to applying the down step $i$ times and then applying the up step
$i$ times.

##  4 The Non-Lazy Walk Operator

Our main object of study is going to be the non-lazy $k$-dimensional random
walk operator. This operator is a generalization of the non-lazy random walk
operator in graphs to higher dimensions. In graphs the non-lazy random walk
operator moves between two vertices if they have an edge connecting them. The
higher dimensional version of this operator is going to be something very
similar: It is going to move between two $k$-faces if there is a $(k+1)$-face
that contains both faces.

######  Definition 4.1 (The Non-Lazy $k$-dimensional Random Walk Operator).

Let $X$ be a pure $d$-dimensional simplicial complex define the
$k$-dimensional random walk operator to be the following operator:

$\left[\left(M^{\prime}\right)^{+}_{k}\right]_{{\sigma},{\tau}}=\begin{cases}\frac{\operatorname{w}_{{\sigma}}\left({\tau}\setminus{\sigma}\right)}{k+1}&{\sigma}\cup{\tau}\in
X(k+1)\\\ 0&\text{Otherwise}\end{cases}$

One can also think of the non-lazy random walk operator as the regular up-down
operator with the lazy part removed. Formally:

######  Observation 4.2.

For every dimension $k$ it holds that:

$\left(M^{\prime}\right)^{+}_{k}=\frac{k+2}{k+1}M^{+}_{k}-\frac{1}{k+1}I$

Of specific interest is the $0$-dimensional non-lazy up-down operator as it
can be used to describe _every_ one of the $0$-dimensional $i$-up-down
operators. This is because every one of these operators ultimately move
between a vertex and its neighbours. The more steps one takes up the complex
the more mixed the result is. By that we mean that the non-lazy walk operator
has a larger effect on the result. Quantitatively, this can be formulated via
the following Lemma.

######  Lemma 4.3.

$\left(M^{\prime}\right)^{+}_{0}=\frac{i+1}{i}M^{+{i}}_{0}-\frac{1}{i}I$

###### Proof.

Consider the up operator:

$\displaystyle M^{+{i}}_{0}{F}({v})$ $\displaystyle=d^{*}_{0}\cdots
d^{*}_{i-1}d_{i-1}\cdots d_{0}{F}({v})=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{v}}(i-1)}{\left[\left(d_{i-1}\cdots
d_{0}{F}\right)_{{v}}({\tau})\right]}=$
$\displaystyle=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{v}}(i-1)}{\left[d_{i-1}\cdots
d_{0}{F}({\tau}{v})\right]}=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{v}}(i-1)}{\left[\operatorname{\mathbbm{E}}_{{u}\in
X\left(0\right)}{\left[{F}({u})\middle|{u}\subseteq{\tau}{v}\right]}\right]}$
$\displaystyle=\sum_{{\tau}\in
X_{{v}}(i-1)}{\operatorname{w}_{{v}}\left({\tau}\right)\sum_{{u}\in{\tau}{v}}{\frac{1}{\binom{i+1}{1}}{F}({u})}}=\sum_{{\tau}\in
X_{{v}}(i-1)}{\sum_{{u}\in{\tau}{v}}{\frac{\operatorname{w}_{{v}}\left({\tau}\right)}{i+1}{F}({u})}}$
$\displaystyle=\sum_{{\tau}\in
X_{{v}}(i-1)}{\frac{\operatorname{w}_{{v}}\left({\tau}\right)}{i+1}{F}({v})}+\sum_{{\tau}\in
X_{{v}}(i-1)}{\sum_{{u}\in{\tau}}{\frac{\operatorname{w}_{{v}}\left({\tau}\right)}{i+1}{F}({u})}}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\sum_{\begin{subarray}{c}{\tau}\in
X(i)\\\ {v}\in{\tau}\end{subarray}}{\sum_{\begin{subarray}{c}{u}\in X(0)\\\
{u}\neq{v},{u}\in{\tau}\end{subarray}}{\frac{\operatorname{w}\left({\tau}\right)missing}{(i+1)^{2}\operatorname{w}\left({v}\right)missing}{F}({u})}}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\sum_{{u}\in
X(0)}{\sum_{\begin{subarray}{c}{\tau}\in X(i)\\\ {u}\neq{v}\\\
{u},{v}\in{\tau}\end{subarray}}{\frac{\operatorname{w}\left({\tau}\right)missing}{(i+1)^{2}\operatorname{w}\left({v}\right)missing}{F}({u})}}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\sum_{\begin{subarray}{c}{u}\in X(0)\\\
{v}{u}\in X(1)\end{subarray}}{\sum_{\begin{subarray}{c}{\tau}\in X(i)\\\
{u},{v}\in{\tau}\end{subarray}}{\frac{\operatorname{w}\left({\tau}\right)missing}{(i+1)^{2}\operatorname{w}\left({v}\right)missing}{F}({u})}}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\sum_{\begin{subarray}{c}{u}\in X(0)\\\
{v}{u}\in
X(1)\end{subarray}}{\frac{1}{(i+1)^{2}\operatorname{w}\left({v}\right)missing}{F}({u})\sum_{\begin{subarray}{c}{\tau}\in
X(i)\\\ {u},{v}\in{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right)}}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\sum_{\begin{subarray}{c}{u}\in X(0)\\\
{v}{u}\in
X(1)\end{subarray}}{\frac{\binom{i+1}{2}\operatorname{w}\left({v}{u}\right)missing}{(i+1)^{2}\operatorname{w}\left({v}\right)missing}{F}({u})}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\sum_{\begin{subarray}{c}{u}\in X(0)\\\
{v}{u}\in
X(1)\end{subarray}}{\frac{i\operatorname{w}\left({v}{u}\right)missing}{2(i+1)\operatorname{w}\left({v}\right)missing}{F}({u})}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\frac{i}{i+1}\sum_{\begin{subarray}{c}{u}\in
X(0)\\\ {v}{u}\in
X(1)\end{subarray}}{\operatorname{w}_{{v}}\left({u}\right){F}({u})}$
$\displaystyle=\frac{1}{i+1}{F}({v})+\frac{i}{i+1}\left(M^{\prime}\right)^{+}_{0}{F}({v})$

Therefore:

$\left(M^{\prime}\right)^{+}_{0}=\frac{i+1}{i}M^{+{i}}_{0}-\frac{1}{i}I$

∎

##  5 Analyzing the Non-Lazy Random Walk Operator

We are now ready to start analyzing the random walk operators. In order to do
so we are going to use a _local to global_ argument. In order to apply a local
to global argument we must understand how to view a cochain through the links.
Specifically we will be interested in viewing methods that satisfy the
following:

######  Definition 5.1 (Link viewer).

A _link viewer_ is any transformation $\Lambda$ that accepts a face ${\sigma}$
and a cochain in $X$. It then returns a cochain in $X_{{\sigma}}$. In
addition, a link viewer satisfies the following:

  * •

For every face ${\sigma}$ it holds that $\Lambda_{{\sigma}}$ is linear.

  * •

For every face ${\sigma}$ it holds that
$\Lambda_{{\sigma}}\mathbbm{1}=\mathbbm{1}$.

  * •

For every two cochains ${F},{G}$ and any two faces of the same dimension
${\sigma}$,${\tau}$ it holds that:

$\dim\left({F}\right)-\dim\left(\Lambda_{{\sigma}}{F}\right)=\dim\left({G}\right)-\dim\left(\Lambda_{{\tau}}{G}\right)$

In addition, denote the dimensional difference for vertices by:

$\Delta\left(\Lambda\right)=\dim\left({F}\right)-\dim\left(\Lambda_{{v}}{F}\right)$

  * •

Viewing of a cochain in a link is only determined by the cochain and the face
for which it is the link (and not the path taken to achieve said view).
Formally: For every ${\tau}\subseteq{\sigma}\in X$ it holds that:

$\Lambda_{{\sigma}}=\Lambda_{{\sigma}\setminus{\tau}}\Lambda_{{\tau}}$

  * •

For every dimension $i$ it holds that:

$\left<{F},{G}\right>=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<\Lambda_{{\sigma}}{F},\Lambda_{{\sigma}}{G}\right>\right]}$

Of particular interest are link viewers that view the non-lazy random walk
operator in “the right way”:

######  Definition 5.2.

A link viewer respects the non-lazy up-down random walk if for every $k$:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>=\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left<\left(M^{\prime}\right)^{+}_{k-\Delta\left(\Lambda\right)}\Lambda_{{v}}{F},\Lambda_{{v}}{F}\right>\right]}$

######  Definition 5.3 ($i$-level cochain).

A cochain ${F}$ is an $i$-level cochain with respect to $\Lambda$ if it holds
that:

$\forall{\sigma}\in X(i-1):\left<\Lambda_{{\sigma}}{F},\mathbbm{1}\right>=0$

When the link viewer is clear from context we will simply refer to them as
$i$-level cochains. Denote the set of $i$-level $j$-dimensional cochains in
$X$ by $C_{\Lambda,i}^{j}\left(X;\mathbbm{R}\right)$.

######  Lemma 5.4.

For every dimension $j\leq i$:

$C_{\Lambda,i}^{k}\left(X;\mathbbm{R}\right)\subseteq
C_{\Lambda,j}^{k}\left(X;\mathbbm{R}\right)$

###### Proof.

Let ${F}\in C_{\Lambda,i}^{k}\left(X;\mathbbm{R}\right)$ and let ${\sigma}$ be
a $(j-1)$-dimensional face and note the following:

$\displaystyle\left<\Lambda_{{\sigma}}{F},\mathbbm{1}\right>$
$\displaystyle=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(i-j)}{\left[\left<\Lambda_{{\tau}}\Lambda_{{\sigma}}{F},\Lambda_{{\tau}}\mathbbm{1}\right>\right]}=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(i-j)}{\left[\left<\Lambda_{{\tau}{\sigma}}{F},\mathbbm{1}\right>\right]}=0$

Where the last equality is due to the fact that ${\sigma}\cup{\tau}$ is an
$(i-1)$-dimensional face. ∎

Of particular interest are $i$-level cochains that are orthogonal to the
$(i+1)$-level cochains. We will therefore define the following:

######  Definition 5.5 (Proper $i$-level cochain).

A cochain ${F}$ is a proper $i$-level cochain with respect to $\Lambda$ if it
holds that:

${F}\in
C_{\Lambda,i}^{j}\left(X;\mathbbm{R}\right)\cap\left(C_{\Lambda,i+1}^{j}\left(X;\mathbbm{R}\right)\right)^{\bot}$

When the link viewer is clear from context we will simply refer to them as
proper $i$-level cochains. Denote the set of proper $i$-level $j$-dimensional
cochains in $X$ by $C_{\Lambda,\hat{i}}^{j}\left(X;\mathbbm{R}\right)$.

Consider the following key property of proper level cochains:

######  Lemma 5.6.

Let $i<j$ and let ${F}$ be a proper $i$-level cochain and ${G}$ be a proper
$j$-level cochain then:

$\left<{F},{G}\right>=0$

###### Proof.

Due to Lemma 5.4 it holds that ${G}$ is also a $i+1$ level cochain and thus is
orthogonal to ${G}$ by definition. ∎

Note that considering proper level cochains is one of the key ingredients of
this paper. In previous results (For example [KO18]) instead of considering
proper $i$-level cochains the authors essentially considered cochains in
$\left(C_{\Lambda,i}^{k}\left(X;\mathbbm{R}\right)\right)^{\bot}$. Using
proper level cochains allows us to separate the different levels completely
and achieve a proper decomposition. Since analyzing the decomposition with
only pure level cochains in mind is hard (as even if ${F}$ is a level cochain
the same cannot be said about $\Lambda_{{\sigma}}{F}$) we resort to first show
the following technical theorem.

######  Theorem 5.7 (Bootstrapping Theorem, Technical Version).

Let $X$ be a pure $d$-dimensional simplicial complex, $\Lambda$ be a link
viewer that respects the non-lazy up-down random walk and for every $i$ let
${F}_{i}\in C_{\Lambda,i}^{k}\left(X;\mathbbm{R}\right)$ and
${F}=\sum_{i=0}^{p}{{F}_{i}}$. Denote $r=k-\Delta\left(\Lambda\right)$ and
suppose that there are values of
$\left\\{\lambda_{{\sigma},i,j}\right\\}_{{\sigma}\in
X,i\in\left[d\right],j\in\left[d\right]}$ ($\lambda_{{\sigma},i,j}$ is the
contraction of an $i$-level $j$-dimensional cochain in the link of ${\sigma}$)
such that for every ${\sigma}\in X$ and ${G}_{0}$ a $0$-level cochain:

$\begin{cases}\lambda_{{\sigma},1,k}\left\|{G}_{0}\right\|^{2}+\operatorname{\mathbbm{E}}_{{v}\in
X_{{\sigma}}(0)}{\left[(1-\lambda_{{\sigma}\cup\left\\{{v}\right\\},1,r})\left\|M^{-{r}}_{r}\Lambda_{{v}}{G}_{0}\right\|^{2}\right]}\leq\lambda_{{\sigma},0,k}\left\|{G}_{0}\right\|^{2}\\\
\max_{{v}\in
X_{{\sigma}}(0)}{\left\\{\lambda_{{\sigma}\cup\left\\{{v}\right\\},i-1,r}\right\\}}\leq\lambda_{{\sigma},i,k}\end{cases}$

Then:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>\leq\sum_{i=0}^{p}{\lambda_{\emptyset,i,k}\left\|{F}_{i}\right\|^{2}}+\sum_{i=0}^{p}{\sum_{\begin{subarray}{c}j=1\\\
i<j\end{subarray}}^{p}{c_{i,j}\left<{F}_{i},{F}_{j}\right>}}$

For some constants $\left\\{c_{i,j}\right\\}$ and where $p$ is the number of
level functions that span the space orthogonal to the constants.

###### Proof.

Let $r$ be the dimension of $\Lambda_{{\sigma}}{F}$. Consider the following:

$\displaystyle\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>$
$\displaystyle=\left<\left(M^{\prime}\right)^{+}_{k}\sum_{i=0}^{p}{{F}_{i}},\sum_{i=0}^{p}{{F}_{i}}\right>=\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left<\Lambda_{{v}}\left(\left(M^{\prime}\right)^{+}_{r}\sum_{i=0}^{p}{{F}_{i}}\right),\Lambda_{{v}}\left(\sum_{i=0}^{p}{{F}_{i}}\right)\right>\right]}$
(1) $\displaystyle=\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left<\left(M^{\prime}\right)^{+}_{r}\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}},\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}}\right>\right]}$
$\displaystyle=\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left<\left(M^{\prime}\right)^{+}_{r}\left(I-M^{-{r}}_{r}\right)\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}},\left(I-M^{-{r}}_{r}\right)\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}}\right>\right]}+$
$\displaystyle\qquad\qquad+\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left<\left(M^{\prime}\right)^{+}_{r}M^{-{r}}_{r}\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}},M^{-{r}}_{r}\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}}\right>\right]}$
$\displaystyle=\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left<\left(M^{\prime}\right)^{+}_{r}\left(I-M^{-{r}}_{r}\right)\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}},\left(I-M^{-{r}}_{r}\right)\sum_{i=0}^{p}{\Lambda_{{v}}{F}_{i}}\right>\right]}+$
$\displaystyle\qquad\qquad+\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}\right]}$

We will now like to apply our Theorem to the localized cochains in the links.
For that, consider the following level cochains:

level | cochain | square of norm
---|---|---
$k-1$ | ${F}^{{v}}_{k-1}:=\Lambda_{{v}}{F}_{k}$ | $\left\|\Lambda_{{v}}{F}_{k}\right\|^{2}$
$\vdots$ | $\vdots$ | $\vdots$
$1$ | ${F}^{{v}}_{1}:=\Lambda_{{v}}{F}_{2}$ | $\left\|\Lambda_{{v}}{F}_{2}\right\|^{2}$
$0$ | ${F}^{{v}}_{0}:=\Lambda_{{v}}{F}_{1}+\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}$ | $\left\|\Lambda_{{v}}{F}_{1}\right\|^{2}+\left\|\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\right\|^{2}+2\left<\Lambda_{{v}}{F}_{1},\Lambda_{{v}}{F}_{0}\right>$

Note that, by definition, for every $i\geq 2$ it holds that
$\Lambda_{{v}}{F}_{i}\in C_{\Lambda,i-1}^{r}\left(X_{{v}};\mathbbm{R}\right)$.
In addition
$\Lambda_{{v}}{F}_{1}+\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\in
C_{\Lambda,0}^{r}\left(X_{{v}};\mathbbm{R}\right)$. We can therefore apply the
Theorem to every link which (after some manipulation of the mixed terms that,
for completion, is presented in Lemma 5.10) yields that, for every link ${v}$,
it holds that:

$\left<\left(M^{\prime}\right)^{+}_{{v},k}\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F},\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}\right>\leq\sum_{i=0}^{k-1}{\lambda_{{v},i,r}\left\|{F}^{{v}}_{i}\right\|}^{2}+\sum_{i=0}^{p}{\sum_{\begin{subarray}{c}j=1\\\
i<j\end{subarray}}^{p}{c_{i,j}\left<{F}^{{v}}_{i},{F}^{{v}}_{j}\right>}}=\\\
=\sum_{i=0}^{k-1}{\lambda_{{v},i,r}\left\|\Lambda_{{v}}{F}_{i}\right\|}^{2}+\lambda_{{v},0,r}\left\|\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\right\|^{2}+\sum_{i=0}^{p}{\sum_{\begin{subarray}{c}j=1\\\
i<j\end{subarray}}^{p}{c^{\prime}_{i,j}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{j}\right>}}$

Combining this with 1 and noting that $\lambda_{\emptyset,i,k}\geq\max_{{v}\in
X(0)}{\left\\{\lambda_{{v},i-1,r}\right\\}}$ yields that:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>\leq\sum_{i=1}^{k}{\lambda_{\emptyset,i,k}\left\|{F}_{i}\right\|}^{2}+\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}+\lambda_{{v},0,r}\left\|\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\right\|^{2}\right]}+\\\
+\sum_{i=0}^{p}{\sum_{\begin{subarray}{c}j=1\\\
i<j\end{subarray}}^{p}{c^{\prime}_{i,j}\left<{F}_{i},{F}_{j}\right>}}$

Therefore all we have to do is prove that:

$\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}+\lambda_{{v},0,r}\left\|\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\right\|^{2}\right]}\leq\lambda_{\emptyset,0,k}\left\|{F}_{0}\right\|^{2}$

This follows directly from our choice of $\lambda$s:

$\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}+\lambda_{{v},0,r}\left\|\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\right\|^{2}\right]}=\\\
=\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left(1-\lambda_{{v},0,r}\right)\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}+\lambda_{{v},0,r}\left(\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}+\left\|\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\right\|^{2}\right)\right]}=\\\
=\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left(1-\lambda_{{v},0,r}\right)\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}+\lambda_{{v},0,r}\left\|\Lambda_{{v}}{F}_{0}\right\|^{2}\right]}\leq\\\
\leq\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left(1-\lambda_{{v},0,r}\right)\left\|M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right\|^{2}\right]}+\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}\leq\lambda_{\emptyset,0,k}\left\|{F}_{0}\right\|^{2}$

∎

######  Theorem 5.8 (Bootstrapping Theorem).

Let $X$ be a pure $d$-dimensional simplicial complex, $\Lambda$ be a link
viewer that respects the non-lazy up-down random walk and for every $i$ let
${F}_{i}\in C_{\Lambda,\hat{i}}^{k}\left(X;\mathbbm{R}\right)$ be a proper
$i$-level cochain and ${F}=\sum_{i=0}^{p}{{F}_{i}}$. Denote
$r=k-\Delta\left(\Lambda\right)$ and suppose that there are values of
$\left\\{\lambda_{{\sigma},i,j}\right\\}_{{\sigma}\in
X,i\in\left[d\right],j\in\left[d\right]}$ such that for every ${\sigma}\in X$
and ${G}_{0}$ a $0$-level cochain:

$\begin{cases}\lambda_{{\sigma},1,k}\left\|{G}_{0}\right\|^{2}+\operatorname{\mathbbm{E}}_{{v}\in
X_{{\sigma}}(0)}{\left[(1-\lambda_{{\sigma}\cup\left\\{{v}\right\\},1,r})\left\|M^{-{r}}_{r}\Lambda_{{v}}{G}_{0}\right\|^{2}\right]}\leq\lambda_{{\sigma},0,k}\left\|{G}_{0}\right\|^{2}\\\
\max_{{v}\in
X_{{\sigma}}(0)}{\left\\{\lambda_{{\sigma}\cup\left\\{{v}\right\\},i-1,r}\right\\}}\leq\lambda_{{\sigma},i,k}\end{cases}$

Then:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>\leq\sum_{i=0}^{p}{\lambda_{\emptyset,i,k}\left\|{F}_{i}\right\|^{2}}$

###### Proof.

Note that the difference between this Theorem and Theorem 5.7 is the choice of
${F}_{i}$s. Specifically, in this Theorem the the cochains ${F}_{i}$ are
chosen to be _proper_ $i$-level cochains. Therefore, due to Lemma 5.6, they
are orthogonal to each other. This allows us to apply Theorem 5.7 and note
that:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>\leq\sum_{i=0}^{p}{\lambda_{\emptyset,i,k}\left\|{F}_{i}\right\|^{2}}+\sum_{i=0}^{p}{\sum_{\begin{subarray}{c}j=1\\\
i<j\end{subarray}}^{p}{{c^{\prime\prime}}_{i,j}\left<{F}_{i},{F}_{j}\right>}}=\sum_{i=0}^{p}{\lambda_{\emptyset,i,k}\left\|{F}_{i}\right\|^{2}}$

∎

It is important to note that, unlike the decomposition known in the two-sided
case, this decomposition is not a decomposition to approximate eigenfunctions.
When applying the walk operator to a level function the result might be spread
over multiple levels. Theorem 5.8 also yields a decomposition to the up-down
operator:

######  Corollary 5.9.

With the same assumptions as Theorem 5.8 it holds that

$\left<M^{+}_{k}{F},{F}\right>\leq\sum_{i=0}^{p}{\left(\frac{k+1}{k+2}\lambda_{\emptyset,i,k}-\frac{1}{k+1}\right)\left\|{F}_{i}\right\|^{2}}$

###### Proof.

The following holds:

$\left<M^{+}_{k}{F},{F}\right>=\sum_{i=0}^{p}{\frac{k+2}{k+1}\left<\left(M^{\prime}\right)^{+}_{k}{F},{F}\right>-\frac{1}{k+1}\left<{F},{F}\right>}\leq\sum_{i=0}^{p}{\frac{k+2}{k+1}\left<\lambda_{\emptyset,i,k}{F},{F}\right>-\frac{1}{k+1}\left\|{F}\right\|^{2}}=\\\
=\sum_{i=0}^{p}{\frac{k+2}{k+1}\lambda_{\emptyset,i,k}\left\|{F}\right\|^{2}-\frac{1}{k+1}\left\|{F}\right\|^{2}}=\sum_{i=0}^{p}{\left(\frac{k+1}{k+2}\lambda_{\emptyset,i,k}-\frac{1}{k+1}\right)\left\|{F}_{i}\right\|^{2}}$

∎

Before we finish this section, we prove the following (fairly technical) Lemma
for completion

######  Lemma 5.10.

With the notations in Theorem 5.7 and $L=\left\\{{F}^{{v}}_{i}\middle|1\leq
i\leq p\right\\}$ it holds that for every set of constants
$\left\\{c_{{G},{G}^{\prime}}\right\\}_{\begin{subarray}{c}{G},{G}^{\prime}\in
L\\\ {G}\neq{G}^{\prime}\end{subarray}}$ there exists constants
$\left\\{c^{\prime}_{{G},{G}^{\prime}}\right\\}_{\begin{subarray}{c}{G},{G}^{\prime}\in
L\\\ {G}\neq{G}^{\prime}\end{subarray}}$ such that:

$\sum_{\begin{subarray}{c}{G},{G}^{\prime}\in L\\\
{G}\neq{G}^{\prime}\end{subarray}}{c_{{G},{G}^{\prime}}\left<{G},{G}^{\prime}\right>}=\sum_{i=0}^{p}{\sum_{\begin{subarray}{c}j=1\\\
i<j\end{subarray}}^{p}{{c^{\prime}}_{i,j}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{j}\right>}}$

###### Proof.

Consider the following:

$\sum_{\begin{subarray}{c}{G},{G}^{\prime}\in L\\\
{G}\neq{G}^{\prime}\end{subarray}}{c_{{G},{G}^{\prime}}\left<{G},{G}^{\prime}\right>}=\sum_{i=2}^{p}{\sum_{\begin{subarray}{c}j=2\\\
i<j\end{subarray}}^{p}{c_{i,j}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{j}\right>}}+\sum_{i=2}^{p}{c_{0,i}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{1}+\left(I-M^{-{r}}_{r}\right)\Lambda_{{v}}{F}_{0}\right>}\\\
=\sum_{i=2}^{p}{\sum_{\begin{subarray}{c}j=2\\\
i<j\end{subarray}}^{p}{c_{i,j}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{j}\right>}}+\sum_{i=2}^{p}{c_{0,i}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{1}+\Lambda_{{v}}{F}_{0}\right>}-\sum_{i=2}^{p}{c_{0,i}\left<\Lambda_{{v}}{F}_{i},M^{-{r}}_{r}\Lambda_{{v}}{F}_{0}\right>}\\\
=\sum_{i=2}^{p}{\sum_{\begin{subarray}{c}j=2\\\
i<j\end{subarray}}^{p}{c_{i,j}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{j}\right>}}+\sum_{i=2}^{p}{c_{0,i}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{1}\right>}+\sum_{i=2}^{p}{c_{0,i}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{0}]\right>}\\\
=\sum_{i=0}^{p}{\sum_{\begin{subarray}{c}j=1\\\
i<j\end{subarray}}^{p}{{c^{\prime}}_{i,j}\left<\Lambda_{{v}}{F}_{i},\Lambda_{{v}}{F}_{j}\right>}}$

∎

##  6 Trickling Down

Before we present our random walk decomposition Theorem, let us start with a
“warm up”: An alternative proof for the trickling down theorem [Opp17] that is
based on Theorem 5.8. We believe that the fact that the main tool presented
here can be used to prove the trickling down theorem is of independent
interest: it shows that there is a single, local to global argument at the
heart of both claims. In the trickling down theorem we are interested in the
connection between the $0$-dimensional non-lazy random walk on the vertices of
a complex and the $0$-dimensional non-lazy up-down random walk on the links of
the vertices of the complex. It will, therefore, be natural to consider a link
viewer that does not incur a decrease in dimension. One such link viewer is
the restriction link viewer defined as:

######  Definition 6.1 (Restriction).

Given a simplicial complex $X$ and a cochain ${F}\in
C^{k}\left(X;\mathbbm{R}\right)$ define the restriction link viewer in the
following way:

$\forall{\sigma}\in X:\Lambda^{r}_{{\sigma}}{F}({\tau})={F}({\tau})$

This link viewer maps the $0$-dimensional non-lazy up-down random walk to the
$0$-dimensional non-lazy up-down on the links of the vertices. We will show
that applying Theorem 5.8 to the restriction link viewer yields the trickling
down theorem. However, before applying Theorem 5.8, we must first show that
restriction is indeed a link viewer that respects the non-lazy up-down random
walk.

######  Lemma 6.2.

The restriction link viewer is a link viewer.

###### Proof.

We will prove the properties point by point:

  * •

$\Lambda^{r}_{{\sigma}}\left({F}+c\cdot{G}\right)({\tau})=\left({F}+c\cdot{G}\right)({\tau})={F}({\tau})+c\cdot{G}({\tau})=\Lambda^{r}_{{\sigma}}{F}({\tau})+c\cdot\Lambda^{r}_{{\sigma}}{G}({\tau})$

  * •

$\Lambda^{r}_{{\sigma}}\mathbbm{1}=\mathbbm{1}$

  * •

It holds that for every cochain ${F}$ and every face ${\sigma}$:

$\dim\left({F}\right)-\dim\left(\Lambda^{r}_{{\sigma}}{F}\right)=\dim\left({F}\right)-\dim\left({F}\right)=0$

  * •

Let ${\tau}\subseteq{\sigma}\in X$ then:

$\Lambda^{r}_{{\sigma}\setminus{\tau}}\Lambda^{r}_{{\tau}}{F}({\tau}^{\prime})=\Lambda^{r}_{{\tau}}{F}({\tau}^{\prime})={F}({\tau}^{\prime})=\Lambda^{r}_{{\sigma}}{F}({\tau}^{\prime})$

  * •

For every dimension $i$ and $j=\dim\left(\Lambda_{{\sigma}}{F}\right)$ it
holds that:

$\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>\right]}=\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right)\left<\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>}=\\\
=\sum_{{\sigma}\in X(i)}{\operatorname{w}\left({\sigma}\right)\sum_{{\tau}\in
X_{{\sigma}}(j)}{\operatorname{w}_{{\sigma}}\left({\tau}\right)\Lambda^{r}_{{\sigma}}{F}({\tau})\Lambda^{r}_{{\sigma}}{G}({\tau})}}=\\\
=\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right)\sum_{\begin{subarray}{c}{\tau}\in
X(j)\\\ {\sigma}\cup{\tau}\in
X(i+j+1)\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\right)\Lambda^{r}_{{\sigma}}{F}({\tau})\Lambda^{r}_{{\sigma}}{G}({\tau})}}=\\\
=\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right)\sum_{\begin{subarray}{c}{\tau}\in
X(j)\\\ {\sigma}\cup{\tau}\in
X(i+j+1)\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\right){F}({\tau}){G}({\tau})}}=\\\
=\sum_{{\tau}\in
X(j)}{\operatorname{w}\left({\sigma}\right)\sum_{\begin{subarray}{c}{\sigma}\in
X(i)\\\ {\sigma}\cup{\tau}\in
X(i+j+1)\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\right){F}({\tau}){G}({\tau})}}=\\\
=\sum_{{\tau}\in
X(j)}{{F}({\tau}){G}({\tau})\sum_{\begin{subarray}{c}{\sigma}\in X(i)\\\
{\sigma}\cup{\tau}\in
X(i+j+1)\end{subarray}}{\operatorname{w}\left({\sigma}\right)\operatorname{w}_{{\sigma}}\left({\tau}\right)}}=\\\
=\sum_{{\tau}\in
X(j)}{\operatorname{w}\left({\tau}\right){F}({\tau}){G}({\tau})}=\left<{F},{G}\right>$

∎

######  Lemma 6.3.

The restriction link viewer respects the non-lazy random walk operator.

###### Proof.

Note that, for every $i$-dimensional cochian ${G}$ it holds that:

$d\Lambda^{r}_{{\sigma}}{G}({\tau})=\sum_{{\tau}^{\prime}\in\binom{{\tau}}{i}}{\frac{1}{i+1}\Lambda^{r}_{{\sigma}}{G}({\tau}^{\prime})}=\sum_{{\tau}^{\prime}\in\binom{{\tau}}{i}}{\frac{1}{i+1}{G}({\tau}^{\prime})}=d{G}({\tau})=\Lambda^{r}_{{\sigma}}\left(d{G}\right)({\tau})$

It therefore holds, for every dimension $k$:

$\left<M^{+}_{k}{F},{G}\right>=\left<d^{*}_{k}d_{k}{F},{G}\right>=\left<d_{k}{F},d_{k}{G}\right>=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<\Lambda^{r}_{{\sigma}}d_{k}{F},\Lambda^{r}_{{\sigma}}d_{k}{G}\right>\right]}\\\
=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<d_{k}\Lambda^{r}_{{\sigma}}{F},d_{k}\Lambda^{r}_{{\sigma}}{G}\right>\right]}=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<d^{*}_{k}d_{k}\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>\right]}=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<M^{+}_{k}\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>\right]}$

And thus:

$\left<\left(M^{\prime}\right)^{+}_{k}{F},{G}\right>=\frac{k+2}{k+1}\left<M^{+}_{k}{F},{G}\right>-\frac{1}{k+1}\left<{F},{G}\right>\\\
=\frac{k+2}{k+1}\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<M^{+}_{k}\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>\right]}-\frac{1}{k+1}\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>\right]}\\\
=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\frac{k+2}{k+1}\left<M^{+}_{k}\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>-\frac{1}{k+1}\left<\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>\right]}=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<\left(M^{\prime}\right)^{+}_{k}\Lambda^{r}_{{\sigma}}{F},\Lambda^{r}_{{\sigma}}{G}\right>\right]}$

∎

######  Lemma 6.4.

It holds for every vertex ${v}$ and every cochain ${F}\in
C^{0}\left(X;\mathbbm{R}\right)$ that:

$M^{-}_{{v},0}\Lambda^{r}_{{v}}{F}_{0}=\left<\Lambda^{r}_{{v}}{F},\mathbbm{1}\right>_{{v}}=\operatorname{\mathbbm{E}}_{{u}\in
X_{{v}}(0)}{\left[\Lambda^{r}_{{v}}{F}({u})\right]}=\left(M^{\prime}\right)^{+}_{0}{F}({v})$

###### Proof.

$\left(M^{\prime}\right)^{+}_{0}{F}({v})=\left[\left(M^{\prime}\right)^{+}_{0}{F}\right]_{{v}}=\sum_{{u}\in
X(0)}{\left[\left(M^{\prime}\right)^{+}_{0}\right]_{{v},{u}}{F}({u})}=\\\
=\sum_{\begin{subarray}{c}{u}\in X(0)\\\ {u}\cup{v}\in
X(1)\end{subarray}}{\operatorname{w}_{{v}}\left({u}\setminus{v}\right){F}({u})}=\sum_{{u}\in
X_{{v}}(0)}{\operatorname{w}_{{v}}\left({u}\right)\Lambda^{r}_{{v}}{F}({u})}=\operatorname{\mathbbm{E}}_{{u}\in
X_{{v}}(0)}{\left[\Lambda^{r}_{{v}}{F}({u})\right]}$

∎

######  Corollary 6.5 (The advantage).

If $X$’s $1$-skeleton is a $\lambda$-spectral expander it holds for every
vertex ${v}$ and every cochain ${F}\in C^{0}\left(X;\mathbbm{R}\right)$ that:

$\left\|d^{*}_{0}\Lambda^{r}_{{v}}{F}_{0}\right\|=\left\|M^{-}_{0}\Lambda^{r}_{{v}}{F}_{0}\right\|\leq\lambda^{2}\left\|{F}\right\|^{2}$

###### Proof.

Note that the $1$-skeleton of $X$ is a $\lambda$-spectral expander and ${F}\in
C^{0}\left(X;\mathbbm{R}\right)$ therefore
$\left\|\left(M^{\prime}\right)^{+}_{0}{F}\right\|^{2}\leq\lambda^{2}\left\|{F}\right\|^{2}$.
Combining this with Lemma 6.4 yields:

$\left\|M^{-}_{0}\Lambda^{r}_{{v}}{F}_{0}\right\|^{2}=\left\|\left(M^{\prime}\right)^{+}_{0}{F}\right\|^{2}=\left\|\left(M^{\prime}\right)^{+}_{0}{F}_{0}\right\|^{2}\leq\lambda^{2}\left\|{F}_{0}\right\|^{2}$

∎

We can now show how applying Theorem 5.8 to the restriction link viewer yields
Oppenheim’s trickling down theorem [Opp17, Theorem 4.1].

######  Theorem 6.6 (Trickling Down, restated Theorem 1.16).

If it holds that:

  * •

For every vertex ${v}$: $X_{{v}}$ is a $\lambda_{{v},0,k}$ spectral expander.

  * •

$X$ is connected.

Then it holds that
$\lambda_{\emptyset,0,k}=\frac{\lambda_{\emptyset,1,k}}{1-\lambda_{\emptyset,1,k}}$.

###### Proof.

Consider the following:

$\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}+(1-\lambda_{\emptyset,1,k})\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[\left\|M^{-}_{{v},0}\Lambda^{r}_{{v}}{F}_{0}\right\|^{2}\right]}\leq\lambda_{\emptyset,0,k}\left\|{F}_{0}\right\|^{2}$

Using Corollary 6.5 it suffices to find values of $\lambda_{{\sigma},i,j}$
such that:

$\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}+(1-\lambda_{\emptyset,1,k})\lambda_{\emptyset,0,k}^{2}\left\|{F}_{0}\right\|^{2}\leq\lambda_{\emptyset,0,k}\left\|{F}_{0}\right\|^{2}$

Therefore solving the following inequality would bound
$\lambda_{\emptyset,0,k}$:

$\lambda_{\emptyset,1,k}+(1-\lambda_{\emptyset,1,k})\lambda_{\emptyset,0,k}^{2}\leq\lambda_{\emptyset,0,k}$

Note that picking
$\lambda_{\emptyset,0,k}=\frac{\lambda_{\emptyset,1,k}}{1-\lambda_{\emptyset,1,k}}$
satisfies the inequality and thus proves the Theorem. ∎

Before we end this section we would like to give a few words on why this proof
does not yield a decomposition of the $0$-dimensioanl random walk operator
that improves upon the Theorem’s original formulation. Consider how the
$1$-level cochains behave when applying the non-lazy random walk to them: Due
to Lemma 6.4 the following holds for every $1$-level cochain ${F}$:

$\left(M^{\prime}\right)^{+}_{0}{F}({v})=\left<\Lambda^{r}_{{v}}{F},\mathbbm{1}\right>=0$

Where the second equality is due to the very definition of $1$-level cochains.
Therefore, while the decomposition that Theorem 5.8 guarantees does exist, it
is also meaningless as
$\left(M^{\prime}\right)^{+}_{0}{F}=\left(M^{\prime}\right)^{+}_{0}{F}_{0}$.

##  7 Decomposition of the Random Walk Operators

We are now ready to present the random walk decomposition theorem based on
Theorem 5.8. Unlike the tricking down theorem, here the assumption we have is
only on the expansion of the no-lazy up-down random walk on the vertices. We
will, therefore, be interested in a link viewer that decreases the dimension
of the cochain. Namely, the localization link viewer, defined as follows:

######  Definition 7.1 (Localization).

Given a simplicial complex $X$ and a cochain ${F}\in
C^{k}\left(X;\mathbbm{R}\right)$ define the localization link viewer in the
following way:

$\forall{\sigma}\in X:\Lambda^{\ell}_{{\sigma}}{F}={F}_{{\sigma}}$

As with the trickling down theorem, we will be interested in applying Theorem
5.8 to the localization link viewer. We will start by proving that the
localization link viewer is indeed a link viewer that respects the non-lazy
up-down random walk.

######  Lemma 7.2.

The localization link viewer is a link viewer.

###### Proof.

We will prove the properties point by point:

  * •

$\Lambda^{\ell}_{{\sigma}}\left({F}+c\cdot{G}\right)({\tau})=\left({F}+c\cdot{G}\right)({\sigma}\cup{\tau})={F}({\sigma}\cup{\tau})+c\cdot{G}({\sigma}\cup{\tau})=\Lambda^{\ell}_{{\sigma}}{F}({\tau})+c\cdot\Lambda^{\ell}_{{\sigma}}{G}({\tau})$

  * •

$\Lambda^{\ell}_{{\sigma}}\mathbbm{1}({\tau})=\mathbbm{1}({\sigma}\cup{\tau})=1$

  * •

For every cochain ${F}$ it holds that
$\dim\left(\Lambda^{\ell}_{{\sigma}}{F}\right)=\dim({F})-\dim({\sigma})$
therefore for every two cochains ${G},{G}^{\prime}$ and any two
$i$-dimensional faces ${\tau},{\tau}^{\prime}$ it holds that:

$\dim({G})-\dim\left(\Lambda^{\ell}_{{\tau}}{G}\right)=\dim({\tau})=\dim({\tau}^{\prime})=\dim({G}^{\prime})-\dim\left(\Lambda^{\ell}_{{\tau}^{\prime}}{G}^{\prime}\right)$

And $\Delta\left(\Lambda^{\ell}\right)=1$.

  * •

Let ${\tau}\subseteq{\sigma}\in X$ then:

$\Lambda^{\ell}_{{\sigma}\setminus{\tau}}\Lambda^{\ell}_{{\tau}}{F}({\tau}^{\prime})=\Lambda^{\ell}_{{\tau}}{F}\left({\tau}^{\prime}\cup\left({\sigma}\setminus{\tau}\right)\right)={F}\left({\tau}^{\prime}\cup\left({\sigma}\setminus{\tau}\right)\cup{\tau}\right)={F}\left({\tau}^{\prime}\cup{\sigma}\right)=\Lambda^{\ell}_{{\sigma}}{F}({\tau}^{\prime})$

  * •

For every dimension $i$ and $j=\dim\left(\Lambda_{{\sigma}}{F}\right)$ it
holds that:

$\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<\Lambda^{\ell}_{{\sigma}}{F},\Lambda^{\ell}_{{\sigma}}{G}\right>\right]}=\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right)\left<\Lambda^{\ell}_{{\sigma}}{F},\Lambda^{\ell}_{{\sigma}}{G}\right>}=\\\
=\sum_{{\sigma}\in X(i)}{\operatorname{w}\left({\sigma}\right)\sum_{{\tau}\in
X_{{\sigma}}(j)}{\operatorname{w}_{{\sigma}}\left({\tau}\right)\Lambda^{\ell}_{{\sigma}}{F}({\tau})\Lambda^{\ell}_{{\sigma}}{G}({\tau})}}=\\\
=\sum_{{\sigma}\in X(i)}{\sum_{{\tau}\in
X_{{\sigma}}(j)}{\frac{\operatorname{w}\left({\tau}\cup{\sigma}\right)missing}{\binom{i+j+2}{i+1}}\Lambda^{\ell}_{{\sigma}}{F}({\tau})\Lambda^{\ell}_{{\sigma}}{G}({\tau})}}=\\\
=\sum_{{\sigma}\in X(i)}{\sum_{{\tau}\in
X_{{\sigma}}(j)}{\frac{\operatorname{w}\left({\tau}\cup{\sigma}\right)missing}{\binom{i+j+2}{i+1}}{F}({\sigma}\cup{\tau}){G}({\sigma}\cup{\tau})}}=\\\
=\sum_{{\tau}\in
X(i+j+1)}{\operatorname{w}\left({\tau}\right){F}({\tau}){G}({\tau})}=\left<{F},{G}\right>$

∎

######  Lemma 7.3.

The localization link viewer respects the non-lazy random walk operator.

###### Proof.

Note that, by definition, it holds that

$\left(M^{\prime}\right)^{+}_{k}{F}({\sigma})=\frac{1}{k+1}\sum_{\begin{subarray}{c}{\tau}\in
X(k)\\\ {\sigma}\cup{\tau}\in
X(k+1)\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\setminus{\sigma}\right){F}({\tau})}$

The Lemma follows from the following calculation:

$\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[\left<\left(M^{\prime}\right)^{+}_{{\sigma},j-i-1}\Lambda^{\ell}_{{\sigma}}{F},\Lambda^{\ell}_{{\sigma}}{G}\right>\right]}=\\\
=\sum_{{\sigma}\in X(i)}{\operatorname{w}\left({\sigma}\right)\sum_{{\tau}\in
X_{{\sigma}}(j-i-1)}{\operatorname{w}_{{\sigma}}\left({\tau}\right)\left(M^{\prime}\right)^{+}_{{\sigma},j-i-1}\Lambda^{\ell}_{{\sigma}}{F}({\tau})\Lambda^{\ell}_{{\sigma}}{G}({\tau})}}=\\\
=\frac{1}{j-i}\sum_{{\sigma}\in X(i)}{\sum_{{\tau}\in
X_{{\sigma}}(j-i-1)}{\operatorname{w}\left({\sigma}\right)\operatorname{w}_{{\sigma}}\left({\tau}\right)\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X_{{\sigma}}(j-i-1)\\\ {\tau}\cup{\tau}^{\prime}\in
X_{{\sigma}}(j-i)\end{subarray}}{\operatorname{w}_{{\sigma}\cup{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right)\Lambda^{\ell}_{{\sigma}}{F}({\tau}^{\prime})\Lambda^{\ell}_{{\sigma}}{G}({\tau})}}}=\\\
=\frac{1}{j-i}\sum_{{\sigma}\in X(i)}{\sum_{{\tau}\in
X_{{\sigma}}(j-i-1)}{\frac{\operatorname{w}\left({\sigma}\cup{\tau}\right)missing}{\binom{j+1}{i+1}}\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X_{{\sigma}}(j-i-1)\\\ {\tau}\cup{\tau}^{\prime}\in
X_{{\sigma}}(j-i)\end{subarray}}{\operatorname{w}_{{\sigma}\cup{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right)\Lambda^{\ell}_{{\sigma}}{F}({\tau}^{\prime})\Lambda^{\ell}_{{\sigma}}{G}({\tau})}}}=\\\
=\frac{1}{j-i}\frac{1}{\binom{j+1}{i+1}}\sum_{{\sigma}\in
X(i)}{\sum_{{\tau}\in
X_{{\sigma}}(j-i-1)}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X_{{\sigma}}(j-i-1)\\\ {\tau}\cup{\tau}^{\prime}\in
X_{{\sigma}}(j-i)\end{subarray}}{\operatorname{w}\left({\sigma}\cup{\tau}\right)\operatorname{w}_{{\sigma}\cup{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right)\Lambda^{\ell}_{{\sigma}}{F}({\tau}^{\prime})\Lambda^{\ell}_{{\sigma}}{G}({\tau})}}}=\\\
=\frac{1}{j-i}\frac{1}{\binom{j+1}{i+1}}\sum_{{\sigma}\in
X(i)}{\sum_{{\tau}\in
X_{{\sigma}}(j-i-1)}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X_{{\sigma}}(j-i-1)\\\ {\tau}\cup{\tau}^{\prime}\in
X_{{\sigma}}(j-i)\end{subarray}}{\operatorname{w}\left({\sigma}\cup{\tau}\right)\operatorname{w}_{{\sigma}\cup{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right){F}({\sigma}\cup{\tau}^{\prime}){G}({\sigma}\cup{\tau})}}}=\\\
=\frac{1}{j-i}\frac{1}{\binom{j+1}{i+1}}\sum_{{\sigma}\in
X(i)}{\sum_{\begin{subarray}{c}{\tau}\in X(j)\\\
{\sigma}\subseteq{\tau}\end{subarray}}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X(j)\\\ {\tau}\cup{\tau}^{\prime}\in X_{{\sigma}}(j+1)\\\
{\sigma}\subseteq{\tau}^{\prime}\end{subarray}}{\operatorname{w}\left({\tau}\right)\operatorname{w}_{{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right){F}({\tau}^{\prime}){G}({\tau})}}}\underset{(*)}{=}\\\
\underset{(*)}{=}\frac{1}{j+1}\frac{1}{\binom{j}{i+1}}\sum_{{\sigma}\in
X(i)}{\sum_{\begin{subarray}{c}{\tau}\in X(j)\\\
{\sigma}\subseteq{\tau}\end{subarray}}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X(j)\\\ {\tau}\cup{\tau}^{\prime}\in X_{{\sigma}}(j+1)\\\
{\sigma}\subseteq{\tau}^{\prime}\end{subarray}}{\operatorname{w}\left({\tau}\right)\operatorname{w}_{{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right){F}({\tau}^{\prime}){G}({\tau})}}}=\\\
=\frac{1}{j+1}\frac{1}{\binom{j}{i+1}}\sum_{{\tau}\in
X(j)}{\sum_{\begin{subarray}{c}{\tau}^{\prime}\in X(j)\\\ \
{\tau}\cup{\tau}^{\prime}\in
X(j+1)\end{subarray}}{\sum_{\begin{subarray}{c}{\sigma}\in X(i)\\\
{\sigma}\subseteq{\tau}\cap{\tau}^{\prime}\end{subarray}}{\operatorname{w}\left({\tau}\right)\operatorname{w}_{{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right){F}({\tau}^{\prime}){G}({\tau})}}}=\\\
=\frac{1}{j+1}\sum_{{\tau}\in
X(j)}{\operatorname{w}\left({\tau}\right){G}({\tau})\sum_{\begin{subarray}{c}{\tau}^{\prime}\in
X(j)\\\ \ {\tau}\cup{\tau}^{\prime}\in
X(j+1)\end{subarray}}{\operatorname{w}_{{\tau}}\left({\tau}^{\prime}\setminus{\tau}\right){F}({\tau}^{\prime})}}=\\\
=\frac{1}{j+1}\sum_{{\tau}\in
X(j)}{\operatorname{w}\left({\tau}\right){G}({\tau})\left(M^{\prime}\right)^{+}_{{\sigma},j}{F}({\tau})}=\left<\left(M^{\prime}\right)^{+}_{{\sigma},j-i-1}{F},{G}\right>$

Where $(*)$ follows from:

$\frac{1}{j-i}\frac{1}{\binom{j+1}{j-i}}=\frac{1}{j-i}\frac{(j-i)!(i+1)!}{(j+1)!}=\frac{1}{j+1}\frac{(j-(i+1))!(i+1)!}{j!}=\frac{1}{j+1}\frac{1}{\binom{j}{i+1}}$

∎

###  7.1 Gaining the Advantage

Before we present the exact Lemma we use as the advantage step we should
expand our understanding of $\Lambda^{\ell}$’s level functions. We will begin
by characterising the space of cochains that are orthogonal to the eigenspace
of $1$ (i.e. the constants).

######  Lemma 7.4.

Let $X$ be a pure $d$-dimensional simplicial complex and let ${F}\in
C^{k}\left({F};\mathbbm{R}\right)$ be a cochain. Then:

$\left<{F},\mathbbm{1}\right>=0\Leftrightarrow{F}\in\ker{\left(d^{*}_{-1}\cdots
d^{*}_{k-1}\right)}$

###### Proof.

Note that, due to Lemma 2.5 it holds that:

$\left<{F},\mathbbm{1}\right>=\operatorname{\mathbbm{E}}_{{\sigma}\in
X(k)}{\left[{F}({\sigma})\right]}=d^{*}_{-1}\cdots d^{*}_{k-1}(\emptyset)$

Which proves the lemma. ∎

Now that we understand the constant part of a cochain we are ready to move on
to understanding cochains of a higher level.

######  Lemma 7.5.

Let $X$ be a pure $d$-dimensional simplicial complex, $i$ be a dimension and
${F}\in C^{k}\left(X;\mathbbm{R}\right)$ be a cochain. Then:

$\forall{\sigma}\in
X(i):\left<\Lambda^{\ell}_{{\sigma}}{F},\mathbbm{1}\right>_{{\sigma}}=0\Leftrightarrow{F}\in\ker{\left(d^{*}_{i}\cdots
d^{*}_{k-1}\right)}$

###### Proof.

Using Lemma 2.5 we prove that:

$\displaystyle\forall{\sigma}\in
X(i):\left<\Lambda^{\ell}_{{\sigma}}{F},\mathbbm{1}\right>_{{\sigma}}$
$\displaystyle=\sum_{{\tau}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({\tau}\right)\Lambda^{\ell}_{{\sigma}}{F}({\tau})}=d^{*}_{{\sigma},i-1}\cdots
d^{*}_{{\sigma},k-2}{F}_{{\sigma}}(\emptyset)=\left(d^{*}_{i}\cdots
d^{*}_{k-1}{F}\right)_{{\sigma}}(\emptyset)$ $\displaystyle=d^{*}_{i}\cdots
d^{*}_{k-1}{F}({\sigma})$

Which proves the Lemma. ∎

######  Corollary 7.6.

It holds that ${F}$ is a proper $k$-dimensional $i$-level cochain iff
${F}\in\operatorname*{Im}{\left(d_{k-1}\cdots
d_{i}\right)}\cap\ker{\left(d^{*}_{i-1}\cdots d^{*}_{k-1}\right)}$.

###### Proof.

The Corollary holds due the definition of $i$-level cochains and Lemma 7.5. ∎

Note that cochains that pure $i$-level cochains can be thought of as
originating in the $i$-dimensional faces. For example, for every pure
$0$-level cochain there is a $0$-dimensional cochain ${G}$ such that
${F}=d\cdots d{G}$. We also note that any cochain that is not originated in
the vertices can be distributed along the links in the sense that they remain
orthogonal to the constants when applying the localization link viewer. We
will therefore be interested in the cochains that originated in the vertices
(as these are exactly the cochains which the local perspective seems to miss).
Consider the following:

######  Lemma 7.7.

Let ${F}$ be a $k$-dimensional proper $0$-level cochain then there exists
${F}^{=0}\in C^{0}\left(X;\mathbbm{R}\right)$ such that:

  1. 1.

$d^{*}_{-1}{F}^{=0}=0$

  2. 2.

$\left\|{F}\right\|^{2}=\left\|{F}^{=0}\right\|^{2}$

  3. 3.

$\left\|d^{*}_{0}\cdots d^{*}_{k-1}{F}\right\|^{2}=\left\|d_{k-1}\cdots
d_{0}{F}^{=0}\right\|^{2}$

###### Proof.

${F}\in\operatorname*{Im}{\left(d_{k-1}\cdots d_{0}\right)}$ therefore let
${G}\in C^{0}\left(X;\mathbbm{R}\right)$ such that ${F}=d_{k-1}\cdots
d_{0}{G}$. Note that $M^{+{k}}_{0}$ is a self adjoint positive semidefinate
operator and thus its square root can be defined. $\sqrt{M^{+{k}}_{0}}$ is
defined as the operator whose eigenvectors are the same as $M^{+{k}}_{0}$ and
whose eigenvalue are the positive square root of the eigenvalues of
$M^{+{k}}_{0}$. Note that $\sqrt{M^{+{k}}_{0}}$ is also self adjoint. We will
now show that ${F}^{=0}=\sqrt{M^{+{k}}_{0}}{G}$ satisfies all of the
conditions of the lemma.

  1. 1.

Note that this condition is equivalent to showing that
$\left<{F}^{=0},\mathbbm{1}\right>=0$. Also note that $\mathbbm{1}$ is an
eigenvector of $\sqrt{M^{+{k}}_{0}}$ with eigenvalue $1$. It is therefore not
hard to see that:

$\left<{F}^{=0},\mathbbm{1}\right>=\left<\sqrt{M^{+{k}}_{0}}{G},\sqrt{M^{+{k}}_{0}}\mathbbm{1}\right>=\left<M^{+{k}}_{0}{G},\mathbbm{1}\right>=\\\
=\left<d_{k-1}\cdots d_{0}{G},d^{*}_{0}\cdots
d^{*}_{k-1}\mathbbm{1}\right>=\left<{F},\mathbbm{1}\right>=0$

  2. 2.

Consider the following:

$\left\|{F}^{=0}\right\|^{2}=\left<{F}^{=0},{F}^{=0}\right>=\left<\sqrt{M^{+{k}}_{0}}{G},\sqrt{M^{+{k}}_{0}}{G}\right>=\left<M^{+{k}}_{0}{G},{G}\right>=\\\
=\left<d_{k-1}\cdots d_{0}{G},d_{k-1}\cdots
d_{0}{G}\right>=\left<{F},{F}\right>=\left\|{F}\right\|^{2}$

  3. 3.

To conclude, note that:

$\displaystyle\left\|d^{*}_{0}\cdots d^{*}_{k-1}{F}\right\|^{2}$
$\displaystyle=\left<d^{*}_{0}\cdots d^{*}_{k-1}{F},d^{*}_{0}\cdots
d^{*}_{k-1}{F}\right>$ $\displaystyle=\left<d^{*}_{0}\cdots
d^{*}_{k-1}d_{k-1}\cdots d_{0}{G},d^{*}_{0}\cdots d^{*}_{k-1}d_{k-1}\cdots
d_{0}{G}\right>$ $\displaystyle=\left<M^{+{k}}_{0}{G},M^{+{k}}_{0}{G}\right>$
$\displaystyle=\left<\sqrt{M^{+{k}}_{0}}\sqrt{M^{+{k}}_{0}}{G},\sqrt{M^{+{k}}_{0}}\sqrt{M^{+{k}}_{0}}{G}\right>$
$\displaystyle=\left<\sqrt{M^{+{k}}_{0}}{F}^{=0},\sqrt{M^{+{k}}_{0}}{F}^{=0}\right>$
$\displaystyle=\left<M^{+{k}}_{0}{F}^{=0},{F}^{=0}\right>$
$\displaystyle=\left<d_{k-1}\cdots d_{0}{F}^{=0},d_{k-1}\cdots
d_{0}{F}^{=0}\right>$ $\displaystyle=\left\|d_{k-1}\cdots
d_{0}{F}^{=0}\right\|^{2}$

∎

We are now ready to present the advantage we use:

######  Lemma 7.8 (The advantage).

Let $X$ be a $d$ dimensional simplicial complex whose $1$-skeleton is a
$\gamma$ spectral expander. Also let ${F}\in
C_{\Lambda^{\ell},0}^{k}\left(X;\mathbbm{R}\right)$ then:

$\left\|d^{*}_{0}\cdots
d^{*}_{k-1}{F}\right\|^{2}\leq\left(1-\frac{k}{k+1}\left(1-\gamma\right)\right)\left\|{F}\right\|^{2}$

###### Proof.

Let ${F}_{0}$ be the projection of ${F}$ into
$C_{\Lambda^{\ell},0}^{k}\left(X;\mathbbm{R}\right)\cap\left(C_{\Lambda^{\ell},1}^{k}\left(X;\mathbbm{R}\right)\right)^{\bot}$.
Due to Lemma 7.5 it holds that for every dimension $i$ that
$C_{\Lambda^{\ell},i}^{k}\left(X;\mathbbm{R}\right)=\ker{\left(d^{*}_{i-1}\cdots
d^{*}_{k-1}\right)}$ and therefore
${F}_{0}\in\operatorname*{Im}{\left(d_{k-1}\cdots
d_{0}\right)}\cap\ker{\left(d^{*}_{-1}\cdots d^{*}_{k-1}\right)}$. We can
therefore use Lemma 7.7 to find ${F}^{=0}$ such that:

  1. 1.

$d^{*}_{-1}{F}^{=0}=0$

  2. 2.

$\left\|{F}_{0}\right\|^{2}=\left\|{F}^{=0}\right\|^{2}$

  3. 3.

$\left\|d^{*}_{0}\cdots d^{*}_{k-1}{F}_{0}\right\|^{2}=\left\|d_{k-1}\cdots
d_{0}{F}^{=0}\right\|^{2}$

Due to Lemma 4.3 it holds that:

$M^{+{k}}_{0}=\frac{k}{k+1}\left(M^{\prime}\right)^{+}_{0}+\frac{1}{k+1}I$

And therefore:

$\displaystyle\left\|d_{k-1}\cdots d_{0}{F}^{=0}\right\|^{2}$
$\displaystyle=\left<d_{k-1}\cdots d_{0}{F}^{=0},d_{k-1}\cdots
d_{0}{F}^{=0}\right>=\left<M^{+{k}}_{0}{F}^{=0},{F}^{=0}\right>=$
$\displaystyle=\left<\left(\frac{k}{k+1}\left(M^{\prime}\right)^{+}_{0}-\frac{1}{k+1}I\right){F}^{=0},{F}^{=0}\right>=$
$\displaystyle=\frac{k}{k+1}\left<\left(M^{\prime}\right)^{+}_{0}{F}^{=0},{F}^{=0}\right>+\frac{1}{k+1}\left<{F}^{=0},{F}^{=0}\right>\leq$
$\displaystyle\leq\left(\frac{k}{k+1}\gamma+\frac{1}{k+1}\right)\left\|{F}^{=0}\right\|^{2}=$
$\displaystyle=\left(\frac{k}{k+1}\gamma-\frac{k}{k+1}+1\right)\left\|{F}^{=0}\right\|^{2}=$
$\displaystyle=\left(1-\frac{k}{k+1}\left(1-\gamma\right)\right)\left\|{F}^{=0}\right\|^{2}=\left(1-\frac{k}{k+1}\left(1-\gamma\right)\right)\left\|{F}_{0}\right\|^{2}$

And thus:

$\left\|d^{*}_{0}\cdots d^{*}_{k-1}{F}\right\|^{2}=\left\|d_{k-1}\cdots
d_{0}{F}_{0}\right\|^{2}\leq\left(1-\frac{k}{k+1}\left(1-\gamma\right)\right)\left\|{F}_{0}\right\|^{2}\leq\left(1-\frac{k}{k+1}\left(1-\gamma\right)\right)\left\|{F}\right\|^{2}$

∎

###  7.2 Decomposing the Random Walk Operators

Now that we have developed the tools we need, we can move on to strengthening
the result of Alev and Lau [AL20] by showing a decomposition of the random
walk operators. We will do so by applying Theorem 5.8 to the localization link
viewer:

######  Theorem 7.9 (Random walk decomposition).

Let $X$ be a $d$-dimensional pure simplicial complex. Also, assume that for
every face ${\sigma}$ of dimension smaller than $d-2$ it holds that
$\lambda_{2}\left(\left(M^{\prime}\right)^{+}_{{\sigma},0}\right)\leq\lambda_{{\sigma}}$.
Denote by $\gamma_{{\tau},i}=\max_{{\sigma}\in
X_{{\tau}}(i)}{\left(\lambda_{{\sigma}}\right)}$. For every set of proper
level cochains ${F}_{i}\in
C_{\Lambda^{\ell},\hat{i}}^{k}\left(X;\mathbbm{R}\right)$ it holds that:

$\left<\left(M^{\prime}\right)^{+}_{k}\sum_{i=0}^{k}{{F}_{i}},\sum_{i=0}^{k}{{F}_{i}}\right>\leq\sum_{i=0}^{k}{\left(1-\frac{1}{k-i+1}\prod_{j=i-1}^{k-1}{(1-\gamma_{j})}\right)\left\|{F}_{i}\right\|^{2}}$

###### Proof.

We will prove this theorem by applying Theorem 5.8 to the $k$-dimensional non-
lazy random walk operator. We start by noting that the space of
$k$-dimensional cochains that are orthogonal to the constants is comprised of
exactly $k$ level functions as the space orthogonal to the constants is
exactly $\ker\left(d^{*}_{0}\cdots d^{*}_{k}\right)$.

We prove the rest of this theorem using a recursive argument. First note that
for $k=0$ the claim holds trivially as:

$\left<\left(M^{\prime}\right)^{+}_{0}{F},{F}\right>\leq\lambda_{{\sigma}}\left\|{F}\right\|^{2}=\gamma_{-1}\left\|{F}\right\|^{2}$

Assume that for every non-empty face ${\sigma}$ it holds that:

$\lambda_{{\sigma},i,k}\leq
1-\frac{1}{k-i+1}\prod_{j=i-1}^{k-1}{(1-\gamma_{{\sigma},j})}$

Note that for every $i\geq 1$:

$\lambda_{\emptyset,i,k}=\max_{{v}\in
X(0)}{\left\\{\lambda_{{v},i-1,k-1}\right\\}}\leq\max_{{v}\in
X(0)}{\left\\{1-\frac{1}{k-i+1}\prod_{j=i-2}^{k-2}{(1-\gamma_{{\sigma},j})}\right\\}}\leq
1-\frac{1}{k-i+1}\prod_{j=i-1}^{k-1}{(1-\gamma_{\emptyset,j})}$

Consider the left hand side of the recursive formula:

$\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}+\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[(1-\lambda_{\emptyset,1,k})\left\|M^{-{(k-1)}}_{(k-1)}\Lambda^{\ell}_{{v}}{F}_{0}\right\|^{2}\right]}\leq\lambda_{\emptyset,0,k}\left\|{F}_{0}\right\|$
(2)

And note that:

$\displaystyle\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}+\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[(1-\lambda_{\emptyset,1,k})\left\|M^{-{(k-1)}}_{(k-1)}\Lambda^{\ell}_{{v}}{F}_{0}\right\|^{2}\right]}$
$\displaystyle\qquad\qquad=\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}+\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[(1-\lambda_{\emptyset,1,k})\left\|d^{*}_{-1}\cdots
d^{*}_{k-2}\Lambda^{\ell}_{{v}}{F}_{0}\right\|^{2}\right]}$
$\displaystyle\qquad\qquad=\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}+\operatorname{\mathbbm{E}}_{{v}\in
X(0)}{\left[(1-\lambda_{\emptyset,1,k})\left\|\Lambda^{\ell}_{{v}}d^{*}_{0}\cdots
d^{*}_{k-1}{F}_{0}\right\|^{2}\right]}$
$\displaystyle\qquad\qquad=\lambda_{\emptyset,1,k}\left\|{F}_{0}\right\|^{2}+(1-\lambda_{\emptyset,1,k})\left\|d^{*}_{0}\cdots
d^{*}_{k-1}{F}_{0}\right\|^{2}$

Consider, again, the left hand side of inequality 2 and note that due to Lemma
7.8 it suffices to solve the following:

$\displaystyle\lambda_{\emptyset,1,k}\left\|{F}^{=0}\right\|^{2}+(1-\lambda_{\emptyset,1,k})\left(1-\frac{k}{k+1}\left(1-\gamma_{-1}\right)\right)\left\|{F}^{=0}\right\|^{2}$
$\displaystyle\leq\lambda_{\emptyset,0,k}\left\|{F}^{=0}\right\|^{2}$
$\displaystyle\lambda_{\emptyset,1,k}+(1-\lambda_{\emptyset,1,k})\left(1-\frac{k}{k+1}\left(1-\gamma_{-1}\right)\right)$
$\displaystyle\leq\lambda_{\emptyset,0,k}$
$\displaystyle\frac{k}{k+1}\left(1-\gamma_{-1}\right)\lambda_{\emptyset,1,k}+\left(1-\frac{k}{k+1}\left(1-\gamma_{-1}\right)\right)$
$\displaystyle\leq\lambda_{\emptyset,0,k}$

Consider the following:

$\frac{k}{k+1}\left(1-\gamma_{-1}\right)\lambda_{\emptyset,1,k}+\left(1-\frac{k}{k+1}\left(1-\gamma_{-1}\right)\right)\leq\\\
\leq\frac{k}{k+1}\left(1-\gamma_{-1}\right)\left(1-\frac{1}{k}\prod_{j=0}^{k-1}{(1-\gamma_{\emptyset,j})}\right)+1-\frac{k}{k+1}\left(1-\gamma_{-1}\right)=\\\
=\frac{k}{k+1}\left(1-\gamma_{-1}\right)-\frac{1}{k+1}\prod_{j=-1}^{k-1}{(1-\gamma_{\emptyset,j})}+1-\frac{k}{k+1}\left(1-\gamma_{-1}\right)=\\\
=1-\frac{1}{k+1}\prod_{j=-1}^{k-1}{(1-\gamma_{\emptyset,j})}$

Thus if we set:

$\lambda_{\emptyset,0,k}=1-\frac{1}{k+1}\prod_{j=-1}^{k-1}{(1-\gamma_{\emptyset,j})}$

We get that for every face ${\sigma}$ and dimensions $i,k$:

$\lambda_{{\sigma},i,k}\leq
1-\frac{1}{k-i+1}\prod_{j=i-1}^{k-1}{(1-\gamma_{{\sigma},j})}$

Applying Theorem 5.8 proves the decomposition. ∎

Note that the decomposition presented in Theorem 7.9 is the first
decomposition theorem to offer a proper (i.e. not approximate) decomposition
of the $k$-dimensional random walk whose components are orthogonal to each
other.

###  7.3 Examples of Cochains of a High Level

In this section we will show two examples of cochains of dimension $k$ are
$k$-level cochains. Specifically we will show two examples of structures that
have this property - the first is minimal cochains and the second is perfectly
balanced cochains.

####  7.3.1 Minimal Cochains

Minimal cochains appear naturally in a topological definition of expansion and
were widely studied over $\mathbbm{F}_{2}$ (as most usages of topological
expanders are of topological expanders over $\mathbbm{F}_{2}$). We will
present a definition of an analogue of these cochains over the real numbers
and show that minimal $k$-cochains over $\mathbbm{R}$ are of level $k$.

We begin by noting that the topological definition of expansion uses
_oriented_ complexes and thus we have to modify our definition of a cochain to
match an oriented complex:

######  Definition 7.10 (Oriented complex).

We define of an oriented simplicial complex $X$ as a simplicial complex that
has an underlying orientation on the vertices. We also define the set
$X_{ord}$ to be the set of all possible orientations of the faces of $X$.

######  Definition 7.11 (Cochain over oriented complex).

A cochain ${F}\in C^{i}\left(X_{ord};\mathbbm{R}\right)$ is a function
${F}:X_{ord}\rightarrow\mathbbm{R}$ such that for every permutation $\rho$ and
every face ${\sigma}\in X_{ord}$ it holds that:

${F}({\sigma}_{\rho(0)},\cdots,{\sigma}_{\rho(i)})=\operatorname*{sign}(\rho){F}({\sigma}_{0},\cdots,{\sigma}_{i})$

For the rest of this section we will assume that the complex has some
underlying orientation and that faces are given in that underlying
distribution. For that reason, unless otherwise stated, we will ignore the
orientation of the complex.

Another key definition in topological notions of high dimensional expanders is
the coboundary operator. In the $0$th dimension over $\mathbbm{F}_{2}$ the
coboundary operator can be thought of as marking all the edges that leave a
set of vertices.

######  Definition 7.12 (Coboundary operator).

Define the coboundary operator
$\delta_{i}:C^{i}\left(X_{ord};\mathbbm{R}\right)\rightarrow
C^{i+1}\left(X_{ord};\mathbbm{R}\right)$ to be:

$\delta_{i}{F}({\sigma}_{0},\cdots,{\sigma}_{i+1})=\sum_{j=0}^{i+1}{(-1)^{j}{F}({\sigma}_{0},\cdots,{\sigma}_{j-1},{\sigma}_{j+1},\cdots,{\sigma}_{i+1})}$

Note that the dimension of the coboundary operator is always clear from
context and thus we will often denote the coboundary operator simply by
$\delta$.

######  Definition 7.13 (Coboundary).

We define the set of coboundaries to be:

$B^{i}\left(X;\mathbbm{R}\right)=\operatorname{Im}(\delta_{i-1})$

We are now ready to define a minimal cochain - a family of cochains that are
all $k$-level cochains. Note that these are one of the central objects of
study when discussing topological definitions of high dimensioanl expanders
(specifically, the expansion of minimal cochains under applications of the
coboundary operator is the very definition of that notion of
expansion888Specifically, this holds true for a notion called coboundary
expansion. There are other notions of topological expansion such as cosystolic
expansion in which minimality is taken with regards to a larger family of
cochains called “the cocycles”.). For a more in-depth discussion of the
topological notions of expansion and their relation to minimal cochains see,
for example [KKL14, EK16, KM21, KM22, KO22].

######  Definition 7.14 (Minimal cochain).

A cochain ${F}\in C^{i}\left(X;\mathbbm{R}\right)$ is minimal if:

${F}=\operatorname*{arg\,min}_{{G}\in
B^{i}\left(X;\mathbbm{R}\right)}{\left\|{F}+{G}\right\|}$

In order to show that that every minimal cochain is indeed a $k$-level cochain
we will first consider a weaker notion of minimality called local-minimality.

######  Definition 7.15 (Locally minimal cochain).

A cochain ${F}\in C^{i}\left(X;\mathbbm{R}\right)$ is
$\Lambda^{\ell}$-$i$-locally minimal if for every ${\sigma}\in X(i)$ it holds
that $\Lambda^{\ell}_{{\sigma}}{F}$ is minimal.

We will show that every $k$-cochain that is $(k-1)$-locally minimal is also a
$k$-level cochain. We will then follow this by showing that any minimal
cochain is $(k-1)$-locally minimal and thus prove the claim.

######  Lemma 7.16.

Let $X$ be a simplicial complex and let ${F}\in
C^{i}\left(X;\mathbbm{R}\right)$ be a cochain. It holds that
$\left\|{F}-a\right\|^{2}<\left\|{F}\right\|^{2}$ if one of the following
conditions hold:

  * •

$a\leq 0$ and $a>2\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[{F}({\sigma})\right]}$.

  * •

$a\geq 0$ and $a<2\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[{F}({\sigma})\right]}$

###### Proof.

Note that the following hold:

$\left\|{F}-a\right\|^{2}<\left\|{F}\right\|^{2}\Leftrightarrow\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right)\left({F}({\sigma})-a\right)^{2}}<\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})^{2}}\Leftrightarrow\\\
\Leftrightarrow\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})^{2}}-2a\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})}+a^{2}<\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})^{2}}\Leftrightarrow\\\
\Leftrightarrow a^{2}<2a\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})}$

If $a\geq 0$ then:

$a^{2}<2a\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})}\Leftrightarrow
a<2\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})}$

In addition, if $a\leq 0$ then:

$a^{2}<2a\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})}\Leftrightarrow
a>2\sum_{{\sigma}\in
X(i)}{\operatorname{w}\left({\sigma}\right){F}({\sigma})}$

∎

######  Corollary 7.17.

Let ${F}\in C^{0}\left(X;\mathbbm{R}\right)$ be a cochain. If ${F}$ is minimal
then $\operatorname{\mathbbm{E}}_{{\sigma}\in
X(0)}{\left[{F}({\sigma})\right]}=0$.

###### Proof.

Note that the $0$-dimensioanl coboundaries are the constant functions and thus
if $\operatorname{\mathbbm{E}}_{{\sigma}\in
X(0)}{\left[{F}({\sigma})\right]}\neq 0$ then note that
$a=\operatorname{\mathbbm{E}}_{{\sigma}\in X(0)}{\left[{F}({\sigma})\right]}$
satisfies the conditions of Lemma 7.16 and thus contradict the minimality of
${F}$. ∎

######  Corollary 7.18.

$(k-1)$-locally minimal cochains are $k$-level cochains.

###### Proof.

Let ${F}$ be a $(k-1)$-locally minimal cochain and let ${\sigma}\in X(k-1)$.
Due to the local minimality of ${F}$ it holds that
$\Lambda^{\ell}_{{\sigma}}{F}$ is minimal in $X_{{\sigma}}$ i.e. for every
${G}\in B^{0}\left(X_{{\sigma}};\mathbbm{R}\right)$ it holds that
$\left\|{F}\right\|\leq\left\|{F}+{G}\right\|$. Note that the $0$-coboundaries
of $X_{{\sigma}}$ over $\mathbbm{R}$ are the constant functions and therefore,
due to Lemma 7.16, it holds that $\operatorname{\mathbbm{E}}_{{\sigma}\in
X(i)}{\left[{F}({\sigma})\right]}=0$ (as if it is not one can pick a
coboundary that minimizes the norm of $\Lambda^{\ell}_{{\sigma}}{F}$). ∎

######  Lemma 7.19.

Minimal cochains are $(k-1)$-locally minimal.

###### Proof.

Let ${F}\in C^{k}\left(X;\mathbbm{R}\right)$ be a minimal cochain. Suppose
that it is not $(k-1)$-locally minimal, therefore there exists a face
${\sigma}\in X(k-1)$ such that $\Lambda^{\ell}_{{\sigma}}{F}$ is not minimal.
Note that $\Lambda^{\ell}_{{\sigma}}{F}\in
C^{0}\left(X_{{\sigma}};\mathbbm{R}\right)$ and therefore, due to the non-
minimality of $\Lambda^{\ell}_{{\sigma}}{F}$ in $X_{{\sigma}}$, there exists
$a\in\mathbbm{R}$ such that
$\left\|{F}-a\right\|^{2}_{{\sigma}}<\left\|{F}\right\|^{2}_{{\sigma}}$ (as
$0$-coboundaries over $\mathbbm{R}$ are the constant functions). Consider the
following $(k-1)$-cochain:

${G}({\tau})=\begin{cases}a&{\tau}={\sigma}\\\ 0&\text{Otherwise}\end{cases}$

The following holds:

$\displaystyle\left\|{F}-\delta{G}\right\|^{2}$ $\displaystyle=\sum_{{\tau}\in
X(k)}{\operatorname{w}\left({\tau}\right)\left({F}({\tau})-\delta{G}({\tau})\right)^{2}}=$
$\displaystyle=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right)\left({F}({\tau})-\delta{G}({\tau})\right)^{2}}+\sum_{\begin{subarray}{c}{\tau}\in
X(k)\\\
{\sigma}\subseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right)\left({F}({\tau})-\delta{G}({\tau})\right)^{2}}=$
$\displaystyle=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right)\left({F}({\tau})-0\right)^{2}}+\sum_{{v}\in
X_{{\sigma}}(0)}{\operatorname{w}\left({\tau}\right)\left({F}({v}{\sigma})-\delta{G}({v}{\sigma})\right)^{2}}=$
$\displaystyle=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right){F}({\tau})}^{2}+\sum_{{v}\in
X_{{\sigma}}(0)}{\operatorname{w}\left({v}{\sigma}\right)\left({F}({v}{\sigma})-a\right)^{2}}=$
$\displaystyle=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right){F}({\tau})^{2}}+\binom{k+1}{k}\operatorname{w}\left({\sigma}\right)\sum_{{v}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({v}\right)\left({F}({v}{\sigma})-a\right)^{2}}=$
$\displaystyle=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right){F}({\tau})^{2}}+\binom{k+1}{k}\operatorname{w}\left({\sigma}\right)\left\|{F}-a\right\|^{2}_{{\sigma}}<$
$\displaystyle<\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right){F}({\tau})^{2}}+\binom{k+1}{k}\operatorname{w}\left({\sigma}\right)\left\|{F}\right\|^{2}_{{\sigma}}=$
$\displaystyle=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right){F}({\tau})^{2}}+\binom{k+1}{k}\operatorname{w}\left({\sigma}\right)\sum_{{v}\in
X_{{\sigma}}(0)}{\operatorname{w}_{{\sigma}}\left({v}\right)\left({F}({v}{\sigma})\right)^{2}}=$
$\displaystyle=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\nsubseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right){F}({\tau})^{2}}+\sum_{\begin{subarray}{c}{\tau}\in
X(k)\\\
{\sigma}\subseteq{\tau}\end{subarray}}{\operatorname{w}\left({\tau}\right){F}({\tau})^{2}}=\sum_{{\tau}\in
X(k)}{\operatorname{w}\left({\tau}\right){F}({\tau})^{2}}=\left\|{F}\right\|^{2}$

Which contradicts the minimality of ${F}$. ∎

######  Corollary 7.20.

Minimal $k$-cochains are $k$-levels cochains.

###### Proof.

This follows directly from Corollary 7.18 and Lemma 7.19. ∎

####  7.3.2 Perfectly Balanced Cochains

We will now show a different family of cochains that are $k$-level cochains.
Specifically we define the notion of perfectly balanced cochains. This will be
a purely combinatorial definition and we will show that cochains that satisfy
this combinatorial definition are $k$-level cochains (up to an additive
constant).

######  Definition 7.21 (Perfectly balanced set of faces).

A set of faces $S\subseteq X(k)$ is perfectly balanced over links of dimension
$i$ if:

$\forall{\sigma}\in X(i):\sum_{{\tau}\in
S}{\operatorname{w}\left({\tau}\right)}=\sum_{\begin{subarray}{c}{\tau}\in
S\\\
{\sigma}\subseteq{\tau}\end{subarray}}{\operatorname{w}_{{\sigma}}\left({\tau}\setminus{\sigma}\right)}$

######  Definition 7.22 (Perfectly balanced cochain).

A cochain ${F}\in C^{k}\left(X;\mathbbm{R}\right)$ is perfectly balanced over
faces of dimension $i$ if there exists a perfectly balanced set of faces
$S\subseteq X(k)$ that is perfectly balanced over faces of dimension $i$ such
that:

${F}({\sigma})=\begin{cases}1&{\sigma}\in S\\\ 0&{\sigma}\notin S\end{cases}$

######  Lemma 7.23.

Let ${F}\in C^{k}\left(X;\mathbbm{R}\right)$ be perfectly balanced over faces
of dimension $i$ then ${F}-\operatorname{\mathbbm{E}}{\left[{F}\right]}$ is an
$i$-level cochain.

###### Proof.

The Lemma follows directly from the definition:

$\forall{\sigma}\in X(i):\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(k-i-1)}{\left[\Lambda^{\ell}_{{\sigma}}\left({F}-\operatorname{\mathbbm{E}}{\left[{F}\right]}\right)({\tau})\right]}=\\\
=\operatorname{\mathbbm{E}}_{{\tau}\in
X_{{\sigma}}(k-i-1)}{\left[\Lambda^{\ell}_{{\sigma}}{F}({\tau})-\operatorname{\mathbbm{E}}{\left[{F}\right]}\right]}=\operatorname{\mathbbm{E}}_{{\tau}\in
X(k)}{\left[{F}({\tau})\right]}-\operatorname{\mathbbm{E}}{\left[{F}\right]}=0$

∎

## References

  * [AJK+22] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Entropic independence: optimal mixing of down-up random walks.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1418–1430, 2022.
  * [AL20] Vedat Levi Alev and Lap Chi Lau.  Improved analysis of higher order random walks and applications.  CoRR, abs/2001.02827, 2020.
  * [ALG20] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1319–1330. IEEE, 2020.
  * [ALGV18] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials ii: High-dimensional walks and an fpras for counting bases of a matroid, 2018.
  * [BHKL20] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett.  High dimensional expanders: Eigenstripping, pseudorandomness, and unique games, 2020.
  * [BHKL21] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett.  Hypercontractivity on high dimensional expanders: a local-to-global approach for higher moments, 2021.
  * [CLV21] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537–1550, 2021.
  * [DDFH18] Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha.  Boolean function analysis on high-dimensional expanders.  In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, volume 116 of LIPIcs, pages 38:1–38:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [DHK+19] Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma.  List decoding with double samplers.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2134–2153. SIAM, 2019.
  * [DK17] Irit Dinur and Tali Kaufman.  High dimensional expanders imply agreement expanders.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 974–985. IEEE Computer Society, 2017.
  * [EK16] Shai Evra and Tali Kaufman.  Bounded degree cosystolic expanders of every dimension.  In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 36–48. ACM, 2016.
  * [GLL22] Tom Gur, Noam Lifshitz, and Siqi Liu.  Hypercontractivity on high dimensional expanders.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 176–184. ACM, 2022.
  * [KKL14] Tali Kaufman, David Kazhdan, and Alexander Lubotzky.  Ramanujan complexes and bounded degree topological expanders.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 484–493. IEEE Computer Society, 2014.
  * [KM17] Tali Kaufman and David Mass.  High dimensional random walks and colorful expansion.  In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 4:1–4:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [KM20] Tali Kaufman and David Mass.  Local-to-global agreement expansion via the variance method.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 74:1–74:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [KM21] Tali Kaufman and David Mass.  Unique-neighbor-like expansion and group-independent cosystolic expansion.  In Hee-Kap Ahn and Kunihiko Sadakane, editors, 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6-8, 2021, Fukuoka, Japan, volume 212 of LIPIcs, pages 56:1–56:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [KM22] Tali Kaufman and David Mass.  Double balanced sets in high dimensional expanders.  In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference), volume 245 of LIPIcs, pages 3:1–3:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022\.
  * [KO18] Tali Kaufman and Izhar Oppenheim.  High order random walks: Beyond spectral gap.  In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, volume 116 of LIPIcs, pages 47:1–47:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [KO22] Tali Kaufman and Izhar Oppenheim.  High dimensional expansion implies amplified local testability.  In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference), volume 245 of LIPIcs, pages 5:1–5:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022\.
  * [Opp17] Izhar Oppenheim.  Local spectral expansion approach to high dimensional expanders part i: Descent of spectral gaps, 2017.