# A Hierarchical Stitching Algorithm for Coded Compressed Sensing

Yi-Jheng Lin, Chia-Ming Chang, and Cheng-Shang Chang, , Y.-J. Lin, C.-M.
Chang, and C.-S. Chang are with the Institute of Communications Engineering,
National Tsing Hua University, Hsinchu 300, Taiwan, R.O.C. email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Recently, a novel coded compressed sensing (CCS) approach was proposed in [1]
for dealing with the scalability problem for large sensing matrices in massive
machine-type communications. The approach is to divide the compressed sensing
(CS) problem into smaller CS sub-problems. However, such an approach requires
stitching the results from the sub-problems to recover the result in the
original CS problem. For this stitching problem, we propose a hierarchical
stitching algorithm that is easier to implement in hardware for
parallelization than the tree coding algorithm in [1]. For our algorithm, we
also derive an upper bound on the probability of recovery errors.

###### Index Terms:

massive machine-type communications, coded compressed sensing, uniform
hashing.

##  I Introduction

There are three connectivity services for the fifth-generation networks (5G)
and beyond: (i) enhanced mobile broadband (eMBB), (ii) ultra-reliable low-
latency communications (URLLC), and (iii) massive machine-type communications
(mMTC) (see, e.g., [2, 3, 4] and references therein). For mMTC, the aim is to
provide communications in the context of the Internet of Things (IoT). As
mentioned in [5], there are three interesting aspects for mMTC: (i) small size
of the payload leads to finite-blocklength (FBL) effects, (ii) only a small
fraction of users are active at any given time (random access), and (iii)
users access channel without any prior resource requests to the base station
(grant-free or uncoordinated transmissions). To cope with these three aspects
for mMTC, Ordentlich and Polyanskiy [6] considered the $T$-user Gaussian
multiple access channel (T-GMAC) and proposed a low-complexity coding scheme,
in which the transmission period is divided into synchronous time slots, and
every active user transmits a codeword during a randomly chosen time slot. As
mentioned in the recent paper [1], there is approximately a 20 dB gap between
the coding scheme in [6] and the achievability limit associated with the
unsourced MAC in [5]. By using successive interference cancellation (SIC)
across time slots as in coded slotted ALOHA (CSA) [7, 8, 9, 10] the gap was
pushed to 6dB in [11].

In [1, 12], a compressed sensing (CS) approach was proposed for the
uncoordinated and unsourced MAC problem. Their approach is to treat
uncoordinated multiple access with a massive number of users as support
recovery in noisy compressed sensing. Suppose that $B$ bits are transmitted by
each user. Then the CS approach requires a sensing matrix with $2^{B}$
columns, and that makes it computationally infeasible if $B$ is on the order
of 100. To address the scalability problem, the idea in [1] is to divide the
$B$ bits into $n$ sub-blocks so that the sub-block size of the sub-CS problem
is within the computational capability of state-of-the-art technology.
However, this also raises the problem to pierce the $n$ sub-blocks sent by the
same user together. For this, a novel coded compressed sensing (CCS) scheme
was devised in [1]. At the end of each sub-block, parity bits are padded by
hashing the previous sub-blocks (of the same user) with random linear codes. A
low-complexity tree coding algorithm that iteratively explores the sub-blocks
in the next time slot, and adds candidate sub-blocks (that pass the
consistency check of parity bits) into a candidate tree of each user. In the
$n^{th}$ time slot, if the candidate tree contains only one path, then the
codeword of a user can be recovered. Instead of using the hard stitching
decisions in [1], a recent advance in [13] is to use soft stitching decisions
based on LDPC codes (with parity sub-blocks) so that the sub-CS problem and
the stitching problem can be iteratively solved. However, as pointed out in
[14], there might be several codewords on the same factor graph within the
LDPC code, and that leads to negative impacts for the application of belief
propagation on the LDPC code.

The exploration of the tree coding algorithm in [1] is sequential from one
time slot to another time slot. There are several disadvantages of that: (i)
(Parallelization) it is not easy to parallelize the tree decoding as the
candidate tree in one time slot depends on the candidate tree in the previous
time slot, (ii) (Identical sub-blocks) the parity bits only depend on the
information of the previous sub-blocks, and it might be problematic when two
users have identical sub-blocks in early time slots, (iii) (Hardware
implementation) to balance the growth of the candidate tree, the number of
parity bits need to be tuned and might be different in every time slot.
Variable sub-block formats in the $n$ time slots complicate the hardware
implementation of the algorithm.

To facilitate the hardware design for parallelization, in the letter we
propose a hierarchical stitching algorithm with an identical sub-block format
in every time slot. For our algorithm, we require that the number of time
slots $n$ is a power of 2 so that the $n$ sub-blocks can be “merged” in a
complete binary tree. Instead of exploring candidates for one user from one
time slot to another time slot, we explore candidates for all the users in two
adjacent time slots, and that leads to $n/2$ candidate sets that contain
fragments in chains of two sub-blocks. Then we recursively move up one level
of the complete binary tree to double the length of fragments. When the root
of the binary tree is reached, we recover all the messages sent by all the
users.

We summarize the contributions of this letter for the coded compressed sensing
problem below.

(i) A hierarchical stitching algorithm with a fixed sub-block format that
enables parallelization in hardware.

(ii) A mathematical analysis for the expected number of erroneous candidates
in the hierarchical stitching algorithm that leads to an upper bound for the
probability of recovery errors. Such a bound holds even when there are
identical sub-blocks from two different users.

(iii) An allocation scheme for the number of parity bits at each level of the
binary tree that can be used for controlling the computational complexity.

##  II The stitching problem

In the letter, we consider the coded compressed sensing scheme for unsourced
multiple access in [1]. As mentioned in the introduction, the approach in [1]
consists of two steps: (i) decomposing the CS problem into several CS sub-
problems, and (ii) stitching the results from sub-problems to recover the
results in the original problem. In this letter, we only consider the
stitching problem. Suppose that there are $K$ users. Let ${\cal
L}=\\{\underline{v}_{1},\underline{v}_{2},\ldots,\underline{v}_{K}\\}$ be the
collection of $K$ codewords sent by the $K$ users. Each codeword is divided
into $n$ sub-blocks and it has the following binary representation:

$\underline{v}_{i}=\underline{w}_{i}(0)\underline{p}_{i}(0)\underline{w}_{i}(1)\underline{p}_{i}(1)\cdots\underline{w}_{i}(n-1)\underline{p}_{i}(n-1),$
(1)

where $\underline{w}_{i}(j)$ represents the information bits in the $j^{th}$
sub-block of user $i$ and $\underline{p}_{i}(j)$ represents the parity bits in
the $j^{th}$ sub-block of user $i$. The $K$ sub-blocks
$\\{\underline{w}_{i}(j)\underline{p}_{i}(j),i=0,1,\ldots,K-1\\}$, are
received at the receiver in the $j^{th}$ time slot, $j=0,1,\ldots,n-1$.
However, the receiver does not know which block belongs to which codeword (for
unsourced MAC). The stitching problem is to use the parity bits to perform a
consistency check and then stitch the $n$ sub-blocks of the same codeword
together.

As there are $K$ codewords among $K^{n-1}$ ways of stitching sub-blocks, we
have the following lower bound for the stitching problem.

###### Proposition 1

Suppose that there are exactly $K$ codewords for the stitching problem with
$n$ time slots. Then the number of parity bits needed for correct recovery of
the $K$ codewords (up to a permutation) is at least

$\displaystyle\log_{2}\left(\begin{array}[]{c}K^{n-1}\\\
K\end{array}\right)=\log_{2}\Big{(}\prod_{k=0}^{K-1}\frac{(K^{n-1}-k)}{K-k}\Big{)}$
(4) $\displaystyle\geq(n-2)K\log_{2}K.$ (5)

##  III Hierarchical stitching

In this section, we propose the hierarchical stitching algorithm. Our
algorithm is basically a divide-and-conquer algorithm. Assume that the number
of sub-blocks $n$ is a power of 2, i.e., $n=2^{M}$ for some $M$. The key idea
is to stitch the $2\ell^{th}$ sub-block and $(2\ell+1)^{th}$ sub-block into a
chain of two sub-blocks, for $\ell=0,1,\ldots 2^{M-1}-1$. By viewing every
chain of two sub-blocks as a new sub-block, we reduce the stitching problem to
the size of $2^{M-1}$ sub-blocks. By recursively carrying out the stitching
operation of two adjacent sub-blocks, we eventually obtain a single chain of
$2^{M}$ sub-blocks.

###  III-A Complete binary tree

To explain our stitching algorithm in detail, let us consider a complete
binary tree with $2^{M}$ leaves as in [15] (see Figure 1 for a complete binary
tree with 16 leaves). In such a binary tree, there are $M+1$ levels, indexed
from $0,1,\ldots,M$. The root is the only node at level 0, and a node is at
level $m$ if it is a child of a node at level $m-1$. Index the root as node
$(0,0)$, and index recursively the two children of node $(m,\ell)$ as nodes
$(m+1,2\ell)$ and $(m+1,2\ell+1)$ for $0\leq\ell\leq 2^{m}-1$ and $0\leq m\leq
M-1$. Clearly, there are $2^{m}$ nodes at level $m$. Note that the $2^{M}$
leaves are simply nodes $(M,0),\ldots,(M,2^{M}-1)$ and we will simply call
node $(M,j)$ as leaf $j$ (by omitting the index of level $M$).

Figure 1: A complete binary tree with 16 leaves (sub-blocks).

For $0\leq m\leq M$ and $0\leq\ell\leq 2^{m}-1$, we now define the $\ell^{th}$
subtree at the $m^{th}$ level as the subtree constructed by node $(m,\ell)$
and all its descendants. Such a subtree is called subtree $T(m,\ell)$. Note
that the set of all the leaves in subtree $T(m,\ell)$ is

$\displaystyle\\{j|\ell\cdot 2^{M-m}\leq j\leq(\ell+1)2^{M-m}-1\\}.$ (6)

Thus, the total number of leaves in subtree $T(m,\ell)$ is $2^{M-m}$.

Now view every sub-block as a leaf node in a complete binary tree. The
stitching algorithm starts from merging two adjacent leaf nodes at level $M$,
and that reduces the number of levels of the complete binary tree by 1. It
then recursively merges two adjacent subtrees from level $M-1$ to 0. When the
root node is reached, we complete the stitching of the $n$ sub-blocks.

###  III-B Parity bits

Figure 2: The sub-block format.

In this section, we discuss how parity bits are generated in our algorithm. To
ease the hardware design, we consider a fixed format for each sub-block. In
each sub-block, there are $b$ information bits and $M$ levels of parity bits.
The number of level $m$ parity bits is $u_{m}$, $m=0,1,\ldots,M-1$ (see Figure
2 for an illustration of the sub-block format). Note that the total number of
parity bits in each sub-block is $\sum_{m=0}^{M-1}u_{m}$. Thus, the total
number of information bits (resp. parity bits) in a codeword is $2^{M}b$
(resp. $P=2^{M}\sum_{m=0}^{M-1}u_{m}$).

The purpose of level $m$ parity bits is for the consistency check when two
subtrees at level $m+1$ are merged into a subtree at level $m$. As each non-
leaf node has two subtrees, we call these two subtrees sibling subtrees.
Specifically, the subtree $T(m,\ell)$ has two sibling subtrees $T(m+1,2\ell)$
and $T(m+1,2\ell+1)$. Since there are $2^{M-m}$ leaf nodes of $T(m,\ell)$, the
total number of information bits for the sub-blocks in the leaf nodes of
$T(m,\ell)$ is $b2^{M-m}$. The idea is to use a hash function to map these
$b2^{M-m}$ information bits to $u_{m}2^{M-m}$ bits, and assign them to the
$2^{M-m}$ leaf nodes in the subtree $T(m,\ell)$ so that each leaf node (sub-
block) is assigned with $u_{m}$ level $m$ parity bits. For example, consider
the binary tree in Figure 1. Suppose that $u_{2}=1$. To merge the two sibling
subtrees $T(2,0)$ and $T(2,1)$ into $T(1,0)$ in Figure 1, the information bits
in sub-blocks 0,1,2,3,4,5,6, and 7, are hashed into 8 bits $c(0),c(1),\ldots
c(7)$. Then bit $c(j)$ is assigned to the level 2 parity bit of the $j^{th}$
sub-block, $j=0,1,\ldots,7$.

In Algorithm 1, we show the detailed steps to generate the parity bits.

Algorithm 1 Generating the parity bits

Input $nb$ information bits with $n=2^{M}$. The number of parity bits at level
$m$, $u_{m}$, $m=0,1,\ldots,M-1$, and a set of hash functions $h_{m}$,
$m=0,1,\ldots,M-1$.

Output Coded $n$ sub-blocks with parity bits.

1: Partition $nb$ information bits into $n$ sub-blocks, each with $b$
information bits.

2: For $m=M-1,M-2,\ldots,0$,

3: For $\ell=0,1,\ldots,2^{m}-1$,

4: Use the hash function $h_{m}$ to map the $b2^{M-m}$ information bits in the
subtree $T(m,\ell)$ into $u_{m}2^{M-m}$ bits.

5: Assign the $u_{m}2^{M-m}$ bits to the $2^{M-m}$ leaf nodes in the subtree
$T(m,\ell)$ so that each leaf node (sub-block) is assigned with $u_{m}$ level
$m$ parity bits.

6: End

7: End

###  III-C The stitching algorithm

Suppose that $K$ users are sending $K$ codewords to the receiver and that each
codeword contains $n=2^{M}$ sub-blocks with the padded parity bits described
in Algorithm 1. Index the $n$ time slots from 0 to $2^{M}-1$. In the
$\ell^{th}$ time slot, the $\ell^{th}$ sub-blocks from the $K$ users are
received, but they are mixed together and the receiver cannot tell which sub-
block belongs to which codeword without looking into the parity bits. Note
that two users may send an identical sub-block in the same time slot. As such,
the total number of sub-blocks received in a time slot might be less than $K$.
An exhaustive search for the $K$ codewords requires $O(K^{n-1})$ computational
complexity. Our stitching algorithm can greatly reduce the computational
complexity by exploiting the power of a divide-and-conquer algorithm. The idea
is to keep a set of “candidates” for each subtree (of the $K$ codewords)
during the hierarchical stitching process. The candidate set for each subtree
contains “chained” sub-blocks that pass the consistency check (for the parity
bits) up to the level of the subtree. Initially, for each time slot $\ell$,
the candidate set at the leaf (sub-block) level, i.e., level $M$, simply
contains the $K$ sub-blocks from the $K$ codewords. To move up one level, we
select a candidate from a subtree and another candidate from its sibling
subtree, and perform the consistency check by using the hash functions in
Algorithm 1. If the concatenation of these two chained sub-blocks passes the
consistency check, then it is added as a candidate in the parent subtree of
these two sibling subtrees. Clearly, the size of each candidate set at level
$M$ is $K$, and thus it requires $K^{2}$ consistency check operations to find
the candidate set at level $M-1$. The key is to maintain the expected sizes of
the candidate sets at level $M-1$ within $O(K)$ so that the number of
consistency check operations remains $O(K^{2})$ when we move up one level. The
chaining (merging) process is repeated until the root node (level 0) is
reached. If there are no errors, one should have exactly $K$ chained sub-
blocks in the candidate set at level 0, and these $K$ chained sub-blocks are
the $K$ codewords sent by the $K$ users. The detailed steps of the hierarchal
stitching algorithm are given in Algorithm 2.

Algorithm 2 The hierarchical stitching algorithm

Input $K$ sub-blocks (with the format in Algorithm 1) in each of the $n=2^{M}$
time slots, and the hash functions $h_{m}$, $m=0,1,\ldots,M-1$, in Algorithm
1.

Output The $K$ codewords from the $K$ users.

1: Let $S(M,\ell)$ be the candidate set that contains at most $K$ sub-blocks
at the $\ell^{th}$ time slot, $\ell=0,1,\ldots,2^{M}-1$.

2: Let $S(m,\ell)$ be an empty set that represents the initial candidate set
for the subtree $T(m,\ell)$, $m=M-1,M-2,\ldots,0$, $\ell=0,1,\ldots,2^{m}-1$.

3: For $m=M-1,M-2,\ldots,0$,

4: For $\ell=0,1,\ldots,2^{m}-1$,

5: For each pair of two candidates in $S(m+1,2\ell)\times S(m+1,2\ell+1)$,

6: Concatenate these two candidates (chained sub-blocks) into a single chained
sub-block, and perform the consistency check by using the hash function
$h_{m}$.

7: If it passes the consistency check, add it to the candidate set
$S(m,\ell)$.

8: End

9: End

10: End

11: Output the candidate set $S(0,0)$.

In Figure 3, we provide an illustrating example of the hierarchical stitching
algorithm with $K=4$ codewords and $n=8$ sub-blocks. We represent a sub-block
as a node in an $n$-stage multi-partite graph. A path in the multi-partite
graph represents a chain of sub-blocks. As $M=3$, there are three subtree
levels: level 2 in Figure 3 (a), level 1 in Figure 3 (b), and level 0 in
Figure 3 (c). As shown in Figure 3, there are four subtrees at level 2,
$T(2,0)$, $T(2,1)$, $T(2,2)$, and $T(2,3)$. The candidate set for $T(2,0)$
(the leftmost bipartite graph) contains 6 candidates with each candidate
represented by a chain of two sub-blocks. As $K=4$, there are 4 correct
candidates in the candidate set of $T(2,0)$ (marked in black) and two
erroneous candidates in the candidate set of $T(2,0)$ (marked in red). At
level 1, the two candidate sets in $T(2,0)$ and $T(2,1)$ are merged into the
candidate set for $T(1,0)$ (the left 4-partite graph in Figure 3(b). The
candidate set for $T(1,0)$ still contains 4 correct candidates. But there is
only one erroneous candidate (with a chain of four sub-blocks). Finally, at
level 0, the two candidate sets for $T(1,0)$ and $T(1,1)$ are merged into the
candidate set for $T(0,0)$ and this candidate set only contains the four
correct candidates that are the original four codewords sent by the four
users.

Figure 3: An illustration of the hierarchical stitching algorithm with $K=4$
codewords and $n=8$ sub-blocks: (a) the four candidate sets at level 2, (b)
the two candidate sets at level 1, and (c) the candidate set at level 0 (with
4 correct codewords). The black (resp. red) paths represent the correct (resp.
erroneous) candidates.

###  III-D Analysis

In this section, we conduct an analysis for Algorithm 2. A candidate for the
subtree $T(m,\ell)$ is a chain of $2^{M-m}$ sub-blocks that satisfies the
consistency check up to level $m$. Let $L(m,\ell)$ be the number of candidates
for the subtree $T(m,\ell)$ and $L_{\rm err}(m,\ell)$ be the number of
erroneous candidates for the subtree $T(m,\ell)$. As in [1], we will show how
to bound ${\bf\sf E}[L_{\rm err}(m,\ell)]$ if the hash functions described in
the previous section satisfy the uniform hashing assumption defined below.

###### Definition 2

(uniform hashing assumption) Let $Z_{N}$ be the set of integers
$\\{0,1,\ldots,N-1\\}$. Consider a family of functions from some set $S$ to
$Z_{N}$. A randomly selected function $h$ in the family of functions is said
to satisfy the uniform hashing assumption if for any $a\neq b\in S$,

${\bf\sf P}(h(a)=h(b))=\frac{1}{N}.$ (7)

In Lemma 11 of [1], it was shown that random linear codes can be used for
generating parity bits that satisfy the uniform hashing assumption.

###### Lemma 3

Suppose that (A1) the hash functions satisfy the uniform hashing assumption,
and (A2) all the information bits are independent Bernoulli random variables
with parameter $1/2$.

(i) For $\ell=0,1,\ldots,2^{M-1}-1$,

${\bf\sf E}[L_{\rm err}(M-1,\ell)]\leq{K^{2}}(\frac{1}{2})^{2u_{M-1}}.$ (8)

(ii) For $\ell=0,1,\ldots,2^{M-1}-1$,

${\bf\sf E}[L(M-1,\ell)]\leq K+{K^{2}}(\frac{1}{2})^{2u_{M-1}}.$ (9)

(iii) For $m=M-2,\ldots,0$, $\ell=0,1,\ldots,2^{m}-1$,

$\displaystyle{\bf\sf E}[L_{\rm err}(m,\ell)]\leq$ $\displaystyle{\bf\sf
E}[L(m+1,2\ell)]{\bf\sf E}[L(m+1,2\ell+1)]{(\frac{1}{2})^{u_{m}2^{M-m}}},$

and

$\displaystyle{\bf\sf E}[L(m,\ell)]\leq K+{\bf\sf E}[L_{\rm err}(m,\ell)].$
(11)

Proof. (i) At level $M-1$, an erroneous candidate occurs when a chain of two
sub-blocks passes the consistency check, and it is not a fragment of a
codeword. As there are $u_{M-1}$ parity bits at level $M-1$ for each sub-
block, to merge two sub-blocks requires the $2u_{M-1}$ parity bits to be the
same as the hashing output of the $2b$ information bits in these two sub-
blocks. From the uniform hashing assumption in Definition 2 and the
independent assumption of information bits, this happens with probability
$(\frac{1}{2})^{2u_{M-1}}$. Since there are at most $K^{2}$ ways of forming an
erroneous candidate, the expected number of erroneous candidates is bounded by
${K^{2}}(\frac{1}{2})^{2u_{M-1}}$.

(ii) Since there are at most $K$ corrected candidates, the expected number of
candidates at level $M-1$ is bounded by $K+{K^{2}}(\frac{1}{2})^{2u_{M-1}}$.

(iii) The argument is basically the same as (i) and (ii). Consider a candidate
in subtree $T(m+1,2\ell)$ and another candidate in subtree $T(m+1,2\ell+1)$.
To merge these two candidates requires the concatenation of the
$u_{m}2^{M-m-1}$ parity bits in the subtree $T(m+1,2\ell)$ and the
$u_{m}2^{M-m-1}$ parity bits in the subtree $T(m+1,2\ell+1)$ to be the same as
the hashing output of the concatenation of the $b2^{M-m-1}$ information bits
in the subtree $T(m+1,2\ell)$ and the $b2^{M-m-1}$ information bits in the
subtree $T(m+1,2\ell+1)$. Once again, from the uniform hashing assumption and
the independent assumption of information bits, an erroneous candidate at
level $m$ happens with probability $(\frac{1}{2})^{u_{m}2^{M-m}}$. Since there
are at most $L(m+1,2\ell)L(m+1,2\ell+1)$ ways to form an erroneous candidate
at level $m$, we have from the independent assumption that the expected number
of erroneous candidates is bounded by

$({\bf\sf E}[L(m+1,2\ell)]{\bf\sf
E}[L(m+1,2\ell+1)]){(\frac{1}{2})^{u_{m}2^{M-m}}}.$

Since there are at most $K$ corrected candidates, the expected number of
candidates at level $m$ is then bounded by (3).

We note that an exact analysis for the expected number of candidates is
complicated as two codewords might have the same information bits and parity
bits in a chain of two sub-blocks. As such, the number of correct candidates
might be less than $K$, and we have to restrict ourselves to the derivation of
the upper bounds in Lemma 3.

In the following theorem, we show that if the number of parity bits at each
level is large enough, then the probability of having erroneous candidates can
be made very small.

###### Theorem 4

Suppose that (A1) and (A2) in Lemma 3 hold. For any constant $C>0$, suppose
that

$u_{M-1}\geq\frac{1}{2}\log_{2}\Big{(}\frac{K}{C}\Big{)},$ (12)

and for $m=M-2,\ldots,0$,

$u_{m}\geq\frac{1}{2^{M-m}}\log_{2}\Big{(}\frac{(1+C)^{2}}{C}K\Big{)}.$ (13)

Then ${\bf\sf E}[L_{\rm err}(m,\ell)]\leq CK$ and ${\bf\sf
E}[L(m,\ell)]\leq(1+C)K$ for all $m,\ell$, and

${\bf\sf P}(L_{\rm err}(0,0)\geq
1)\leq(\frac{1}{2})^{u_{0}2^{M}}(1+C)^{2}K^{2}.$ (14)

Thus, the probability that the $K$ codewords can be recovered correctly is at
least

$1-(\frac{1}{2})^{u_{0}2^{M}}(1+C)^{2}K^{2}.$

Proof. We first show by induction that ${\bf\sf E}[L_{\rm err}(m,\ell)]\leq
CK$ and ${\bf\sf E}[L(m,\ell)]\leq(1+C)K$ for all $m,\ell$ under (12) and
(13). For $m=M-1$, it follow from Lemma 3(i), Lemma 3(ii), and (12) that
${\bf\sf E}[L_{\rm err}(M-1,\ell)]\leq CK$ and ${\bf\sf
E}[L(M-1,\ell)]\leq(1+C)K$. Assume that ${\bf\sf E}[L_{\rm err}(m+1,\ell)]\leq
CK$ and ${\bf\sf E}[L(m+1,\ell)]\leq(1+C)K$ hold for all
$\ell=0,1,\ldots,2^{m+1}-1$ as the induction hypotheses. As a direct result of
Lemma 3(iii) and the induction hypotheses, we have ${\bf\sf E}[L_{\rm
err}(m,\ell)]\leq CK$ and ${\bf\sf E}[L(m,\ell)]\leq(1+C)K$ for all
$\ell=0,1,\ldots,2^{m}-1$. Using these in (3) with $m=0$ yields

$L_{\rm err}(0,0)\leq(\frac{1}{2})^{u_{0}2^{M}}(1+C)^{2}K^{2}.$

The upper bound in (14) then follows from Markov’s inequality.

As ${\bf\sf E}[L(m,\ell)]\leq(1+C)K$ for all $m,\ell$, the expected number of
hash operations (for consistency check) for merging two subtrees is bounded by
$(1+C)^{2}K^{2}$. Since there are $2^{M}-1$ non-leaf nodes (that needs to be
merged) in a complete binary tree with $2^{M}$ leaf nodes, the expected total
number of hash operations is bounded by $(2^{M}-1)(1+C)^{2}K^{2}$ if the
parity bits are allocated to satisfy (12) and (13).

Suppose that we choose
$u_{M-1}=\lceil\frac{1}{2}\log_{2}\Big{(}\frac{K}{C}\Big{)}\rceil\leq\lceil\frac{1}{2}\log_{2}\Big{(}\frac{(1+C)^{2}}{C}K\Big{)}\rceil$
and
$u_{m}=\lceil\frac{1}{2^{M-m}}\log_{2}\Big{(}\frac{(1+C)^{2}}{C}K\Big{)}\rceil$,
$m=M-2,\ldots,0$. Then it follows from Theorem 4 that the probability of
correct recovery of the $K$ codewords approaches to 1 as $n\to\infty$. Using
$\lceil x\rceil\leq 1+x$, it is straightforward to show that the total number
of parity bits in a sub-block

$\sum_{m=0}^{M-1}u_{m}\leq
M+\log_{2}K+\log_{2}\Big{(}\frac{(1+C)^{2}}{C}\Big{)}.$

Since there are $K$ codewords with $n=2^{M}$ sub-blocks, the total number of
parity bits needed in our hierarchical stitching algorithm is

$nK\Big{(}\log_{2}n+\log_{2}K+\log_{2}\Big{(}\frac{(1+C)^{2}}{C}\Big{)}\Big{)}.$

This is quite close to the lower bound in Proposition 1.

Note from Theorem 4 that for $K=300$ and $M=5$, there are $n=32$ sub-blocks.
For $C=9$, we can choose $u_{4}=3$, $u_{3}=3$, and $u_{2}=2$ and
$u_{1}=u_{0}=1$ to satisfy the condition in (12) and (13). The total number of
parity bits in each sub-block is 10 for this case, and the total number of
parity bits in each codeword (with 32 sub-blocks) is 320 bits. From Theorem 4,
the probability that the $300$ codewords can be recovered correctly (up to a
permutation) is at least

$1-(10)^{2}(300)^{2}(\frac{1}{2})^{32}\approx 0.998.$

## References

  * [1] V. K. Amalladinne, J.-F. Chamberland, and K. R. Narayanan, “A coded compressed sensing scheme for unsourced multiple access,” _IEEE Transactions on Information Theory_ , vol. 66, no. 10, pp. 6509–6533, 2020.
  * [2] M. Bennis, M. Debbah, and H. V. Poor, “Ultrareliable and low-latency wireless communication: Tail, risk, and scale,” _Proceedings of the IEEE_ , vol. 106, no. 10, pp. 1834–1853, 2018.
  * [3] P. Popovski, Č. Stefanović, J. J. Nielsen, E. De Carvalho, M. Angjelichinoski, K. F. Trillingsgaard, and A.-S. Bana, “Wireless access in ultra-reliable low-latency communication (urllc),” _IEEE Transactions on Communications_ , vol. 67, no. 8, pp. 5783–5801, 2019.
  * [4] T.-K. Le, U. Salim, and F. Kaltenberger, “An overview of physical layer design for ultra-reliable low-latency communications in 3gpp releases 15, 16, and 17,” _IEEE Access_ , 2020.
  * [5] Y. Polyanskiy, “A perspective on massive random-access,” in _2017 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 2523–2527.
  * [6] O. Ordentlich and Y. Polyanskiy, “Low complexity schemes for the random access gaussian channel,” in _2017 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 2528–2532.
  * [7] G. Liva, “Graph-based analysis and optimization of contention resolution diversity slotted aloha,” _IEEE Transactions on Communications_ , vol. 59, no. 2, pp. 477–487, 2011.
  * [8] K. R. Narayanan and H. D. Pfister, “Iterative collision resolution for slotted aloha: An optimal uncoordinated transmission policy,” in _Turbo Codes and Iterative Information Processing (ISTC), 2012 7th International Symposium on_. IEEE, 2012, pp. 136–139.
  * [9] E. Paolini, G. Liva, and M. Chiani, “Random access on graphs: A survey and new results,” in _Signals, Systems and Computers (ASILOMAR), 2012 Conference Record of the Forty Sixth Asilomar Conference on_. IEEE, 2012, pp. 1743–1747.
  * [10] Č. Stefanović and D. Vukobratović, “Coded random access,” in _Network Coding and Subspace Designs_. Springer, 2018, pp. 339–359.
  * [11] A. Vem, K. R. Narayanan, J.-F. Chamberland, and J. Cheng, “A user-independent successive interference cancellation based coding scheme for the unsourced random access gaussian channel,” _IEEE Transactions on Communications_ , vol. 67, no. 12, pp. 8258–8272, 2019.
  * [12] A. Fengler, P. Jung, and G. Caire, “Sparcs and amp for unsourced random access,” in _2019 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2019, pp. 2843–2847.
  * [13] V. K. Amalladinne, A. K. Pradhan, C. Rush, J.-F. Chamberland, and K. R. Narayanan, “Unsourced random access with coded compressed sensing: Integrating amp and belief propagation,” _arXiv preprint arXiv:2010.04364_ , 2020.
  * [14] J. R. Ebert, V. K. Amalladinne, S. Rini, J.-F. Chamberland, and K. R. Narayanan, “Stochastic binning and coded demixing for unsourced random access,” _arXiv preprint arXiv:2104.05686_ , 2021.
  * [15] H.-S. Chueh, C.-M. Lien, C.-S. Chang, J. Cheng, and D.-S. Lee, “Load-balanced birkhoff-von neumann switches and fat-tree networks,” in _2013 IEEE 14th International Conference on High Performance Switching and Routing (HPSR)_. IEEE, 2013, pp. 142–147.


$\tilde{E}_{i}$ (chosen uniformly at random between the two edges in the
middle if the watermelon has an even number of edges). We again write
$R(E_{i})$ the radius of the largest fpp-ball centred at $E_{i}$ containing
only $2$-faces. For conciseness we drop the $\lfloor\cdot\rfloor$. If $t>0$,
then by the second moment method,

$\displaystyle\mathbb{P}$ $\displaystyle\left(\left.\exists
i\leq\ell^{3/2},R(E_{i})\geq
t\log\ell\right|\widetilde{\mathfrak{M}}^{(\ell)}\right)$
$\displaystyle\geq\frac{\mathbb{E}(\\#\left\\{i\in[\\![1,\ell^{3/2}]\\!],R(E_{i})\geq
t\log\ell\right\\}|\widetilde{\mathfrak{M}}^{(\ell)})^{2}}{\mathbb{E}((\\#\left\\{i\in[\\![1,\ell^{3/2}]\\!],R(E_{i})\geq
t\log\ell\right\\})^{2}|\widetilde{\mathfrak{M}}^{(\ell)})}$
$\displaystyle=\frac{\ell^{3}\mathbb{P}(R(E)\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})^{2}}{\ell^{3/2}\mathbb{P}(R(E)\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})+\ell^{3/2}(\ell^{3/2}-1)\mathbb{P}(R(E_{1}),R(E_{2})\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})}$

Now, one can distinguish whether $\tilde{E}_{1}=\tilde{E}_{2}$ or not. Then,
in probability as $\ell\to\infty$,

$\displaystyle\mathbb{P}$ $\displaystyle(R(E_{1}),R(E_{2})\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})$
$\displaystyle\leq\mathbb{P}(\tilde{E}_{1}=\tilde{E}_{2}\text{ and
}R(E_{1})\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})+\mathbb{P}(\tilde{E}_{1}\neq\tilde{E}_{2}\text{
and }R(E_{1}),R(E_{2})\geq t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})$
$\displaystyle=\frac{1}{\\#\mathrm{Edges}(\widetilde{\mathfrak{M}}^{(\ell)})}\mathbb{P}(R(E)\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})+\frac{\\#\mathrm{Edges}(\widetilde{\mathfrak{M}}^{(\ell)})-1}{\\#\mathrm{Edges}(\widetilde{\mathfrak{M}}^{(\ell)})}\mathbb{P}(R(E_{1}),R(E_{2})\geq
t\log\ell|\tilde{E}_{1}\neq\tilde{E}_{2},\widetilde{\mathfrak{M}}^{(\ell)})$
$\displaystyle=O(\ell^{-3/2})\mathbb{P}(R(E)\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})+\mathbb{P}(R(E)\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})^{2},$

where the last line is due to the convergence in distribution of
$\\#\mathrm{Edges}(\widetilde{\mathfrak{M}}^{(\ell)})\ell^{-3/2}$ as
$\ell\to\infty$, see e.g. Proposition 10.4 in [13].

By taking $t<3/(4(1-q_{1}^{2}))$ we ensure that $\ell^{3/2}\mathbb{P}(R(E)\geq
t\log\ell|\widetilde{\mathfrak{M}}^{(\ell)})\to\infty$ in probability as
$\ell\to\infty$, hence

$\mathbb{P}\left(\left.\exists i\leq\ell^{3/2},R(E_{i})\geq
t\log\ell\right|\widetilde{\mathfrak{M}}^{(\ell)}\right)\mathop{\longrightarrow}\limits_{\ell\to\infty}^{(\mathbb{P})}1.$

This entails what we wanted to show. ∎

###  6.3 Upper bound of the diameter for the graph distance

We next upper bound the diameter of $\mathfrak{M}^{(\ell,\dagger)}$ for the
graph distance. The proposition below implies the second upper bound of
Theorem 1.2. Unlike the case of the fpp distance, the upper bound for the
graph distance is universal (i.e. it does not depend on $\bf q$).

######  Proposition 6.5.

Let $\mathrm{Diam}_{\mathrm{gr}}^{\dagger}(\mathfrak{M}^{(\ell)})$ be the
diameter of $\mathfrak{M}^{(\ell,\dagger)}$ for the graph distance. Then for
all $\delta>0$, with probability $1-o(1)$ when $\ell\to\infty$,

$\frac{\mathrm{Diam}_{\mathrm{gr}}^{\dagger}(\mathfrak{M}^{(\ell)})}{(\log\ell)^{2}}\leq
18+\delta.$

To prove this result, we will need to use the height process $H_{\ell}$ during
the peeling by layers exploration, together with the interpolated height
process. Let us first recall the definition of the interpolated height process
from [11]. At time $n$ of the exploration, let $D_{n}$ be the number of edges
in the boundary $\partial\overline{\mathfrak{e}}_{n}$ that are at height
$H_{\ell}(n)$, so that the other $2P_{\ell}(n)-D_{n}$ edges are at height
$H_{\ell}(n)+1$. If $f:[0,1]\to[0,1]$ is a non-increasing function, the
interpolated height process $H^{f}_{\ell}(n)$ under $\mathbb{P}^{(1)}_{\ell}$
and its increment at time $n<\tau_{-\ell}$ are defined by

$H_{\ell}^{f}(n)\coloneqq
H_{\ell}(n)+f(D_{n}/2P_{n})\qquad\text{and}\qquad\Delta
H_{\ell}^{f}(n)\coloneqq H_{\ell}^{f}(n+1)-H_{\ell}^{f}(n),$

where by convention, we set $H^{f}_{\ell}(n)=H^{f}_{\ell}(\tau_{-\ell}-1)$ for
$n\geq\tau_{-\ell}$. The next lemma is an analogue of Lemma 6 from [11],
bounding from above the mean increase of the interpolated height.

######  Lemma 6.6.

Let $0<\varepsilon<1$. If $f:[0,1]\to[0,1]$ is twice continuously
differentiable with
$f(0)=1,f(1)=0,f^{\prime}(0)=f^{\prime}(1)=f^{\prime\prime}(0)=f^{\prime\prime}(1)=0$
and $0\leq-f^{\prime}(x)\leq 1+\varepsilon$ for all $x\in[0,1]$, then there
exist $C(\varepsilon,{\bf q}),C^{\prime}(\varepsilon,{\bf q})>0$ such that for
all $\ell_{0}\geq 1,\ell\geq 1,n\geq 0$,

$\mathbb{E}^{(\ell_{0})}_{\ell}\left(\left.\Delta
H_{\ell}^{f}(n)\right|\mathcal{F}_{n}\right)\leq\frac{(1+3\varepsilon)^{2}}{1-\varepsilon}\frac{p_{\bf
q}}{2}\frac{\log(P_{\ell}(n))+C(\varepsilon,{\bf
q})}{P_{\ell}(n)}\enskip\text{and}\enskip\mathbb{E}^{(\ell_{0})}_{\ell}\left(\left.\left(\Delta
H_{\ell}^{f}(n)\right)^{2}\right|\mathcal{F}_{n}\right)\leq\frac{C^{\prime}(\varepsilon,{\bf
q})}{P_{\ell}(n)},$

where $(\mathcal{F}_{n})_{n\geq 0}$ is the filtration associated to the
exploration process.

###### Proof.

The proof is essentially the same as the proof of Lemma 6 of [11], but a
little more complex. Indeed, the same terms appear except that they are
multiplied by a factor $(p+\ell)/(p+k+\ell)$. Let us detail the proof.

We extend $f$ to $\mathbb{R}$ by setting $f(x)=1$ for $x\leq 0$ and $f(x)=0$
for all $x\geq 1$. As in [11], by the Markov property of the exploration
(Proposition 3.1), we claim that $(H_{\ell}(n),P_{\ell}(n),D_{n})_{n\geq 0}$
is a Markov chain and that if $p\geq 1$ and $1\leq d\leq 2p$, then

$\displaystyle\mathbb{E}^{(\ell_{0})}_{\ell}$ $\displaystyle\left(\left.\Delta
H_{\ell}^{f}(n)\right|P_{\ell}(n)=p,D_{n}=d\right)$ (6.3) $\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}\nu(k)\frac{p+\ell}{p+k+\ell}\frac{h^{\uparrow}(p+k)}{h^{\uparrow}(p)}\left[f\left(\frac{d-1}{2p+2k}\right)-f\left(\frac{d}{2p}\right)\right]$
(6.4)
$\displaystyle+\sum_{k=1}^{p-1}\frac{\nu(-k)}{2}\frac{p+\ell}{p-k+\ell}\frac{h^{\uparrow}(p-k)}{h^{\uparrow}(p)}\left[f\left(\frac{d-2k}{2p-2k}\right)-f\left(\frac{d}{2p}\right)\right]$
(6.5)
$\displaystyle+\sum_{k=1}^{p-1}\frac{\nu(-k)}{2}\frac{p+\ell}{p-k+\ell}\frac{h^{\uparrow}(p-k)}{h^{\uparrow}(p)}\left[f\left(\frac{d-1}{2p-2k}\right)-f\left(\frac{d}{2p}\right)\right].$
(6.6)

Indeed, if $d=1$, then either $\Delta H_{\ell}(n)=1$ and
$D_{n+1}=2P_{\ell}(n+1)$, and therefore $\Delta H_{\ell}^{f}(n)=1-f(1/(2p))$,
with probability
$\sum_{k=-p+1}^{\infty}\nu(k)(h^{\downarrow}_{\ell}(p+k)/h^{\downarrow}_{\ell}(p))$;
or $\tau_{-\ell}=n+1$ and in that case $\Delta H_{\ell}^{f}(n)=0$, with
probability $\nu(-p-\ell)/{h^{\downarrow}_{\ell}(p)}$. This agrees with the
sums since $f(x)=1$ for $x\leq 0$ (and by using the definition of
$h^{\uparrow}$ and $h^{\downarrow}_{\ell}$ in (2.1)). Now, in the case $d\geq
2$, if an event $C_{k+1}$ happens, then $P_{\ell}(n+1)=p+k$ and $D_{n+1}=d-1$,
hence the first line (6.4) (again using (2.1)). If an event $G_{\square,k-1}$
happens for $1\leq k\leq p-1$, i.e. if the peeled edge is identified with an
edge on its right, then $P_{\ell}(n+1)=P_{\ell}(n)-k$ and either
$D_{n+1}=d-2k$ and $\Delta H_{\ell}(n)=0$, or $D_{n+1}=2P_{\ell}(n+1)$ and
$\Delta H_{\ell}(n)=1$, depending on the sign of $d-2k$. These two cases are
taken into account in the second line (6.5) since $f(x)=1$ for all $x\leq 0$.
If an event $G_{k-1,\square}$ happens for some $1\leq k\leq p-1$, i.e. if the
peeled edge is identified with an edge on its left, then again
$P_{\ell}(n+1)=P_{\ell}(n)-k$ but $\Delta H_{\ell}(n)=0$ and either
$D_{n+1}=d-1$ or $D_{n+1}=2P_{\ell}(n+1)$, depending on which is the smallest.
Both situations are incorporated by the last line (6.6). Finally, if the event
$C_{\ell}^{\mathrm{stop}}$ happens, then $\Delta H_{\ell}^{f}(n)=0$ by
definition of the interpolated height process.

To deal with these three sums, we will use the notation $y=d/(2p)\in(0,1]$.
Let $c>0$ given by Taylor’s theorem such that
$|f(x)-f(y)-f^{\prime}(y)(x-y)|\leq c(x-y)^{2}$ for all $x\in\mathbb{R}$. We
will also rely on the inequality

$\forall
k>-p,\qquad\sqrt{1+k/p}(1-1/p)\leq\frac{h^{\uparrow}(p+k)}{h^{\uparrow}(p)}\leq\sqrt{1+k/p}(1+1/p).$

Let $N>0$ such that $1-\varepsilon<k^{2}\nu(-k)/p_{\bf q}<1+\varepsilon$ and
$1-\varepsilon<k\nu([k,\infty))/p_{\bf q}<1+\varepsilon$ for all $k\geq N$,
given by (1.3). From the mean value inequality applied to $f$, the first $N$
terms in each sum contribute $O(p^{-1})$ uniformly in $d,\ell$, so it suffices
to bound the sums restricted to $|k|\geq N$. Since $(p+\ell)/(p+k+\ell)\leq
1$, the aforementioned inequalities, the first sum from $N$ to $\infty$, which
only contains positive terms, is smaller than

$\sum_{k=N}^{\infty}\nu(k)\sqrt{1+k/p}(1+1/p)\left[|f^{\prime}(y)|\frac{1+yk}{p+k}+c\left(\frac{1+k}{p+k}\right)^{2}\right]$

where we used that

$\frac{d}{2p}-\frac{d-1}{2p+2k}\leq\frac{1+yk}{p+k}\leq\frac{1+k}{p+k}.$

Thus, by summation by parts, using that $1-\varepsilon<k\nu([k,\infty))/p_{\bf
q}<1+\varepsilon$ for all $k\geq N$, and then recognizing a Riemann sum, the
first sum (6.4) is upper bounded by

$(1+\varepsilon)p_{\bf
q}y\frac{1}{p}\int_{(N-1)/p}^{\infty}\frac{dx}{x\sqrt{1+x}}+O(p^{-1})\leq(1+\varepsilon)^{2}p_{\bf
q}y\frac{\log p}{p}+O(p^{-1}),$ (6.7)

where the $O(p^{-1})$ is uniform in $d$ and $\ell$. For the second sum (6.5),
which again has only positive terms, we distinguish whether $k\leq\varepsilon
p$ or $k>\varepsilon p$. If $k\leq\varepsilon p$, $(p+\ell)/(p-k+\ell)\leq
1/(1-\varepsilon)$, so that applying the inequalities and the fact that
$1-\varepsilon<k^{2}\nu(-k)/p_{\bf q}<1+\varepsilon$ for all $k\geq N$ gives
us that

$\displaystyle\sum_{k=N}^{\varepsilon
p}\frac{\nu(-k)}{2}\frac{p+\ell}{p-k+\ell}$
$\displaystyle\frac{h^{\uparrow}(p-k)}{h^{\uparrow}(p)}\left[f\left(\frac{d-2k}{2p-2k}\right)-f\left(\frac{d}{2p}\right)\right]$
$\displaystyle\leq$ $\displaystyle\sum_{k=N}^{\varepsilon
p}\frac{1+\varepsilon}{1-\varepsilon}\frac{p_{\bf
q}}{2k^{2}}(1+1/p)\sqrt{1-k/p}\left[|f^{\prime}(y)|(1-y)\frac{k}{p}\frac{1}{1-\frac{k}{p}}+c\left(\frac{k}{p}\frac{1}{1-\frac{k}{p}}\right)^{2}\right],$

where we used that

$\frac{d}{2p}-\frac{d-2k}{2p-2k}=(1-y)\frac{k}{p}\frac{1}{1-\frac{k}{p}}\leq\frac{k}{p}\frac{1}{1-\frac{k}{p}}.$

Hence, by recognizing a Riemann sum, we can upper bound the sum for the
$k\leq\varepsilon p$ by

$\frac{1+\varepsilon}{1-\varepsilon}p_{\bf
q}\frac{1-y}{2}|f^{\prime}(y)|\frac{1}{p}\int_{(N-1)/p}^{\varepsilon+1/p}\frac{1}{x\sqrt{1-x}}dx+O(p^{-1})\leq\frac{1+\varepsilon}{1-\varepsilon}p_{\bf
q}\frac{1-y}{2}|f^{\prime}(y)|\frac{\log p}{p}+O(p^{-1}).$

If $\varepsilon p\leq k\leq p-1$, we have

$1\leq\frac{p+\ell}{p-k+\ell}\leq\frac{p}{p-k}$

and

$\frac{\nu(-k)}{2}\frac{h^{\uparrow}(p-k)}{h^{\uparrow}(p)}\left[f\left(\frac{d-2k}{2p-2k}\right)-f\left(\frac{d}{2p}\right)\right]\leq\nu(-k)\frac{h^{\uparrow}(p-k)}{h^{\uparrow}(p)}\leq\sqrt{(p-k)/p}O(p^{-2}).$

So, using a Riemann sum, the sum for $k\geq\varepsilon p$ is upper bounded by
$O(p^{-1})$. Therefore, the second sum (6.5) is bounded by

$\frac{1+\varepsilon}{1-\varepsilon}p_{\bf
q}\frac{1-y}{2}|f^{\prime}(y)|\frac{\log p}{p}+O(p^{-1}).$ (6.8)

For the last sum (6.6), we first focus on the positive terms, i.e. those such
that $kd\leq p$. If $d\geq 2$, then this entails that $(p+\ell)/(p-k+\ell)\leq
2$. Moreover, for all $1\leq k\leq p-1$,

$\frac{d}{2p}-\frac{d-1}{2p-2k}\leq\frac{1}{2p},$

so that the sum of the positive terms is a $O(p^{-1})$. If $d=1$, then by
Taylor’s theorem $f(0)-f(1/(2p))=O(p^{-2})$, so that the sum of the positive
terms is a $O(p^{-2})$. In these two cases, the sum of the positive terms of
(6.6) is upper bounded by a $O(p^{-1})$. In the case $0<y<\varepsilon$, the
upper bounds for the positive terms already enable to conclude since by
summing (6.7), (6.8) and the $O(p^{-1})$, we obtain the uniform bound

$\frac{(1+\varepsilon)^{3}}{1-\varepsilon}\frac{p_{\bf q}}{2}\frac{\log
p}{p}+O(p^{-1})\leq\frac{(1+3\varepsilon)^{2}}{1-\varepsilon}\frac{p_{\bf
q}}{2}\frac{\log p}{p}+O(p^{-1}).$

In the case $y\geq\varepsilon$, we assume that we have chosen
$N>1/\varepsilon$, so that $N\geq 2p/d$ and thus all the terms of (6.6) for
$N\leq k\leq\varepsilon p$ are negative. Using that $(p+\ell)/(p-k+\ell)\geq
1$, the sum of the negative terms of (6.6) with $N\leq k\leq\varepsilon p$ can
be upper bounded by

$-\frac{1-\varepsilon}{2}\sum_{k=N}^{\varepsilon p}\frac{p_{\bf
q}}{k^{2}}(1-1/p)\sqrt{1-k/p}\left[|f^{\prime}(y)|\left(y\frac{k}{p}-\frac{1}{2p}\right)-c(2k/p)^{2}\right],$

where we used that

$\frac{d-1}{2p-2k}-\frac{d}{2p}\geq\frac{dk-p}{2p^{2}}=y\frac{k}{p}-\frac{1}{2p}\qquad\text{and}\qquad\left|\frac{d}{2p}-\frac{d-1}{2p-2k}\right|\leq\frac{k}{(1-\varepsilon)p}.$

Therefore, using again a Riemann sum, the sum (6.6) is upper bounded by

$-(1-\varepsilon)p_{\bf q}\frac{y}{2}|f^{\prime}(y)|\frac{\log
p}{p}+O(p^{-1}).$ (6.9)

Finally, summing the upper bounds (6.7), (6.8), (6.9) and the $O(p^{-1})$, one
recovers the desired result in the case $\varepsilon\leq y\leq 1$ as well for
$\mathbb{E}^{(\ell_{0})}_{\ell}\left(\left.\Delta
H_{\ell}^{f}(n)\right|\mathcal{F}_{n}\right)$. For the expectation of the
square, one can perform the same computation with the three sums (6.4), (6.5),
(6.6), except that the expressions into brackets are squared. One can check
using the same ideas that each sum is a $O(p^{-1})$ (uniformly in $d,\ell$),
hence the second upper bound. ∎

We will rely on a direct consequence of Lemma 6.6.

######  Corollary 6.7.

For all $\varepsilon\in(0,1)$, there exists $\lambda(\varepsilon)>0$ (which
does not depend on $\bf q$) and $C(\varepsilon,{\bf q})>0$ such that for all
$0<\lambda<\lambda(\varepsilon)$, for all $\ell\geq 1$ and $n\geq 0$,

$\mathbb{E}^{(1)}_{\ell}\left(\left.e^{\lambda\Delta
H_{\ell}^{f}(n)}\right|\mathcal{F}_{n}\right)\leq
1+\lambda\left(\frac{(1+3\varepsilon)^{2}}{1-\varepsilon}\frac{p_{\bf
q}}{2}{\log(P_{\ell}(n))\over P_{\ell}(n)}+\frac{C(\varepsilon,{\bf
q})}{P_{\ell}(n)}\right),$

where $(\mathcal{F}_{n})_{n\geq 0}$ is the filtration associated to the
exploration (using the peeling by layers algorithm).

###### Proof.

It suffices to take $\lambda(\varepsilon)$ small enough so that for all
$0<\lambda<c(\varepsilon)$, we have the inequality $e^{\lambda\Delta
H_{\ell}^{f}(n)}\leq 1+\lambda\Delta H_{\ell}^{f}(n)+\lambda^{2}(\Delta
H_{\ell}^{f}(n))^{2}$ (such a $\lambda(\varepsilon)$ does exist given that
$-1\leq\Delta H_{\ell}^{f}(n)\leq 1$). ∎

We can therefore define another family of supermartingales.

######  Corollary 6.8.

Let $\varepsilon\in(0,1)$. Let $\lambda<\lambda(\varepsilon)$ where
$\lambda(\varepsilon)$ is given by Corollary 6.7. For all $\ell\geq 1$ for all
$n\geq 0$, let

$M^{\varepsilon,\lambda,\ell}_{n}=\exp\left({\lambda
H_{\ell}^{f}(n)-\lambda\sum_{k=0}^{n-1}\left(\frac{(1+3\varepsilon)^{3}}{1-\varepsilon}\frac{p_{\bf
q}}{2}{\log(P_{\ell}(k))\over P_{\ell}(k)}+\frac{C(\varepsilon,{\bf
q})}{P_{\ell}(k)}\right)}\right).$

Then, under $\mathbb{P}^{(1)}_{\ell}$,
$\left(M^{\varepsilon,\lambda,\ell}_{n}\right)_{n\geq 0}$ is a supermartingale
with respect to the filtration $(\mathcal{F}_{n})_{n\geq 0}$ associated to the
exploration.

We will also use a variant of Lemma 6.2, whose proof is similar and left to
the reader.

######  Lemma 6.9.

If $\varepsilon>0$, let $k_{0}$ such that $e^{(p_{\bf q}-\varepsilon)/k}\leq
1+(\nu((-\infty,-k])-\nu(-\ell-k))$ for all $k\geq k_{0}$ and $\ell\geq 1$.
For all $\ell\geq 1,n\geq 0$, let

$M^{\varepsilon,k_{0},\ell}_{n}=\frac{1}{h^{\downarrow}_{\ell}(P_{\ell}(n))}\exp\left({(p_{\bf
q}-\varepsilon)\sum_{j=0}^{n-1}\frac{1}{P_{\ell}(j)}{\bf 1}_{P_{\ell}(j)\geq
k_{0}}}\right).$

then for all $\ell\geq 1$, under $\mathbb{P}_{\ell}^{(1)}$,
$(M^{\varepsilon,k_{0},\ell}_{n})_{n\geq 0}$ is a supermartingale with respect
to the filtration $(\mathcal{F}_{n})_{n\geq 0}$ associated to the peeling
exploration.

Subsequently, from the above results, we obtain a large deviation inequality
for the height of a random uniform edge in $\mathfrak{M}^{(\ell)}$.

######  Corollary 6.10.

Let $c>0$. Let $\delta>0$ and

$K=\frac{1}{2}(c+3)\left(c+\frac{5}{2}\right)+\delta.$

Let $\mathfrak{M}^{(\ell)}$ of law $\mathbb{P}^{(\ell)}$, let $E$ be a uniform
random edge of $\mathfrak{M}^{(\ell)}$. Then,

$\mathbb{P}\left(d_{\mathrm{gr}}^{\dagger}(f_{r},E)\geq
K(\log\ell)^{2}\right)=O(\ell^{-c})\text{ when }\ell\to\infty.$

###### Proof.

First of all, since the distance to an edge is smaller than the distance to
the $2$-face obtained by unzipping the edge, and by (3.4),

$\displaystyle\mathbb{P}\left(d_{\mathrm{gr}}^{\dagger}(f_{r},E)\geq
K(\log\ell)^{2}\right)$
$\displaystyle\leq\frac{W_{1}^{(\ell)}}{W^{(\ell)}}\mathbb{E}_{1}^{(\ell)}\left(\frac{1}{\\#\mathrm{Edges}(\mathfrak{m}_{\square})-1}{\bf
1}_{d_{\mathrm{gr}}^{\dagger}(f_{r},\square)\geq K(\log\ell)^{2}}\right)$
$\displaystyle\leq\frac{W_{1}^{(\ell)}}{W^{(\ell)}}\mathbb{P}_{1}^{(\ell)}\left(d_{\mathrm{gr}}^{\dagger}(f_{r},\square)\geq
K(\log\ell)^{2}\right).$

But, since $W_{1}^{(\ell)}/W^{(\ell)}$ is a $O(\ell^{3/2})$ by (3.3), it is
enough to prove that if
$K^{\prime}=\frac{1}{2}\left(c+\frac{3}{2}\right)(c+1)+\delta$, then

$\mathbb{P}_{1}^{(\ell)}(d_{\mathrm{gr}}^{\dagger}(f_{r},\square)\geq
K^{\prime}(\log\ell)^{2})=O(\ell^{-c}).$

Since $d^{\dagger}_{\mathrm{gr}}(f_{r},\square)\leq
H_{\ell}(\tau_{-\ell}-1)+1$ and $H_{\ell}(n)\leq H_{\ell}^{f}(n)$ for all
$n\leq\tau_{-\ell}-1$, by taking $\delta$ a bit smaller it suffices to show
that

$\mathbb{P}^{(1)}_{\ell}\left(H_{\ell}^{f}(\tau_{-\ell}-1)\geq
K^{\prime}(\log\ell)^{2}\right)=O(\ell^{-c})\text{ when }\ell\to\infty.$

So as to prove that, we can first see from Corollary 6.8 that if
$\varepsilon\in(0,1)$, if $0<\lambda<\lambda(\varepsilon)$ and
$\mu=\frac{(1+3\varepsilon)^{3}}{1-\varepsilon}\frac{p_{\bf q}}{2}$ then for
all $\ell\geq 1$,

$\displaystyle\mathbb{E}^{(1)}_{\ell}\exp\left({\lambda
H_{\ell}^{f}(\tau_{-\ell}-1)-\lambda\mu\sum_{k=0}^{\tau_{-\ell}-2}{\log(P_{\ell}(k))\over
P_{\ell}(k)}-\lambda C(\varepsilon,{\bf
q})\sum_{k=0}^{\tau_{-\ell}-2}\frac{1}{P_{\ell}(k)}}\right)$
$\displaystyle=\mathbb{E}^{(1)}_{\ell}M^{\varepsilon,\lambda,\ell}_{\tau_{-\ell}-1}$
$\displaystyle\leq\mathbb{E}^{(1)}_{\ell}M_{0}^{\varepsilon,\lambda,\ell}$
$\displaystyle=1.$

As a consequence, if $A>0$ is such that $\lambda A>c$, we have

$\displaystyle\mathbb{P}^{(1)}_{\ell}$
$\displaystyle\left(H_{\ell}^{f}(\tau_{-\ell})\geq\mu\sum_{k=0}^{\tau_{-\ell}-1}{\log(P_{\ell}(k))\over
P_{\ell}(k)}+C(\varepsilon,{\bf
q})\sum_{k=0}^{\tau_{-\ell}-1}\frac{1}{P_{\ell}(k)}+A\log\ell\right)$
$\displaystyle\leq\mathbb{P}^{(1)}_{\ell}\left(\exp\left({\lambda
H_{\ell}^{f}(\tau_{-\ell})-\lambda\mu\sum_{k=0}^{\tau_{-\ell}-1}\left({\log(P_{\ell}(k))\over
P_{\ell}(k)}+\frac{1}{P_{\ell}(k)}\right)}\right)\geq\ell^{A\lambda}\right)$
$\displaystyle\leq\frac{1}{\ell^{A\lambda}}=O(\ell^{-c}).$

From (6.2), $\sum_{k=0}^{\tau_{-\ell}-1}\frac{1}{P_{\ell}(k)}$ is well
controlled by a constant times $\log\ell$. Thus it is sufficient to show that

$\mathbb{P}^{(1)}_{\ell}\left(\sum_{k=0}^{\tau_{-\ell}-1}{\log(P_{\ell}(k))\over
P_{\ell}(k)}{\bf 1}_{P_{\ell}(k)\geq
k_{0}}\geq\frac{K^{\prime}}{\mu}(\log\ell)^{2}\right)=O(\ell^{-c}),$ (6.10)

where $k_{0}>0$ will be chosen later in the proof. However, one can note that
since $x\mapsto x/\log x$ is increasing on $[e,\infty)$, we have

$\sum_{k=3}^{\tau_{-\ell}-1}{\log(P_{\ell}(k))\over P_{\ell}(k)}{\bf
1}_{P_{\ell}(k)\geq k\log k}\leq\sum_{k=3}^{\tau_{-\ell}-1}\frac{\log
k+\log\log k}{k\log k}\leq 2\log\tau_{-\ell}$

Moreover, using Lemma 2.5 and then that
$\mathbb{E}^{(1)}_{\infty}({\ell}/{P_{\infty}(\ell)})=O(1)$ by Lemma 4 of [11]
as $\ell\to\infty$,

$\mathbb{P}_{\ell}^{(1)}(\tau_{-\ell}>\ell^{c+1})=\mathbb{E}^{(1)}_{\infty}\frac{1+\ell}{P_{\infty}(\lfloor\ell^{1+c}\rfloor)+\ell}\leq
2\mathbb{E}_{\infty}^{(1)}\frac{\ell}{P_{\infty}(\lfloor\ell^{c+1}\rfloor)}=O(\ell^{-c}).$
(6.11)

Consequently,

$\mathbb{P}^{(1)}_{\ell}\left(\sum_{k=0}^{\tau_{-\ell}-1}{\log(P_{\ell}(k))\over
P_{\ell}(k)}{\bf 1}_{P_{\ell}(k)\geq k\log k}\geq
2(c+1)\log\ell\right)=O(\ell^{-c}).$

Hence, so as to prove (6.10), it suffices to show that

$\mathbb{P}^{(1)}_{\ell}\left(\sum_{k=0}^{\tau_{-\ell}-1}{\log(P_{\ell}(k))\over
P_{\ell}(k)}{\bf 1}_{k\log k\geq P_{\ell}(k)\geq
k_{0}}\geq\frac{K^{\prime}}{\mu}(\log\ell)^{2}\right)=O(\ell^{-c}).$

But one can upper bound

$\displaystyle\sum_{k=0}^{\tau_{-\ell}-1}{\log(P_{\ell}(k))\over
P_{\ell}(k)}{\bf 1}_{k\log k\geq P_{\ell}(k)\geq k_{0}}$
$\displaystyle\leq\sum_{k=0}^{\tau_{-\ell}-1}{\log k+\log\log k\over
P_{\ell}(k)}{\bf 1}_{k\log k\geq P_{\ell}(k)\geq k_{0}}$
$\displaystyle\leq\left(\log\tau_{-\ell}+\log\log\tau_{-\ell}\right)\sum_{k=0}^{\tau_{-\ell}-1}{1\over
P_{\ell}(k)}{\bf 1}_{k\log k\geq P_{\ell}(k)\geq k_{0}}.$

So, using again (6.11) and then taking $\varepsilon$ small enough so that
$\mu=\frac{(1+3\varepsilon)^{3}}{1-\varepsilon}\frac{p_{\bf q}}{2}$ is close
to $\frac{p_{\bf q}}{2}$, we just need to prove that for all $p_{\bf
q}>\delta>0$,

$\mathbb{P}^{(1)}_{\ell}\left(\sum_{k=0}^{\tau_{-\ell}-1}{1\over
P_{\ell}(k)}{\bf 1}_{P_{\ell}(k)\geq k_{0}}\geq\frac{c+\frac{3}{2}}{p_{\bf
q}-\delta}(\log\ell)^{2}\right)=O(\ell^{-c}).$ (6.12)

In order to show that we will use the supermartingale $M^{\delta,k_{0},\ell}$
of Lemma 6.9 for $k_{0}$ chosen large enough. Applying Markov’s inequality and
Fatou’s lemma, we get that for $K^{\prime\prime}=(c+3/2)/(p_{\bf q}-\delta)$,

$\displaystyle\mathbb{P}^{(1)}_{\ell}\left(\sum_{k=0}^{\tau_{-\ell}-1}{1\over
P_{\ell}(k)}{\bf 1}_{P_{\ell}(k)\geq k_{0}}\geq
K^{\prime\prime}\log\ell\right)$ $\displaystyle\leq\ell^{-(p_{\bf
q}-\delta)K^{\prime\prime}}\mathbb{E}^{(1)}_{\ell}\exp\left({(p_{\bf
q}-\delta)\sum_{k=0}^{\tau_{-\ell}-1}\frac{1}{P_{\ell}(k)}{\bf
1}_{P_{\ell}(k)\geq k_{0}}}\right)$ $\displaystyle=\ell^{-(p_{\bf
q}-\delta)K^{\prime\prime}}\mathbb{E}^{(1)}_{\ell}M^{\delta,k_{0},\ell}_{\tau_{-\ell}}$
$\displaystyle\leq\ell^{-(p_{\bf
q}-\delta)K^{\prime\prime}}\mathbb{E}^{(1)}_{\ell}M^{\delta,k_{0},\ell}_{0}$
$\displaystyle=\ell^{-(p_{\bf
q}-\delta)K^{\prime\prime}}\frac{1}{h^{\downarrow}_{\ell}(1)}$
$\displaystyle=O(\ell^{3/2-(p_{\bf q}-\delta)K^{\prime\prime}})=O(\ell^{-c}),$

hence (6.12). ∎

The proof of Proposition 6.5 is then exactly the same as the proof of
Proposition 6.1 using Corollary 6.10:

###### Proof of Proposition 6.5.

Since the diameter is upper bounded by twice the maximal height, it suffices
to show that for all $\delta>0$

$\mathbb{P}\left(\exists e\in\mathrm{Edges}(\mathfrak{M}^{(\ell)}),\
d_{\mathrm{gr}}^{\dagger}(f_{r},e)\geq(9+\delta)(\log\ell)^{2}\right)\mathop{\longrightarrow}\limits_{\ell\to\infty}0,$

inasmuch as for all $f\in\mathrm{Faces}(\mathfrak{M}^{(\ell)})$, if $e$ is an
edge surrounding $f$, then $d_{\mathrm{gr}}^{\dagger}(f_{r},f)\leq
d_{\mathrm{gr}}^{\dagger}(f_{r},e)+1$. Next, we distinguish whether the number
of edges is too large or not: let $\varepsilon>0$.

$\displaystyle\mathbb{P}$ $\displaystyle\left(\exists
e\in\mathrm{Edges}(\mathfrak{M}^{(\ell)}),\
d_{\mathrm{gr}}^{\dagger}(f_{r},e)\geq(9+\delta)(\log\ell)^{2}\right)$
$\displaystyle\leq$
$\displaystyle\enskip\mathbb{E}\left(\\#\left\\{e\in\mathrm{Edges}(\mathfrak{M}^{(\ell)});\
d_{\mathrm{gr}}^{\dagger}(f_{r},e)\geq(9+\delta)(\log\ell)^{2}\right\\}{\bf
1}_{\\#\mathrm{Edges}(\mathfrak{M}^{(\ell)})\leq\frac{2b_{\bf
q}}{\varepsilon}\ell^{3/2}}\right)$
$\displaystyle+\mathbb{P}\left(\\#\mathrm{Edges}(\mathfrak{M}^{(\ell)})\geq\frac{2b_{\bf
q}}{\varepsilon}\ell^{3/2}\right),$

and the last term is smaller than $\varepsilon$ for $\ell$ large enough by
(3.3). Henceforth we focus on the first term. Conditionally on
$\mathfrak{M}^{(\ell)}$, let $E$ be a uniform edge of $\mathfrak{M}^{(\ell)}$.

$\displaystyle\mathbb{E}$
$\displaystyle\left(\\#\left\\{e\in\mathrm{Edges}(\mathfrak{M}^{(\ell)});\
d_{\mathrm{gr}}^{\dagger}(f_{r},e)\geq(9+\delta)(\log\ell)^{2}\right\\}{\bf
1}_{\\#\mathrm{Edges}(\mathfrak{M}^{(\ell)})\leq\frac{2b_{\bf
q}}{\varepsilon}\ell^{3/2}}\right)$
$\displaystyle\leq\mathbb{E}\left(\frac{2b_{\bf
q}}{\varepsilon}\ell^{3/2}\mathbb{P}(d_{\mathrm{gr}}^{\dagger}(f_{r},E)\geq(9+\delta)(\log\ell)^{2}|\mathfrak{M}^{(\ell)})\right)$
$\displaystyle=\frac{2b_{\bf
q}}{\varepsilon}\ell^{3/2}\mathbb{P}(d_{\mathrm{gr}}^{\dagger}(f_{r},E)\geq(9+\delta)(\log\ell)^{2}).$

The expression on the last line tends to zero by Corollary 6.10 when
$\ell\to\infty$ since for $c=3/2$ we have
$\left(c+3\right)\left(c+5/2\right)/2=9$. ∎

Acknowledgements. I thank Cyril Marzouk and Nicolas Curien for their constant
support and for their insightful comments on earlier versions.

## References

  * [1] O. Angel.  Growth and percolation on the uniform infinite planar triangulation.  Geom. Funct. Anal., 13(5):935–974, 2003.
  * [2] J. Bertoin, T. Budd, N. Curien, and I. Kortchemski.  Martingales in self-similar growth-fragmentations and their connections with random planar maps.  Probab. Theory Relat. Fields, 172(3-4):663–724, 2018.
  * [3] J. Bertoin and I. Kortchemski.  Self-similar scaling limits of Markov chains on the positive integers.  Ann. Appl. Probab., 26(4):2556–2595, 2016.
  * [4] J. Bertoin and M. Yor.  The entrance laws of self-similar Markov processes and exponential functionals of Lévy processes.  Potential Anal., 17(4):389–400, 2002.
  * [5] G. Borot, J. Bouttier, and E. Guitter.  A recursive approach to the $O(n)$ model on random maps via nested loops.  J. Phys. A, Math. Theor., 45(4):38, 2012.  Id/No 045002.
  * [6] J. Bouttier, P. Di Francesco, and E. Guitter.  Planar maps as labeled mobiles.  Electron. J. Comb., 11(1):research paper r69, 27, 2004.
  * [7] T. Budd.  Peeling random planar maps (lecture notes).  http://hef.ru.nl/tbudd/docs/mappeeling.pdf.
  * [8] T. Budd.  The peeling process of infinite Boltzmann planar maps.  Electron. J. Comb., 23(1):research paper p1.28, 37, 2016.
  * [9] T. Budd.  The peeling process on random planar maps coupled to an o(n) loop model (with an appendix by linxiao chen), 2018.
  * [10] T. Budd and N. Curien.  Geometry of infinite planar maps with high degrees.  Electron. J. Probab., 22:37, 2017.  Id/No 35.
  * [11] T. Budd, N. Curien, and C. Marzouk.  Infinite random planar maps related to Cauchy processes.  J. Éc. Polytech., Math., 5:749–791, 2018.
  * [12] F. Caravenna and L. Chaumont.  Invariance principles for random walks conditioned to stay positive.  Ann. Inst. Henri Poincaré, Probab. Stat., 44(1):170–190, 2008\.
  * [13] N. Curien.  Peeling random planar maps.  École d’Été de Probabilités de Saint-Flour XLIX–2019, (to appear).
  * [14] R. A. Doney.  Conditional limit theorems for asymptotically stable random walks.  Z. Wahrscheinlichkeitstheor. Verw. Geb., 70:351–360, 1985.
  * [15] R. A. Doney and M. S. Savov.  The asymptotic behavior of densities related to the supremum of a stable process.  Ann. Probab., 38(1):316–326, 2010.
  * [16] G. Elek and G. Tardos.  Convergence and limits of finite trees.  Combinatorica, 42(6):821–852, 2022.
  * [17] S. Janson.  On the Gromov-Prohorov distance.  arXiv:2005.13505 [math.PR], 2020.
  * [18] S. Janson.  Tree limits and limits of random trees.  Combinatorics, Probability and Computing, 30(6):849–893, 2021\.
  * [19] S. Janson and S. Ö. Stefánsson.  Scaling limits of random planar maps with a unique large face.  Ann. Probab., 43(3):1045–1081, 2015.
  * [20] A. E. Kyprianou, J. C. Pardo, and V. Rivero.  Exact and asymptotic $n$-tuple laws at first and last passage.  Ann. Appl. Probab., 20(2):522–564, 2010.
  * [21] J.-F. Le Gall and G. Miermont.  Scaling limits of random planar maps with large faces.  Ann. Probab., 39(1):1–69, 2011.
  * [22] J.-F. Marckert and G. Miermont.  Invariance principles for random bipartite planar maps.  Ann. Probab., 35(5):1642–1705, 2007.
  * [23] S. Sheffield.  Exploration trees and conformal loop ensembles.  Duke Math. J., 147(1):79–129, 2009.
  * [24] S. Sheffield and W. Werner.  Conformal loop ensembles: the Markovian characterization and the loop-soup construction.  Ann. Math. (2), 176(3):1827–1917, 2012.
  * [25] M. Talagrand.  The supremum of some canonical processes.  Am. J. Math., 116(2):283–325, 1994.
  * [26] V. A. Vatutin and V. Wachtel.  Local probabilities for random walks conditioned to stay positive.  Probab. Theory Relat. Fields, 143(1-2):177–217, 2009.
  * [27] Y. Watabiki.  Construction of non-critical string field theory by transfer matrix formalism in dynamical triangulation.  Nucl. Phys., B, 441(1-2):119–163, 1995.