# Word Discovery in Visually Grounded, Self-Supervised Speech Models

###### Abstract

We present a method for visually-grounded spoken term discovery. After
training either a HuBERT or wav2vec2.0 model to associate spoken captions with
natural images, we show that powerful word segmentation and clustering
capability emerges within the model’s self-attention heads. Our experiments
reveal that this ability is not present to nearly the same extent in the base
HuBERT and wav2vec2.0 models, suggesting that the visual grounding task is a
crucial component of the word discovery capability we observe. We also
evaluate our method on the Buckeye word segmentation and ZeroSpeech spoken
term discovery tasks, where we perform on par with or better than currently
published methods on several metrics.

Index Terms: visually-grounded speech, spoken term discovery, speech
segmentation, self-supervised speech processing

##  1 Introduction and Related Work

The task of spoken term discovery involves starting with a corpus of
untranscribed, unsegmented speech audio data and developing an algorithm or
computational model that is capable of 1) inferring the temporal location of
each word boundary and 2) clustering the resulting speech segments into
categories that reflect word identity. The motivation behind this task is
twofold. First, a model capable of solving this problem would be immensely
useful for building speech understanding systems using a limited amount of
transcribed data that could be applied to low-resource languages and domains.
Second, the model could be used by cognitive science researchers as a model
for the process by which human children acquire spoken language [1].

The spoken term discovery task has a long history dating back at least to the
seminal work of Park and Glass [2], who proposed a segmental dynamic time
warping algorithm to solve both the segmentation and clustering sub-tasks. In
the time since then, numerous other approaches have been proposed, based on
techniques such as refinements to the S-DTW algorithm [3], Bayesian
probabilistic models [4, 5], dynamic programming algorithms [6, 7, 8] and
contrastive predictive coding with neural models [9, 10, 11]. The ZeroSpeech
[12] challenge was also introduced to provide a standard benchmark to the
community for the word discovery task, in addition to other related tasks in
zero-resource speech processing.

A separate line of research has investigated training speech models using a
visual grounding (VG) objective [13, 14, 15, 16]. Given untranscribed,
unsegmented speech that semantically describes an auxiliary input from the
visual modality, a model is trained to associate the inputs together. Numerous
works have demonstrated that these models’ learned representations capture
linguistic abstractions such as phonemes and words [17, 18, 19, 20, 21, 22,
23, 24, 25], but so far none of them have explicitly used a VG model on the
spoken term discovery task.

In this paper, we present a method for visually-grounded spoken term
discovery111code and model weights will be made available at
https://github.com/jasonppy/word-discovery using a Transformer [26] model. Our
method is simple: it simply involves applying a binary threshold to the self-
attention maps produced by the model, and extracting contiguous temporal
regions of the speech signal with attention scores above the threshold. We
find that these segments accurately predict both the boundaries and identity
of the underlying words, which we verify with a suite of experiments on the
SpokenCOCO dataset. Additionally, we evaluate our proposed method on the
Buckeye word segmentation [27] and ZeroSpeech [12] English spoken term
discovery tasks, and find in both cases it significantly outperforms the
current state-of-the-art, non-visually-grounded models from the literature.

##  2 Models

Our model has a simple Transformer-based dual-encoder architecture consisting
of an audio encoder and an image encoder. The model takes as input a raw
speech waveform $A$ and an image $I$, and outputs a similarity score that
should be large when the speech faithfully describes the content of the image,
and small otherwise. The audio encoder has the same architecture as the
wav2vec2.0 (W2V2) and HuBERT Base models. The input speech utterance is
represented as waveform samples which are processed by a convolutional block
to obtain features of a higher temporal resolution. Convolutional positional
embeddings are added to the output features. We then follow [28] and augment
the features with a [CLS_A] token before feeding them to the stack of
Transformer layers. The image encoder is a Vision Transformer (ViT) [29, 30].
It takes an RGB image and splits it into a grid of non-overlapping patches,
then uses a linear layer to embed the patches into a sequence of feature
vectors. Trainable positional embeddings are added to the features, which are
then concatenated with a [CLS_I] token before being fed to the Transformer
layers. The similarity score between image $I$ and audio $A$ is defined as the
dot product of [CLS_I] and [CLS_A]. Given parallel speech-image data, we can
train the model using the InfoNCE loss[9, 31], where positive samples are
matched pairs and negative samples unmatched pairs. The loss encourages high
similarity scores between matched image-speech pairs and low similarity scores
otherwise.

Unlike most models used in vision and language research, none of the modules
in our model are pretrained on any supervised tasks such as image
classification, object detection or automatic speech recognition. Both our
image and audio encoders are pretrained in a completely self-supervised
fashion. We will refer to our visually-grounded variants of HuBERT and W2V2 as
VG-HuBERT and VG-W2V2. As will be shown in section 3, similar to [32], we
found that reinitializing the last few Transformer layers of the pretrained
HuBERT or W2V2 with random weights can significantly improve the word
discovery performance. We name models that reinitialize weights of the last
$x$ Transformer layers $\text{VG-HuBERT}_{x}$ and $\text{VG-W2V2}_{x}$.

##  3 Experiments

Datasets. We train our models on the visual grounding task with the Karpathy
training split [33] of the SpokenCOCO dataset [34]. SpokenCOCO contains $123$k
images, each with $5$ spoken captions produced by humans speaking aloud the
text captions in MSCOCO [35]. We evaluate our model using both speech-image
retrieval and word discovery tasks on the SpokenCOCO Karpathy test set. We
additionally evaluate our model on the spoken term discovery task using a 6
hour test set [8] of the Buckeye corpus [27], as well as the ZeroSpeech 2020
[12] spoken term discovery evaluation split.

Implementation Details. Our image encoder inherits the architecture and is
initialized from the DINO [30] self-supervised Vision Transformer. In
particular, we initialize the image encoder weights from DINO-ViT small with
patch size 8x8. The model consists of a linear embedding layer, a learnable
positional embedding, and a $12$-layer transformer with hidden dimension of
$384$ and $6$ attention heads. The audio encoder inherits its architecture and
initial weights from HuBERT (or W2V2) Base, which contains a $7$-layer
convolutional block, and a $12$-layer Transformer with a hidden dimension of
$786$ and $12$ attention heads. We project the output [CLS_I] and [CLS_A]
separately using $2$-layer MLPs to a $2048$ dimensional space before taking
their dot product. Models are trained on the visual grounding task with batch
size $100$ for $30$ epochs. We optimize with BertAdam [36] using a learning
rate linearly ramped up $5e-5$ over the first 10% of training, and then
linearly decayed to $0$. Except for the convolutional block in the audio
encoder that is frozen, all other layers are trainable.

Retrieval Performance. As an initial sanity check, we first quantify how well
our models learn to associate spoken descriptions with images by evaluating
them on an image-speech retrieval task. We report Recall@K for $K=1,5,10$ in
Table 1. Although VG-HuBERT and $\text{VG-HuBERT}_{3}$ do not use any
supervised vision modules, they still perform relatively well on this
benchmark compared to $\text{FaST-VGS}_{\text{CO}}$, which is the current SoTA
dual-encoder retrieval model that uses a pretrained Faster RCNN for image
feature extraction.

Table 1: Comparison of VG-HuBERT with other models on the 1k retrieval task on
the SpokenCOCO test set.

|  Speech $\rightarrow$ Image |  Image $\rightarrow$ Speech
---|---|---
Model | R@1 | R@5 | R@10 | R@1 | R@5 | R@10
ResDAVEnet [37] | 17.3 | 41.9 | 55.0 | 22.0 | 50.6 | 65.2
$\text{FaST-VGS}_{\text{CO}}$ [28] | 31.8 | 62.5 | 75.0 | 42.5 | 73.7 | 84.9
$\text{FaST-VGS}_{\text{CTF}}$ [28] | 35.9 | 66.3 | 77.9 | 48.8 | 78.2 | 87.0
VG-HuBERT | 30.4 | 60.7 | 72.7 | 42.7 | 73.6 | 84.1
$\text{VG-HuBERT}_{3}$ | 30.6 | 60.8 | 72.8 | 42.8 | 73.5 | 83.9

Table 2: Different models evaluated on their word discovery ability on the on
SpokenCOCO test. $\pm$ indicates the standard deviation across 5 clustering
runs with different random seeds; all models used 4096 k-means clusters.
HuBERTFT and W2V2FT indicate models that were further fine-tuned on the
SpokenCOCO audio captions.

| Area | Boundary | Word
---|---|---|---
Model | WC | tIoU | CD (ms) | A-score | Precision | Recall | $F_{1}$ | OS |  $R$-val | Purity | WD
ResDAVEnet-VQ [38] | 98.39 | 23.78 | 119.4 | 38.30 | 10.42 | 50.96 | 17.30 | 38.88 | -250.77 |  31.6 $\pm$ 0 | 262 $\pm$ 0
W2V2 [39] | 77.68 | 38.56 | 111.9 | 51.54 | 11.52 | 24.33 | 15.63 | 11.12 | -33.34 |  41.2 $\pm$ 0.3 | 407 $\pm$ 13
$\text{W2V2}_{\text{FT}}$ [39] | 73.96 | 39.87 | 116.1 | 51.81 | 11.88 | 24.79 | 16.06 | 10.87 | -31.10 |  43.0 $\pm$ 0.1 | 397 $\pm$ 11
HuBERT [40] | 72.63 | 37.72 | 117.9 | 49.66 | 12.18 | 24.97 | 16.37 | 10.51 | -28.26 |  43.1 $\pm$ 0.2 | 404 $\pm$ 12
$\text{HuBERT}_{\text{FT}}$ [40] | 73.78 | 39.31 | 116.0 | 51.30 | 11.90 | 25.81 | 16.29 | 11.68 | -36.72 |  45.3 $\pm$ 0.3 | 500 $\pm$ 9
FaST-VGS [28] | 75.92 | 54.86 | 67.8 | 63.69 | 28.99 | 26.17 | 27.51 | -9.72 | 40.10 |  70.9 $\pm$ 0.5 | 1011 $\pm$ 12
FaST-VGS+ [41] | 77.40 | 51.46 | 80.5 | 61.82 | 22.66 | 27.86 | 24.99 | 22.93 | 28.54 |  72.3 $\pm$ 0.3 | 1026 $\pm$ 12
VG-W2V2 | 65.94 | 45.56 | 76.8 | 53.89 | 18.47 | 19.78 | 19.10 | 7.09 | 28.86 |  62.5 $\pm$ 0.4 | 743 $\pm$ 14
$\text{VG-W2V2}_{4}$ | 71.28 | 54.06 | 82.0 | 61.49 | 28.15 | 22.90 | 25.26 | -18.64 | 39.67 |  73.0 $\pm$ 0.3 |  1182 $\pm$ 20
$\text{VG-W2V2}_{5}$ | 73.32 | 53.09 | 72.2 | 61.58 | 28.70 | 25.45 | 26.98 | -11.32 | 39.94 |  75.4 $\pm$ 0.1 | 1149 $\pm$ 16
VG-HuBERT | 73.16 | 44.02 | 89.0 | 54.97 | 18.31 | 18.90 | 18.60 | 3.26 | 29.60 |  63.2 $\pm$ 0.4 | 823 $\pm$ 20
$\text{VG-HuBERT}_{3}$ | 70.94 | 61.29 | 64.6 | 65.77 | 35.90 | 27.03 | 30.84 | -24.72 | 44.42 |  75.3 $\pm$ 0.2 | 1167 $\pm$ 26
$\text{VG-HuBERT}_{4}$ | 73.97 | 56.35 | 78.9 | 63.97 | 28.39 | 25.64 | 26.94 | -9.70 | 39.64 |  75.2 $\pm$ 0.2 | 1230 $\pm$ 18

Word Discovery. The main focus of this paper is studying the emergence of word
segmentation in visually grounded speech models (the image branch is not used
in any word discovery experiment). We first discovered this phenomenon by
plotting the [CLS_A] token’s attention weight across each temporal frame of
the speech at layer $y$ of the audio encoder; Figure 1 displays several
examples using $y=12$ from the $\text{VG-HuBERT}_{3}$ model. We threshold the
weights to retain only the top $z\%$ of the total attention weight for each
attention head ($z=10$). The ground truth transcripts and force aligned word
boundaries (red dashed lines) are also plotted for reference. Figure
LABEL:fig:girl_lighthouse is generated the same way with $y=9,z=10$. Although
we do not impose any constraints on the attention weights except for the
thresholding described above, the visualization shows that the our model
exhibits word localization, segmentation, and identification as it puts chunks
of attention associated with different heads (indicated by different colors)
under different words. In the following paragraphs, we pose several questions
and metrics to quantitatively investigate these phenomena.

Figure 1: Examples of CLS attention segments from SpokenCOCO, the bottom one
also show how word boundaries are generated from attention segments

1\. Does the model’s attention map indicate the presence of words? We define
two metrics to study this question: word coverage (WC), defined as
$\frac{\\#\text{hits}}{\\#\text{words}}$, where $\\#\text{hits}$ is the number
of times the model assigns one or more attention segments to a word, and
$\\#\text{words}$ is the count of total words in the corpus. We define an
attention segment to be a consecutive sequence of frames with nonzero
attention weights (after thresholding has been applied), and consider a
segment to be assigned to a particular word if more than half of the segment’s
length falls between the ground-truth boundaries of that word. We also define
Temporal intersection over union (tIoU) as
$\frac{1}{|\mathcal{S}|}\sum_{s\in\mathcal{S}}\frac{s\cap w_{s}}{s\cup
w_{s}}$, where $\mathcal{S}$ is the set of all attention segments, $w_{s}$ is
the word that attention segment $s$ is assigned to, and the output of the
intersection (or union) operation is the duration in frames of the
intersection (or union) between the segment spanned by $w_{s}$ and the segment
spanned by $s$. WC and tIoU are complementary to each other — WC reflects how
good the model is at detecting all words within an utterance, and tIoU shows
how good the model is at localizing the span of each word it detects. A model
could achieve a high WC if it assigns an attention segment every few frames
(similar to HuBERT’s attention map shown in Figure LABEL:fig:girl_lighthouse),
but this will lead to a low tIoU; on the other hand, a model might achieve a
good tIoU score if it ignores most words, and places attention segments only
under the words that it is very confident about (e.g. salient visual words).
To balance these metrics, we introduce a summary metric named area score
(A-score), defined as the harmonic mean of WC and tIoU, i.e.
$\text{A-score}=\frac{2\text{WC}\cdot\text{tIoU}}{\text{WC}+\text{tIoU}}$. In
addition, we also show center distance (CD) which is defined as the average
distance in milliseconds between the center of each attention segment and
center of the word that the segment is assigned to. We group the all above
metrics under the name “Area”.

Table 3: Performance of $\text{VG-HuBERT}_{x}$ on SpokenCOCO validation set.

| Area | Boundary | Word
---|---|---|---
reinit last x | WC | tIoU | A-score | $F_{1}$ | WD
x=0 | 73.21 | 44.16 | 55.09 | 18.46 | 817
x=1 | 69.29 | 51.88 | 59.33 | 22.17 | 1003
x=2 | 69.63 | 57.73 | 63.12 | 28.52 | 1036
x=3 | 70.95 | 61.51 | 65.91 | 31.07 | 1169
x=4 | 73.90 | 56.32 | 63.92 | 27.02 | 1229
x=5 | 74.92 | 54.44 | 63.05 | 25.52 | 1044
x=6 | 73.43 | 51.38 | 60.45 | 23.30 | 879

Figure 2: #WD given by $\text{VG-HuBERT}_{x}$ with varied #K-means clusters.

Figure 3: #WD given by different models across all layers.

2\. Can we use the model to identify word boundaries? Here, we are interested
in seeing whether we can use the model to precisely predict the onset and
offset of each word in an utterance. For evaluation, we use the standard
boundary precision, recall, $\bm{F_{1}}$, over-segmentation (OS), and
$\bm{R}$-value metrics [8]. These metrics are quite strict and only assume a
very small tolerance window (20ms for SpokenCOCO and Buckeye [8] and 30ms for
ZeroSpeech [12]). However, we note that visually, the boundaries of our
thresholded attention segments are typically narrower than the words they are
assigned to. To address this, we instead infer word boundaries to be the
midpoints between the edges of adjacent attention segments (example shown at
the bottom in Figure 1). We group the metrics used for studying question 2
under the name “Boundary”.

3\. Can the model determine word identity? Here, we use the word detection
evaluation introduced by [38]. To do so, we first average pool the
representations belonging to each attention segment to obtain a single feature
vector representing that segment. We apply this procedure to all utterances in
the SpokenCOCO test set, and then use a K-means clustering algorithm to group
all of the segments across the test set. Next, following [38], we consider
each cluster as a potential “detector” for every different vocabulary word
appearing in the ground-truth transcripts. We compute precision, recall, and
F1 scores for each unique cluster-word pair, and consider a cluster to be a
“word detector” if it achieves an F1 score greater than or equal to 0.5 for
some vocabulary word. Finally, we count the number of word-detecting clusters
and report that as the word detection (WD) score. We additionally report
cluster purity (in terms of the identity of each attention segment’s assigned
word) as a way of measuring the clustering performance. We group the metrics
used for studying word detection under the name “Word”.

Hyperparameter tuning. Performance on all of the above metrics depends on the
model layer being examined, as well as the threshold applied to the attention
maps. We tune these hyperparameters on the SpokenCOCO dev set separately for
each metric group (Area, Boundary, and Word), respectively optimizing for
A-score, boundary F1, and the number of word detectors found. During this
tuning, we consider all 12 Transformer layers. For the attention threshold we
sweep the threshold between 0.5 and 0.99. After tuning, we report all final
results on the SpokenCOCO test set.

Results on SpokenCOCO. We summarize our results across the Area, Boundary, and
Word metrics on the SpokenCOCO test dataset in Table 2. We compare against
several visually-grounded baseline models from the literature, including
ResDAVEnet-VQ [19], FaST-VGS [28] and FaST-VGS+ [41]. For ResDAVEnet-VQ, we
use the layer 3 representations from the $\\{3\\}\rightarrow\\{2,3\\}$ model
from [19] distributed by the authors as it achieved the highest word detection
performance in [19]. We first fine-tune ResDAVEnet-VQ on the SpokenCOCO data
and then derive segments from consecutive frames assigned to the same VQ3
codebook entry. For the FaST-VGS models, we consider all layers of the trm1
module and report results for layer achieving the best results on the dev set.
Because trm1 is also a transformer stack augmented with a [CLS_A] token, we
derive attention segments from these models in the same manner as for VG-
HuBERT. Finally, we compare against the Librispeech-pretrained HuBERT and
wav2vec2.0 Base models, and these models fine-tuned on audio of SpokenCOCO.
Although these are non-visually grounded models, they share the same
architecture as VG-HuBERT and VG-W2V2 so making this comparison allows us to
probe whether the same architecture trained solely with a masked language
modeling objective will still exhibit emergent word discovery ability in its
self-attention maps. Because W2V2 and HuBERT don’t use a [CLS_A] token, we use
the sum of attention weights each frame receives from other frames (separate
summation for each attention head) to get the self-attention map, and then
segments are derived in the same manner as for VG-HuBERT.

In Table 2, we first note that the highest overall performance for the Area
and Boundary metrics is achieved by the VG-HuBERT3 model, while the highest
performance for the Word metrics is achieved by the VG-HuBERT4 model. For both
VG-HuBERT and VG-W2V2, we find that reinitializing the last few layers before
training on the visual grounding task is highly beneficial, which is in line
with the results found by [32]. A more extensive comparison of layer
reinitialization is shown in Table 3. ResDAVEnet-VQ, W2V2, and HuBERT all have
a low A-score, mainly due to a low tIoU, which indicates their relative
inability to segment words; this is further confirmed by their low boundary F1
scores. In Figure LABEL:fig:girl_lighthouse, we visually see that the
attention segments produced by HuBERT are highly fragmented and do not clearly
correspond to words. Despite this, both HuBERT and W2V2 achieve nontrivial
word detection results, outperforming the ResDAVEnet-VQ model but
significantly underperforming VG-HuBERT, VG-W2V2, and FaST-VGS, all of which
learn more than twice as many word detectors as HuBERT. This indicates that
the masked language modeling objective used to train HuBERT and W2V2 does
result in representations strong enough to capture word identity, but the
visual grounding objective appears to be significantly more powerful in this
respect. Additionally, the visual grounding objective leads to the emergence
of word segmentation ability, whereas the masked language modeling objective
does not. Finally, in comparing to FaST-VGS and FaST-VGS+ we note that these
models use a strongly supervised vision module (Faster RCNN), whereas VG-
HuBERT and VG-W2V2 are fully self-supervised and yet still outperform FaST-VGS
and FaST-VGS+ across all metrics.

In Figures 3 and 3, we examine the word detection performance of various
models across different Transformer layers and as we vary the number of
K-means clusters. Although increasing the number of clusters does lead to a
larger number of detectors (Figure 3), we see significant diminishing returns
and thus fix $K=4096$ in all of our experiments, unless stated otherwise. In
Figure 3, we see that for all models, word detection performance is best in
the middle and upper half of the model, which is also consistent with the
analysis of [32] Finally, we compare the word detection performance of VG-
HuBERT when using oracle word boundaries to determine segments (rather than
the model’s thresholded self-attention), which we counterintuitively find
hurts the model’s word detection ability. Combined with the observation that
the attention segments tend to concentrate at the nucleus of words, we
hypothesize that the model’s contextualization is pushing word identity
information towards the temporal center of each word.

Table 4: Results on ZeroSpeech 2020 spoken term discovery.

| Words | NED | Cov | M-score | Prec. | Rec. | $F_{1}$
---|---|---|---|---|---|---|---
J.V. [42] | 18821 | 32.4 | 7.9 | 14.1 | 32.1 | 3.2 | 5.9
Granada et al. | 92544 | 72.0 | 76.9 | 41.1 | 30.7 | 43.8 | 36.1
Räsänen et al. | 321603 | 52.5 | 28.7 | 35.8 | 23.9 | 24.2 | 24.1
ES-KMeans [6] | 42473 | 73.2 | 100.0 | 42.3 | 49.4 | 66.8 | 56.7
SEA [43] | 240033 | 89.5 | 99.5 | 19.0 | 32.5 | 78.9 | 46.1
PDTW [44] | 85425 | 48.2 | 85.4 | 64.5 | 26.5 | 88.2 | 40.8
$\text{VG-HuBERT}_{3}$ (Ours) | 104696 | 42.5 | 95.4 | 71.8 | 44.7 | 54.2 | 49.0

Table 5: Unsupervised word segmentation on Buckeye test set.

| Boundary | Token
---|---|---
Model | Prec. | Rec. | $F_{1}$ |  $R$-val. | $F_{1}$
Adaptor gram. [45] | 15.9 | 57.7 | 25.0 | -139.9 | 4.4
SylSeg [46] | 27.7 | 28.9 | 28.3 | 37.7 | 19.3
ES-KMeans [6] | 30.3 | 16.6 | 21.4 | 39.1 | 19.2
BES-GMM [5] | 31.5 | 12.4 | 17.8 | 37.2 | 18.6
SCPC [47] | 36.9 | 29.9 | 33.0 | 45.6 | -
mACPC [10] | 42.1 | 30.3 | 35.1 | 47.4 | -
DPDP [8] | 35.3 | 37.7 | 36.4 | 44.3 | 25.0
$\text{VG-HuBERT}_{3}$ (Ours) | 36.2 | 32.2 | 34.1 | 45.6 | 24.1

Results on Buckeye and ZeroSpeech 2020. Finally, we test our best performing
model ($\text{VG-HuBERT}_{3}$) 222we use model’s best word segmentation
hyperparams, max-pooling instead of mean-pooling for segment features, and
16384 clusters for K-means., on two additional benchmarks: the ZeroSpeech 2020
spoken term discovery track (English) and the Buckeye word segmentation
task333we make use of https://github.com/kamperh/vqwordseg.

Table 4 shows model performance on ZeroSpeech, where following the official
challenge leaderboard and [44], we report number of discovered words (Word),
phoneme level normalized edit distance (NED) of the discovered segment pairs,
coverage of the discovered segments (Cov) w.r.t. all utterances in the given
corpus, and also word segmentation performance (precision, recall, F-score).
We also report M-score [44], which is the harmonic mean of (100 - NED) and Cov
that summarizes the trade-off between purity and coverage (similar to A-score
we used for previous evaluation). We see that $\text{VG-HuBERT}_{3}$ achieves
the highest M-score and second best boundary $F_{1}$.

Table 5 shows word segmentation performance on Buckeye test set, where we
again report boundary precision, recall, and $F_{1}$. Token $F_{1}$ is harsher
metric where both left and right boundaries of a word need to be successfully
predicted. We see that our $\text{VG-HuBERT}_{3}$ performs competitively
compared to the state of the art approaches on Boundary $F_{1}$, $R$-value,
and Token $F_{1}$.

Importantly, we note that all other models in Table 4 and 5 are unimodal
models, i.e. they are only trained on the audio modality, while our model uses
the visual modality during training (visual modality is not needed during
testing). On the other hand, these other models are explicitly designed for
word discovery and segmentation via specific mechanisms or learning
objectives, while our model is instead trained with a cross-modal grounding
objective. Our experiments demonstrate that this objective, combined with the
Transformer architecture pre-trained on a masked language modeling task,
facilitates emergent word discovery ability from raw speech signals.

##  4 Conclusion and Future Directions

In this paper, we demonstrated that training the popular HuBERT and wav2vec2.0
models on a visual grounding task resulted in them learning to automatically
discover (localize, segment, and identify) words in the speech signal. We
verified that this same ability did not exist in the models prior to them
undergoing training on the visual grounding task, suggesting that a
combination of multiple self-supervised objectives may be essential in order
for a computational model to learn the structure of spoken language from
untranscriped speech audio.

In our future work, we plan to use the word-level representations learned by
our model to anchor the learning of sub-word structure (e.g. automatically
learning a pronunciation lexicon in terms of discovered speech units) as well
as the higher level syntactic structure of spoken language. We also plan to
investigate whether a similar method to the one we propose could facilitate
visual object discovery, and also explore applications of our method to low-
resource ASR.

##  5 Acknowledgements

We thank Abdelrahman Mohamed, Karen Livescu, Haoyue Freda Shi, Cheng-I Jeff
Lai, and Bowen Shi for their insights.

## References

  * [1] E. Dupoux, “Cognitive science in the era of artificial intelligence: A roadmap for reverse-engineering the infant language-learner,” in _Cognition_ , 2018\.
  * [2] A. S. Park and J. R. Glass, “Unsupervised pattern discovery in speech,” _TASLP_ , vol. 16, no. 1, pp. 186–197, 2008.
  * [3] A. Jansen, K. W. Church, and H. Hermansky, “Towards spoken term discovery at scale with zero resources,” in _INTERSPEECH_ , 2010.
  * [4] C.-y. Lee, T. J. O’Donnell, and J. Glass, “Unsupervised lexicon discovery from acoustic input,” _TACL_ , vol. 3, pp. 389–403, 2015.
  * [5] H. Kamper, A. Jansen, and S. Goldwater, “A segmental framework for fully-unsupervised large-vocabulary speech recognition,” _Computer Speech & Language_, 2017.
  * [6] H. Kamper, K. Livescu, and S. Goldwater, “An embedded segmental k-means model for unsupervised segmentation and clustering of speech,” in _ASRU_ , 2017\.
  * [7] H. Kamper and B. van Niekerk, “Towards unsupervised phone and word segmentation using self-supervised vector-quantized neural networks,” in _Interspeech_ , 2021.
  * [8] H. Kamper, “Word segmentation on discovered phone units with dynamic programming and self-supervised scoring,” _ArXiv_ , vol. abs/2202.11929, 2022\.
  * [9] A. van den Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” _CoRR_ , vol. abs/1807.03748.
  * [10] S. Cuervo, M. Grabias, J. Chorowski, G. Ciesielski, A. La’ncucki, P. Rychlikowski, and R. Marxer, “Contrastive prediction strategies for unsupervised segmentation and categorization of phonemes and words,” _ArXiv_ , vol. abs/2110.15909, 2021.
  * [11] S. Bhati, J. Villalba, P. Żelasko, L. Moro-Velázquez, and N. Dehak, “Segmental contrastive predictive coding for unsupervised word segmentation,” in _Interspeech_ , 2021.
  * [12] M. Versteegh, R. Thiollière, T. Schatz, X.-N. Cao, X. A. Miró, A. Jansen, and E. Dupoux, “The zero resource speech challenge 2017,” _ASRU_ , 2017.
  * [13] G. Synnaeve, M. Versteegh, and E. Dupoux, “Learning words from images and speech,” 2014.
  * [14] D. F. Harwath and J. R. Glass, “Deep multimodal semantic embeddings for speech and images,” _ASRU_ , 2015.
  * [15] D. F. Harwath, A. Torralba, and J. R. Glass, “Unsupervised learning of spoken language with visual context,” in _NIPS_ , 2016.
  * [16] G. Chrupała, “Visually grounded models of spoken language: A survey of datasets, architectures and evaluation techniques,” _JAIR_ , vol. 73, pp. 673–707, 2022.
  * [17] D. Harwath, A. Recasens, D. Surís, G. Chuang, A. Torralba, and J. Glass, “Jointly discovering visual objects and spoken words from raw sensory input,” _ECCV_ , 2018.
  * [18] W. N. Havard, J.-P. Chevrot, and L. Besacier, “Word recognition, competition, and activation in a model of visually grounded speech,” in _CoNLL_ , 2019\.
  * [19] D. F. Harwath, W.-N. Hsu, and J. R. Glass, “Learning hierarchical discrete linguistic units from visually-grounded speech,” in _ICLR_ , 2020.
  * [20] K. Khorrami and O. J. Räsänen, “Can phones, syllables, and words emerge as side-products of cross-situational audiovisual learning? - a computational investigation,” _ArXiv_ , vol. abs/2109.14200, 2021.
  * [21] G. C. Mitja Nikolaus, Afra Alishahi, “Learning english with peppa pig,” _ArXiv_ , vol. abs/2202.12917, 2022.
  * [22] S. Scholten, D. Merkx, and O. Scharenborg, “Learning to recognise words using visually grounded speech,” _ISCAS_ , 2021.
  * [23] K. Olaleye and H. Kamper, “Attention-based keyword localisation in speech using visual grounding,” in _Interspeech_ , 2021.
  * [24] L. Wang and M. Hasegawa-Johnson, “A translation framework for visually grounded spoken unit discovery,” in _ACSSC_ , 2021.
  * [25] A. H. Liu, S. Jin, C.-I. Lai, A. Rouditchenko, A. Oliva, and J. R. Glass, “Cross-modal discrete representation learning,” _ArXiv_ , vol. abs/2106.05438, 2021.
  * [26] A. Vaswani, N. M. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NeurIPS_ , 2017.
  * [27] M. Pitt, K. Johnson, E. Hume, S. F. Kiesling, and W. Raymond, “The Buckeye corpus of conversational speech: labeling conventions and a test of transcriber reliability,” _Speech Commun._ , 2005.
  * [28] P. Peng and D. Harwath, “Fast-slow transformer for visually grounding speech,” in _ICASSP_ , 2022.
  * [29] Alexey Dosovitskiy et al., “An image is worth 16x16 words: Transformers for image recognition at scale,” in _ICLR_ , 2021.
  * [30] M. Caron, H. Touvron, I. Misra, H. J’egou, J. Mairal, P. Bojanowski, and A. Joulin, “Emerging properties in self-supervised vision transformers,” in _ICCV_ , 2021.
  * [31] G. Ilharco, Y. Zhang, and J. Baldridge, “Large-scale representation learning from visually grounded untranscribed speech,” in _CoNLL_ , 2019.
  * [32] A. Pasad, J.-C. Chou, and K. Livescu, “Layer-wise analysis of a self-supervised speech representation model,” in _ASRU_ , 2021.
  * [33] A. Karpathy and L. Fei-Fei, “Deep visual-semantic alignments for generating image descriptions,” _TPAMI_ , 2017.
  * [34] W.-N. Hsu, D. F. Harwath, C. Song, and J. Glass, “Text-free image-to-speech synthesis using learned segmental units,” in _ACL_ , 2021.
  * [35] T.-Y. Lin, M. Maire, S. J. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in _ECCV_ , 2014.
  * [36] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in _NAACL_ , 2019\.
  * [37] W.-N. Hsu, D. F. Harwath, and J. Glass, “Transfer learning from audio-visual grounding to speech recognition,” in _INTERSPEECH_ , 2019.
  * [38] D. Harwath, W.-N. Hsu, and J. Glass, “Learning hierarchical discrete linguistic units from visually-grounded speech,” in _ICLR_ , 2020.
  * [39] A. Baevski, H. Zhou, A. Mohamed, and M. Auli, “wav2vec 2.0: A framework for self-supervised learning of speech representations,” in _NeurIPS_ , 2020\.
  * [40] W.-N. Hsu, B. Bolte, Y.-H. H. Tsai, K. Lakhotia, R. Salakhutdinov, and A. Mohamed, “Hubert: Self-supervised speech representation learning by masked prediction of hidden units,” 2021.
  * [41] P. Peng and D. Harwath, “Self-supervised representation learning for speech using visual grounding and masked language modeling,” in _SAS@AAAI_ , 2022\.
  * [42] A. Jansen and B. Van Durme, “Efficient spoken term discovery using randomized algorithms,” in _ASRU_ , 2011.
  * [43] S. Bhati, J. Villalba, P. Żelasko, and N. Dehak, “Self-expressing autoencoders for unsupervised spoken term discovery,” in _Interspeech_ , 2020\.
  * [44] O. J. Räsänen and M. A. C. Blandón, “Unsupervised discovery of recurring speech patterns using probabilistic adaptive metrics,” in _Interspeech_ , 2020.
  * [45] A. J. et al., “A summary of the 2012 jhu clsp workshop on zero resource speech technologies and models of early language acquisition,” in _ICASSP_ , 2013\.
  * [46] O. Räsänen, G. Doyle, and M. C. Frank, “Unsupervised word discovery from speech using automatic segmentation into syllable-like units,” in _Interspeech_ , 2015.
  * [47] S. Bhati, J. Villalba, P. Żelasko, L. Moro-Velázquez, and N. Dehak, “Segmental contrastive predictive coding for unsupervised word segmentation,” in _Interspeech_ , 2021.


# On random irregular subgraphs

Jacob Fox Department of Mathematics, Stanford University, Stanford, CA 94305.
Email<EMAIL_ADDRESS>Research supported by a Packard Fellowship and
by NSF Awards DMS-1800053 and DMS-2154169. Sammy Luo Department of
Mathematics, Stanford University, Stanford, CA 94305. Email:
<EMAIL_ADDRESS>Research supported by NSF GRFP Grant DGE-1656518. Huy
Tuan Pham Department of Mathematics, Stanford University, Stanford, CA 94305.
Email<EMAIL_ADDRESS>Research supported by a Two Sigma Fellowship.

###### Abstract

Let $G$ be a $d$-regular graph on $n$ vertices. Frieze, Gould, Karoński and
Pfender began the study of the following random spanning subgraph model
$H=H(G)$. Assign independently to each vertex $v$ of $G$ a uniform random
number $x(v)\in[0,1]$, and an edge $(u,v)$ of $G$ is an edge of $H$ if and
only if $x(u)+x(v)\geq 1$. Addressing a problem of Alon and Wei, we prove that
if $d=o(n/(\log n)^{12})$, then with high probability, for each nonnegative
integer $k\leq d$, there are $(1+o(1))n/(d+1)$ vertices of degree $k$ in $H$.

##  1 Introduction

Given a graph $H$ and a nonnegative integer $k$, let $m(H,k)$ be the number of
vertices in $H$ with degree $k$, and let $m(H)=\max_{k}m(H,k)$. It is well-
known that in any finite simple graph $H$, there is some pair of vertices with
the same degree, that is, $m(H)\geq 2$. Alon and Wei [1] initiated the study
of the following question: Given a $d$-regular graph $G$ on $n$ vertices, can
we find a spanning subgraph $H$ of $G$ such that $m(H)$ is as small as
possible? Since such a subgraph $H$ has maximum degree at most $d$, we clearly
have $m(H)\geq\frac{n}{d+1}$. Alon and Wei showed that this lower bound is in
fact nearly optimal by proving that every $d$-regular graph $G$ has a spanning
subgraph $H$ satisfying $m(H)\leq(1+o_{n}(1))\frac{n}{d+1}+2$ (in fact, it
suffices to assume that $G$ has minimum degree $d$). They conjectured that for
regular graphs, one can guarantee a stronger conclusion, that $m(H,k)$ is
close to $\frac{n}{d+1}$ for all $0\leq k\leq d$.

######  Conjecture 1.1 ([1], Conjecture 1.1).

Every $d$-regular graph $G$ on $n$ vertices contains a spanning subgraph $H$
such that

$\big{|}m(H,k)-\frac{n}{d+1}\big{|}\leq 2\qquad\text{for all }0\leq k\leq d.$

Loosely speaking, we describe a subgraph $H$ as _irregular_ when each $m(H,k)$
is close to $\frac{n}{d+1}$, as the degrees of its vertices are close to as
uniformly distributed as possible. While the argument of Alon and Wei provides
a nearly optimal upper bound to $m(H)$, it does not yield even the following
weaker asymptotic version of Conjecture 1.1 that they ask.

######  Conjecture 1.2 ([1]).

Let $d=o(n)$. Then every $d$-regular graph $G$ on $n$ vertices contains a
spanning subgraph $H$ such that

$m(H,k)=(1+o(1))\frac{n}{d+1}\qquad\text{for all }0\leq k\leq d.$ ($*$)

While both conjectures remain open, significant progress has been made on
Conjecture 1.2 in certain ranges of $d$. In fact, an earlier work of Frieze,
Gould, Karoński and Pfender [6] already gave a method for constructing a
random spanning subgraph $H$ satisfying ($*$ ‣ 1.2) whenever $d\leq(n/\log
n)^{1/4}$. This construction was motivated by their study of the _irregularity
strength_ $s(G)$ of a graph $G$, defined as the smallest integer $w$ such that
one can assign integer weights in $[w]$ to every edge of $G$ so that the sums
of the weights incident to each vertex are distinct. Faudree and Lehel
conjectured in [4] that there is some absolute constant $C$ such that
$s(G)\leq\frac{n}{d}+C$ whenever $G$ is a $d$-regular graph on $n$ vertices;
see [8, 9, 10] for recent progress on this conjecture.

The natural construction considered in [6] is as follows: For each vertex
$v\in V(G)$, pick a weight $x(v)\in[0,1]$ uniformly and independently at
random. Then, for each edge $(u,v)\in E(G)$, we keep it as an edge of $H$ if
and only if $x(u)+x(v)\geq 1$. We will henceforth refer to this construction
as the _irregular random subgraph_ model. It is easy to check that this model
satisfies at least the basic properties one would expect from a construction
of a very irregular subgraph. Indeed, fix $k\in\\{0,1,\ldots,d\\}$ and
consider the random variable $X=m(H,k)$. For a vertex $v$, let
${\mathbb{I}}_{v}$ be the indicator random variable for the event that $v$ has
degree $k$ in $H$. Then, $X=\sum_{v\in V(G)}{\mathbb{I}}_{v}$. Observe that
$v$ has degree $k$ in $H$ if and only if, among the set of $d+1$ numbers
consisting of $1-x(v)$ and the $d$ numbers $x(u)$ with $u$ a neighbor of $v$
in $G$, $1-x(v)$ is the $(k+1)^{th}$ largest. It follows that $v$ has degree
$k$ in $H$ with probability $1/(d+1)$. By linearity of expectation,
$\mathbb{E}[X]=n/(d+1)$. To give an asymptotically tight bound on $m(H,k)$, it
then remains to show that the random variable $X$ is well-concentrated around
this mean. The authors of [6] do so via an application of the Azuma-Hoeffding
inequality. In [1], Alon and Wei show a larger range of values of $d$ over
which ($*$ ‣ 1.2) holds with high probability in this construction by using a
more careful concentration argument. They start by equitably partitioning the
vertices of $G$ into $O(d^{2})$ disjoint sets $V_{i}$ such that within each
$V_{i}$, each pair of vertices has distance at least $3$, and thus the degrees
in $H$ of all vertices in $V_{i}$ are independent. This allows them to apply
Chernoff’s inequality to show that ($*$ ‣ 1.2) holds with high probability
whenever $d=o((n/\log n)^{1/3})$.

In this paper, we take a more direct approach to studying the concentration
properties of this irregular random subgraph model, showing the desired
asymptotic irregularity property for an even wider range of values of $d$.
First, we take a natural approach of applying the second moment method to
study the variance of the random variable $X$. We show that
$\operatorname{Var}(X)\leq\frac{17n}{d+1}=17{\mathbb{E}}[X]$, implying by
Chebyshev’s inequality and the union bound that ($*$ ‣ 1.2) holds with high
probability whenever $d=o(n^{1/2})$. This argument is detailed in Section 2.
However, one might conjecture much stronger concentration bounds to hold due
to exponential-type decay in the distribution of $X$. By using a much more
technical argument employing the martingale Bernstein inequality, we manage to
extend the result to all $d=o(n/(\log n)^{12})$, showing the following main
theorem.

######  Theorem 1.3.

Let $G$ be a $d$-regular graph on $n$ vertices with $d=o(n/(\log n)^{12})$.
Then with high probability, the irregular random subgraph $H=H(G)$ satisfies
that for $0\leq k\leq d$, the number of vertices with degree $k$ in $H$ is
$(1+o(1))n/(d+1)$.

In particular, this theorem confirms Conjecture 1.2 for all $d=o(n/(\log
n)^{12})$. We conjecture that the irregular random subgraph $H$ satisfies
Property $*$ ‣ 1.2 with high probability for all $d=o(n/\log n)$. On the other
hand, it is likely that for $d=\omega(n/\log n)$, the irregular random
subgraph model does not satisfy Property $*$ ‣ 1.2 with high probability, and
new ideas would be required to show Conjecture 1.2 in the full range.

The proof of Theorem 1.3 is in Section 3. Since these two arguments are more
or less independent, they can be read in any desired order.

##  2 The second moment argument

In this section, we prove Theorem 1.3 in the case $d=o(n^{1/2})$ through a
second moment argument. We establish the following bound on the variance of
the random variable $X=m(H,k)$.

######  Theorem 2.1.

Let $G$ be a $d$-regular graph on $n$ vertices, and let $H=H(G)$ be the
irregular random subgraph. Then for all $0\leq k\leq d$, the variance of the
random variable $X=m(H,k)$ is at most $17\frac{n}{d+1}$.

Recall that $X=\sum_{v\in V(G)}{\mathbb{I}}_{v}$, so

$\operatorname{Var}(X)=\mathbb{E}[X^{2}]-\mathbb{E}[X]^{2}=n/(d+1)+\sum_{u\not=v}\mathbb{E}[{\mathbb{I}}_{u}{\mathbb{I}}_{v}]-(n/(d+1))^{2}.$
(1)

We begin by establishing the following key lemma. It gives an upper bound on
the probability that two given vertices each have degree $k$ in the irregular
random subgraph model that depends on the codegree of the two vertices in $G$.
Recall that the codegree $d(u,v)$ is the number of common neighbors of
vertices $u$ and $v$ in graph $G$. For a vertex $u$ of $G$, let $N(u)$ denote
the neighborhood of $u$ in $G$ and $N_{+}(u)=N(u)\cup\\{u\\}$. We also use
$u\sim v$ to denote that vertices $u$ and $v$ are adjacent in graph $G$.

######  Lemma 2.2.

For any two vertices $u$ and $v$,

$\mathbb{E}[{\mathbb{I}}_{u}{\mathbb{I}}_{v}]\leq\frac{1}{(d+1)^{2}}\left(1+\frac{16d(u,v)}{d+1}\right).$

###### Proof.

We have ${\mathbb{I}}_{u}={\mathbb{I}}_{v}=1$ if and only if, for each
$w\in\\{u,v\\}$, $1-x(w)$ is the $(k+1)^{th}$ largest number among
$\\{1-x(w),x(z):z\sim w\\}$. Let $N_{u}=N(u)\setminus(N(v)\cup\\{v\\})$,
$N_{v}=N(v)\setminus(N(u)\cup\\{u\\})$, and $N_{u,v}=N(u)\cap N(v)$. Let
$t=d(u,v)$. We consider two cases based on the value of $t$.

Case 1: $t\geq d/2$.

Condition on an arbitrary realization of $x(z)$ for all $z\in N_{u}\cup
N_{v}$, and a realization of the set of values $S=\\{1-x(u),1-x(v),x(z):z\in
N_{u,v}\\}$ (but not the specific value of each $x(z)$ in this set, nor of
$x(u)$ or $x(v)$). As $1-x(u),1-x(v),x(z)$ for $z\in N(u)\cup
N(v)\setminus\\{u,v\\}$ are independent and identically distributed, the
conditional distribution of $(1-x(u),1-x(v),x(z):z\in N(u)\cap N(v))$ is given
by a uniformly random permutation of the values in $S$.

Let $r_{u}$ and $r_{v}$ be the positions of $1-x(u),1-x(v)$ realized in a
random permutation of the values in $S$ (when $S$ is ordered in non-increasing
order). When $u\nsim v$, there are at most two choices of $r_{u}$ and $r_{v}$
so that ${\mathbb{I}}_{u}={\mathbb{I}}_{v}=1$, depending on whether $1-x(u)$
and $1-x(v)$ need to be in the same position or different positions relative
to the other $x(z)$. When $u\sim v$, depending on whether $x(u)+x(v)\geq 1$,
the positions of $1-x(u)$ and $1-x(v)$ among $\\{1-x(u)\\}\cup N_{u}\cup
N_{u,v}$ and $\\{1-x(v)\\}\cup N_{v}\cup N_{u,v}$ respectively must either
both be $k^{th}$ largest or both be $(k+1)^{th}$ largest. For a fixed set of
values $S$, however, only one of these two cases can yield the correct final
ordering of $\\{1-x(u),x(z):z\sim u\\}$ and $\\{1-x(v),x(z):z\sim v\\}$, since
going from $k^{th}$ largest to $(k+1)^{th}$ largest means choosing strictly
smaller values for $1-x(u)$ and $1-x(v)$ among $S$, which increases
$x(u)+x(v)$. Thus, in any case, there are at most two choices of $r_{u}$ and
$r_{v}$ so that ${\mathbb{I}}_{u}={\mathbb{I}}_{v}=1$. Thus, the conditional
probability that ${\mathbb{I}}_{u}={\mathbb{I}}_{v}=1$ is at most
$2t!/(t+2)!<2/t^{2}$.

Case 2: $t<d/2$.

Condition on an arbitrary realization of $x(z)$ for all $z\in N_{u,v}$, and
for each $w\in\\{u,v\\}$, a realization of the set of values
$S_{w}=\\{1-x(w),x(z):z\in N_{w}\\}$ (but not the specific value of each
$x(z)$ in this set, nor of $x(w)$). As $1-x(u),1-x(v),x(z)$ for $z\in N(u)\cup
N(v)\setminus\\{u,v\\}$ are independent and identically distributed, the
conditional distributions of $(1-x(u),x(z):z\in N_{u})$ and $(1-x(v),x(z):z\in
N_{v})$ are uniformly and independently distributed among permutations of
$S_{u}$ and $S_{v}$.

Let $r_{u}$ and $r_{v}$ be the positions of $1-x(u),1-x(v)$ realized in random
permutations of the values in $S_{u}$ and $S_{v}$ respectively. If $u$ and $v$
are not adjacent, there is a unique choice of $(r_{u},r_{v})$ so that
${\mathbb{I}}_{u}={\mathbb{I}}_{v}=1$, while if $u$ and $v$ are adjacent, as
in the previous case we have two possible pairs of positions, but at most one
pair can be valid given the set of values in $S_{u}$ and $S_{v}$. Thus, the
conditional probability that ${\mathbb{I}}_{u}={\mathbb{I}}_{v}=1$ is at most
$1/(d-t)^{2}$.

Hence, in both cases, we obtain

$\mathbb{E}[{\mathbb{I}}_{u}{\mathbb{I}}_{v}]\leq\frac{1}{(d+1)^{2}}\left(1+\frac{16t}{d+1}\right).$

∎

From Lemma 2.2, the desired bound on $\operatorname{Var}(X)$ follows.

###### Proof of Theorem 2.1.

By Lemma 2.2,

$\displaystyle\mathbb{E}[X^{2}]$ $\displaystyle\leq\frac{n}{d+1}+\sum_{u\neq
v}\frac{1}{(d+1)^{2}}\left(1+\frac{16d(u,v)}{d+1}\right)$
$\displaystyle=\frac{n}{d+1}+\frac{16}{(d+1)^{3}}\sum_{u\neq
v}d(u,v)+\frac{n(n-1)}{(d+1)^{2}}$
$\displaystyle=\frac{n}{d+1}+\frac{16}{(d+1)^{3}}\cdot
nd(d-1)+\frac{n(n-1)}{(d+1)^{2}}$
$\displaystyle\leq\frac{17n}{d+1}+\left(\frac{n}{d+1}\right)^{2},$

where in the second equality, we have used the identity $\sum_{u\neq
v}d(u,v)=2\sum_{w}\binom{|N(w)|}{2}=nd(d-1)$. Hence, by (1),

$\textrm{Var}(X)=\mathbb{E}[X^{2}]-\mathbb{E}[X]^{2}\leq\frac{17n}{d+1}.\qed$
(2)

This immediately implies the following desired result.

######  Corollary 2.3.

Theorem 1.3 holds in the case $d=o(n^{1/2})$.

###### Proof.

By Chebyshev’s inequality and the bound (2), the probability that
$|X-\mathbb{E}[X]|\geq z$ with $z=\epsilon n/(d+1)$ is at most

$\frac{\textrm{Var}(X)}{z^{2}}\leq\frac{17(d+1)}{\epsilon^{2}n}.$

By the union bound over the $d+1$ possible values of $k$, the probability that
there exists $k$ such that $|m(H,k)-n/(d+1)|>\epsilon n/(d+1)$ is at most
$\frac{17(d+1)^{2}}{\epsilon^{2}n}$. For $d\leq\epsilon^{2}\sqrt{n}/5-1$, we
then have that with probability at least $1-\epsilon^{2}$,
$|m(H,k)-n/(d+1)|<\epsilon n/(d+1)$ for all $k\leq d$. By taking $\epsilon\to
0$ sufficiently slowly, we obtain that for $d=o(n^{1/2})$, with high
probability, $m(H,k)=(1+o(1))n/(d+1)$ for all $k\leq d$, as desired. ∎

In the next section we will see that the range of $d$ can be significantly
improved by replacing the use of Chebyshev’s inequality with a much stronger
concentration result that holds for the random variable $X$.

##  3 Exponential concentration via martingale Bernstein inequality

In this section, we use the martingale Bernstein inequality in order to show
that the random variable $X=m(H,k)$ defined in the introduction, which is the
number of vertices of degree $k$ in the random subgraph $H=H(G)$, is
exponentially concentrated on its expected value. This will allow us to prove
Theorem 1.3 in full generality. Since Corollary 2.3 handles the case
$d=o(n^{1/2})$, to cover the remaining range of $d$, in this section, we can
and will assume that $d=\omega(\log n)$.

We aim to get exponential concentration for $X$ based on the following
Bernstein concentration bound for sums of martingale differences. This is
essentially due to Freedman [5], but we will use the following version, which
follows from combining Corollary 2.3 and Remark 2.1 in the paper by Fan, Grama
and Liu [3].

######  Lemma 3.1.

Let
$\mathcal{F}_{1}\subseteq\mathcal{F}_{2}\subseteq\cdots\subseteq\mathcal{F}_{n}$
be an increasing sequence of $\sigma$-algebras. Given random variables
$Y_{1},\dots,Y_{n}$ such that $\mathbb{E}[Y_{j}|\mathcal{F}_{j-1}]=0$, let
$X_{i}=\sum_{j=1}^{i}Y_{j}$, and let
$M_{i}=\sum_{j=1}^{i}\mathbb{E}[Y_{j}^{2}\mid\mathcal{F}_{j-1}]$. Then for any
$z\geq 0$, $a>0$ and $L>0$,

$\mathbb{P}[\max_{i\leq n}|X_{i}-X_{0}|\geq z,M_{n}\leq
L]\leq\exp\left(-\frac{1}{2}\frac{(z/a)^{2}}{L/a^{2}+z/a}\right)+\mathbb{P}[\max_{i\leq
n}|Y_{i}|>a].$

Let $\pi$ be a permutation of the vertices of the graph chosen uniformly at
random. In the following, we identify vertices of the graph with integers in
$[n]$ according to the permutation $\pi$. Let ${\cal F}_{i}=\sigma(x(u):u\leq
i)$ denote the $\sigma$-algebra generated by the random variables $x(u)$ with
$u\leq i$. Let $X_{i}=\mathbb{E}[X\mid\mathcal{F}_{i}]$, so
$\mathbb{E}[X]=X_{0}$ and $X=X_{n}$. Let $Y_{i}=X_{i}-X_{i-1}$ and let
$M_{i}=\sum_{j=1}^{i}\mathbb{E}[Y_{j}^{2}\mid\mathcal{F}_{j-1}]$. In order to
apply Lemma 3.1 in our setting, we need the following two lemmas.

######  Lemma 3.2.

There exists a constant $C_{1}>0$ such that, with probability at least
$1-n^{-50}$, we have $|Y_{i}|\leq C_{1}\log n$ for all $i$.

######  Lemma 3.3.

Assume that $d=\omega(\log n)$. There exists a constant $C_{2}>0$ such that,
with probability at least $1-n^{-100}$, we have that $M_{n}\leq C_{2}(\log
n)^{11}n/d$.

We now give the proof of Theorem 1.3 assuming Lemma 3.2 and Lemma 3.3.

###### Proof of Theorem 1.3.

Let $C_{0}=\max(C_{1},C_{2})$. For $z>0$, let $\mathcal{E}_{1}$ be the event
that $|X_{n}-X_{0}|>z$, $\mathcal{E}_{2}$ the event that $M_{n}\leq C_{0}(\log
n)^{11}n/d$, and $\mathcal{E}_{3}$ the event that $\sup_{j\leq n}|Y_{j}|\leq
C_{0}(\log n)$. By Lemma 3.1 with $a=C_{0}(\log n)$ and $L:=C_{0}(\log
n)^{11}n/d$, we have for some $c>0$ that

$\mathbb{P}[\mathcal{E}_{1}\wedge\mathcal{E}_{2}]\leq\exp\left(-\frac{cz^{2}}{(\log
n)^{11}n/d+(\log n)z}\right)+{\mathbb{P}}[\overline{\mathcal{E}_{3}}].$

Thus,

$\displaystyle\mathbb{P}[\mathcal{E}_{1}]$
$\displaystyle\leq\mathbb{P}\left[\mathcal{E}_{1}\wedge\mathcal{E}_{2}\right]+\mathbb{P}[\overline{\mathcal{E}_{2}}]$
$\displaystyle\leq\exp\left(-\frac{cz^{2}}{(\log n)^{11}n/d+(\log
n)z}\right)+2n^{-50},$

where we used that $\mathbb{P}[\overline{\mathcal{E}_{2}}]\leq n^{-50}$ by
Lemma 3.3 and $\mathbb{P}[\overline{\mathcal{E}_{3}}]\leq n^{-50}$ by Lemma
3.2.

In particular, for any $\epsilon>0$, if $z=\epsilon n/(d+1)$ with
$d<c^{\prime}\epsilon^{2}n/(\log n)^{12}$, then we have

$\mathbb{P}[|X_{n}-X_{0}|>z]<1/n.$

Note that $X_{0}=\mathbb{E}[X]=n/(d+1)$. By taking $\epsilon\to 0$
sufficiently slowly and using the union bound over the $d+1$ nonnegative
integers $k\leq d$, we obtain the following conclusion. With high probability,
for all $k\leq d$, the number of vertices with degree exactly $k$ in $H$ is
$(1+o(1))n/(d+1)$. ∎

It thus remains to prove Lemmas 3.2 and 3.3. This is done in the next two
subsections.

###  3.1 Supremum of the martingale differences

In this subsection, we give the proof of Lemma 3.2, which gives an upper bound
on the supremum of the martingale difference $Y_{i}$.

Here and throughout, we denote by $C$ a sufficiently large absolute constant,
$\kappa=C\log n$, and $k_{+}=C\max(k,\kappa)$.

We will use the following three simple claims in the proof, which are standard
applications of the Chernoff bound.

######  Claim 3.4.

Let $h>0$. Let $I\subseteq\mathbb{R}$ be an interval of positive length. Let
$x_{1},\dots,x_{m}$ be independent and uniformly distributed random variables
in $I$. For a given subinterval of $I$ of length $h|I|/m$, the probability
that the number of elements $x_{i}$ lying in the interval is not contained in
$[h\pm\sqrt{\kappa\max(h,\kappa)}]$ is at most $\exp(-\kappa/3)$.

###### Proof.

The number of variables $x_{i}$ contained in a fixed interval of length
$h|I|/m$ is a sum of $m$ independent $\textrm{Ber}(h/m)$, which has
expectation $h$. By the multiplicative form of the Chernoff bound, the
probability that this deviates from $h$ by more than
$\ell:=\sqrt{\kappa\max(h,\kappa)}$ is at most

$\exp\left(-\min\left(\left(\ell/h\right)^{2},\ell/h\right)h/3\right)\leq\exp(-\kappa/3).\qed$

######  Claim 3.5.

Let $h>1$. Let $x_{1},\dots,x_{m}$ be independent and uniformly distributed
random variables in an interval $I$. For each subinterval of length $h|I|/m$,
the probability that there are more than $2h$ variables $x_{i}$ in this
interval is at most $\exp(-h/3)$.

###### Proof.

The number of variables $x_{i}$ contained in a fixed subinterval of $I$ of
length $h|I|/m$ is a sum of $m$ independent $\textrm{Ber}(h/m)$, which has
expectation $h$. By the multiplicative form of the Chernoff bound, the
probability that this is more than $2h$ is at most $\exp(-h/3)$. ∎

######  Claim 3.6.

Let $h>1$. Let $x_{1},\dots,x_{m}$ be independent and uniformly distributed
random variables in an interval $I$. The probability that there exists an
interval of length at least $h|I|/m$ with no element $x_{i}$ is at most
$3m\exp(-h/3)$.

###### Proof.

Clearly, we may assume $h\leq m$. Partition $I$ into $t=\lceil 2m/h\rceil$
equal length intervals. This guarantees that every interval of length $h|I|/m$
contains at least one of these $t$ intervals in the partition. The probability
that a given one of these $t$ intervals contains none of $x_{1},\dots,x_{m}$
is $(1-1/t)^{m}\leq e^{-m/t}\leq e^{-h/3}$. Taking the union bound over all
$t$ intervals, the probability that at least one of the $t$ intervals contains
none of $x_{1},\dots,x_{m}$ is at most $te^{-h/3}\leq 3me^{-h/3}$. ∎

Recall that for a vertex $u$ of $G$, $N(u)$ denotes the neighborhood of $u$ in
$G$ and $N_{+}(u)=N(u)\cup\\{u\\}$.

###### Proof of Lemma 3.2.

Observe that

$\displaystyle|Y_{u}|$
$\displaystyle=|\mathbb{E}[X|\mathcal{F}_{u}]-\mathbb{E}[X|\mathcal{F}_{u-1}]|$
$\displaystyle=\left|\sum_{v\in
N_{+}(u)}(\mathbb{E}[{\mathbb{I}}_{v}|\mathcal{F}_{u}]-\mathbb{E}[{\mathbb{I}}_{v}|\mathcal{F}_{u-1}])\right|$
$\displaystyle\leq\mathbb{E}\left[\sum_{v\in
N(u)}{\mathbb{I}}_{v}\bigg{|}\mathcal{F}_{u}\right]+\mathbb{E}\left[\sum_{v\in
N(u)}{\mathbb{I}}_{v}\bigg{|}\mathcal{F}_{u-1}\right]+1.$

Let $S(u)=\sum_{v\in N(u)}{\mathbb{I}}_{v}$. Then it suffices to show that
$S(u)\leq 10\kappa=10C\log n$ with probability at least $1-3n^{-100}$, as
combining with $S(u)\leq d\leq n$, we have that
$\mathbb{E}\left[S(u)|\mathcal{F}_{u}\right]\leq 20\kappa$ with probability at
least $1-n^{-99}$. Indeed, if $\mathbb{E}[S(u)|\mathcal{F}_{u}]>20\kappa$,
then $\mathbb{E}[\mathbb{I}(S(u)>10\kappa)|\mathcal{F}_{u}]>1/n$, and the
probability of such an event is at most $n^{-99}$. Thus, we must have that
$\mathbb{P}[\mathbb{E}[S(u)|\mathcal{F}_{u}]>10\kappa]<n^{-99}$.

First consider the case $|k/d-1/2|>\sqrt{\kappa k_{+}}/d$. Let $\mathcal{G}$
be the $\sigma$-algebra generated by $\mathbb{I}(x(v)\notin[k/d\pm\sqrt{\kappa
k_{+}}/d])x(v)$ for all $v\in N(u)$. Condition on $\mathcal{G}$ (i.e., on the
set of $v\in N(u)$ with $|x(v)-k/d|>\sqrt{\kappa k_{+}}/d$ and on the value of
$x(v)$ for each such $v$) satisfying the following properties:

  1. 1.

All vertices $v$ in $N(u)$ with $H$-degree $k$ have
$|x(v)-k/d|\leq\sqrt{\kappa k_{+}}/d$ with probability at least $1-n^{-50}$
conditional on $\mathcal{G}$.

  2. 2.

The number of vertices $v\in N(u)$ such that $|x(v)-k/d|\leq\sqrt{\kappa
k_{+}}/d$ is at most $4\sqrt{\kappa k_{+}}$.

  3. 3.

The values $x(v)$ for $v\in N(u)$ satisfying $x(v)\notin[k/d\pm\sqrt{\kappa
k_{+}}/d]$ partition $[0,1]\setminus[k/d\pm\sqrt{\kappa k_{+}}/d]$ into
consecutive intervals of length at most $\kappa/d$.

######  Claim 3.7.

The $\sigma$-algebra $\mathcal{G}$ satisfies the above three properties with
probability at least $1-n^{-100}$.

###### Proof.

By Claim 3.4, with probability at least $1-n^{-100}/4$, for each vertex $v$,
the number of neighbors $v^{\prime}$ of $v$ with $x(v^{\prime})\geq 1-x(v)$ is
$dx(v)\pm\sqrt{\kappa\max(\kappa,dx(v))}$. Under such an event, if $v\in N(u)$
has $H$-degree $k$, then $k\in[dx(v)\pm\sqrt{\kappa\max(\kappa,dx(v))}]$. This
implies that $x(v)\leq 2k/d+\kappa/d$, from which we obtain that
$|x(v)-k/d|\leq
2\frac{\sqrt{\kappa}}{d}\sqrt{\max(\kappa,dx(v))}\leq\sqrt{\kappa k_{+}}/d$.

Claim 3.5 implies that the second property holds with probability at least
$1-d\exp(-2\sqrt{\kappa k_{+}}/3)>1-n^{-100}/4$. Claim 3.6 implies that the
third property holds with probability at least
$1-3d\exp(-\kappa/3)>1-n^{-100}/4$. ∎

Let $S$ be the set of vertices $v\in N(u)$ with $|x(v)-k/d|\leq\sqrt{\kappa
k_{+}}/d$. By our assumption that $\mathcal{G}$ satisfies the second property
above, $|S|\leq 4\sqrt{\kappa k_{+}}$. Partition $[k/d-\sqrt{\kappa
k_{+}}/d,k/d+\sqrt{\kappa k_{+}}/d]$ into consecutive intervals with endpoints
at each value in the set $\\{1-x(w):\>w\in N(u),\>x(w)\in[1-k/d-\sqrt{\kappa
k_{+}}/d,1-k/d+\sqrt{\kappa k_{+}}/d]\\}$, which is $\mathcal{G}$-measurable
because $|k/d-1/2|>\sqrt{\kappa k_{+}}/d$. Conditioned on $\mathcal{G}$, for
each $v\in S$, there is at most one interval $I_{v}$ in this partition for
which $v$ can have $H$-degree $k$ only if $x(v)\in I_{v}$. Furthermore, the
third property above implies that $|I_{v}|\leq\kappa/d$. Conditional on
$\mathcal{G}$, the random variables $x(v)$ for $v\in S$ are independently and
uniformly distributed in the interval $[k/d-\sqrt{\kappa
k_{+}/d},k/d+\sqrt{\kappa k_{+}/d}]$. Note that $|I_{v}|/(2\sqrt{\kappa
k_{+}}/d)\leq 2\kappa/|S|$. By Claim 3.5, the number of $v\in S$ with $x(v)\in
I_{v}$ is at most $4\kappa$ with probability at least $1-\exp(-\kappa/3)\geq
1-n^{-100}$. Hence, with probability at least $1-2n^{-100}$, there are at most
$4\kappa$ neighbors of $u$ with degree $k$.

Next consider the case $|k/d-1/2|\leq\sqrt{\kappa k_{+}}/d$. Pick three
consecutive intervals $J_{1},J_{2},J_{3}$ whose union contains
$[k/d\pm\sqrt{\kappa k_{+}}/d]$, with the properties that $J_{2}$ has length
at most $\kappa/d$ and $\frac{1}{2}\in J_{2}$, and $J_{1}$ and $J_{3}$ each
has length $\sqrt{\kappa k_{+}}/d$. It follows that $1-x\notin J_{j}$ for
$x\in J_{j}$ and $j=1,3$. Let $\mathcal{G}$ be the $\sigma$-algebra generated
by $\mathbb{I}(x(v)\notin J_{1}\cup J_{2}\cup J_{3})x(v)$ for all $v\in N(u)$,
and let $\mathcal{G}_{j}$ be the $\sigma$-algebra generated by
$\mathbb{I}(x(v)\notin J_{j})x(v)$. Condition on $\mathcal{G}$ and
$\mathcal{G}_{2},\mathcal{G}_{3}$ satisfying the following properties:

  1. 1.

All vertices $v$ in $N(u)$ with $H$-degree $k$ lie in $J_{1}\cup J_{2}\cup
J_{3}$ with probability at least $1-n^{-50}$ conditional on $\mathcal{G}$.

  2. 2.

There are at most $2\kappa$ vertices $v\in N(u)$ with $x(v)\in J_{2}$, and at
most $2\sqrt{\kappa k_{+}}$ vertices with each of $x(v)\in J_{1}$ or $x(v)\in
J_{3}$.

  3. 3.

The values $x(v)$ for $v\in N(u)$ satisfying $x(v)\notin[k/d\pm\sqrt{\kappa
k_{+}}/d]$ or $x(v)\in J_{2}\cup J_{3}$ partition $[0,1]\setminus J_{1}$ into
consecutive intervals of length at most $\kappa/d$.

As in Claim 3.7, we can verify that
$\mathcal{G},\mathcal{G}_{2},\mathcal{G}_{3}$ satisfy these properties with
probability at least $1-n^{-100}$.

Let $S$ be the set of vertices $v$ with $x(v)\in J_{1}$ (so they are the only
remaining vertices with $x(v)$ not measurable in
$\mathcal{G},\mathcal{G}_{2},\mathcal{G}_{3}$). By the second property
conditioned on above, $|S|\leq 2\sqrt{\kappa k_{+}}$. By the third property
above, the vertices $v$ with $x(v)\notin J_{1}$ partition $[0,1]\setminus
J_{1}$ into consecutive intervals each of length at most $\kappa/d$. As
before, since $1-x(v)\notin J_{1}$ for any $v\in S$, for each $v\in S$,
conditional on $\mathcal{G}$, $\mathcal{G}_{2}$, and $\mathcal{G}_{3}$, there
is at most one interval $I_{v}$ in this partition for which $v$ can have
$H$-degree $k$ only if $x(v)\in I_{v}$. As before, $|I_{v}|/|J_{1}|\leq
2\kappa/|S|$, and by Claim 3.5, the number of $v\in S$ with $x(v)\in I_{v}$
conditional on $\mathcal{G},\mathcal{G}_{2},\mathcal{G}_{3}$ is at most
$4\kappa$ with probability at least $1-n^{-100}$. Thus, the number of vertices
with $x(v)\in J_{1}$ and $H$-degree $k$ is at most $4\kappa$ with probability
at least $1-n^{-100}$. A similar argument shows that the number of vertices
with $x(v)\in J_{3}$ and $H$-degree $k$ is at most $4\kappa$ with probability
at least $1-n^{-100}$. Finally, since there are at most $2\kappa$ vertices
$v\in N(u)$ with $x(v)\in J_{2}$, with probability at least $1-3n^{-100}$,
there are at most $10\kappa$ neighbors of $u$ with $H$-degree $k$, completing
the proof. ∎

###  3.2 The variance proxy

In this subsection, we give the proof of Lemma 3.3. Recall that

$M_{n}=\sum_{j=1}^{n}\mathbb{E}[Y_{j}^{2}|\mathcal{F}_{j-1}].$ (3)

We first develop several preliminary estimates that will be useful for the
proof of Lemma 3.3. We have that

$\displaystyle\mathbb{E}[Y_{j}^{2}\mid\mathcal{F}_{j-1}]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{u\in
N(j)}(\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j}]-\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j-1}])\right)^{2}\bigg{|}\mathcal{F}_{j-1}\right].$

For an integer $h\in[0,t]$, define

$p(x,t,h)=\binom{t}{h}x^{h}(1-x)^{t-h}.$

If $h<0$ or $h>t$ then by convention we set $p(x,t,h)=0$. Note that $p(x,t,h)$
is the probability that $u$ has degree $k$ conditioned on the events that
$x(u)=x$, and among $d-t$ revealed neighbors $v$ of $u$ in $G$, there are
exactly $k-h$ neighbors with $x(v)\geq 1-x$.

For each $j$, let $t(u,j)$ be the number of neighbors of $u$ that arrive after
$j$ in the ordering. We then have for $u$ adjacent to $j$ in $G$ that

$\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j}]=\mathbb{E}[p(x(u),t(u,j),k-h(u,x(u),j))\mid\mathcal{F}_{j}],$

where $h(u,x(u),j)$ is the number of neighbors $v$ of $u$ arriving by time $j$
with $x(v)\geq 1-x(u)$. In particular, if $u\leq j$, then

$\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j}]=p(x(u),t(u,j),k-h(u,x(u),j)).$

Note that for a neighbor $u$ of $j$, $u$ has degree $k$ if $x(j)\geq 1-x(u)$
and $k-1-h(u,x(u),j-1)$ neighbors $v^{\prime}$ of $u$ coming after $j$ have
$x(v^{\prime})\geq 1-x(u)$; or $x(j)<1-x(u)$ and $k-h(u,x(u),j-1)$ neighbors
$v^{\prime}$ of $u$ coming after $j$ have $x(v^{\prime})\geq 1-x(u)$. Thus,

$\displaystyle\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j-1}]$
$\displaystyle=\mathbb{E}[p(x(u),t(u,j),k-h(u,x(u),j-1))\cdot(1-x(u))\mid\mathcal{F}_{j-1}]$
$\displaystyle\qquad\qquad+\mathbb{E}[p(x(u),t(u,j),k-1-h(u,x(u),j-1))\cdot
x(u)\mid\mathcal{F}_{j-1}],$

while

$\displaystyle\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j}]$
$\displaystyle=\mathbb{E}[p(x(u),t(u,j),k-h(u,x(u),j-1))\cdot\mathbb{I}(x(j)<1-x(u))\mid\mathcal{F}_{j-1}]$
$\displaystyle\qquad\qquad+\mathbb{E}[p(x(u),t(u,j),k-1-h(u,x(u),j-1))\cdot\mathbb{I}(x(j)\geq
1-x(u))\mid\mathcal{F}_{j-1}].$

Thus, if $j$ is adjacent to $u$ in $G$,

$\displaystyle\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j}]-\mathbb{E}[{\mathbb{I}}_{u}\mid\mathcal{F}_{j-1}]$
$\displaystyle=\mathbb{E}[(p(x(u),t(u,j),k-1-h(u,x(u),j-1))-p(x(u),t(u,j),k-h(u,x(u),j-1)))$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\cdot(\mathbb{I}(x(j)\geq
1-x(u))-x(u))\mid\mathcal{F}_{j-1}].$ (4)

Let
$\delta_{k}(j,u)=p(x(u),t(u,j),k-1-h(u,x(u),j-1))-p(x(u),t(u,j),k-h(u,x(u),j-1))$.
Note that $h(u,x(u),j-1)$ is $\sigma(\mathcal{F}_{j-1},x(u))$-measurable. In
particular, if $u\leq j-1$, then $\delta_{k}(j,u)$ is
$\mathcal{F}_{j-1}$-measurable, and otherwise it is determined by
$\mathcal{F}_{j-1}$ and the (independent) choice of $x(u)$, and we have

$\displaystyle\mathbb{E}[Y_{j}^{2}\mid\mathcal{F}_{j-1}]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{u\in
N(j)}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq
1-x(u))-x(u))\right)^{2}\bigg{|}\mathcal{F}_{j-1}\right]$ $\displaystyle\leq
2\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq 1-x(u))-x(u))\right)^{2}\right]$
$\displaystyle\qquad\qquad+2\mathbb{E}_{x(j),x(u)}\left[\left(\sum_{u\in
N(j),u>j-1}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq
1-x(u))-x(u))\right)^{2}\right],$ (5)

where in the first summand we are averaging over the uniform random variable
$x(j)$, and in the second summand we are averaging over independent $x(j)$ and
$x(u)$ for all $u>j-1,u\in N(j)$.

Let

$A_{1}(j):=\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq 1-x(u))-x(u))\right)^{2}\right],$ (6)

and let

$A_{2}(j):=\mathbb{E}_{x(j),x(u)}\left[\left(\sum_{u\in
N(j),u>j-1}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq
1-x(u))-x(u))\right)^{2}\right].$ (7)

In the next subsection, we will derive some useful bounds on $\delta_{k}(j,u)$
before turning to the upper bounds for $\sum_{j}A_{1}(j)$ and
$\sum_{j}A_{2}(j)$, which complete the proof of Lemma 3.3.

####  3.2.1 Bounds on $\delta_{k}(j,u)$

We will now derive some useful bounds for $\delta_{k}(j,u)$ for fixed $u$. For
convenience in notation, let $h=k-1-h(u,x(u),j-1)$, $x=x(u)$ and $t=t(u,j-1)$.
Note that $m!=\Theta(\sqrt{m}(m/e)^{m})$ for all $m\geq 1$ from Stirling’s
approximation. Letting $\alpha=h/(t-1)$, when $0<h<t-1$, we have

$\displaystyle|\delta_{k}(j,u)|$ $\displaystyle=|p(x,t,h)-p(x,t,h+1)|$
$\displaystyle=\frac{t!}{(h+1)!(t-h)!}x^{h}(1-x)^{t-h-1}\left|(1-x)(h+1)-x(t-h)\right|$
$\displaystyle\ll\frac{|t(\alpha-x)+1-\alpha-x|}{(\alpha(1-\alpha)t)^{3/2}}\exp\big{(}[\alpha\log(x/\alpha)+(1-\alpha)\log((1-x)/(1-\alpha))](t-1)\big{)}$
$\displaystyle\ll\frac{|t(\alpha-x)|+3}{(\alpha(1-\alpha)t)^{3/2}}\exp\big{(}[\alpha\log(x/\alpha)+(1-\alpha)\log((1-x)/(1-\alpha))](t-1)\big{)}.$
(8)

We also have the trivial bound $|\delta_{k}(j,u)|\leq 1$, since
$\delta_{k}(j,u)$ is the difference of two probabilities.

######  Claim 3.8.

There exists an absolute constant $c>0$ such that the following holds. For
each $x\in[0,1]$, the function
$f(\alpha)=\alpha\log(x/\alpha)+(1-\alpha)\log((1-x)/(1-\alpha))$ satisfies

$f(\alpha)\leq-c\min(|x-\alpha|,(1/x+1/(1-x))(x-\alpha)^{2}).$ (9)

###### Proof.

Note that

$f^{\prime}(\alpha)=\log\frac{x}{\alpha}-\log\frac{1-x}{1-\alpha},\qquad
f^{\prime\prime}(\alpha)=-\frac{1}{\alpha}-\frac{1}{1-\alpha}.$

Thus, by Taylor’s theorem, noting that $f(x)=f^{\prime}(x)=0$,

$f(\alpha)=f(x)+f^{\prime}(x)(\alpha-x)+f^{\prime\prime}(\alpha^{\prime})(\alpha-x)^{2}=-\left(\frac{1}{\alpha^{\prime}}+\frac{1}{1-\alpha^{\prime}}\right)(x-\alpha)^{2},$
(10)

for some $\alpha^{\prime}$ between $\alpha$ and $x$.

By symmetry about $1/2$, we can assume without loss of generality that $x\leq
1/2$. If $\alpha\leq 2x$, then
$\frac{1}{\alpha^{\prime}}+\frac{1}{1-\alpha^{\prime}}\geq
c\left(\frac{1}{x}+\frac{1}{1-x}\right)$ for any $\alpha^{\prime}$ between
$\alpha$ and $x$, so (10) implies (9). Otherwise, $\alpha>2x$, in which case
we can verify that for some constants $c_{1},c_{2}>0$,

$f(\alpha)=f(2x)+f(\alpha)-f(2x)\leq f(2x)+(\alpha-2x)f^{\prime}(2x)\leq-
c_{1}x-c_{2}(\alpha-2x)\leq-\min(c_{1},c_{2})|x-\alpha|.\qed$

####  3.2.2 Bounding $\sum_{j}A_{1}(j)$ and $\sum_{j}A_{2}(j)$

Recall that

$A_{1}(j)=\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq 1-x(u))-x(u))\right)^{2}\right].$

######  Claim 3.9.

  1. (a)

With probability at least $1-n^{2}\exp(-c\kappa)$ over the random permutation
$\pi$, we have that

$\left||N(v)\cap[j]|-d\frac{j}{n}\right|\leq\max\left(\sqrt{\kappa\frac{d}{n}\min(n-j,j)},\kappa\right)$
(11)

for all $v\in[n]$ and $j\in[n]$.

  2. (b)

With probability at least $1-n^{4}\exp(-c\kappa)$ (over the randomness of all
$x(u)$ with $u\in[n]$), we have that for any interval $I\subseteq[0,1]$ of
length at least $2/d$,

$\big{|}\left|\\{z\in N(v)\cap[j]:x(z)\in I\\}\right|-d|I|j/n\big{|}\leq
e_{|I|}$ (12)

for all $v\in[n]$ and $j\in[n]$, where

$e_{r}=\kappa+\sqrt{\kappa drj/n}.$

###### Proof.

We first prove the bound in (a). Note that under the random permutation $\pi$,
$|N(v)\cap[j]|$ follows the hypergeometric distribution with parameters
$(n,d,j)$. By Hoeffding’s Theorem (Theorem 4 of [7], that the hypergeometric
distribution concentrates at least as much as the corresponding binomial
distribution), we have that

$\mathbb{P}\left(\left||N(v)\cap[j]|-d\frac{j}{n}\right|>\theta
d\frac{j}{n}\right)\leq\exp(-\min(\theta/3,\theta^{2}/2)dj/n).$

In particular, if $\kappa<\sqrt{dj/n}$, then

$\mathbb{P}\left(\left||N(v)\cap[j]|-d\frac{j}{n}\right|>\sqrt{\kappa
dj/n}\right)\leq\exp(-c\kappa).$

If $\kappa\geq\sqrt{dj/n}\geq 1$, then

$\mathbb{P}\left(\left||N(v)\cap[j]|-d\frac{j}{n}\right|>\kappa\sqrt{dj/n}\right)\leq\exp(-c\kappa\sqrt{dj/n})\leq\exp(-c\kappa).$

Finally, if $\kappa\geq\sqrt{dj/n}$ and $\sqrt{dj/n}<1$, then

$\mathbb{P}\left(\left||N(v)\cap[j]|-d\frac{j}{n}\right|>\kappa\right)\leq\exp(-c\kappa).$

Hence, in all cases,

$\mathbb{P}\left(\left||N(v)\cap[j]|-d\frac{j}{n}\right|>\max(\sqrt{\kappa
dj/n},\kappa)\right)\leq\exp(-c\kappa).$

Finally, one has $|N(v)\cap[j]|=d-|N(v)\cap[j+1,n]|$, and an identical
argument gives that

$\mathbb{P}\left(\left||N(v)\cap[j]|-d\frac{j}{n}\right|>\max(\sqrt{\kappa
d(n-j)/n},\kappa)\right)\leq\exp(-c\kappa).$

The final bound follows from the union bound over all $v$ and $j$.

Next, we prove (b). Let $|N(v)\cap[j]|=N_{v,j}$. Conditional on $\pi$, the
random variable $N_{v,j,\ell,\ell^{\prime}}:=|\\{z\in
N(v)\cap[j]:x(z)\in[\ell/d,\ell^{\prime}/d]\\}|$ is a binomial random variable
with parameters $(N_{v,j},(\ell^{\prime}-\ell)/d)$, so

$\mathbb{E}\left[\exp(\lambda
N_{v,j,\ell,\ell^{\prime}})|\pi\right]=\left(\frac{\ell^{\prime}-\ell}{d}(e^{\lambda}-1)+1\right)^{|N_{v,j}|}.$

Next, we note that the function
$y\mapsto\left(\frac{\ell^{\prime}-\ell}{d}(e^{\lambda}-1)+1\right)^{y}$ is
convex, so by Hoeffding’s Theorem (Theorem 4 of [7]), we have

$\displaystyle\mathbb{E}\left[\left(\frac{\ell^{\prime}-\ell}{d}(e^{\lambda}-1)+1\right)^{|N_{v,j}|}\right]$
$\displaystyle\leq\left(\frac{j}{n}\left(\frac{\ell^{\prime}-\ell}{d}(e^{\lambda}-1)+1\right)+1-\frac{j}{n}\right)^{d}$
$\displaystyle=\mathbb{E}\left[\exp(\lambda Z)\right],$

where $Z$ is binomially distributed with parameters
$(d,\frac{j(\ell^{\prime}-\ell)}{dn})$. This yields Chernoff-type bounds for
concentration of $N_{v,j,\ell,\ell^{\prime}}$, from which similar to the proof
of (a), we obtain that with probability at least $1-\exp(-c\kappa)$,

$\left||\\{z\in
N(v)\cap[j]:x(z)\in[\ell/d,\ell^{\prime}/d]\\}|-j(\ell^{\prime}-\ell)/n\right|\leq\frac{1}{2}\max\left(\kappa,\sqrt{\kappa
j(\ell^{\prime}-\ell)/n}\right).$ (13)

By the union bound, we can guarantee this property for all
$v,j,\ell,\ell^{\prime}$ with probability at least $1-n^{4}\exp(-c\kappa)$.

The final conclusion follows upon noticing that, given any interval $I$ of
length at least $2/d$, $I$ is contained in an interval
$[\ell/d,\ell^{\prime}/d]$ of length $(\ell^{\prime}-\ell)/d\leq|I|+1/d$, and
$I$ contains an interval $[\tilde{\ell}/d,\tilde{\ell}^{\prime}/d]$ of length
$(\tilde{\ell}^{\prime}-\tilde{\ell})/d\geq|I|-1/d$.

∎

Recall that $\kappa=C\log n$ and $k_{+}=C\max(k,\kappa)$ for a sufficiently
large constant $C$. In the rest of the section, we will work under the event
$\mathcal{E}$ that the events in Claim 3.9 hold. Let
$k^{\prime}=\max(k,\kappa)$.

######  Lemma 3.10.

Let $n$ be sufficiently large and $j\leq n-C\kappa n/d$. We have

$\sum\delta_{k}(j,u)<n^{-10},$

where the summation ranges over $u\in N(j)$ with $u\leq j-1$ such that
$|x(u)-k/d|>\sqrt{\kappa k_{+}}/d$ or $|h/(t-1)-x(u)|>\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$.

###### Proof.

Under the event $\mathcal{E}$, Claim 3.9(b) tells us that

$\left|h(u,x(u),j-1)-x(u)(j-1)d/n\right|\leq e_{x(u)},$

so

$\left|h-(k-1-x(j-1)d/n)\right|\leq e_{x}.$ (14)

By Claim 3.9(a),

$\left|t-(d-d(j-1)/n)\right|\leq\max(\kappa,\sqrt{\kappa
d\min(n-(j-1),j-1)/n}).$ (15)

From (14) and (15), we have

$h/(t-1)-x\in\left[\frac{M_{1}-E_{1}}{M_{2}+E_{2}},\frac{M_{1}+E_{1}}{M_{2}-E_{2}}\right],$
(16)

where

$\displaystyle M_{1}$ $\displaystyle=k-1-x(d-1),\,\,$ $\displaystyle M_{2}$
$\displaystyle=d-1-d(j-1)/n,$ $\displaystyle E_{1}$
$\displaystyle=e_{x}+x(\kappa+\sqrt{\kappa d\min(n-(j-1),j-1)/n}),\,\,$
$\displaystyle E_{2}$ $\displaystyle=\kappa+\sqrt{\kappa
d\min(n-(j-1),j-1)/n}.$

Note that

$E_{2}\leq\kappa+\sqrt{\kappa d(n-j+1)/n}\leq\kappa+\sqrt{\kappa(M_{2}+1)}\leq
M_{2}/2,$

where we use the fact that $M_{2}\geq C\kappa-1$ for $j\leq n-C\kappa n/d$.
This, along with (15), implies that

$t\geq M_{2}+1-E_{2}=1+\frac{1}{2}M_{2}>\frac{1}{2}d(1-(j-1)/n).$ (17)

Furthermore, recall that

$e_{x}=\kappa+\sqrt{\kappa dx(j-1)/n}.$

Let $c$ be the constant in Claim 3.8 and let $C^{\prime}=cC/6400$. Assume that
$C$ is sufficiently large so $C^{\prime}>1$. By Claim 3.8, if
$|h/(t-1)-x|>\frac{1}{64C^{\prime}}\kappa/(d(1-j/n))$ and
$|h/(t-1)-x|^{2}/x>\frac{1}{64C^{\prime}}\kappa/(d(1-j/n))$, then

$\displaystyle\exp\big{(}[\alpha\log(x/\alpha)+(1-\alpha)\log((1-x)/(1-\alpha))](t-1)\big{)}$
$\displaystyle\leq\exp\left(-cd(1-j/n)\min\left(|h/(t-1)-x|,\frac{1}{x}|h/(t-1)-x|^{2}\right)\right)$
$\displaystyle<n^{-15},$ (18)

upon choosing the constant $C$ in the definition of $\kappa$ sufficiently
large.

We will next show that the conditions of (18) (and hence the conclusion) hold
if $|x-k/d|>\sqrt{\kappa k_{+}}/d$ or $|h/(t-1)-x|>\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$. Given this, by (3.2.1), we
have that for $u\in N(j)$ with $u\leq j-1$, and either
$|x(u)-k/d|\geq\sqrt{\kappa k_{+}}/{d}\geq\sqrt{C^{\prime}\kappa
k^{\prime}}/{d}$ or $|h/(t-1)-x(u)|>\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$,

$\delta_{k}(j,u)\ll\frac{|t(\alpha-x)|+3}{(\alpha(1-\alpha)t)^{3/2}}n^{-15}<n^{-12}.$

Summing over at most $n$ such $u$’s, we obtain the desired bound.

We now turn to verify the conditions of (18) when $|x-k/d|>\sqrt{\kappa
k_{+}}/d$ or $|h/(t-1)-x|>\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$. Let $\eta:=|x-k/d|$, and let
$\eta_{0}:=\sqrt{C^{\prime}\kappa k^{\prime}}/d$.

Case 1: $|x-k/d|=\eta\geq\eta_{0}$.

From (16), we first claim that if $\eta\geq\eta_{0}$ then $|E_{1}|<|M_{1}|/2$.
Indeed, if $x<64k^{\prime}/d$, then

$\displaystyle|M_{1}|$ $\displaystyle>\eta d-2\geq\sqrt{C^{\prime}\kappa
k^{\prime}}-2,\,\,$ $\displaystyle|E_{1}|$
$\displaystyle<2(\kappa+\sqrt{\kappa dx})\leq 2(\kappa+8\sqrt{\kappa
k^{\prime}})\leq 18\sqrt{\kappa k^{\prime}}.$

Otherwise, if $x\geq 64k^{\prime}/d$, then $\eta<x$, and

$\displaystyle|M_{1}|$ $\displaystyle>\frac{1}{2}dx,\,\,$
$\displaystyle|E_{1}|$ $\displaystyle<2(\kappa+\sqrt{\kappa dx}).$

In both cases, recalling that $k^{\prime}=\max(k,\kappa)\geq\kappa$, we indeed
have for a sufficiently large $C$ that $|E_{1}|<|M_{1}|/2$. Combining this
estimate with the fact that $E_{2}\leq M_{2}/2$ yields

$4\eta/(1-j/n)>|h/(t-1)-x|>\frac{1}{4}\eta/(1-j/n).$ (19)

In particular, since $k^{\prime}\geq\kappa$, we have

$|h/(t-1)-x|>\frac{1}{4}\eta_{0}/(1-j/n)=\frac{1}{4}\sqrt{C^{\prime}\kappa
k^{\prime}}/(d(1-j/n))\geq\frac{1}{64C^{\prime}}\kappa/(d(1-j/n)).$ (20)

For $\alpha=h/(t-1)$, if $|x-k/d|=\eta\geq\sqrt{C^{\prime}\kappa
k^{\prime}}/d$, then

$\frac{1}{x}|h/(t-1)-x|^{2}\geq\frac{1}{16}\frac{1}{k/d+\eta}\frac{\eta^{2}}{(1-j/n)^{2}}.$

Thus, if $\eta>(k+\kappa)/d$, then

$\frac{1}{x}|h/(t-1)-x|^{2}\geq\frac{\eta}{32(1-j/n)^{2}}>\frac{k+\kappa}{32d(1-j/n)^{2}}>\frac{1}{64C^{\prime}}\frac{\kappa}{d(1-j/n)},$

and otherwise if $\eta\leq(k+\kappa)/d$, then

$\frac{1}{x}|h/(t-1)-x|^{2}\geq\frac{1}{16}\frac{d}{2k+\kappa}\frac{\eta_{0}^{2}}{(1-j/n)^{2}}\geq\frac{1}{16}\frac{C^{\prime}k^{\prime}}{2k+\kappa}\frac{\kappa}{d(1-j/n)^{2}}\geq\frac{1}{48}\frac{\kappa}{d(1-j/n)}>\frac{1}{64C^{\prime}}\frac{\kappa}{d(1-j/n)}.$

The estimates above and (20) yield that the conditions of (18) hold when
$|x-k/d|\geq\sqrt{C^{\prime}\kappa k^{\prime}}/d$.

Case 2: $|x-k/d|\leq\eta_{0}=\sqrt{C^{\prime}\kappa k^{\prime}}/d$ and
$|h/(t-1)-x|>\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$.

Since $|x-k/d|\leq\sqrt{C^{\prime}\kappa k^{\prime}}/d$, we have $x\leq
2\max(k/d,\sqrt{C^{\prime}\kappa k^{\prime}}/d)$. Then

$\displaystyle\frac{1}{x}|h/(t-1)-x|^{2}$
$\displaystyle\geq\frac{1}{2\max(k/d,\sqrt{C^{\prime}\kappa
k^{\prime}}/d)}\cdot\frac{\kappa
k_{+}}{d^{2}(1-j/n)}\geq\frac{1}{2C^{\prime}(k+\kappa)/d}\cdot\frac{\kappa(\kappa+k)/2}{d^{2}(1-j/n)}$
$\displaystyle>\frac{1}{64C^{\prime}}\frac{\kappa}{d(1-j/n)}.$

Furthermore,

$|h/(t-1)-x|>\frac{\kappa}{d(1-j/n)}>\frac{1}{64C^{\prime}}\frac{\kappa}{d(1-j/n)}.$

This yields the conditions of (18) in this case and completes the proof of the
lemma.

∎

We next return to the task of bounding $\sum_{j}A_{1}(j)$. Let
$\mathcal{U}_{j}$ be the set of $u$ with $|x(u)-k/d|\leq\sqrt{\kappa k_{+}}/d$
and $|h/(t-1)-x(u)|\leq\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$. Note that by symmetry in
degrees of $H$ about $d/2$, we can and will assume that $k\leq d/2$. Let
$C^{\prime\prime}$ be a sufficiently large constant whose choice depends on
$C$. In the following, we first consider values of $j$ such that $j\leq
n-C^{\prime\prime}n\kappa/d$. For these $j$ we have
$d\sqrt{1-j/n}\geq\sqrt{C^{\prime\prime}\kappa d}\geq\sqrt{C\kappa k_{+}}$,
since $d=\omega(\log n)$ and $d(1-j/n)\geq C^{\prime\prime}\kappa$. Thus, for
$C$ sufficiently large and $k\leq d/2$, we have that $\min(1-\alpha,1-k/d)\geq
1/4$ (where we recall that $\alpha=h/(t-1)$).

By Claim 3.9(b), the number of $u\in N(j)\cap[j-1]$ with
$|x(u)-k/d|\leq\sqrt{\kappa k_{+}}/d$ is at most $\frac{dj}{n}\cdot
2\frac{\sqrt{\kappa k_{+}}}{d}+\left(\kappa+\sqrt{2\kappa\sqrt{\kappa
k_{+}}j/n}\right)\leq 4\left(\kappa+\sqrt{\kappa k_{+}j/n}\right)$.
Furthermore, recall that

$\displaystyle A_{1}(j)$
$\displaystyle=\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq 1-x(u))-x(u))\right)^{2}\right]$
$\displaystyle\ll\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1,u\notin\mathcal{U}_{j}}\delta_{k}(j,u)\right)^{2}\right]$
$\displaystyle\qquad\qquad+\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1,u\in\mathcal{U}_{j}}\delta_{k}(j,u)(\mathbb{I}(x(j)\geq
1-x(u))-x(u))\right)^{2}\right].$

If $x(j)<1-k/d-\sqrt{\kappa k_{+}}/d$, then the second term can be bounded by

$\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1,u\in\mathcal{U}_{j}}\delta_{k}(j,u)(k+\sqrt{\kappa
k_{+}})/d\right)^{2}\right].$

Since $x(j)\geq 1-k/d-\sqrt{\kappa k_{+}}/d$ occurs with probability at most
$k/d+\sqrt{\kappa k_{+}}/d$, we conclude that

$\displaystyle A_{1}(j)$
$\displaystyle\ll\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1,u\notin\mathcal{U}_{j}}\delta_{k}(j,u)\right)^{2}\right]$
$\displaystyle\qquad\qquad+\mathbb{E}_{x(j)}\left[\left(\sum_{u\in N(j),u\leq
j-1,u\in\mathcal{U}_{j}}\delta_{k}(j,u)\right)^{2}\right]\left(\frac{(k+\sqrt{\kappa
k_{+}})^{2}}{d^{2}}+\frac{k+\sqrt{\kappa k_{+}}}{d}\right)$ $\displaystyle\ll
n^{-20}+\frac{k+\sqrt{\kappa k_{+}}}{d}\mathbb{E}_{x(j)}\left[\left(\sum_{u\in
N(j),u\leq j-1,u\in\mathcal{U}_{j}}\delta_{k}(j,u)\right)^{2}\right],$ (21)

where the the bound on the first term follows from Lemma 3.10. In particular,
in the following part of the argument, we only need to restrict our attention
to the case where $|x-k/d|\leq\sqrt{\kappa k_{+}}/d$ and
$|h/(t-1)-x|\leq\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$, so $\alpha\in[k/d\pm
2\max\big{(}\sqrt{\kappa k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}]$.

Condition on $x(v)$ with $|x(v)-k/d|>\sqrt{\kappa k_{+}}/d$. Since the event
in Claim 3.9(b) holds, the $x(v)$ with $|x(v)-k/d|>\sqrt{\kappa k_{+}}/d$
partition $[0,1]\setminus[k/d\pm\sqrt{\kappa k_{+}}/d]$ into consecutive
intervals each of length at most $\kappa/d$, and the union of any $q$
consecutive intervals has length at most $(2q+4\kappa)/d$. Indeed, this
follows since any interval of length $(2q+4\kappa)/d$ contains at least
$(2q+4\kappa)-(\kappa+\sqrt{\kappa(2q+4\kappa)})>q$ elements $x(v)$.

Since $|x(u)-k/d|\leq\sqrt{\kappa k_{+}/d}$, if
$|h/(t-1)-x(u)|\leq\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}$, then $h/(t-1)$ is contained
in an interval centered at $k/d$ of length

$w:=2\sqrt{\kappa k_{+}/d}+2\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}.$

Thus, $h$ must be contained in a fixed interval of length at most $(t-1)w$,
which implies that $u$ is contained in a (fixed) union of at most $(t-1)w$
consecutive intervals in the partition by $x(v)$ with $|x(v)-k/d|>\sqrt{\kappa
k_{+}}/d$. (Note that each possible value of $h$ determines an interval in the
partition that $x(u)$ must lie in.) Hence, $x(u)$ must be contained in a fixed
interval of length at most

$\Big{(}4\kappa+2(t-1)w\Big{)}/d<12\kappa/d+16\sqrt{\kappa k_{+}(1-j/n)}/d,$

where we have used the fact that $t<2d(n-j)/n$. The number of such $u$ in
$N(j)\cap[j-1]$ is at most $32(\kappa+\sqrt{\kappa k_{+}(1-j/n)})$.

Letting $\bar{t}=d(n-j)/n$, we have $t=\Theta(\bar{t})$ by Claim 3.9(a), as
reasoned in the proof of Lemma 3.10. By (3.2.1) and recalling that
$\min(1-\alpha,1-k/d)\geq 1/4$, we have the bound

$\delta_{k}(j,u)\ll\frac{3+t\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}}{(\max(1,\alpha t))^{3/2}}.$
(22)

Note that if $k<4\sqrt{\kappa k_{+}}/\sqrt{1-j/n}$, then
$\bar{t}k/d=k(1-j/n)\ll\kappa^{2}$. Similarly, if $k<4\kappa/(1-j/n)$, then
$\bar{t}k/d=k(1-j/n)\ll\kappa$. On the other hand, if
$k\geq\max\big{(}4\sqrt{\kappa k_{+}}/\sqrt{1-j/n},4\kappa/(1-j/n)\big{)}$,
then

$\alpha\geq k/d-\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}\geq k/d-k/(2d)=k/(2d).$

Thus, in both cases, $\max(1,\alpha t)\gg\bar{t}\kappa^{-2}k/d$. Hence,

$\displaystyle\delta_{k}(j,u)$
$\displaystyle\ll\kappa^{3}\frac{3+\bar{t}\max\big{(}\sqrt{\kappa
k_{+}}/(d\sqrt{1-j/n}),\kappa/(d(1-j/n))\big{)}}{(k\bar{t}/d)^{3/2}}$
$\displaystyle\ll\kappa^{3}\frac{\kappa+\sqrt{\kappa
k_{+}(1-j/n)}}{(k(1-j/n))^{3/2}}.$ (23)

We also have the trivial bound

$\delta_{k}(j,u)\leq 1.$

Hence, we have

$\displaystyle\kappa^{-6}\sum_{j=1}^{n-C^{\prime\prime}\kappa
n/d}A_{1}(j)-n^{-19}$ $\displaystyle\ll\sum_{j=1}^{n-C^{\prime\prime}\kappa
n/d}\frac{k+\sqrt{\kappa k_{+}}}{d}\left((\kappa+\sqrt{\kappa
k_{+}(1-j/n)})\cdot\min\left(1,\frac{\kappa+\sqrt{\kappa
k_{+}(1-j/n)}}{(k(1-j/n))^{3/2}}\right)\right)^{2}$
$\displaystyle\ll\frac{k+\sqrt{\kappa
k_{+}}}{d}\sum_{j\in[1,n-C^{\prime\prime}\kappa
n/d]:k(1-j/n)>1}\left((\kappa+\sqrt{\kappa
k(1-j/n)})\cdot\frac{\kappa+\sqrt{\kappa
k_{+}(1-j/n)}}{(k(1-j/n))^{3/2}}\right)^{2}$
$\displaystyle\qquad\qquad\qquad\qquad+\frac{k+\sqrt{\kappa
k_{+}}}{d}\sum_{j\in[1,n-C^{\prime\prime}\kappa n/d]:k(1-j/n)\leq
1}\kappa^{2}$ $\displaystyle\ll\frac{k+\sqrt{\kappa
k_{+}}}{d}\bigg{(}\kappa^{4}\sum_{j<n-n/k}\frac{n^{3}}{k^{3}(n-j)^{3}}+\kappa^{3}\sum_{j<n-n/k}\frac{(k+\kappa)n^{2}}{k^{3}(n-j)^{2}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\kappa^{3}\sum_{j<n-n/k}\frac{n^{2}}{k^{2}(n-j)^{2}}+\sum_{j<n-n/k}\kappa^{2}\frac{(k+\kappa)n}{k^{2}(n-j)}+\kappa^{2}\frac{n}{k}\bigg{)}$
$\displaystyle\ll\kappa^{4}\frac{k+\kappa}{d}\cdot\frac{n^{3}}{(n/k)^{2}k^{3}}+\kappa^{3}\frac{(k+\kappa)^{2}n^{2}}{k^{3}(n/k)d}+\kappa^{3}\frac{k+\kappa}{d}\cdot\frac{n^{2}}{k^{2}(n/k)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\frac{(\log
k)\kappa^{2}(k+\kappa)^{2}n}{dk^{2}}+\kappa^{2}\frac{n(k+\kappa)}{dk}$
$\displaystyle\ll\kappa^{5}n/d.$ (24)

Here, we note that $k(1-j/n)>1$ if and only if $j<n-n/k$. The first inequality
follows from applying (21) and (3.2.2). The second inequality follows from
breaking the summation into the ranges $j<n-n/k$ and $j\geq n-n/k$ and
bounding each separately. Specifically, in the range $j<n-n/k$, we use the
bound

$\kappa+\sqrt{\kappa
k_{+}(1-j/n)}\ll\kappa+\sqrt{\kappa(\kappa+k)(1-j/n)}\ll\kappa+\sqrt{\kappa
k(1-j/n)},$

and in the range $j\geq n-n/k$, we use the bound

$(\kappa+\sqrt{\kappa
k_{+}(1-j/n)})\cdot\min\left(1,\frac{3+\sqrt{(1-j/n)\kappa
k_{+}}}{(k(1-j/n))^{3/2}}\right)\ll\kappa+\sqrt{\kappa
k_{+}(1-j/n)}\ll\kappa+\sqrt{\kappa k(1-j/n)}\ll\kappa.$

The third inequality follows from applications of the inequality $(a+b)^{2}\ll
a^{2}+b^{2}$. The fourth inequality follows from the elementary bounds
$\sum_{j<n-n/k}\frac{1}{(n-j)^{s}}\ll(n/k)^{-s+1}$ for $s\geq 2$, and
$\sum_{j<n-n/k}\frac{1}{n-j}\ll\log k$, as well as the observation
$k+\sqrt{\kappa k_{+}}\ll k+\kappa$. In the last inequality, we use the bound
$(k+\kappa)/k\ll\kappa$.

Finally, in the range $j\geq n-C^{\prime\prime}\kappa n/d$, by Lemma 3.2, we
have that $A_{1}(j)\ll\kappa^{2}$ and hence

$\sum_{j=n-C^{\prime\prime}\kappa n/d}^{n}A_{1}(j)\ll\kappa^{2}\cdot\kappa
n/d=\kappa^{3}n/d.$ (25)

Combining (24) and (25), we obtain

$\sum_{j=1}^{n}A_{1}(j)\ll(\log n)^{11}n/d.$ (26)

The control of

$A_{2}(j)=\mathbb{E}_{x(j),x(u)}\left[\left(\sum_{u\in
N(j),u>j-1}\delta_{k}(j,u)(\mathbb{I}(x(j)>1-x(u))-x(u))\right)^{2}\right]$

is very similar, and we omit the details of the argument. One first considers
a realization of the random variables $x(u)$ for $u\in N(j),u>j-1$. The same
argument used in bounding $A_{1}$ then allows us to prove the same bound on
$A_{2}$:

$\sum_{j=1}^{n}A_{2}(j)\ll(\log n)^{11}n/d.$ (27)

We are now ready to finish the proof of Lemma 3.3 and hence the proof of
Theorem 1.3.

###### Proof of Lemma 3.3.

By (3) and (5), we have

$M_{n}\ll\sum_{j=1}^{n}A_{1}(j)+\sum_{j=1}^{n}A_{2}(j)\ll(\log n)^{11}n/d,$

where in the last inequality we have used (26) and (27). ∎

## References

  * [1] N. Alon and F. Wei, Irregular subgraphs, preprint, arXiv:2108.02685.
  * [2] B. Cuckler and F. Lazebnik, Irregularity strength of dense graphs, J. Graph Theory 58 (2008), 299–313.
  * [3] X. Fan, I. Grama, Q. Liu, Hoeffding’s inequality for supermartingales, Stochastic Process. Appl. 122 (2012), 3545–3559.
  * [4] R. J. Faudree and J. Lehel, Bound on the irregularity strength of regular graphs, Colloq. Math. Soc. János Bolyai 52 (1988), 247–256.
  * [5] D. A. Freedman, On tail probabilities for martingales, Ann. Probability 3 (1975), 100–118.
  * [6] A. Frieze, R. J. Gould, M. Karoński and F. Pfender, On graph irregularity strength, J. Graph Theory 41 (2002), 120–137.
  * [7] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30.
  * [8] J. Przybyło, Asymptotic confirmation of the Faudree-Lehel conjecture on irregularity strength for all but extreme degrees, J. Graph Theory 100(1) (2022), 189–204.
  * [9] J. Przybyło and F. Wei, On the asymptotic confirmation of the Faudree-Lehel Conjecture for general graphs, preprint, arXiv:2109.04317.
  * [10] J. Przybyło and F. Wei, Short proof on the asymptotic confirmation of the Faudree-Lehel conjecture, preprint, arXiv:2109.13095.