We present SynPick, a synthetic dataset for dynamic scene understanding
in bin-picking scenarios.
In contrast to existing datasets, our dataset is both situated in a realistic
industrial application domain—inspired by the well-known Amazon Robotics
Challenge (ARC)—and features dynamic scenes with authentic picking actions
as chosen by our picking heuristic developed for the ARC 2017.
The dataset is compatible with the popular BOP dataset format.
We describe the dataset generation process in detail, including
object arrangement generation and manipulation simulation using the NVIDIA PhysX
physics engine.
To cover a large action space, we perform untargeted and targeted
picking actions, as well as random moving actions.
To establish a baseline for object perception, a state-of-the-art pose estimation approach
is evaluated on the dataset.
We demonstrate the usefulness of
tracking poses during manipulation instead of single-shot estimation
even with a naive filtering approach.
The generator source code and dataset are publicly available.

§ INTRODUCTION

6D pose estimation is an important and effective perceptual tool in many robotic
applications, such as grasping (both in industrial as well as service robotics contexts),
state estimation, and prediction. It explains scene geometry using few parameters.

Learning 6D pose estimation is tricky, however. There are issues with the
problem definition itself, such as how to deal with object symmetries and other
ambiguities, or with the chosen parametrization of the SE(3) group.
A more practical issue is how to gather training data for pose estimation.
Whereas manual annotations for classification, object detection, and even
semantic segmentation can be done in reasonable time, pose annotations are both
time-consuming and prone to annotation errors.

To address these issues, it has become common practice to augment smaller-scale real datasets
with larger synthetic datasets <cit.>. We present such a synthetic
dataset specifically focused on bin picking. Our immediate inspiration is the
setting of the Amazon Robotics Challenge 2017, which required participants
to do both targeted picking of desired objects, and untargeted
emptying of totes.

(a) Initial scene     (b) Picking action

(c) Semantic annotation     (d) Physics simulation

SynPick contains typical dynamic bin picking sequences with pose & semantic segmentation annotations.

In contrast to existing datasets, our SynPick dataset does not only have static scenes, but consists of
fully dynamic picking sequences (see <ref>). It is our hope that having such a dataset
(and the accompanying generator) will enable the bin picking community to
advance from analysis of static scenes to live object tracking during manipulation.

In short, our contributions include:

* A dynamic scene generator, capable of producing realistic picking
and moving sequences, both online and offline,

* a larger-scale multi-view dataset produced with said generator and detailed analysis
of its properties, and

* a baseline evaluation of a state-of-the-art object pose estimation method and
a filtering method for tracking on the dataset.

Both generator source code and the SynPick dataset itself are publicly available[<http://ais.uni-bonn.de/datasets/synpick/>].

§ RELATED WORK

6D Pose Estimation and Tracking Datasets

Name                                               Type                 Objects     #Frames     Annotation          Diverse Lighting     Dynamics     Multi-View

YCB-Video <cit.>                 Real videos          21           133,827     Semi-auto     Yes         Static        Moving cam

Linemod-Occluded <cit.>     Real videos          8            1,214       Semi-auto     No         Static        Moving cam

TUD-L <cit.>                         Real videos          3            23,914      Semi-auto     Yes          Static        Moving cam

TYO-L <cit.>                         Real images          21           1,670       Manual        Yes          Static        No

HomebrewedDB <cit.>       Real videos          33           17,420      Semi-auto     No           Static        Moving cam

BlenderProc4BOP <cit.>              Synthetic images     flexible     50,000      Automated     Yes          Static        25 views

FAT <cit.>                    Synthetic videos     21           61,500      Automated     Yes          Falling       Stereo

ObjectSynth <cit.>       Synthetic images     39           600,000     Automated     Yes          Static         200 views

SynPick (ours)                            Synthetic videos     21           503232      Automated     Yes          Pick/Move     3 views

In recent years, with the advent of deep learning models for 6D object pose estimation,
the datasets for training and benchmarking these models have also grown in size.
The generation of large-scale datasets for 6D object pose estimation remains work-intensive, though.
Unlike obtaining ground truth annotations for 2D computer vision tasks like object detection or object classification,
annotating 6D ground truth poses is time-consuming, making the manual annotation of 6D poses on a large scale prohibitive.
Thus, most of the datasets for benchmarking 6D object pose estimation rely on semi-automated pipelines.
These pipelines involve capturing short video sequences of tabletop scenes, annotating the first frame of the sequence manually, and propagating the annotated poses to the rest of the frames by computing the camera trajectory using visual odometry techniques.
During the training of deep learning methods for 6D pose estimation, real annotated training images are often supplemented with synthetic images.
Synthetic image generation is done based on two approaches: “render & paste” and physics-based rendering (PBR). The “render & paste” technique involves rendering objects onto random backgrounds using standard rasterization.
This technique is simple and fast but generates physically unrealistic, poor-quality training images.
PBR is often implemented using ray tracing, which although compute-intensive and thus time-consuming,
generates high-quality training images.

Existing datasets for 6D object pose estimation include
YCB-Video <cit.>, Linemod-Occluded <cit.>,
HomebrewedDB <cit.>, TUD-Light (TUD-L) <cit.>,
Toyota Light (TYO-L) <cit.>, and Rutgers APC <cit.>.
See <ref> for an overview.
Each of the datasets focuses on specific real-world scenarios. <cit.> unified the existing datasets to a common BOP Dataset. Furthermore, they supplemented each dataset with PBR training images as a part of the BOP Challenge for benchmarking the progress in 6D object pose estimation research.
One of the key findings from the BOP Challenge 2020 is that 50K PBR images yield better results than 1M “render & paste” images.
This finding provides a compelling motivation to develop efficient pipelines for physics-based training image generation.
Despite the advantages, the time-consuming nature of the ray tracing methods limits their applicability. <cit.> introduced Stillleben, an efficient data generation pipeline that can generate PBR training images using OpenGL rasterization on the fly,
completely eliminating the need for an offline data generation pipeline and demonstrated the advantages of synthetic data generation for semantic segmentation tasks.

An interesting orthogonal approach to supervised pose estimation is self-supervised 6D object pose estimation proposed by <cit.>. In this approach, a 6D pose estimation module trained in a supervised manner is used to initialize the 6D poses of objects in the scene.
The robot changes the configuration of the objects in the scene by random pick and place actions. By capturing the images of objects in new configurations and propagating the initial pose estimate to these using forward kinematics, the authors generate new training data and refine the pose estimator actively.
While this method provides a scalable approach to train pose estimators, it is limited by the simple object manipulation actions the robot can perform without breaking the object pose tracking module. Our proposed method does not suffer from this limitation and can model complex object interactions accurately.
Furthermore, our data generator runs faster than real-time and can be easily parallelized.

Nearly all datasets geared towards 6D pose estimation feature only static scenes.
While the camera often travels
around the arrangement, object configurations remain fixed. In contrast, our dataset features
dynamic scenes, suitable for training and evaluating not only pose estimation, but also pose tracking methods.

[>=latex',line join=bevel,xscale=0.3,yscale=0.2,font=,
every node/.style=inner sep=0pt,text opacity=0,minimum width=10pt,minimum height=10pt
(v003_cracker_box) at (99.0bp,162.0bp) [fill=strokecolor,ellipse] 0;
(v005_tomato_soup_can) at (27.0bp,90.0bp) [fill=strokecolor,ellipse] 1;
(v006_mustard_bottle) at (209.0bp,90.0bp) [fill=strokecolor,ellipse] 2;
(v037_scissors) at (99.0bp,90.0bp) [fill=strokecolor,ellipse] 7;
(v052_extra_large_clamp) at (181.0bp,18.0bp) [fill=strokecolor,ellipse] 8;
(v009_gelatin_box) at (27.0bp,234.0bp) [fill=strokecolor,ellipse] 3;
(v025_mug) at (137.0bp,234.0bp) [fill=strokecolor,ellipse] 4;
(v035_power_drill) at (209.0bp,234.0bp) [fill=strokecolor,ellipse] 5;
(v036_wood_block) at (109.0bp,306.0bp) [fill=strokecolor,ellipse] 6;
[->] (v003_cracker_box) ..controls (74.25bp,136.94bp) and (60.476bp,123.55bp)  .. (v005_tomato_soup_can);
[->] (v003_cracker_box) ..controls (135.67bp,137.67bp) and (161.76bp,121.06bp)  .. (v006_mustard_bottle);
[->] (v003_cracker_box) ..controls (99.0bp,135.98bp) and (99.0bp,126.71bp)  .. (v037_scissors);
[->] (v003_cracker_box) ..controls (117.59bp,135.15bp) and (127.26bp,121.0bp)  .. (135.0bp,108.0bp) .. controls (147.38bp,87.192bp) and (159.9bp,62.694bp)  .. (v052_extra_large_clamp);
[->] (v006_mustard_bottle) ..controls (199.09bp,64.216bp) and (195.06bp,54.14bp)  .. (v052_extra_large_clamp);
[->] (v009_gelatin_box) ..controls (51.75bp,208.94bp) and (65.524bp,195.55bp)  .. (v003_cracker_box);
[->] (v009_gelatin_box) ..controls (27.0bp,191.67bp) and (27.0bp,147.21bp)  .. (v005_tomato_soup_can);
[->] (v035_power_drill) ..controls (172.33bp,209.67bp) and (146.24bp,193.06bp)  .. (v003_cracker_box);
[->] (v035_power_drill) ..controls (209.0bp,191.67bp) and (209.0bp,147.21bp)  .. (v006_mustard_bottle);
[->] (v036_wood_block) ..controls (104.09bp,277.53bp) and (102.04bp,264.05bp)  .. (101.0bp,252.0bp) .. controls (99.216bp,231.34bp) and (98.753bp,207.89bp)  .. (v003_cracker_box);
[->] (v036_wood_block) ..controls (80.817bp,280.94bp) and (64.309bp,266.85bp)  .. (v009_gelatin_box);
[->] (v036_wood_block) ..controls (118.91bp,280.22bp) and (122.94bp,270.14bp)  .. (v025_mug);
[->] (v036_wood_block) ..controls (142.28bp,281.7bp) and (164.74bp,265.98bp)  .. (v035_power_drill);

Picking heuristic. Starting from an RGB image and the ground truth
segmentation, our ARC 2017 pipeline <cit.> generates object
contours with suction grasp points, as well as a clutter graph describing the
scene layout. Each edge in the graph points from the object on top to the
object below.

Most related to our work is the Falling Things Dataset (FAT) <cit.>. It consists of renderings of randomly sampled
subsets of YCB objects placed in different indoor and outdoor scenes. Unlike most other datasets, FAT does not
include tabletop scenes where the objects are nicely arranged without significant occlusions. Instead, the objects are dropped
from a height onto the scenery, using a physics engine to model object interactions.
However, both the context (kitchen/temple/forest) as well as the dynamics (objects falling on the background
geometry) do not really fit a bin picking application. In comparison, our dataset features a standard picking
tote and demonstrates pick and move dynamics.

§ DATASET GENERATION

We use Stillleben <cit.> as the base rendering engine for generating the SynPick dataset,
as it has built-in physics simulation for table-top arrangements and is capable of online generation.
However, Stillleben was developed for fast scene generation of different scenes. In this section, we describe the
extensions to Stillleben we developed to adapt it for generation of continuous bin picking sequences
and detail the dataset generation process.

§.§ Scene Generation

We rely on Stillleben's scene arrangement engine for physically realistic scene generation.
We start with adding the tote object to the scene. Then, we randomly sample a set of objects such that the total volume of the objects does not exceed a threshold of 7 l, which generates scenes that contain many occlusions.
We let the objects fall into the tote from a fixed height and simulate the effect of gravity and collision with other objects and the tote.
Stillleben internally uses the PhysX engine by NVIDIA[PhysX: <https://developer.nvidia.com/physx-sdk>] for simulation.
We use meshes provided by the YCB-Video dataset <cit.> for rendering.
Simulating collisions with these high-resolution meshes would be prohibitively slow. For most objects, we compute
convex hulls of low complexity.
For three highly concave objects (, , and ), we use the V-HACD <cit.> convex decomposition algorithm to find a number of smaller convex meshes describing the geometry accurately.

Lighting variants. We show the same object arrangement in different sIBL light maps.

After the scene arrangement has been generated, we start the generation of training frames. During generation,
we run PhysX simulation with a very small step size of 2 ms to ensure realistic behavior.
With a rate of 15 Hz (relative to simulated time), we generate output frames from three different camera poses
above the tote.
The simulated cameras have Full HD resolution (1920$\times$1080) and are mounted 2 m above the tote, similar
to our ARC 2017 system <cit.>.

For RGB rendering, the standard Stillleben pipeline is used. A physics-based rendering shader pipeline combined
with randomly selected image-based lighting (IBL) maps from the sIBL archive[<http://www.hdrlabs.com/sibl/archive.html>] ensure interesting and realistic lighting effects (see <ref>).

In the following sections, we describe the simulation of pick and move actions in detail.

§.§ Untargeted Picking

In the pick task simulation, we simulate the robot emptying the tote by picking the objects out of the tote,
similar to the Stow task of the Amazon Robotics Challenge 2017.
Starting with the tote filled with objects in random configurations generated by the arrangement engine,
we follow the pick planning and grasp heuristics selection strategy proposed by <cit.>. See <ref> for a visualization.
We substitute the semantic segmentation network with the ground-truth segmentation masks produced by Stillleben.
After extracting object contours, ideal suction points are found inside the contour. Depending on object weight,
either the pole of inaccessibility <cit.>, i.e. the point with maximum distance to the contour
is found to minimize the chance of catching other objects, or the center of mass is computed from the contour to ensure
good mass distribution.

The system introduced by <cit.> also computes a clutter graph, identifying which object
is resting on top of which object. The final decision on which object to pick is based on this graph, ensuring
that we do not attempt to grasp objects caught beneath others.

Articulated gripper. The cone-shaped finger
ends in an actuated tiltable suction cup (joint axis marked in red).

Once the target object and the corresponding suction point are determined, we find an inverse kinematics solution
for the articulated gripper (see <ref>), which places the suction cup orthogonally on the local surface, as estimated
by a local average of the pixel-wise normals. A gripper trajectory is then computed to bring the gripper to
the target pose, apply suction, and lift the object out of the tote.

The gripper is moved along the trajectory using Cartesian impedance control, with a stiffness of 2500 $\frac{N}{m}$ and
a spring damping of 200 $\frac{Ns}{m}$. The force exerted by the impedance control is limited to 200 $N$.
The high stiffness simulates an industrial robotic arm holding the gripper in place.

Exemplary scenes from the dataset demonstrating the evolution of the scene while the gripper is performing picking (a) and moving (b) actions. Objects in the tote are covered/uncovered as the scene evolves.

Once the target position is reached, switching on the suction is simulated by performing ten raycasts in gripper
direction, emitting from the gripper perimeter. Every object hit by the raycast (with a maximum distance of 3 cm) is
considered caught. For every caught object, a PhysX joint is created between it and the suction cup,
simulating a strong force pulling the object against the gripper as well as limiting its orientation relative to the
The joints have a force limit of 40 $N$ or 2 $N$, depending on whether all rays found a target (indicating a
good vacuum seal). If the force required to keep the object at the suction cup exceeds this limit, the joint
breaks and the object is dropped back into the tote.

The picking process is repeated until the tote is empty. If three picking attempts
have failed, we also stop the sequence to prevent infinite loops.
An example sequence is shown in <ref>a).

§.§ Targeted Picking

In a second mode, we simulate targeted picking, where a specific object
needs to be extracted. We run the same pipeline as above, with one key difference:
We choose the object which is occluded most, i.e. is at the bottom of the
clutter graph. This choice should lead to more complex object interactions during picking.

§.§ Moving

As a third possible action, we perform a non-picking manipulation sequence. The goal
is to disturb the object arrangement so that other objects become visible.

We simulate the move action by moving the gripper, starting from one corner inside the tote, to
all four corners in random order. The gripper is moved at a fixed velocity of 0.1 $\frac{m}{s}$.
In this mode, the gripper is operated with a lower stiffness of 1000 $\frac{N}{m}$ and
a force limit of 30 $N$. This ensures we do not squeeze objects against the immovable
tote too much, which could result in instability of the physics simulation.
An exemplary scene for the move action is shown in <ref>b).

§ DATASET STATISTICS

Datasets statistics

Mode     Split     Frames      Object visibility

Untargeted pick     train     137,544     0.77

Move                train     99,786     0.67

Targeted pick       train     164,991     0.77

Untargeted pick     test      31,119     0.77

Move                test      23,910     0.69

Targeted pick       test     45,882     0.75

Total         503232     0.74

Number of frames in each SynPick dataset split along with the corresponding mean visibility fraction.

ybar stacked,
bar width=0.2cm,
legend columns=3,
legend style=

at=(0.5,1.1), anchor=south,
reverse legend=true,
xticklabels from table=Label,
xticklabel style=rotate=50,anchor=east, font=,
ticklabel style=font=,
cycle list/Set1-6,
table [y=trainpick, meta=Label, x expr=]
Untargeted pick-train
table [y=trainmove, meta=Label, x expr=]
+[fill,point meta=y]
table [y=trainbad, meta=Label, x expr=]
Targeted pick-train
+[fill,point meta=y]
table [y=testpick, meta=Label, x expr=]
Untargeted pick-test
+[fill,point meta=y]
table [y=testmove, meta=Label, x expr=]
+[draw=cyan!80,fill=cyan!80,point meta=y]
table [y=testbad, meta=Label, x expr=]
Targeted pick-test

Number of 6D pose annotations for each object category present in SynPick dataset splits.

§.§.§ Number of Frames

SynPick consists of 240 scenes for training and 60 scenes for testing for each of the targeted pick, untargeted pick, and move tasks.
Each scene consists of a varying number of frames. In <ref>, we present the number of frames present in each split.

§.§.§ Mean Visibility Fraction

Like in any computer vision task, occlusions present a significant hindrance for 6D pose estimation.
A prerequisite for training robust 6D pose estimation models is a dataset that captures real-world occlusion scenarios.
Physically realistic simulation of dynamic bin picking scenes captures more realistic occlusion scenarios that are not captured
in a static scene. To analyze the degree of occlusions present in the SynPick dataset,
we present in <ref>, the mean visibility fraction for the different SynPick dataset splits.

§.§.§ Object Distribution

As discussed in <ref>, the arrangement engine picks objects at random until the total volume exceeds a threshold.
In <ref>, we present the distribution of object categories across various splits of the SynPick dataset.

§ BASELINE OBJECT PERCEPTION METHODS

§.§ Single-View RGB(D) 6D Pose Estimation

State-of-the-Art Methods
The state-of-the-art methods for single-view RGB(D) pose estimation are predominantly deep-learning-based.
Some example methods include direct-regression <cit.>,
keypoint-based methods <cit.>,
render-and-compare methods <cit.>, and augmented
autoencoders <cit.>. The BOP Challenge is organized to benchmark the progress
of 6D pose estimation methods <cit.>.

Baseline Method
We evaluate CosyPose <cit.>, the state-of-the-art winning entry of BOP Challenge 2020 <cit.>, on the SynPick dataset to establish
a baseline for our dataset. CosyPose consists of an object detection module, a coarse refinement module,
and a fine refinement module. The coarse and fine refinement modules, based on DeepIM <cit.>, formulate
6D pose estimation as an iterative refinement process. The coarse refinement module estimates an initial 6D pose given the
canonical pose of the object as the input. It is trained completely on a large synthetically generated dataset. In contrast,
the fine refinement module that estimates an accurate 6D pose given the coarse 6D pose as an input is trained using the YCB-Video
dataset, disturbing the ground truth pose annotations to form inputs to be corrected by the network.
Since the coarse refinement module is trained only on a domain-agnostic synthetic dataset,
fine-tuning it on the SynPick dataset is not necessary.
Thus, we directly use the coarse refinement module weights provided by the
authors, whereas we fine-tune the object detection and
fine pose refinement module on the SynPick dataset.

Evaluation results on our test splits are presented in <ref>.

Evaluation Metrics
We use the area under the  accuracy-threshold curve (AUC) of ADD and ADD-S metrics for varying thresholds between 0 and 0.1m <cit.>.
ADD metric is the average distance between the model points in ground truth and estimated poses. Formally,

\begin{equation}
\text{ADD} = \frac{1}{m} \sum_{x \in \mathcal{M}} \| (\mathbf{Rx} + \mathbf{T}) - (\widetilde{\mathbf{R}}\mathbf{x}  + \widetilde{\mathbf{T}})  \|
\end{equation}

where $\mathcal{M}$ is the set of 3D model points with $m$ number of points, $\mathbf{R}$ and $\mathbf{T}$ are orientation and translation
components of ground truth 6D pose, and $\widetilde{\mathbf{R}}$ and $\widetilde{\mathbf{T}}$ are estimated orientation and translation, respectively.

Objects that exhibit symmetries perform poorly on the ADD metric. ADD-S is a variant of ADD metric that takes symmetries into account by formulating an ICP-like metric that selects closes points:

\begin{equation}
\text{ADD-S} = \frac{1}{m} \sum_{x_1 \in \mathcal{M}} \min_{x_2 \in \mathcal{M}} \| (\mathbf{Rx_1} + \mathbf{T}) - (\widetilde{\mathbf{R}}\mathbf{x_2}  + \widetilde{\mathbf{T}})  \|.
\end{equation}

Evaluation metrics.

columns=Class, CosyPoseADD, CosyPoseICPADDS, AlphalowADD, AlphalowADDs, AlphahighADD, AlphahighADDs,
every column/.style=
column type=r,
/pgf/number format/fixed,
/pgf/number format/fixed zerofill,
/pgf/number format/precision=1,
column name=Object,
column type=l,
string type,
string replace=SymCClass-wise average,
column name=ADD,
multiply with=100,
column name=ADD-S,
multiply with=100,
column name=ADD,
multiply with=100,
column name=ADD-S,
multiply with=100,
column name=ADD,
multiply with=100,
column name=ADD-S,
multiply with=100,
every head row/.style=
before row=    2cCosyPose
2cFilter $\alpha$=0.05
2cFilter $\alpha$=0.2

(lr) 2-3
(lr) 4-5
(lr) 6-7
after row=,
every last row/.style=after row=

§.§ 6D Pose Tracking

[spy using outlines=circle, magnification=1.8, size=0.5cm, connect spies,
m/.style=below,circle,fill=red!50,inner sep=2pt
[cycle list/Set1-4, legend pos=south west, ymax=2.2, ymin=1, legend cell align=left, xlabel=Frame number, ylabel=$z$ position [m]]
+[mark=none] table [x=t,y=gtz] ;
Ground truth

+[mark=none] table [x=t,y=pz] ;

+[mark=none] table [x=t,y=fz] ;
Filter $\alpha$=0.05

+[mark=none] table [x=t,y=f2z] ;
Filter $\alpha$=0.2

(spypoint) at (axis cs:160,1.95);
(glass) at (axis cs:600,1.35);

[m] at (axis cs:23, 2.2) ;
[m] at (axis cs:75, 2.2) ;
[m] at (axis cs:127, 2.2) ;
[m] at (axis cs:180, 2.2) ;
[m] at (axis cs:232, 2.2) ;
[m] at (axis cs:284, 2.2) ;
[m] at (axis cs:337, 2.2) ;
[m] at (axis cs:389, 2.2) ;
[m] at (axis cs:442, 2.2) ;
[m] at (axis cs:494, 2.2) ;
[m] at (axis cs:546, 2.2) ;
[m] at (axis cs:599, 2.2) ;
[m] at (axis cs:651, 2.2) ;
[m] at (axis cs:703, 2.2) ;
[m] at (axis cs:756, 2.2) ;
[m] at (axis cs:808, 2.2) ;
[m] at (axis cs:860, 2.2) ;

[green!70!black,size=3cm] on (spypoint) in node [fill=white] at (glass);

Position trajectory ($z$ axis) of the scissors object in the first test scene.
We show raw CosyPose predictions and an exponentially moving average with different
recursive filter coefficients $\alpha$. The time of each pick attempt has been marked with a red circle.

The 6D pose estimation baseline established in <ref> is useful,
but does not really capture a real bin picking situation. In our picking scenario,
which is typical for industrial applications, a tote of objects is emptied completely,
object by object. It is certainly beneficial to monitor the object poses over time,
to make use of dependencies between frames.
This way, not only temporary effects such as occlusions by the gripper or other objects
can be mitigated, but noisy predictions can also be smoothed to obtain a more precise
estimate than from a single frame alone.

State of the Art

While there are many works on single-view pose estimation, the research field
in 6D pose tracking is narrower, but just as diverse.
<cit.> present a 6D pose estimation
and tracking framework based on self-supervised sparse keypoints.
<cit.> formulate the pose tracking problem in the particle filter framework.
In contrast, <cit.> follow a render-and-compare approach to perform
very fast 6D pose tracking with 90 fps.

We present a naive tracking baseline based on the CosyPose approach evaluated in
<ref>. This baseline is intended to demonstrate the low-hanging
fruit which can be reached by temporal filtering. We implement an exponentially moving
average (EMA) with recursive filter coefficient $\alpha$:

\begin{equation}
\hat{t}_n = (1-\alpha) \hat{t}_{n-1} + \alpha t_{n},
\end{equation}

where $t_n$ is the CosyPose translation estimate at frame $n$ of the sequence
and $\hat{t}_n$ is the filtered output.
The object orientations are filtered very similarly, but in quaternion space
in order to interpolate the orientations correctly:

\begin{equation}
\hat{q}_n = \textrm{slerp}(\hat{q}_{n-1}, q_n, \alpha),
\end{equation}

where slerp is the spherical linear interpolation function, which interpolates
with $0<\alpha<1$ between the two given rotations.

<Ref> shows a sequence of raw CosyPose translation predictions in the $z$ axis (into the image) for one exemplary object.
It can be seen that CosyPose exhibits both stationary noise as well as large deviations,
which are mostly caused by temporary occlusions—either by the gripper or other objects.
While our naive filtering cannot address steady-state errors, it does smoothen the
stationary noise and softens the large jumps caused by occlusions.
<Ref> corroborates these results: Both ADD and ADD-S scores
benefit from filtering.

§ DISCUSSION & CONCLUSION

We presented the SynPick dynamic bin-picking dataset together with its
online generator. Our baseline experiments demonstrate that
state-of-the-art can achieve good per-frame accuracy, but also that
temporal filtering should be employed to correct both estimator noise
and effects of temporary occlusions.
Further research in the applicability of recent tracking approaches
to industrial robotics applications is definitely warranted.
We hope that our dataset can serve as an inspiration to researchers
in the field of bin picking and facilitates 6D object tracking for industrial automation.

§ ACKNOWLEDGMENT

This research has been supported by an Amazon Research Award and by the Competence Center for Machine Learning Rhine Ruhr
(ML2R), which is funded by the Federal Ministry of Education and Research of Germany (grant no. 01—S18038A).

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

booktitleEuropean Conference on Computer Vision (ECCV)
titleBOP: Benchmark for 6D object pose estimation

booktitleRobotics: Science and Systems (RSS)
titlePoseCNN: A Convolutional Neural Network for 6D Object
Pose Estimation in Cluttered Scenes

booktitleEuropean Conference on Computer Vision (ECCV)
titleLearning 6D object pose estimation using 3D object

booktitleIEEE International Conference on Computer Vision (ICCV)
titleHomebrewedDB: RGB-D dataset for 6D pose estimation of
3D objects

booktitleEuropean Conf. on Computer Vision (ECCV)
titleBOP challenge 2020 on 6D object localization

booktitleIEEE/CVF Conference on Computer Vision and Pattern
Recognition (CVPR) Workshops
titleFalling things: A synthetic dataset for 3D object detection
and pose estimation

booktitleIEEE International Conference on Image Processing (ICIP)
titlePhotorealistic image synthesis for object instance detection

titleA dataset for improved RGBD-based object detection and pose
estimation for warehouse pick-and-place
journaltitleIEEE Robotics and Automation Letters (RA-L)

booktitleIEEE International Conference on Robotics and Automation
titleStillleben: Realistic scene synthesis for deep learning in

booktitleInt. Conference on Robotics and Automation (ICRA)
titleSelf-supervised 6D object pose estimation for robot

booktitleInternational Conference on Robotics and Automation
titleFast object learning and dual-arm coordination for cluttered
stowing, picking, and packing

AK Peters

booktitleGame Engine Gems 3
titleVolumetric hierarchical approximate convex decomposition

Taylor & Francis

titlePoles of inaccessibility: A calculation algorithm for the
remotest places on earth
journaltitleScottish Geographical Journal

booktitleIEEE/CVF Conference on Computer Vision and Pattern
Recognition (CVPR)
titleDenseFusion: 6D object pose estimation by iterative dense

booktitleIEEE Conference on Computer Vision and Pattern
Recognition (CVPR)
titleReal-time seamless single shot 6D object pose prediction

booktitleConf. on Computer Vision and Pattern Recognition (CVPR)
titlePVNet: Pixel-wise voting network for 6DOF pose

booktitleIEEE International Conference on Computer Vision (ICCV)
titleBB8: A scalable, accurate, robust to partial occlusion
method for predicting the 3D poses of challenging objects without using

booktitleEuropean Conference on Computer Vision (ECCV)
titleMaking Deep Heatmaps Robust to Partial Occlusions for 3D
Object Pose Estimation

booktitleEuropean Conference on Computer Vision (ECCV)
titleDeepIM: Deep iterative matching for 6D pose estimation

booktitleConference on Computer Vision and Pattern Recognition
titlePFRL: Pose-Free Reinforcement Learning for 6D Pose

booktitleInternational Conf. on Humanoid Robots (Humanoids)
titleRefining 6D object pose predictions using abstract

booktitleEuropean Conference on Computer Vision (ECCV)
titleImplicit 3D Orientation Learning for 6D Object Detection
from RGB Images

booktitleRobotics: Science and Systems (RSS)
titlePoseRBPF: A Rao-Blackwellized Particle Filter for 6D
Object Pose Tracking

booktitleEuropean Conference on Computer Vision (ECCV)
titleCosyPose: Consistent multi-view multi-object 6D pose

booktitleIEEE International Conference on Robotics and Automation
title6-PACK: Category-level 6D pose tracker with anchor-based

booktitleIEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS)
titleSE(3)-TrackNet: Data-driven 6D Pose Tracking by
Calibrating Image Residuals in Synthetic Domains


# The concentration inequality for a discrete height function model perturbed
by random potential

Andrew Krieger  Department of Mathematics, University of California, Los
Angeles<EMAIL_ADDRESS>
###### Abstract.

We present a proof of the concentration inequality for a discrete random
surface model, where the underlying potential is perturbed by an additive
random potential. The proof is based on annealing the random potential, and
follows the method of [CEP96] and other works. Our result demonstrates the
robustness of this method.

###### Key words and phrases:

Concentration inequality, random surfaces.

###### 2010 Mathematics Subject Classification:

82B41

##  1\. Introduction

Random surface models are common objects of study in statistical physics and
combinatorics (e.g. [Geo88, She05]). Random surface models describe membrane
surfaces or hypersurfaces whose formation and shape are governed on the
microscopic scale by a random interaction or process. One is interested in
predicting the macroscopic behavior using data about the microscopic random
process. There is a wide literature studying many different random surface
models. A incomplete list includes domino tilings and dimer models (e.g.
[Kas63, CEP96, CKP01]), polymer models (e.g. [BP18, BY19]), lozenge tilings
(e.g. [Des98, LRS01, Wil04]), Ginzburg-Landau models (e.g. [DGI00, FO04]), the
Ising model (e.g. [DKS92, Cer06]), asymmetric exclusion processes (e.g.
[FS06]), sandpile models (e.g.[LP08]), the six vertex model (e.g. [BCG16,
CS16, RS18]), and Young tableaux (e.g. [LS77, VK77, PR07]). Most relevant to
the current work are discrete Lipschitz functions (e.g. [PSY13, Pel17, LT20])
and graph homomorphisms from certain discrete graphs to $\mathbb{Z}$ (e.g.
[BHM00, Kah01, Gal03, CPST20]).

The specific model studied here is built upon graph homomorphisms from
subgraphs of the nearest-neighbor lattice $\mathbb{Z}^{m}$ ($m\geq 1$) into
the graph $\mathbb{Z}$, again with nearest-neighbor edge structure; in the
sequel these are called “height functions.” In dimension $m=2$ these
$\mathbb{Z}$-valued graph homomorphisms correspond to height functions of the
six-vertex model, under the convention used in [Sri16]. The model is extended
by assigning random weights to all such graph homomorphisms depending on the
height values they take (see the definition of the perturbed measures
$\mu(\cdot,\omega)$ in Definition 6 below). Homogenization of this model was
previously studied by the current author in conjunction with coauthors in
[KMT21], and the same group of authors studied the underlying model (i.e.
$\mathbb{Z}$-valued graph homomorphisms from subsets of $\mathbb{Z}^{m}$,
without random perturbation) in [KMT20].

The main result of this note is the concentration inequality, presented as
Theorem 8 below. Our result implies that the probability mass of a perturbed
random distribution $\mu(\cdot,\omega)$ concentrates on functions that are
“close,” relative to the size of the domain, to the
$\mu(\cdot,\omega)$-expected height at each point in the domain. To properly
ground this result in the surrounding literature, let us consider analogues of
the concentration inequality in other settings. Generally, concentration
inequalities control the magnitude and likelihood of fluctuations of a random
variable, especially a random statistic that quantifies some large-scale
property of an underlying random system. The concentration inequality is a
bound on the probability that the random variable differs from its expected
value (or sometimes, another typical value) by more than $t>0$ (in some
metric). The probability bound vanishes as $t\to\infty$ or as the size of the
underlying random system goes to infinity. The simplest example is the weak
law of large numbers (cf. [Dur10, Theorem 2.2.3]): Let $X_{1},\dotsc,X_{n}$ be
uncorrelated random variables (meaning that $E(X_{i}X_{j})=E(X_{i})E(X_{j})$
for $i\neq j$), all with common mean $\mu\in\mathbb{R}$ and common variance
bound $E[(X_{i}-E(X_{i}))^{2}]\leq\sigma^{2}$ for some $\sigma^{2}>0$. Define
$M_{n}=(X_{1}+\dotsb+X_{n})/n$. Then $E(M_{n})=\mu$ and for any $t>0$,

$P\biggl{(}|M_{n}-\mu|>\frac{t}{\sqrt{n}}\biggr{)}\leq\frac{\sigma^{2}}{t^{2}}.$

Focusing on random surface models, concentration inequalities are closely
related to the limit shape phenomenon. A limit shape occurs when samples of
the random microscopic model converge with high probability to a deterministic
shape, i.e. the limit shape, under a suitable scaling limit. The concentration
inequality provides a route towards proving the existence of a limit shape.
Indeed, the concentration inequality implies that when the system size is
large, a sample of the model is close to the expected value for that system
size, with high probability; see for example Figure 1. Then it remains to show
that these expected values converge as the system size tends to infinity, and
the limit is necessarily the limit shape for the model. This convergence can
be established by means of a variational principle, which characterizes the
limit shape via a variational problem. See e.g. [MT20, Theorem 2.12], which is
the variational principle for a similar model, and whose proof is based on a
concentration inequality [MT20, Theorem 3.10]. Let us also mention the
concentration inequality [CEP96, Theorem 21], whose proof is the inspiration
for the work that follows. Finally we cite Chapter 7 of [She05]. There, a
large deviations principle is proved for a wide class of random surface
models, and [She05] also explains how concentration inequalities can be
derived from that large deviations principle under certain conditions (i.e.
uniqueness of the minimizer of the rate function).

(a) $25\times 25$ system.

(b) $25\times 25$ system.

(c) $100\times 100$ system.

(d) $100\times 100$ system.

Figure 1.  Pictured are 3D plots of height functions on $\mathbb{Z}^{2}$. The
domains are respectively $25\times 25$ and $100\times 100$ grids, realized as
square faces, and the height values assigned by the height function are
indicated by the height of the column above each square face. Boundary values
are fixed, and are chosen so as to increase or decrease as rapidly as possible
along each boundary edge. It is visually apparent that each sample is close to
a smooth limiting shape, except for small fluctuations, and that on the larger
domain, the fluctuations are smaller relative to the domain size. This
illustrates the conclusion of the concentration inequality.

Now, let us describe our strategy for proving the homogenized concentration
inequality. For the simpler case of random surface models without random
perturbations, there are two approaches in the literature to proving the
concentration inequality directly: an approach that leverages monotonicity and
stochastic dominance (e.g. [CEP96, LT20]) and a dynamic approach using a
natural Markov chain on height functions (e.g. [MT20]). The second approach
does not easily carry over to the case of random perturbations. It relies on
monotonicity on the quenched level (i.e. with fixed random potential
$\omega$), but monotonicity only occurs in the annealed setting (i.e. after
averaging over $\omega$). This complicates the dynamic structure of the second
approach. Therefore we use the first approach. See the statement and proof of
Lemma 10 for details.

The remainder of this note is divided into two sections. Section 2 defines the
model in detail, and Section 3 provides the exact statement proof of the
concentration inequality.

##  2\. Definitions

The notation and definitions below are similar to those in [KMT21]. For
further explanation and further examples, we kindly refer the reader to
[KMT21, Section 2].

Throughout the sequel, whenever $\mathbb{Z}^{m}$ is viewed as a graph, the
edge set is always taken to be the collection of all nearest neighbor edges;
in other words, two points $x,y\in\mathbb{Z}^{m}$ are adjacent if and only if
the $\ell^{1}$ distance $|x-y|_{1}$ is exactly $1$. Likewise, subsets of
$R\subset\mathbb{Z}^{m}$ are taken to be graphs with the induced subgraph
structure, so any two vertices $x,y\in\Lambda\subset\mathbb{Z}^{m}$ are
adjacent if and only if $|x-y|_{1}=1$. We assume that the subgraph
$R\subset\mathbb{Z}^{m}$ is connected. The edges of these graphs are written
as $e_{x,y}$ for the edge connecting $x,y\in\mathbb{Z}^{m}$. These are
undirected edges, i.e. $e_{y,x}=e_{x,y}$.

######  Definition 1 (Height function).

A height function on a connected subgraph $R\subset\mathbb{Z}^{m}$ is a
parity-preserving graph homomorphism $h_{R}:R\to\mathbb{Z}$. In other words,
if $x,y\in R$ and $x\sim y$, then $\lvert h_{R}(x)-h_{R}(y)\rvert=1$, and for
any $x=(x_{1},\dotsc,x_{m})\in R$,

(1) $h_{R}(x)=\sum_{i=1}^{m}x_{i}\pmod{2}.$

The set of all height functions on $R$ is denoted as

(2) $M(R):=\bigl{\\{}h_{R}:R\to\mathbb{Z}\,\big{|}\,\text{$h_{R}$ is a height
function}\bigr{\\}}$

and given a subgraph $R^{\prime}\subset R$ and a height function
$h_{R^{\prime}}\in M(R^{\prime})$, the set of height functions extending
$h_{R^{\prime}}$ to $R$ is denoted as

(3) $M(R;h_{R^{\prime}}):=\bigl{\\{}h_{R}\in
M(R)\,\big{|}\,h_{R}|_{R^{\prime}}=h_{R^{\prime}}\bigr{\\}}.$

The set $M(R)$ is never empty; indeed, the function $h_{R}$ that maps each
point in $R$ to either $0$ or to $1$ according to the parity of the source
point is a height function. A natural question to ask is under which
conditions the set of extensions $M(R;h_{R^{\prime}})$ is nonempty. Necessary
and sufficient conditions are given by the Kirszbraun theorem for functions on
$\mathbb{Z}^{d}$, which is a discrete analogue of the classical Kirszbraun
theorem for Lipschitz functions on $\mathbb{R}^{d}$. This is a well-known
result (see e.g. [She05, Lemma 4.3.1]), and we omit the proof from this
article.

######  Theorem 2 (Kirszbraun theorem for $\mathbb{Z}^{d}$).

Let $R$ be a connected region of $\mathbb{Z}^{m}$, let $R^{\prime}$ be a
subset of $R$, and let $h^{\prime}:R^{\prime}\to\mathbb{Z}$ be a graph
homomorphism that preserves parity. There exists a graph homomorphism
$h:R\to\mathbb{Z}$ such that $h=h^{\prime}$ on $R^{\prime}$ if and only if for
all $x,y\in R^{\prime}$,

(4) $\bigl{|}h^{\prime}(x)-h^{\prime}(y)\bigr{|}\leq d_{R}(x,y),$

where $d_{R}$ denotes the graph distance on $R$.

######  Remark 3.

One might hope to derive sufficient conditions that are easier to verify, such
as the following: suppose that $R^{\prime}$ is a line segment, i.e.
$R^{\prime}=\\{v,v+e,v+2e,\dotsc,v+(\ell-1)e\\}$ for some $\ell\in\mathbb{N}$
and $v,e\in\mathbb{Z}^{d}$ with $|e|_{1}=1$. Then $R^{\prime}$ is an isometric
subgraph of $R$, meaning that for any points $x,y\in R^{\prime}$,
$d_{R^{\prime}}(x,y)=d_{R}(x,y)$. Indeed, clearly $d_{R^{\prime}}(x,y)\geq
d_{R}(x,y)$, and for any $i,j$, by observation
$d_{R^{\prime}}(v+ie,v+je)=|i-j|=d_{\mathbb{Z}^{d}}(v+ie,v+je)\leq
d_{R}(x,y)$. Since $R^{\prime}$ is an isometric subgraph of every $R\supseteq
R^{\prime}$, it follows that for any $h_{R^{\prime}}\in M(R^{\prime})$ and any
$x,y\in R^{\prime}$, we have $|h_{R^{\prime}}(x)-h_{R^{\prime}}(y)|\leq
d_{R^{\prime}}(x,y)=d_{R}(x,y)$. Thus by the Kirszbraun theorem
$h_{R^{\prime}}$ admits at least one extension to $R$. This idea can be pushed
a little bit farther. For example, the exact same argument works whenever
$R^{\prime}$ is a geodesic, i.e. a shortest path between two points in $R$; a
similar argument via the isometric subgraph property applies when ever
$R^{\prime}$ is a box, i.e. when
$R^{\prime}=\\{(z_{1},\dotsc,z_{i})\in\mathbb{Z}^{d}\colon a_{i}\leq z_{i}\leq
b_{i}\\}$ for some $a_{1}\leq b_{1},\dotsc,a_{d}\leq b_{d}$. However, this
approach ultimately is not fruitful for our current purposes. The motivating
example we use is the case where $R$ is a box and $R^{\prime}$ is its
boundary, and one can check easily that this subgraph $R^{\prime}$ is not
isometric. For example, in two dimensions, if
$R=\\{0,1,2\\}\times\\{0,1,2\\}$, then the opposite midpoints $(0,1)$ and
$(2,1)$ have $d_{R^{\prime}}((0,1),(2,1))=4>2=d_{R}((0,1),(2,1))$. Indeed, one
can check that there is a unique height function on $R^{\prime}$ with
$h_{R^{\prime}}((0,1))=1$ and $h_{R^{\prime}}((2,1))=5$, which violates the
Kirszbraun hypothesis (4). As such, in the sequel we must account for the
possibility that $M(R;h_{R^{\prime}})$ may be empty for some or even for all
$h_{R^{\prime}}\in M(R^{\prime})$.

Moving on to the random potential, the assumptions we make are the same as in
[KMT21], namely:

######  Assumption 4 (Random potential $\omega$).

Let $\omega=(\omega_{e})_{e\in E(\mathbb{Z})}\in\mathbb{R}^{E(\mathbb{Z})}$
denote a random potentials, defined on the set of edges $E(\mathbb{Z})$ of
$\mathbb{Z}$, that satisfies the following assumptions:

  * •

$\omega$ is almost surely finite, in the sense that

(5) $\displaystyle C_{\omega}:=1\vee\sup_{e\in
E(\mathbb{Z})}\lvert\omega_{e}\rvert\in L^{1}\qquad\text{(i.e.\
$\mathbb{E}[C_{\omega}]<\infty$)}.$

  * •

$\omega$ is shift invariant, i.e. for any $k\in\mathbb{N}$, any edges
$e_{x_{1},y_{1}},\dotsc,e_{x_{k},y_{k}}\in E(\mathbb{Z})$, any
$z\in\mathbb{Z}$, and any bounded and measurable function
$\xi:\mathbb{R}^{k}\to\mathbb{R}$,

(6)
$\mathbb{E}\bigl{[}\xi(\omega_{e_{x_{1},y_{1}}},\dotsc,\omega_{e_{x_{k},y_{k}}})\bigr{]}=\mathbb{E}\bigl{[}\xi(\omega_{e_{x_{1}+z,y_{1}+z}},\dotsc,\omega_{e_{x_{k}+z,y_{k}+z}})\bigr{]}.$

  * •

Moreover, the random potential $\omega$ is ergodic with respect to the set of
shifts $\\{\tau_{z}\,|\,z\in\mathbb{Z},\,z=0\pmod{2}\\}$, where
$\tau_{z}(e_{x,y})=e_{x+z,y+z}$. This means that if $E=\tau_{2}^{-1}(E)$, then
$\mathbb{P}(E)\in\\{0,1\\}$.

  * •

As a matter of normalization, assume that $\mathbb{E}[\omega_{(0,1)}]=0$.

######  Definition 5 (The Hamiltonian).

Given a finite connected graph $R\subset\mathbb{Z}^{m}$, the interior
Hamiltonian $H^{\circ}_{R}:M(R)\to\mathbb{R}$ and the exterior Hamiltonian
$H^{+}_{R}:M(R^{+})\to\mathbb{R}$ are defined as

(7) $H^{\circ}_{R}(h_{R},\omega)=\sum_{e\in
E(R)}\omega_{h_{R}(e)}\qquad\text{and}\qquad
H^{+}_{R}(h_{R^{+}},\omega)=\sum_{e\in E(R^{+})}\omega_{h_{R^{+}}(e)},$

where $R^{+}:=R\cup\\{x\in\mathbb{Z}^{m}\colon\exists y\in R,x\sim y\\}$ is
the extension of the subgraph $R$ by all neighboring vertices in the ambient
graph $\mathbb{Z}^{m}$.

######  Definition 6 (Quenched measure).

Given a realization $\omega$ of the random potential and a set $A\subset M(R)$
of height functions, the partition function $Z_{\omega}(A)$ is given by

(8) $Z_{\omega}(A)=\sum_{h_{R}\in
A}\exp\bigl{(}H^{\circ}_{R}(h_{R},\omega)\bigr{)}\,.$

Given a subgraph $R^{\prime}\subset R$, a height function $h_{R^{\prime}}\in
M(R^{\prime})$, and a realization $\omega$ of the random potential, the
perturbed measure $\mu_{M(R;h_{R^{\prime}})}(\cdot,\omega)$ is the probability
measure on the finite space $M(R;h_{R^{\prime}})$, defined on atoms $h_{R}\in
M(R;h_{R^{\prime}})$ by

(9)
$\mu_{M(R;h_{R^{\prime}})}(h_{R},\omega):=\frac{\exp\bigl{(}H^{\circ}_{R}(h_{R},\omega)\bigr{)}}{Z_{\omega}\bigl{(}M(R;h_{R^{\prime}})\bigr{)}}.$

######  Definition 7 (Annealed measure).

Below we prove that, for any $R^{\prime}\subset R$ and any $h_{R^{\prime}}\in
M(R^{\prime})$, the function
$(\omega,A)\mapsto\mu_{M(R;h_{R^{\prime}})}(A,\omega)$ from
$\Omega\times\mathcal{P}(M(R;h_{R^{\prime}}))$ to $[0,1]$ is a probability
kernel. In other words, for all $\omega\in\Omega$,
$A\mapsto\mu_{M(R;h_{R^{\prime}})}(A,\omega)$ is a probability measure, and
for all $A\subset M(R;h_{R^{\prime}})$,
$\omega\mapsto\mu_{M(R;h_{R^{\prime}})}(A,\omega)$ is measurable. Thus, the
formula

$(\mu_{M(R;h_{R^{\prime}})}\circ\mathbb{P})(A):=\mathbb{E}[\mu_{M(R;h_{R^{\prime}})}(A,\omega)],\quad
A\subset M(R;h_{R^{\prime}})$

defines a probability measure $\mu_{M(R;h_{R^{\prime}})}\circ\mathbb{P}$ on
$M(R;h_{R^{\prime}})$. Moreover, for any function
$f:M(R;R^{\prime})\to\mathbb{R}$, if $h_{R}$ is a random variable with law
$\mu_{M(R;h_{R^{\prime}})}\circ\mathbb{P}$ then

(10)
$E[f(X)]=\mathbb{E}\bigl{[}E_{\mu_{M(R;h_{R^{\prime}})}(\cdot,\omega)}(f)\bigr{]}.$

###### Proof (of claims in Definition 7).

By definition $\mu_{M(R;h_{R^{\prime}})}(\cdot,\omega)$ is a probability
measure for fixed $\omega$. The second property follows from how
$\mu_{M(R;h_{R^{\prime}})}(h_{R},\omega)$ is defined: the numerator is a sum
of finitely many random potential values $\omega_{e}$ inside of the
(continuous, hence measurable) exponential function, and the denominator is a
finite sum over copies of the numerator, only using different height functions
to select the random potential values $\omega_{e}$. The equation (10) is a
standard identity for regular conditional distributions and its proof is a
straightforward exercise; see e.g. [Dur10, Exercise 5.1.14]. Note that since
$M(R;R^{\prime})$ is finite, each function $f:M(R;R^{\prime})\to\mathbb{R}$ is
measurable. ∎

##  3\. The concentration inequality

Having stated the definitions above, we are prepared to state the main result
of this note, then move on to proofs.

######  Theorem 8.

Let $R_{n}\subset\mathbb{Z}^{m}$ be a sequence of finite, connected subgraphs
such that $\operatorname{diam}(R_{n}):=\max_{x,y\in R_{n}}|x-y|_{1}\leq An$
for some $A>0$. Let $\varepsilon>0$ and $h_{\partial R_{n}}\in M({\partial
R_{n}})$ be given, and let $\mu_{n}=\mu_{M(R;h_{\partial
R_{n}})}(\cdot,\omega)$ denote the (perturbed) distribution on
$M(R;h_{\partial R_{n}})$. Then for any $c>0$ and any $n\in\mathbb{N}$,

(11) $\mu_{n}\circ\mathbb{P}\biggl{(}\max_{v\in
R_{n}}\,\Big{\lvert}h_{R_{n}}(v)-E_{\mu_{n}}(h_{R_{n}}(v))\Big{\rvert}\geq
c\sqrt{n}\biggr{)}\leq 2\,|R_{n}|\,e^{-nc^{2}/A}.$

######  Remark 9.

Theorem 8 gives quantitative bounds for the probability that a height function
$h_{R}$ differs from expected value on the scale of $\sqrt{n}$. The
probability bounds are exponential in a constant times $n$, which comes about
because of the one-dimensional nature of the Azuma–Hoeffding inequality. In
comparison, results such as the large deviations principle of [She05, LT20]
achieve a volume-order term in the exponential. The cost of those results is
that control over the size of fluctuations is not quantitative. For example,
ignoring the random potential $\omega$ and using the uniform measure on
$M(R;h_{\partial R})$ instead, the large deviations principle implies that
$\mu_{n}(\max_{v}|h_{R_{n}}(v)-E_{\mu_{n}}(h_{R_{n}}(v))|\geq\varepsilon)\leq\exp(-n^{m}I(\varepsilon))$.
Here $I(\varepsilon)>0$ is (related to) the rate function of the LDP, which
does not admit an obvious closed form expression in terms of $\varepsilon$. It
would be interesting if we could obtain a quantitative concentration result
with volume-order term in the exponential of the probability bound.

We will build up to the proof of the concentration inequality via a few
intermediate results. Lemma 10 below establishes the monotonicity property,
which is the main ingredient of the proof. We derive from it Corollary 11,
which is used in the proof of an auxiliary concentration inequality in Lemma
13. The difference between Lemma 13 and the main theorem is that the former
addresses only a single point $v\in R$, whereas the latter concerns the
maximum deviation from the mean over the entire domain. The statements and
proofs of these results are based on the method presented in [CEP96]; we cite
the analogous steps where appropriate below. Differences arise starting with
Corollary 11 below, where the shift-invariant and ergodic properties of the
law of $\omega$ must be used to account for the fact that height functions
with different base heights “see” different random potential values
$\omega_{e}$. However, the essential steps of the proof still goes through,
since even under the influence of $\omega$ the relevant measures are Gibbs
measures, based upon a finite-range potential (indeed, a nearest-neighbor
potential, which enforces the Lipschitz property). It seems like the proof
should extend to other finite-range models and perhaps beyond, but for brevity
we will not explore that idea further here.

######  Lemma 10 (cf. [CEP96, Lemma 18]).

Let $R^{\prime}\subset R$ and let
$h_{R^{\prime}},\widetilde{h}_{R^{\prime}}\in M(R^{\prime})$ be such that
$h_{R^{\prime}}\leq\widetilde{h}_{R^{\prime}}$ and that $M(R;h_{R^{\prime}})$
and $M(R;\widetilde{h}_{R^{\prime}})$ are not empty. Then for any realization
$\omega$, $\mu_{M(R;h_{R^{\prime}})}(\cdot,\omega)$ is stochastically
dominated by $\mu_{M(R;\widetilde{h}_{R^{\prime}})}(\cdot,\omega)$. More
precisely, there exists a measurable function $\pi:M(R;h_{R^{\prime}})\times
M(R;\widetilde{h}_{R^{\prime}})\times\Omega\to[0,1]$ such that:

  * •

for almost every $\omega$, $\pi(\cdot,\cdot,\omega)$ is a coupling, i.e.

$\sum_{\widetilde{h}_{R}}\pi(h_{R},\widetilde{h}_{R},\omega)=\mu_{M(R;h_{R^{\prime}})}(h_{R},\omega)\qquad\text{and}\qquad\sum_{h_{R}}\pi(h_{R},\widetilde{h}_{R},\omega)=\mu_{M(R;\widetilde{h}_{R^{\prime}})}(\widetilde{h}_{R},\omega),$

and

  * •

$\pi\bigl{(}\\{h_{R}\leq\widetilde{h}_{R}\\},\omega\bigr{)}=1.$

$R=\\{$$\\}$$R^{\prime}=\\{$$\\}$$\partial_{R}(R^{\prime})=\\{$$\\}$$\\{v^{\prime\prime}\\}=R^{\prime\prime}\setminus
R^{\prime}=\\{$$\\}$ Figure 2. An example of the sets relevant to the proof of
Lemma 10. On the left is a $5\times 5$ subset of $\mathbb{Z}^{2}$, with points
decorated according to the key on the right.

###### Proof.

Consider the “relative boundary” $\partial_{R}(R^{\prime}):=\\{v^{\prime}\in
R^{\prime}\colon\exists v\in R\setminus R^{\prime},v\sim v^{\prime}\\}$, i.e.
the points in $R^{\prime}$ that are directly adjacent to $R$. As we shall see
below, these are the only essentially relevant points of $R^{\prime}$. Indeed,
we split the proof into two cases, depending on the restrictions
$h_{R^{\prime}}|_{\partial_{R}(R^{\prime})}$ and
$\widetilde{h}_{R^{\prime}}|_{\partial_{R}(R^{\prime})}$ on
$\partial_{R}(R^{\prime})$. The first case is the easier of the two. In the
first case, the two height functions agree on $\partial_{R}(R^{\prime})$. In
the second case, there is a strict inequality
$h_{R^{\prime}}(v)<\widetilde{h}_{R^{\prime}}(v)$ for at least one point
$v\in\partial_{R}(R^{\prime})$.

Case 1: Assume first that $h_{R^{\prime}}(v)=h_{R^{\prime}}(v)$ for all
$v\in\partial_{R}(R^{\prime})$. Since $\partial_{R}(R^{\prime})$ may be a
proper subset of $R^{\prime}$, this does not imply that
$h_{R^{\prime}}=\widetilde{h}_{R^{\prime}}$. (Although in the case where
$\partial_{R}(R^{\prime})$, then this case does indeed reduce to the trivial
assertion that $\mu_{M(R;h_{R^{\prime}})}$ is stochastically dominated by
itself.) However, it does hold that $h_{R^{\prime}}$ and
$\widetilde{h}_{R^{\prime}}$ have the same extensions to $R\setminus
R^{\prime}$; to be very precise,

(12) $\bigl{\\{}h_{R}|_{R\setminus R^{\prime}}\colon h_{R}\in
M(R;h_{R^{\prime}})\bigr{\\}}=\bigl{\\{}\widetilde{h}_{R}|_{R\setminus
R^{\prime}}\colon\widetilde{h}_{R}\in
M(R;\widetilde{h}_{R^{\prime}})\bigr{\\}}.$

For clarity, let us repeat the above paragraph in the context of Figure 2.
Case 1 of the proof concerns data $h_{R^{\prime}}$ and
$\widetilde{h}_{R^{\prime}}$ that agree on the solid black circle region (i.e.
$\partial_{R}(R^{\prime})$), though they may differ on the solid black square
points (i.e. $R^{\prime}\setminus\partial_{R}(R^{\prime})$). By definition of
$\partial_{R}(R^{\prime})$, the solid black circle points surround the white
circle region (i.e. $R\setminus R^{\prime}$), at least relative to the domain
$R$. (Often we will assume that $\partial R\subset R^{\prime}$, but that
assumption isn’t necessary here, and it does not hold in the figure.) Since
$h_{R^{\prime}}$ and $\widetilde{h}_{R^{\prime}}$ agree on
$\partial_{R}(R^{\prime})$, they have the same extensions to the white circle
region, in the sense of (12).

An easy calculation shows that for $h_{R}\in M(R;h_{R^{\prime}})$,

(13)
$\mu_{M(R;h_{R^{\prime}})}(h_{R},\omega)=\frac{\exp\bigl{(}H^{+}_{R\setminus
R^{\prime}}(h_{R},\omega)\bigr{)}}{\sum_{f_{R}\in
M(R;h_{R^{\prime}})}\exp\bigl{(}H^{+}_{R\setminus
R^{\prime}}(f_{R},\omega)\bigr{)}},$

where we recall that $H^{+}_{R\setminus R^{\prime}}$ denotes the Hamiltonian
on domain $R\setminus R^{\prime}$, including the edges that cross between
$R\setminus R^{\prime}$ and $\partial_{R}(R^{\prime})$. Therefore in
particular that the right-hand expression (13) depends only on the values of
the extension $h_{R}$ restricted $(R\setminus
R^{\prime})\cup\partial_{R}(R^{\prime})$. The same is true of extensions
$\widetilde{h}_{R}\in M(R;\widetilde{h}_{R^{\prime}})$. As such, the obvious
bijection between the two sets in (12) is measure-preserving in both
directions. The existence of a coupling $\pi$ satisfying the claims of the
lemma follows immediately.

Case 2: Assume instead that $h_{R^{\prime}}(v)<\widetilde{h}_{R^{\prime}}(v)$
for some $v\in R^{\prime}$ adjacent to a vertex $v^{\prime\prime}\in
R\setminus R^{\prime}$. In Figure 2, $v^{\prime\prime}$ is the white circle
marked with an “X,” and $v$ might be either of the adjacent solid black
circles. Let $R^{\prime\prime}=R^{\prime}\cup\\{v^{\prime\prime}\\}$. We
proceed by induction on the cardinality of $R\setminus R^{\prime}$. The
induction hypothesis states that given any height functions
$h_{R^{\prime\prime}},\widetilde{h}_{R^{\prime\prime}}\in M(R^{\prime\prime})$
such that $h_{R^{\prime\prime}}\leq\widetilde{h}_{R^{\prime\prime}}$ and such
that both $M(R;h_{R^{\prime\prime}})$ and
$M(R;\widetilde{h}_{R^{\prime\prime}})$ are nonempty, the measure
$\mu_{M(R;h_{R^{\prime\prime}})}$ is stochastically dominated by
$\mu_{M(R;\widetilde{h}_{R^{\prime\prime}})}$. Note that the base case of the
induction occurs when $R\setminus R^{\prime}=\\{v^{\prime\prime}\\}$ has
cardinality $1$, and so $R^{\prime\prime}=R$; the lemma is trivial in this
case.

So let us extend induction hypothesis from $R^{\prime\prime}$ to $R^{\prime}$.
From the hypotheses of the lemma, each of $h_{R^{\prime}}$ and
$\widetilde{h}_{R^{\prime}}$ admits at least one extension to $R$. Therefore
each admits at least one extension to $R^{\prime\prime}$ that in turn admits
an extension to $R$. On the other hand since $R^{\prime\prime}\setminus
R^{\prime}=\\{v^{\prime\prime}\\}$ is a set of cardinality $1$, each of
$h_{R^{\prime}}$ and $\widetilde{h}_{R^{\prime}}$ admits at most two
extensions to $R^{\prime}$. Formally, let $h_{R^{\prime\prime}}^{+}$ and
$h_{R^{\prime\prime}}^{-}$ denote the two possible extensions of
$h_{R^{\prime}}$ to $R^{\prime\prime}$, where
$h_{R^{\prime\prime}}^{\pm}(v^{\prime\prime})=h_{R^{\prime}}(v)\pm 1$. Below
we will address the possibility that one or the other of these putative
extensions does not exist. Likewise, let
$\widetilde{h}_{R^{\prime\prime}}^{\pm}\in
M(R^{\prime\prime};\widetilde{h}_{R^{\prime}})$ denote the two extensions of
$\widetilde{h}_{R^{\prime}}$ to $R^{\prime\prime}$, subject to the possibility
that one or the other of the two extensions may not exist.

By conditioning on the height value at $v^{\prime\prime}$, we see that

(14) $\displaystyle\mu_{M(R;h_{R^{\prime}})}$
$\displaystyle=p^{+}\mu_{M(R;h_{R^{\prime\prime}}^{+})}+p^{-}\mu_{M(R;h_{R^{\prime\prime}}^{-})}\quad\text{and}$
$\displaystyle\mu_{M(R;\widetilde{h}_{R^{\prime}})}$
$\displaystyle=\widetilde{p}^{+}\mu_{M(R;\widetilde{h}_{R^{\prime\prime}}^{+})}+\widetilde{p}^{-}\mu_{M(R;\widetilde{h}_{R^{\prime\prime}}^{-})},$

where

(15) $\displaystyle p^{\pm}$
$\displaystyle:=\mu_{M(R;h_{R^{\prime}})}(\\{h_{R}(v^{\prime\prime})=h_{R^{\prime}}(v)\pm
1\\})\in[0,1]\quad\text{and}$ $\displaystyle\widetilde{p}^{\pm}$
$\displaystyle:=\mu_{M(R;\widetilde{h}_{R^{\prime}})}(\\{\widetilde{h}_{R}(v^{\prime\prime})=\widetilde{h}_{R^{\prime}}(v)\pm
1\\})\in[0,1].$

This addresses the issue noted above, about the possibility that one (but not
both) of $h_{R^{\prime\prime}}^{\pm}$ may not exist; if so, the corresponding
$p^{\pm}$ term is $0$, and the other $p^{\mp}$ term is $1$. By parity
considerations, it must hold (assuming that the various extensions exist),
that

$h_{R^{\prime\prime}}^{-}(v^{\prime\prime})<h_{R^{\prime\prime}}^{+}(v^{\prime\prime})=h_{R^{\prime}}(v)+1\leq\widetilde{h}_{R^{\prime}}(v)-1=\widetilde{h}_{R^{\prime\prime}}^{-}(v^{\prime\prime})<\widetilde{h}_{R^{\prime\prime}}^{+}(v^{\prime\prime}).$

By (up to) four applications of the induction hypothesis, we conclude that
each of the measures $\mu_{M(R;h_{R^{\prime\prime}}^{\pm})}$ is stochastically
dominated by each of the measures
$\mu_{M(R;\widetilde{h}_{R^{\prime\prime}}^{\pm})}$. Since all the measures
are probability measures and since all four of $p^{\pm},\widetilde{p}^{\pm}$
are nonnegative, the identities (14) implies that $\mu_{M(R;h_{R^{\prime}})}$
is stochastically dominated by $\mu_{M(R;\widetilde{h}_{R^{\prime}})}$. ∎

We will make use of stochastic dominance via expectations, as captured in the
following corollary.

######  Corollary 11 (cf. [CEP96, Corollary 19]).

Let $R^{\prime}\subset R$, let $v\in R\setminus R^{\prime}$, and let
$h_{R^{\prime}},\widetilde{h}_{R^{\prime}}\in M(R^{\prime})$ with
$h_{R^{\prime}}\leq\widetilde{h}_{R^{\prime}}+2$. Let $h_{R}(v)$ and
$\widetilde{h}_{R}(v)$ denote the $\mathbb{Z}$-valued random variables
obtained by sampling $h_{R}$ from $\mu_{M(R;h_{R^{\prime}})}\circ\mathbb{P}$
and $\widetilde{h}_{R}$ from
$\mu_{M(R;\widetilde{h}_{R^{\prime}})}\circ\mathbb{P}$ and evaluating the
respective height functions at $v$. Then

$E_{\mu_{M(R;h_{R^{\prime}})}\circ\mathbb{P}}[h_{R}(v)]\leq
E_{\mu_{M(R;\widetilde{h}_{R^{\prime}})}\circ\mathbb{P}}[\widetilde{h}_{R}(v)]+2.$

######  Remark 12.

Notice that unlike the stochastic monotonicity result of Lemma 10, which is
almost sure in $\omega$, the corollary above requires an expectation over the
law $\mathbb{P}$ of $\omega$. This is a substantial difference from [CEP96]
caused by the random potential. Indeed, the requirement arises from the fact
that $h_{R^{\prime}}$ and $\widetilde{h}_{R^{\prime}}+2$ “see” a different
part of the random potential $\omega$. Since $\mu$ is a shift-invariant Gibbs
measure, we can average out this height shift by annealing over the random
potential.

###### Proof.

By Lemma 10, for each fixed $\omega$ we have
$\mu_{M(R;h_{R^{\prime}})}(\cdot,\omega)\overset{\textnormal{law}}{\leq}\mu_{M(R;\widetilde{h}_{R^{\prime}}+2)}(\cdot,\omega)$,
so

$E_{\mu_{M(R;h_{R^{\prime}})}(\cdot,\omega)}[h_{R}(v)]\leq
E_{\mu_{M(R;\widetilde{h}_{R^{\prime}}+2)}(\cdot,\omega)}[\widetilde{h}_{R}(v)],\quad\text{for
a.e.~{}$\omega$}.$

We will transfer the height shift from the “$\widetilde{h}_{R^{\prime}}+2$”
into the random potential $\omega$ and into the height function inside the
expectation. Indeed, from the definition of the Hamiltonian, we have for
$R\subset\mathbb{Z}^{d}$ and $f_{R}\in M(R)$ that

(16) $H^{\circ}_{R}(f_{R}+2,\omega)=H^{\circ}_{R}(f_{R},\tau_{2}\omega),$

where $\tau_{2}:\Omega\to\Omega$ is defined by
$(\tau_{2}(\omega))_{x,x+1}=\omega_{x+2,x+3}$ for all $x\in\mathbb{Z}$. A
straightforward calculation (see Appendix A) establishes that, for any
$h_{R}\in M(R)$,

(17)
$\mu_{M(R;\widetilde{h}_{R^{\prime}}+2)}(h_{R},\omega)=\mu_{M(R;\widetilde{h}_{R^{\prime}})}(h_{R}-2,\tau_{2}\omega).$

By change of variables,

$E_{\mu_{M(R;h_{R^{\prime}})}(\cdot,\omega)}[h_{R}(v)]\leq
E_{\mu_{M(R;\widetilde{h}_{R^{\prime}})}(\cdot,\tau_{2}\omega)}[\widetilde{h}_{R}(v)+2],\quad\text{for
a.e.~{}$\omega$}.$

Take expectations with respect to $\mathbb{P}$. Under the expectation the
shift $\tau_{2}$ vanishes, by ergodicity. The result follows by construction
of the measures $\mu_{M(R;h_{R^{\prime}})}\circ\mathbb{P}$ and
$\mu_{M(R;\widetilde{h}_{R^{\prime}})}\circ\mathbb{P}$; cf. equation (10). ∎

Now we are prepared to prove a limited version of the concentration
inequality, where we are concerned with only a single point $v\in R$. The key
to the proof is the monotonicity of Corollary 11. We translate this into an
inductive bound on martingale differences: each time we take a “step” starting
at the boundary $\partial R$ and “walking” towards $v$, the two possible
extensions at that step differ by at most $2$. Then we use the Azuma–Hoeffding
inequality to establish the probability bound. From this point on the proof is
standard, following closely to the methods used in [CEP96] and other works.

######  Lemma 13 (Auxiliary concentration inequality cf. [CEP96, Theorem 21]).

Let $h_{\partial R}\in M({\partial R})$ and let $v\in R$ be such that there is
a path $x_{0}\in{\partial R},x_{1},\dotsc,x_{l-1}=v$ of length $l$ with
$x_{i}\sim x_{i-1}$ for $i=1,\dotsc,l-1$. Then for any $c>0$,

$\mu_{M(R;h_{\partial R})}\circ\mathbb{P}\Bigl{(}\Bigl{\\{}h_{R}\in
M(R;h_{\partial R})\colon\big{\lvert}h_{R}(v)-E_{\mu_{M(R;h_{\partial
R})}}[h_{R}(v)]\big{\rvert}>lc\Bigr{\\}}\Bigr{)}<2e^{-lc^{2}/2}.$

###### Proof.

For $k=1,\dotsc,l$, define $\sigma$-algebras
$\mathcal{F}_{k}:=\sigma(h_{R}\mapsto h_{R}(x_{i}),0\leq
i<k)\subset\mathcal{P}(M(R;h_{\partial R}))$ and define a martingale
$M_{k}:=E[h_{R}(v)|\mathcal{F}_{k}]$, where $E[\,\cdot\,]$ denotes the
expectation with respect to the measure
$\mu_{M(R;h_{R^{\prime}})}\circ\mathbb{P}$. Note that $M_{1}=E[h_{R}(v)]$ and
that $M_{l}=h_{R}(v)$.

We claim that for each $k=1,\dotsc,l-1$, the martingale difference
$|M_{k+1}-M_{k}|$ is less than or equal to $2$ almost surely. To this end, fix
$k$ and condition on $h(x_{i})=z_{i}\in\mathbb{Z}$ for $i=0,\dotsc,k-1$. To
avoid events of probability zero, assume that $z_{0},\dotsc,z_{k-1}$ are such
that there exists at least one extension in $M(h_{R};h_{\partial R})$ with
$h_{R}(x_{i})=z_{i}$ for each $i$; by hypothesis $M(h_{R};h_{\partial R})$ is
nonempty, so at least one such assignment of heights $z_{i}$ exists.

Having fixed these height values, there are at most two assignments of the
height value $z_{k}:=h_{R}(x_{k})$ which admit further extensions in
$M(R;h_{\partial R})$: namely, $z_{k}=z_{k-1}\pm 1$. Therefore the martingale
$M_{k+1}=E[h_{R}(v)|\mathcal{F}_{k+1}]$ takes at most two distinct values
conditioned on $\\{h_{R}(x_{i})=z_{i},\,i=0,\dotsc,k-1\\}$. Because the (at
most) two possible values of $h_{R}(x_{k})$ differ by at most $2$, and because
the height values at $x_{0},\dotsc,x_{k-1}$ have been fixed, Corollary 11
applied with $R^{\prime}=\\{x_{0},\dotsc,x_{k}\\}$ implies that the (at most)
two distinct values of $M_{k+1}$ differ by at most $2$. Since
$M_{k}=E[M_{k+1}|\mathcal{F}_{k}]$ is the weighted average of these (at most)
two values of $M_{k+1}$, it follows that $\lvert M_{k+1}-M_{k}\rvert\leq 2$.
The conclusion follows immediately from the Azuma–Hoeffding inequality. ∎

Now we are prepared to prove the main result, i.e. the concentration
inequality.

###### Proof of Theorem 8.

By the union bound and Lemma 13,

(18) $\mu_{n}\circ\mathbb{P}\Bigl{(}\max_{v\in
R_{n}}\>\big{\lvert}h_{R_{n}}(v)-E_{\mu_{n}}(h_{R_{n}}(v))\big{\rvert}\geq
c\sqrt{n}\Bigr{)}\leq\sum_{v\in
R_{n}}\mu_{n}\circ\mathbb{P}\Bigl{(}\,\big{\lvert}h_{R_{n}}(v)-E_{\mu_{n}}(h_{R_{n}}(v))\big{\rvert}\geq
c\sqrt{n}\Bigr{)}.$

For each $v\in R_{n}$, apply Lemma 13 with the path length parameter $l_{v}$
chosen as small as possible and with parameter $c_{v}$ chosen such that
$l_{v}c_{v}=c\sqrt{n}$. Recall that by hypothesis the diameter of $R_{n}$ is
at most $An$, so $l\leq An/2$. It follows that

$l_{v}c_{v}^{2}=\frac{(l_{v}c_{v})^{2}}{l_{v}}=\frac{c^{2}n}{l_{v}}\geq\frac{2c^{2}n}{A}.$

Using also the hypotheses that $|R_{n}|\leq Bn^{m}$, we have

(19) $\displaystyle\hskip-30.00005pt\mu_{n}\circ\mathbb{P}\biggl{(}\max_{v\in
R_{n}}\>\big{\lvert}h_{R_{n}}(v)-E_{\mu}(h_{R_{n}}(v))\big{\rvert}\geq
c\sqrt{n}\biggr{)}$ $\displaystyle\leq\sum_{v\in
R_{n}}\mu_{n}\circ\mathbb{P}\biggl{(}\big{\lvert}h_{R_{n}}(v)-E_{\mu_{n}}\bigl{(}h_{R_{n}}(v)\bigr{)}\big{\rvert}\geq
l_{v}c_{v}\biggr{)}$ $\displaystyle\leq\sum_{v\in
R_{n}}2e^{-l_{v}c_{v}^{2}/2}$ $\displaystyle\leq 2|R_{n}|e^{-c^{2}n/A}.$

∎

##  Appendix A Proof of Eq. (17) from Corollary 11

The following equation was used in the proof of Corollary 11 above. The proof
that this equation holds has been moved here in an appendix, since it requires
several lines, and it is not enlightening or crucial enough to justify taking
space in the body of the proof. The equation in question is (cf. (17) above):

$\mu_{M(R;\widetilde{h}_{R^{\prime}})+2}(h_{R},\omega)=\mu_{M(R;\widetilde{h}_{R^{\prime}})}(h_{R}-2,\tau_{2}\omega).$

Indeed:

$\displaystyle\mu_{M(R;\widetilde{h}_{R^{\prime}}+2)}(h_{R},\omega)$
$\displaystyle=\frac{\exp\bigl{(}H^{\circ}_{R}(h_{R},\omega)\bigr{)}}{\sum_{f_{R}\in
M(R;h_{R^{\prime}}+2)}\exp\bigl{(}H^{\circ}_{R}(f_{R},\omega)\bigr{)}}$
$\displaystyle=\frac{\exp\bigl{(}H^{\circ}_{R}(h_{R},\omega)\bigr{)}}{\sum_{f_{R}\in
M(R;h_{R^{\prime}})}\exp\bigl{(}H^{\circ}_{R}(f_{R}+2,\omega)\bigr{)}}$
$\displaystyle=\frac{\exp\bigl{(}H^{\circ}_{R}(h_{R},\omega)\bigr{)}}{\sum_{f_{R}\in
M(R;h_{R^{\prime}})}\exp\bigl{(}H^{\circ}_{R}(f_{R},\tau_{2}\omega)\bigr{)}}$
$\displaystyle=\frac{\exp\bigl{(}H^{\circ}_{R}(h_{R}-2,\tau_{2}\omega)\bigr{)}}{\sum_{f_{R}\in
M(R;h_{R^{\prime}})}\exp\bigl{(}H^{\circ}_{R}(f_{R},\tau_{2}\omega)\bigr{)}}$
$\displaystyle=\mu_{M(R;\widetilde{h}_{R^{\prime}})}(h_{R}-2,\tau_{2}\omega).$

∎

## References

  * [BCG16] Alexei Borodin, Ivan Corwin, and Vadim Gorin.  Stochastic six-vertex model.  Duke Math. J., 165(3):563–624, 2016.
  * [BHM00] Itai Benjamini, Olle Häggström, and Elchanan Mossel.  On random graph homomorphisms into Z.  J. Comb. Theory Ser. B, 78(1):86–114, 2000.
  * [BP18] Marek Biskup and Eviatar B. Procaccia.  Eigenvalue versus perimeter in a shape theorem for self-interacting random walks.  Ann. Appl. Probab., 28(1):340–377, 2018.
  * [BY19] Nathanaël Berestycki and Ariel Yadin.  Condensation of a self-attracting random walk.  Ann. Inst. H. Poincaré Probab. Statist., 55(2):835–861, 2019.
  * [CEP96] Henry Cohn, Noam Elkies, and James Propp.  Local statistics for random domino tilings of the Aztec diamond.  Duke Math. J., 85(1):117–166, 1996.
  * [Cer06] Raphaël Cerf.  The Wulff Crystal in Ising and Percolation Models, volume 1878 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2006.
  * [CKP01] Henry Cohn, Richard Kenyon, and James Propp.  A variational principle for domino tilings.  J. Amer. Math. Soc., 14(2):297–346 (electronic), 2001.
  * [CL06] Fan Chung and Linyuan Lu.  Concentration inequalities and martingale inequalities — a survey.  Internet Math., 3(1):79–127, 2006.
  * [CPST20] Nishant Chandgotia, Ron Peled, Scott Sheffield, and Martin Tassy.  Delocalization of uniform graph homomorphisms from $\mathbb{Z}^{2}$ to $\mathbb{Z}$.  arXiv:1810.10124, 2020.  Preprint.
  * [CS16] Filippo Colomo and Andrea Sportiello.  Arctic curves of the six-vertex model on generic domains: The tangent method.  J. Stat. Phys., 164(6):1488–1523, 2016.
  * [Des98] Nicolas Destainville.  Entropy and boundary conditions in random rhombus tilings.  J. Phys. A, 31(29):6123–6139, 1998.
  * [DGI00] Jean-Dominique Deuschel, Giambattista Giacomin, and Dmitry Ioffe.  Large deviations and concentration properties for $\nabla\phi$ interface models.  Probab. Theory Relat. Fields, 117(1):49–111, 2000.
  * [DKS92] Roland Lvovich Dobrushin, Roman Koteckỳ, and Senya Shlosman.  Wulff Construction, volume 104 of Translations of Mathematical Monographs.  American Mathematical Society, Providence, RI, 1992.  A global shape from local interaction, Translated from the Russian by the authors.
  * [Dur10] Rick Durrett.  Probability: Theory and Examples.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, fourth edition, 2010.
  * [FO04] Tadahisa Funaki and Hirofumi Osada.  Stochastic Analysis on Large Scale Interacting Systems.  Advanced studies in pure mathematics. Mathematical Society of Japan, 2004\.
  * [FS06] Patrik L. Ferrari and Herbert Spohn.  Scaling limit for the space-time covariance of the stationary totally asymmetric simple exclusion process.  Commun. Math. Phys., 265(1):1–44, 2006.
  * [Gal03] David Galvin.  On homomorphisms from the Hamming cube to Z.  Isr. J. Math., 138:189–213, 2003.
  * [Geo88] Hans-Otto Georgii.  Gibbs Measures and Phase Transitions, volume 9 of de Gruyter Studies in Mathematics.  Walter de Gruyter & Co., Berlin, 1988.
  * [Kah01] Jeff Kahn.  Range of cube-indexed random walk.  Isr. J. Math., 124:189–201, 2001.
  * [Kas63] Pieter W Kasteleyn.  Dimer statistics and phase transitions.  J. Math. Phys., 4:287–293, 1963.
  * [KMT20] Andrew Krieger, Georg Menz, and Martin Tassy.  Deducing a variational principle with minimal a priori assumptions.  Electron. J. Comb., 27(4), 2020.
  * [KMT21] Andrew Krieger, Georg Menz, and Martin Tassy.  Homogenization of the variational principle for discrete random maps.  arXiv:1710.11330, 2021.  Preprint.
  * [LP08] Lionel Levine and Yuval Peres.  Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile.  Potential Anal., 30(1):1, 2008.
  * [LRS01] Michael Luby, Dana Randall, and Alistair Sinclair.  Markov chain algorithms for planar lattice structures.  SIAM J. Comput., 31(1):167–192, 2001.
  * [LS77] Benjamin F Logan and Larry A Shepp.  A variational problem for random Young tableaux.  Adv. Math., 26(2):206–222, 1977.
  * [LT20] Piet Lammers and Martin Tassy.  Macroscopic behavior of Lipschitz random surfaces.  arXiv:2004.15025, 2020.  Preprint.
  * [MT20] Georg Menz and Martin Tassy.  A variational principle for a non-integrable model.  Probab. Theory Relat. Fields, 177(3):747–822, 2020.
  * [Pel17] Ron Peled.  High-dimensional Lipschitz functions are typically flat.  The Annals of Probability, 45(3):1351–1447, 2017.
  * [PR07] Boris Pittel and Dan Romik.  Limit shapes for random square Young tableaux.  Adv. Appl. Math., 38(2):164–209, 2007.
  * [PSY13] Ron Peled, Wojciech Samotij, and Amir Yehudayoff.  Lipschitz functions on expanders are typically flat.  Combinatorics, Probability and Computing, 22:566–591, 2013.
  * [RS18] Nicolai Reshetikhin and Ananth Sridhar.  Limit shapes of the stochastic six vertex model.  Commun. Math. Phys., 363(3):741–765, 2018.
  * [She05] Scott Sheffield.  Random Surfaces, volume 304 of Astérisque.  Société mathématique de France, 2005.
  * [Sri16] Ananth Sridhar.  Limit Shapes in the Six Vertex Model.  PhD thesis, University of California, Berkeley, 2016.
  * [VK77] Anatolii Moiseevich Veršik and Sergei V. Kerov.  Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux.  Dokl. Akad. Nauk SSSR, 233(6):1024–1027, 1977.
  * [Wil04] David Bruce Wilson.  Mixing times of lozenge tiling and card shuffling Markov chains.  Ann. Appl. Probab., 14(1):274–325, 2004.