Reconstructing Random Pictures Bhargav Narayanan and Corrine Yap Abstract. Given a random binary picture Pnof size n i.e. an nngrid filled

2025-04-29 0 0 439.64KB 23 页 10玖币
侵权投诉
Reconstructing Random Pictures
Bhargav Narayanan and Corrine Yap
Abstract.
Given a random binary picture
Pn
of size
n
, i.e., an
n×n
grid filled
with zeros and ones uniformly at random, when is it possible to reconstruct
Pn
from
its
k
-deck, i.e., the multiset of all its
k×k
subgrids? We demonstrate “two-point
concentration” for the reconstruction threshold by showing that there is an integer
kc
(
n
)
∼
(2
log n
)
1/2
such that if
k > kc
, then
Pn
is reconstructible from its
k
-deck
with high probability, and if
k < kc
, then with high probability, it is impossible
to reconstruct
Pn
from its
k
-deck. The proof of this result uses a combination of
interface-exploration arguments and entropic arguments.
1. Introduction
Reconstruction problems, at a very high level, ask the following general question:
is it possible to uniquely reconstruct a discrete structure from the “deck” of all its
substructures of some fixed size? The study of such problems dates back to the graph
reconstruction conjectures of Kelly and Ulam [
9
,
11
,
23
], and analogous questions for
various other families of discrete structures have since been studied; see [
1
,
17
,
18
,
19
] for
examples concerning other objects such as hypergraphs, abelian groups, and subsets of
Euclidean space. The line of inquiry that we pursue here concerns reconstructing typical,
as opposed to arbitrary, structures in a family of discrete structures. Such questions,
best phrased in the language of probabilistic combinatorics, often have substantially
different answers compared to their extremal counterparts; see [4,22], for instance.
Our aim in this paper is to investigate a two-dimensional reconstruction problem,
namely that of reconstructing random pictures. Before we describe the precise question
we study, let us motivate the problem at hand. Perhaps the most basic one-dimensional
reconstruction problem concerns reconstructing a random binary string from the multiset
of its substrings of some fixed size, a problem intimately connected to that of shotgun-
sequencing DNA sequences; on account of its wide applicability, this question has
been investigated in great detail, as in [
2
,
15
] for instance. A natural analogue of the
aforementioned one-dimensional problem concerns reconstructing a random binary grid
(or picture, for short) from the multiset of its subgrids of some fixed size; this is the
question that will be our focus here. While shotgun-reconstruction of random strings is
2020 Mathematics Subject Classification. Primary 60C05; Secondary 60K35, 68R15.
Key words and phrases. reconstruction, random reconstruction, shotgun assembly.
1
arXiv:2210.09410v3 [math.CO] 28 Jan 2025
Figure 1. A picture of size 3 and its 2-deck.
a well-studied problem, there has been renewed interest — originating from the work of
Mossel and Ross [
13
] — in generalizations of this problem like the one considered here;
see [8,10,14,21] for some recent examples.
Writing [
n
] for the set
{
1
,
2
, . . . , n}
, a picture of size
n
is an element of
{
0
,
1
}[n]2
viewed as a two-coloring of an
n×n
grid using the colors 0 and 1. The
k
-deck of a
picture
P
of size
n
, denoted
Dk
(
P
), is the multiset of its
k×k
colored subgrids of which
there are precisely (
n−k
+ 1)
2
; see Figure 1for an illustration. We say that a picture
P
is reconstructible from its
k
-deck if
Dk
(
P′
) =
Dk
(
P
) implies that
P′
=
P
. Writing
Pn
for a random picture of size
n
chosen uniformly from the set of all pictures of size
n
, our primary concern is then the following question raised by Mossel and Ross [
13
]:
when is
Pn
reconstructible from its
k
-deck with high probability? More specifically, is
there a threshold value for
k
such that in the supercritical regime,
Pn
is reconstructible
with high probability and in the subcritical regime
Pn
is not reconstructible with high
probability? It was previously determined by Mossel and Ross [
13
] (under the dual
perspective of coloring lattice vertices rather than faces) that the threshold lies between
p(1 −ϵ) log n
and
p(1 + ϵ)4 log n
, and Ding and Liu [
7
] subsequently narrowed down
the location of the threshold to (
p(1 −ϵ)2 log n, p(1 + ϵ)2 log n
). We note that these
results also hold in higher dimensions. We shall give a nearly complete answer to this
question. Let
kc
(
n
) be the nearest integer value to
p2 log2n
. Writing
R
(
n, k
) for the
event that the random picture
Pn
is reconstructible from its
k
-deck, our main result is
as follows.
Theorem 1.1. As n→ ∞,we have
P(R(n, k)) →(0if k < kc(n),and
1if k > kc(n)
In other words, Theorem 1.1 shows that the “reconstruction threshold” of a random
picture is concentrated on at most two consecutive integers. The two results contained in
the statement of Theorem 1.1 are proved by rather disparate methods: the “0-statement”
2
follows from entropic considerations, while the “1-statement” is proved by an interface-
exploration argument, a technique more commonly seen in percolation theory. The
definition of
kc
(
n
) ensures that
n2/
2
k2→ ∞
if
k < kc
(
n
) while
kn2/
2
k2−k→
0 if
k > kc(n), which is the main way we will use the definition of kc(n) in our arguments.
Let us briefly mention that a related, but somewhat different, two-dimensional
question about reconstructing “jigsaws” was raised by Mossel and Ross [
13
]. Following
work of Bordenave, Feige, and Mossel [
5
] and Nenadov, Pfister, and Steger [
16
], the
coarse asymptotics of the reconstruction threshold in this setting were independently
established by Balister, Bollob´as, and the first author [
3
] and by Martinsson [
12
]. In
contrast, our main result establishes fine-grained asymptotics of the reconstruction
threshold in the (somewhat different) setting considered here.
This paper is organized as follows. We give the short proof of the 0-statement
in Theorem 1.1 in Section 2. The bulk of the work in this paper is in the proof of
the 1-statement in Theorem 1.1 which follows in Section 3. We conclude with some
discussion of future directions in Section 4.
Note added in proof: Subsequent to our paper’s appearance on the arXiv, Demidovich,
Panichkin, and Zhukovskii [
6
] extended our results to
r
colors and
d
dimensions for
r, d ≥3. While it is straightforward to verify that our computations allow for a larger
number of colors, we posited in a previous version of this paper that it would be
necessary to find an appropriate higher-dimensional generalization of the interface
paths in our arguments in order to extend beyond
d
= 2. However, the methods of [
6
]
circumvent this need by careful modification to our reconstruction algorithm.
2. Proof of the 0-statement
In this short section, we prove the 0-statement in Theorem 1.1 which, as mentioned
earlier, follows from considerations of entropy.
Proof of the 0-statement in Theorem 1.1.
An easy calculation shows that the definition
of kc(n) ensures that
n2/2k2→ ∞ (1)
as
n→ ∞
for every
k < kc
(
n
). Under this condition, we show that with high probability,
it impossible to reconstruct a random picture
Pn
of size
n
from its
k
-deck. The reason
is simple: under this assumption on
k
, the
k
-deck does not contain enough entropy
to allow reconstruction; for simplicity, we phrase this argument in the language of
counting.
First, the number of pictures of size
n
is 2
n2
. Next, the number of such pictures that
are reconstructible from their
k
-decks is at most the number of distinct
k
-decks, which
is itself at most the number of solutions to the equation
x1+x2+· · · +x2k2= (n−k+ 1)2
3
over the non-negative integers, where
xi
is the number of copies of the
i
th
k×k
grid in
D. It follows that
P[R(n, k)] ≤(n−k+ 1)2+ 2k2−1
2k2−12−n2≤10n2
2k22k2
2−n2.
It is now straightforward to check that
P
[
R
(
n, k
)]
→
0 by
(1)
. This proves the 0-
statement in Theorem 1.1.□
3. Proof of the 1-statement
A simple calculation shows that the definition of kc(n) ensures that
kn2/2k2−k→0 (2)
as
n→ ∞
for all
k > kc
(
n
). We shall show that if
(2)
holds, then
Pn
is reconstructible
from its
k
-deck with high probability. To accomplish this, we provide an algorithm for
reconstruction and bound the probability that
Pn
is not the output when this algorithm
is run on Dk(Pn).
To motivate our preliminary analysis, we first give a rough description of the algorithm.
It begins by randomizing the deck and attempting to build the picture outward from
the first element, in one direction at a time. It will begin by extending the starting
element to a small rectangle “naively,” which means it will simply place the first deck
element that fits. Then it will extend the rectangle by one column at a time, followed
by one row at a time. The starting rectangle size will be linear in
k
, small enough
that a union bound suffices to show the rectangle is likely a correct reconstruction.
However, continuing to place deck elements naively will not suffice to give a whp correct
reconstruction. Thus, in the row and column extension steps we select deck elements to
place more carefully, in a way that has a lower probability of failure.
In the next section, we provide some notation including precise definitions of “exten-
sion.” We then consider the particular types of subpictures and extensions that will
come into play in our algorithm and show that with high probability, the deck does not
contain elements that will extend “badly.” At last, we provide our algorithm and put
together all of the results to show that the probability the algorithm fails tends to 0
above the threshold.
3.1. Notation and Terminology. We first set up some notation and conventions to
use throughout this section. As before, we will let
P
=
Pn
be the random picture we
wish to reconstruct from its
k
-deck
D
=
Dk
(
P
). A partial picture is a (not necessarily
rectangular) contiguous colored subset of an
n×n
picture. A grid or subgrid is a
rectangular partial picture, and a k-grid is a k×kgrid.
As in matrix notation, the coordinate (
i, j
) will denote the cell in the
i
th row from
the top,
j
th column from the left. For a partial picture
S
, the notation
S
(
i, j
) will
4
Figure 2. On the left is a grid
S
, in the center is a grid
T
, and on the
right is the extension of Sto the right by T.
denote the entry of cell (
i, j
), either 0 or 1. In our proof we may assume the elements
of
D
are distinct; indeed, we will show that the probability a given
k
-grid appears more
than once in
D
is
o
(1
/k
) in the supercritical regime. Thus, for a
k
-grid
T
, we may use
the notation
P
[
T
] to mean the cells of the
k×k
subgrid of
P
whose entries are identical
to
T
, as this is well-defined, and similarly
P
[
T
(
i, j
)] to mean the entry of
P
in the
i
th
row and jth column of the k-grid P[T].
(More formally, we can introduce an injective map
ϕ
:
D→P
mapping each deck
element
T
to the
k×k
subgrid of
P
identical to
T
; using this notion, then,
P
[
T
] refers
to
ϕ
(
T
). To lighten the notational burden, we will not use this notion in the remaining
discussion but mention it here for the reader’s benefit.)
We first need the notion of “extending” a partial picture.
Definition 3.1. Given two
k×k
grids
S
with columns
s1, . . . , sk∈ {
0
,
1
}k
and
T
with
columns
t1, . . . , tk∈ {
0
,
1
}k
,we say that
T
extends
S
to the right if
ti
=
si+1
for all
1
≤i≤k−
1. We call
T
itself an extension of
S
to the right and the resulting
k×
(
k
+1)
grid with columns s1, . . . , sk, tkthe extended grid.
See Figure 2for an illustration. We define extensions of a
k
-grid to the left, upwards,
and downwards analogously. We may also generalize this definition to larger partial
pictures, both rectangular and non-rectangular.
Definition 3.2. Given a partial picture
Q
and a
k×k
subgrid
S
of
Q
,we say that a
k×k
grid
T
extends
Q
to the right at
S
if it is an extension of
S
by the above definition
and if the extension is consistent with all other entries of Q\S.
In other words,
T
extends
Q
to the right at
S
if it is possible to place
T
as an
extension of Swithout creating any conflicts.
In the next subsection, we give some probability bounds that we will use in our
argument. The events that we define will play a role in the analysis of our reconstruction
algorithm described in Section 3.6, but we discuss the events here to make it clear that
they do not depend on the algorithm itself.
5
摘要：

ReconstructingRandomPicturesBhargavNarayananandCorrineYapAbstract.GivenarandombinarypicturePnofsizen,i.e.,ann×ngridfilledwithzerosandonesuniformlyatrandom,whenisitpossibletoreconstructPnfromitsk-deck,i.e.,themultisetofallitsk×ksubgrids?WedemonstrateΨwo-pointconcentration”forthereconstructionthreshol...

展开>> 收起<<
Reconstructing Random Pictures Bhargav Narayanan and Corrine Yap Abstract. Given a random binary picture Pnof size n i.e. an nngrid filled.pdf

共23页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：23 页 大小：439.64KB 格式：PDF 时间：2025-04-29

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 23
评分 收藏
分享
立即下载
客服
关注