betaFeedback

WorksMathematics

Shotgun Assembly of the Non-Uniform Labeled Lattice Model

Abstract

In this paper, we study the graph shotgun assembly problem in the labeled lattice model, as introduced by Mossel and Ross (2019). We start with a dd-dimensional lattice of length nn, where the color of each vertex is sampled i.i.d. from a distribution ππ. Then, we ask whether it is possible to reconstruct the coloring of the lattice given the coloring of each subgrid of length kk. While previous work by Ding and Liu (2023) and Demidovich, Panichkin, and Zhukovskii (2023) identified the reconstruction threshold when ππ is uniform, we examine the non-uniform case. This paper establishes a sufficient condition for the impossibility of reconstruction for d≥2d \geq 2 using information-theoretic arguments. Our negative result matches the known threshold in the uniform case.

Introduction

The graph shotgun assembly problem aims to infer a graph when given collections of local neighborhoods of the graph. One motivating application is the reconstruction of neural connections in neuroscience: given sub-networks of neurons collected from experiments, the goal is to reconstruct the entire neural network of the brain [19]. The term shotgun assembly is inspired by the problem of DNA shotgun assembly, in which an entire DNA sequence is reconstructed from fragments of DNA subsequences that overlap each other. In this setting, we have a long 1-dimensional lattice of nodes, each labeled with one of four values (adenine, cytosine, guanine, or thymine), and we would like to recover the label of each node based on observations of smaller, overlapping fragments.

The labeled lattice model, proposed by Mossel and Ross [15], generalizes DNA shotgun assembly for any arbitrary dimension and number of labels. Let π\pi be the probability mass function of a discrete distribution on rr values. Then, the labeled lattice model is defined as the dd-dimensional lattice of length nn, denoted Znd\mathbb{Z}^d_n, with i.i.d. vertex labels (also called colors) from a fixed π\pi. For the rest of this paper, we will use “lattice” to refer to the labeled lattice model.

The shotgun assembly problem on the labeled lattice model asks when it is possible to recover the coloring of the whole lattice, given that we can observe the coloring of small subgrids (but not their location within the lattice). To formalize this, we define a kk-card of the lattice as a subgrid of length kk where the coloring and orientation are observed, but the location is not. Then, we define the kk-deck of the lattice as the collection of all kk-cards. Note that each kk-card has kdk^d vertices, and that the kk-deck contains (n−k+1)d(n-k+1)^d total cards. Then, we call a lattice identifiable from its kk-deck if no other lattice shares the same kk-deck, and non-identifiable otherwise. The shotgun assembly problem aims to 1) determine the values of kk for which the lattice is identifiable and non-identifiable, and 2) if the lattice is identifiable, find an efficient algorithm to recover the lattice coloring from the kk-deck.

Prior work has largely focused on the case where π\pi is a uniform discrete distribution. The threshold for d=1d=1 was found by Dyer, Frieze, and Suen [8], who showed that as n→∞n \to\infty, the lattice is identifiable with a constant nontrivial probability if k=2log⁡n−log⁡(c)log⁡rk = \frac{2\log n-\log(c)}{\log r} where cc is a constant. Consequently, the lattice coloring is identifiable with high probability when k≥2(1+ϵ)log⁡nlog⁡rk \ge\frac{2(1+\epsilon)\log n}{\log r} while it is non-identifiable with high probability when k≤2(1−ϵ)log⁡nlog⁡rk \le\frac{2(1-\epsilon)\log n}{\log r}.

The threshold for d≥2d \ge2 was first found by Ding and Liu [7], who showed that if kd≥(1+ϵ)log⁡ndlog⁡rk^d \ge\frac{(1+\epsilon)\log n^d}{\log r}, then the lattice is identifiable with high probability, while if kd≤(1−ϵ)log⁡ndlog⁡rk^d \le\frac{(1-\epsilon)\log n^d}{\log r}, the lattice is non-identifiable with high probability. We note that Ding and Liu also developed an efficient algorithm to recover the lattice coloring above the threshold. Later, Narayanan and Yap [16] improved the threshold to two-point concentration in the case where d=2d = 2 and r=2r = 2 using an alternative algorithm, which was later generalized to all d≥2d \ge2 and r≥2r \ge2 by Demidovich, Panichkin, and Zhukovskii [5]. The latter showed that if k≥(log⁡ndlog⁡r)1/d+1d+ϵk \ge\left(\frac{\log n^d}{\log r}\right)^{1/d} + \frac{1}{d} + \epsilon, then the lattice is identifiable with high probability, while if k<(log⁡ndlog⁡r)1/d−ϵk < \left(\frac{\log n^d}{\log r}\right)^{1/d} - \epsilon, then the lattice is non-identifiable with high probability. Thus, the threshold for identifiability is well-understood in the uniform case.

Moving to the case where π\pi is non-uniform, the threshold for d=1d = 1 was also identified by Dyer, Frieze, and Suen [8]; the authors showed that as n→∞n \to\infty, the lattice can be recovered with a constant nontrivial probability when k=2log⁡n−log⁡clog⁡(1/q)k = \frac{2\log n-\log c}{\log(1/q)} where q:=∑i=1rπi2q := \sum_{i=1}^{r} \pi_i^2 and cc is a constant. Thus, the lattice coloring is identifiable with high probability when k≥2(1+ϵ)log⁡nlog⁡(1/q)k \ge\frac{2(1+\epsilon)\log n}{\log(1/q)}, and non-identifiable with high probability when k≤2(1−ϵ)log⁡nlog⁡(1/q)k \le\frac{2(1-\epsilon)\log n}{\log(1/q)}.

However, much less is known for d≥2d \ge2 since the analysis becomes substantially more difficult. Mossel and Ross [15] identified a sufficient condition for identifiability in which all (k−1)(k-1)-cards are unique, which is kd≥2(1+ϵ)log⁡ndlog⁡(1/q)k^d \ge\frac{2(1+\epsilon)\log n^d}{\log(1/q)}. Under this condition, we can recover the lattice by starting with an arbitrary initial kk-card, and then looking for other cards with a shared subgrid of length k−1k-1; since all subgrids with length k−1k-1 are unique in the lattice, cards with shared subgrids must necessarily be adjacent. We note that their sufficient condition does not match the threshold in the uniform case. To the best of our knowledge, this was the only known result in the non-uniform case.

Our main contribution is establishing a sufficient condition for non-identifiability in the non-uniform case, which matches the known threshold in the uniform case for d≥2d \ge2. We conjecture that our sufficient condition for non-identifiability is the true threshold in the non-uniform case. In addition, we also provide an alternative proof of non-identifiability for the d=1d = 1 case, which could help with understanding the lattice’s properties better.

Related Work

There is also a large body of work on related shotgun assembly problems that were first introduced by Mossel and Ross [15], and we discuss some of them here.

Dense Erdős–Rényi. One of the most well-studied such problems is shotgun assembly of unlabeled Erdős–Rényi graphs, which asks whether we can reconstruct a graph (up to isomorphism) from the local rr-neighborhood of each vertex. In the dense G(n,pn)G(n,p_n) setting, the focus has largely been on finding the edge probabilities pnp_n such that reconstruction is possible for a fixed rr. There are two phase transitions—reconstruction is possible when the probability is very small or very large, and impossible in between. Intuitively, when pnp_n is very small, all components fit within a single rr-neighborhood, while if pnp_n is very large, all rr-neighborhoods are unique [13].

For r=1r = 1, work by Gaudio and Mossel [9], Huang and Tikhomirov [11], and Johnston, Kronenberg, Roberts, and Scott [13] have identified the phase transitions at pn=Θ(n−3/2)p_n = \Theta(n^{-3/2}) and pn=Θ~(n−1/2)p_n = \widetilde{\Theta}(n^{-1/2}), where Θ~\widetilde{\Theta} denotes equality up to polylog factors.

For r=2r = 2, Johnston et al. [13] identified one phase transition at pn=Θ(n−5/4)p_n = \Theta(n^{-5/4}). The other phase transition is still unknown; Gaudio and Mossel [9] showed that if pn≤n−3/4−ϵp_n \le n^{-3/4-\epsilon} then reconstruction is impossible, while Johnston et al. [13] showed that if pn≥n−2/3+ϵp_n \ge n^{-2/3+\epsilon} then reconstruction is possible.

For r=3r = 3, the phase transitions are known from Johnston et al. [13], expanding on the initial work of Mossel and Ross [15]. One transition occurs at pn=Θ(n−2r+12r)p_n = \Theta\left(n^{-\frac{2r+1}{2r}}\right), while the other transition occurs at pn=Θ(log⁡2nn(log⁡log⁡n)3)p_n = \Theta\left(\frac{\log^2 n}{n(\log\log n)^3}\right).

Finally, for r≥4r \ge4, Johnston et al. [13] identified the phase transitions at pn=Θ(n−2r+12r)p_n = \Theta\left(n^{-\frac{2r+1}{2r}}\right) and pn=Θ(log⁡nn)p_n = \Theta\left(\frac{\log n}{n}\right). A more precise result is known for r=4r = 4: Gaudio, Rácz, and Sridhar [10] showed that reconstruction is possible when pn≥(1+ϵ)log⁡nnp_n \ge(1+\epsilon)\frac{\log n}{n}.

Sparse Erdős–Rényi. The sparse setting considers whether reconstruction is possible in G(n,λ/n)G(n,\lambda/n), which depends on the value of rr. Initial work by Mossel and Ross [15] showed that the threshold occurs at r=Θ(log⁡n)r = \Theta(\log n). Later, Ding, Jiang, and Ma [6] identified a sharp threshold at r=log⁡nlog⁡(λ2γλ)−1r = \frac{\log n}{\log(\lambda^{2}\gamma_{\lambda})-1}, where γλ\gamma_{\lambda} is the probability that two independent Galton-Watson trees with parameter λ\lambda are isomorphic. In particular, they showed that if r≤(1−ϵ)log⁡nlog⁡(λ2γλ)−1r \le\frac{(1-\epsilon)\log n}{\log(\lambda^{2}\gamma_{\lambda})-1} then reconstruction is impossible, while if r≥(1+ϵ)log⁡nlog⁡(λ2γλ)−1r \ge\frac{(1+\epsilon)\log n}{\log(\lambda^{2}\gamma_{\lambda})-1} then reconstruction is possible via a polynomial time algorithm.

Random Jigsaw Puzzles Another related problem introduced by Mossel and Ross [15] is reconstructing random “jigsaw puzzles”. In this problem, we consider a grid of n×nn \times n squares, where each border between adjacent squares has one of qq configurations drawn uniformly at random. Then, we want to know the values of qq for which we can reassemble the squares back together.

Bordenave, Feige, and Mossel [3] and Nenadov, Pfister, and Steger [17] initially showed that if q≥n1+ϵq \ge n^{1+\epsilon}, then the puzzle has a unique solution, while if q=o(n)q = o(n), then the puzzle does not have a unique solution. Follow-up work by Balister, Bollobás, and Narayanan [2] showed that there exist constants c,Cc, C such that q≥Cnq \ge Cn implies that the puzzle is unique, while q≤cnq \le cn implies that the puzzle is not unique. Then, Martinsson [14] identified specific constants, showing that if q≥(2+ϵ)nq \ge(2+\epsilon)n then the puzzle is unique, while if q≤2enq \le\frac{2}{\sqrt{e}}n then the puzzle is not unique. The true threshold remains an open problem.

The remainder of the paper is organized as follows. In Section 2, we present our main result, a sufficient condition for non-identifiability when d≥2d \ge2. We subsequently prove our main result in Section 3. In Section 4, we provide an alternative proof of non-identifiability for d=1d = 1. In Section 5, we discuss potential candidates for the true threshold for d≥2d \ge2. Finally, we conclude with some future research directions in Section 6.

Main Result

In this section, we present a sufficient condition for the lattice to be non-identifiable, which matches the known threshold in the uniform case [7].

Theorem 2.1. Let d≥2d \ge2 and fix ϵ>0\epsilon> 0. Then, the lattice is non-identifiable with high probability if

kd≤(1−ϵ)log⁡ndH(π),(1)k^{d} \le\frac{(1-\epsilon)\log n^{d}}{H(\pi)}, \tag*{(1)}

where H(π):=−∑i=1rπilog⁡(πi)H(\pi) := -\sum_{i=1}^{r} \pi_i \log(\pi_i) denotes the entropy of π\pi.

Remark. Observe that if π\pi is uniform, then H(π)=∑i=1r1rlog⁡r=log⁡rH(\pi) = \sum_{i=1}^{r} \frac{1}{r}\log r = \log r. Thus, our condition for non-identifiability becomes kd≤(1−ϵ)log⁡ndlog⁡rk^{d} \le\frac{(1-\epsilon)\log n^{d}}{\log r}, which is indeed the threshold in the uniform case.

We use techniques from information theory to prove Theorem 2.1. In particular, we use Fano’s inequality to lower bound the probability that the MAP estimator fails to recover the lattice from the deck, which shows that the error probability is 1−o(1)1-o(1). Intuitively, under Condition (1), the entropy of the lattice exceeds the entropy of the kk-deck, so there is not enough information in the kk-deck to recover the lattice.

Proof of Non-identifiability for d≥2d \ge2

In this section, we show that the lattice is non-identifiable with high probability when kd≤(1−ϵ)log⁡ndH(π)k^{d} \le\frac{(1-\epsilon)\log n^{d}}{H(\pi)}.

Preliminaries

We first state several lemmas that will be used in the proof.

Lemma 3.1 (Fano’s Inequality (Theorem 2.11.1 in [4])). Let X,YX, Y be correlated random variables. Suppose that we observe YY, and we want to estimate XX from the observed value of YY, which we denote X^\hat{X}. Define the error probability

Pe=P(X^≠X).P_{\mathrm{e}} = \mathbb{P}(\hat{X} \ne X).

Then, for any estimator X^=g(Y)\widehat{X}=g(Y)

Pe≥H(X∣Y)−1log⁡∣X∣,(2)P_e \ge\frac{H(X\mid Y)-1}{\log|\mathcal{X}|}, \tag*{(2)}

where H(X∣Y)H(X\mid Y) denotes the conditional entropy of XX conditioned on YY, and X\mathcal{X} is the support of XX.

Lemma 3.2 (Fannes-Audenaert Inequality [1]). Let PP and QQ be discrete random variables on the same support of NN elements with total variation distance dTV(P,Q)<ϵd_{TV}(P,Q)<\epsilon. Then

∣H(P)−H(Q)∣≤H(ϵ)+ϵlog⁡N.|H(P)-H(Q)| \le H(\epsilon)+\epsilon\log N.

where H(ϵ):=−ϵlog⁡ϵ−(1−ϵ)log⁡(1−ϵ)H(\epsilon):=-\epsilon\log\epsilon-(1-\epsilon)\log(1-\epsilon) is the binary entropy of $\epsilon.

Lemma 3.3 (Hoeffding’s Inequality). Let X∼Bin⁡(n,p)X\sim\operatorname{Bin}(n,p). Then,

P(∣X−E[X]∣≥t)≤2exp⁡(−2t2n).\mathbb{P}(|X-\mathbb{E}[X]|\ge t)\le2\exp\left(-\frac{2t^2}{n}\right).

Lemma 3.4 (Binomial Chernoff Bound). Let X∼Bin⁡(n,p)X\sim\operatorname{Bin}(n,p) and μ:=E[X]\mu:=\mathbb{E}[X]. Then,

P(X<(1−δ)μ)≤exp⁡(−μδ22).\mathbb{P}(X<(1-\delta)\mu)\le\exp\left(-\frac{\mu\delta^2}{2}\right).

Let GG be a lattice drawn from the labeled lattice model, and let DD be the corresponding kk-deck. To show that the lattice is non-identifiable, we can show that any estimator G^\widehat{G} fails to recover GG with high probability, meaning that P(G^≠G)=1−o(1)\mathbb{P}(\widehat{G}\ne G)=1-o(1). Rather than analyzing an estimator G^\widehat{G} over all possible lattices, we instead consider a simpler set of lattices whose probability goes to 11 as n→∞n\to\infty, and show that any estimator fails to recover such lattices with high probability.

Fix a sequence δn=n−d/3\delta_n=n^{-d/3}, which implies that δn2nd→∞\delta_n^2n^d\to\infty and that δn→0\delta_n\to0 as n→∞n\to\infty. We define TδnT_{\delta_n} as the event that the nn-lattice has a “typical” coloring σ\sigma, in the sense that for all i∈[r]i\in[r],

∣{v:σ(v)=i}∣∈[(1−δn)πind,(1+δn)πind].\left|\{v:\sigma(v)=i\}\right|\in\left[(1-\delta_n)\pi_i n^d,(1+\delta_n)\pi_i n^d\right].

That is, the number of vertices of each color is close to their expectation. Thus, we call a lattice δn\delta_n-typical if TδnT_{\delta_n} holds. It turns out that the lattice coloring is typical with high probability.

Lemma 3.5. The event TδnT_{\delta_n} holds with high probability.

Proof. Let πmin⁡:=min⁡iπi\pi_{\min}:=\min_i\pi_i. Observe that the number of vertices of color ii follows a Bin⁡(nd,πi)\operatorname{Bin}(n^d,\pi_i) distribution. By Hoeffding’s inequality and the union bound,

P(Tδn)≥1−∑i∈[r]2exp⁡(−2δn2πi2nd)≥1−2rexp⁡(−2δn2nd)=1−o(1),(3)\mathbb{P}(T_{\delta_n})\ge1-\sum_{i\in[r]}2\exp(-2\delta_n^2\pi_i^2n^d)\ge1-2r\exp(-2\delta_n^2n^d)=1-o(1), \tag*{(3)}

which shows that TδnT_{\delta_n} holds with high probability.

Since the lattice coloring is typical with high probability, it suffices to show that typical lattices are not identifiable with high probability. To this end, we define G~\widetilde{G} as a lattice coloring with the same distribution as GG conditioned on TδnT_{\delta_n}, and D~\widetilde{D} as a kk-deck with the same distribution as DD conditioned on TδnT_{\delta_n}. Let G′G' be the MAP estimator for estimating G~\widetilde{G} from D~\widetilde{D}. Then, showing that typical lattices are non-identifiable with high probability is equivalent to showing that P(G′≠G~)=1−o(1)\mathbb{P}(G'\ne\widetilde{G})=1-o(1).

In addition, we define Tδn\mathcal{T}_{\delta_n} as the set of lattice colorings that satisfy TδnT_{\delta_n}, and denote Mn=∣Tδn∣M_n=|\mathcal{T}_{\delta_n}|, which is the number of δn\delta_n-typical nn-lattices.

Proposition 3.6. Suppose that the following three properties hold.

  1. H(G~)=ndH(π)+o(1)H(\widetilde{G})=n^dH(\pi)+o(1),

  1. log⁡Mn≤ndH(π)+o(nd)\log M_n\le n^dH(\pi)+o(n^d), and

  1. H(D~)=o(nd)H(\widetilde{D}) = o(n^d).

Then, P(G′≠G~)=1−o(1)P(G' \ne\widetilde{G}) = 1 - o(1), which shows that the lattice is non-identifiable with high probability.

Proof. From Fano’s inequality, we have that

P(G′≠G~)≥H(G~∣D~)−1log⁡Mn=H(G~)−H(D~)−1log⁡Mn.P(G' \ne\widetilde{G}) \ge\frac{H(\widetilde{G} \mid\widetilde{D}) - 1}{\log M_n} = \frac{H(\widetilde{G}) - H(\widetilde{D}) - 1}{\log M_n}.

where H(G~∣D~)=H(G~)−H(D~)H(\widetilde{G} \mid\widetilde{D}) = H(\widetilde{G}) - H(\widetilde{D}) because D~\widetilde{D} is completely determined by G~\widetilde{G}. Then, using Properties 1-3 above, we obtain

P(G′≠G~)≥ndH(π)+o(1)−o(nd)−1ndH(π)+o(nd)=1−o(1).P(G' \ne\widetilde{G}) \ge\frac{n^d H(\pi) + o(1) - o(n^d) - 1}{n^d H(\pi) + o(n^d)} = 1 - o(1).

In the sequel, we prove that the three properties in Proposition 3.6 hold when kd≤(1−ϵ)log⁡ndH(π)k^d \le\frac{(1-\epsilon)\log n^d}{H(\pi)}, which allows us to conclude Theorem 2.1.

Proof of Property 1

Lemma 3.7 (Property 1). We have that H(G~)=ndH(π)+o(1)H(\widetilde{G}) = n^d H(\pi) + o(1).

Proof. Observe that we can represent the lattice as ndn^d i.i.d. random variables which encode the color of each vertex in the lattice. Since the joint entropy of i.i.d. random variables equals the sum of their individual entropies, we obtain that H(G)=ndH(π)H(G) = n^d H(\pi). Hence, it is sufficient to show that H(G~)=H(G)+o(1)H(\widetilde{G}) = H(G) + o(1).

To accomplish this, we first compute the total variation distance between GG and G~\widetilde{G}, denoted dTV(G,G~)d_{\mathrm{TV}}(G,\widetilde{G}). By the coupling inequality (Lemma 4.1.11 in [18]), we have that

dTV(G,G~)≤P(G≠G~)d_{\mathrm{TV}}(G,\widetilde{G}) \le P(G \ne\widetilde{G})

for all couplings of GG and G~\widetilde{G}. Thus, we consider the following coupling: If G∈TδG \in T_\delta then we let G~=G\widetilde{G} = G. If G∉TδG \notin T_\delta, then we sample G~\widetilde{G} separately so that the marginal distribution of G~\widetilde{G} is preserved. In this case, we have

dTV(G,G~)≤P(G≠G~)=1−P(Tδn)≤2rexp⁡(−2δn2nd)(4)d_{\mathrm{TV}}(G,\widetilde{G}) \le P(G \ne\widetilde{G}) = 1 - P(T_\delta^n) \le2r\exp(-2\delta_n^2 n^d) \tag*{(4)}

from (3). Now, we apply the Fannes-Audenaert inequality, which yields

∣H(G)−H(G~)∣≤H(2rexp⁡(−2δn2nd))+2rexp⁡(−2δn2nd)log⁡rnd.\left|H(G) - H(\widetilde{G})\right| \le H(2r\exp(-2\delta_n^2 n^d)) + 2r\exp(-2\delta_n^2 n^d)\log r^{n^d}.

To analyze the first term, recall that δn2nd→∞\delta_n^2 n^d \to\infty as n→∞n \to\infty. Therefore, we have that 2rexp⁡(−2δn2nd)→02r\exp(-2\delta_n^2 n^d) \to0, which implies that H(2rexp⁡(−2δn2nd))→0H(2r\exp(-2\delta_n^2 n^d)) \to0 as well. For the second term, we use the fact that δn=n−d/3\delta_n = n^{-d/3} to obtain

2rexp⁡(−2δn2nd)log⁡rnd=2rexp⁡(−2nd/3)ndlog⁡r→0.2r\exp(-2\delta_n^2 n^d)\log r^{n^d} = 2r\exp(-2n^{d/3})n^d\log r \to0.

Therefore, ∣H(G)−H(G~)∣=o(1)\left|H(G) - H(\widetilde{G})\right| = o(1), which shows that H(G~)=H(G)+o(1)=ndH(π)+o(1)H(\widetilde{G}) = H(G) + o(1) = n^d H(\pi) + o(1).

Proof of Property 2

Lemma 3.8 (Property 2). We have that log⁡Mn≤ndH(π)+o(nd)\log M_n \le n^d H(\pi) + o(n^d).

Proof. Observe that the probability of any given δn\delta_n-typical lattice is at least

∏i=1rπi(1+δn)πind\prod_{i=1}^{r} \pi_i^{(1+\delta_n)\pi_i n^d}

since there are at most (1+δn)πind(1+\delta_n)\pi_i n^d vertices with color ii. Therefore, the number of typical lattices is at most

Mn≤(∏i=1rπi(1+δn)πind)−1M_n \le\left(\prod_{i=1}^{r}\pi_i^{(1+\delta_n)\pi_i n^d}\right)^{-1}

which implies that

log⁡Mn≤−∑i=1r(1+δn)πindlog⁡(πi)=(1+δn)nd∑i=1r−πilog⁡πi=(1+δn)ndH(π).\log M_n \le-\sum_{i=1}^{r}(1+\delta_n)\pi_i n^d\log(\pi_i)=(1+\delta_n)n^d\sum_{i=1}^{r}-\pi_i\log\pi_i=(1+\delta_n)n^dH(\pi).

Since δn→0\delta_n\to0, we have that log⁡Mn≤(1+o(1))ndH(π)=ndH(π)+o(nd)\log M_n\le(1+o(1))n^dH(\pi)=n^dH(\pi)+o(n^d), which completes the proof. □

Proof of Property 3

We prove Property 3 using a similar strategy as Property 1. First, we show that H(D)=o(nd)H(D)=o(n^d) by finding an explicit encoding for DD and showing that the expected encoding length is o(nd)o(n^d); since H(D)H(D) is less than the expected encoding length of any encoding [4], it follows that H(D)=o(nd)H(D)=o(n^d) as well. Then, we use the coupling inequality to compute the total variation distance between DD and D~\widetilde{D}, and apply the Fannes-Audenaert inequality to show that ∣H(D)−H(D~)∣=o(1)\lvert H(D)-H(\widetilde{D})\rvert=o(1).

Lemma 3.9. If kd≤(1−ϵ)log⁡ndH(π)k^d\le\frac{(1-\epsilon)\log n^d}{H(\pi)}, then H(D)=o(nd)H(D)=o(n^d).

Proof. We construct an explicit encoding of the deck and show that the expected encoding length is o(nd)o(n^d). Consider the following encoding: For every type of card that appears in the deck, we will encode the type of card using a unique identifier of length log⁡(rkd)\log(r^{k^d}), then encode the number of times that type of card appears using a string of length log⁡(nd)\log(n^d).

Observe that there are at most rkdr^{k^d} types of cards because there are kdk^d vertices in each card and rr choices for the color of each vertex. Thus, we can give each type of card a unique identifier using log⁡(rkd)\log(r^{k^d}) bits. Meanwhile, there are less than ndn^d cards in the deck (which is also the maximum number of times any given type of card can appear), so we can encode the count of each card type using log⁡(nd)\log(n^d) bits.

Now, we compute the expected encoding length of the deck from the point of view of a fixed, unrevealed card. Its contribution to the encoding length is given by

1Z(log⁡(rkd)+log⁡(nd)),\frac{1}{Z}\left(\log(r^{k^d})+\log(n^d)\right),

where ZZ is the number of times that card appears in the deck—this is an overcounting factor, since all cards of the same type have a collective encoding length of log⁡(rkd)+log⁡(nd)\log(r^{k^d})+\log(n^d). Thus, the expected encoding length of the deck is

E[1Z]⋅nd(log⁡(rkd)+log⁡(nd)).\mathbb{E}\left[\frac{1}{Z}\right]\cdot n^d\left(\log(r^{k^d})+\log(n^d)\right).

It remains to bound E[1/Z]\mathbb{E}[1/Z]. First, observe that for any t>0t>0,

E[1Z]=E[1Z∣Z≥t]P(Z≥t)+E[1Z∣Z<t]P(Z<t)≤1tP(Z≥t)+P(Z<t)≤1t+P(Z<t).(5)\begin{aligned} \mathbb{E}\left[\frac{1}{Z}\right] &=\mathbb{E}\left[\left.\frac{1}{Z}\right|Z\ge t\right]\mathbb{P}(Z\ge t)+\mathbb{E}\left[\left.\frac{1}{Z}\right|Z<t\right]\mathbb{P}(Z<t)\\ &\le\frac{1}{t}\mathbb{P}(Z\ge t)+\mathbb{P}(Z<t)\\ &\le\frac{1}{t}+\mathbb{P}(Z<t). \tag*{(5)} \end{aligned}

To upper-bound E[1/Z]\mathbb{E}[1/Z], we let t=nϵd/2t=n^{\epsilon d/2} and focus on upper-bounding P(Z<t)\mathbb{P}(Z<t). Rather than examine ZZ directly, we define a new random variable Z′Z' as follows: Partition the lattice into non-overlapping regions of kdk^d vertices, which we call the cards of the partitioned lattice; there are a total of (n/k)d(n/k)^d cards in the partitioned lattice. Then, consider a random card from the partitioned lattice, which we call the top card, and let Z′Z' be the number of times the top card appears in the partitioned lattice. We note that Z′⪯ZZ' \preceq Z stochastically, which yields P(Z<t)≤P(Z′<t)\mathbb{P}(Z < t) \le\mathbb{P}(Z' < t).

We now upper-bound P(Z′<t)\mathbb{P}(Z' < t). Let X=(X1,…,Xr)X = (X_1,\ldots,X_r), where XiX_i is the number of vertices of color ii in the top card. For any fixed δ>0\delta> 0, define EδE_\delta as the event

Eδ={Xi∈[(1−δ)πikd,(1+δ)πikd] ∀i∈[r]}.(6)E_\delta= \left\{X_i \in[(1-\delta)\pi_i k^d,(1+\delta)\pi_i k^d] \ \forall i \in[r]\right\}. \tag*{(6)}

meaning that the number of vertices of each color is close to its expectation. We call the top card δ\delta-typical if EδE_\delta holds. Note that the top card is δ\delta-typical with high probability, which can be shown using a similar argument to Lemma 3.5.

To compute P(Z′<t)\mathbb{P}(Z' < t), we fix δ=ϵ/4\delta= \epsilon/4 and use the law of total probability, conditioning on XX. Furthermore, we divide the sum into two parts depending on whether the card is δ\delta-typical, which yields

P(Z′<t)=∑x∈EδP(Z′<t∣X=x)P(X=x)+P({Z′<t}∩{X∉Eδ})=∑x∈EδP(Z′<t∣X=x)P(X=x)+o(1).(7)\begin{aligned} \mathbb{P}(Z' < t) &= \sum_{x \in E_\delta} \mathbb{P}(Z' < t \mid X=x)\mathbb{P}(X=x) + \mathbb{P}(\{Z' < t\} \cap\{X \notin E_\delta\}) \\ &= \sum_{x \in E_\delta} \mathbb{P}(Z' < t \mid X=x)\mathbb{P}(X=x) + o(1). \tag*{(7)} \end{aligned}

Conditioned on X=xX=x, the probability that any given card equals the top card is ∏i=1rπixi\prod_{i=1}^{r}\pi_i^{x_i}. Therefore, the number of cards matching the top card is distributed according to (Z′∣X=x)∼Bin⁡((n/k)d,∏i=1rπixi)(Z' \mid X=x) \sim\operatorname{Bin}((n/k)^d,\prod_{i=1}^{r}\pi_i^{x_i}).

Now, define Y∼Bin⁡((n/k)d,∏i=1rπi(1+δ)πikd)Y \sim\operatorname{Bin}((n/k)^d,\prod_{i=1}^{r}\pi_i^{(1+\delta)\pi_i k^d}), and since x∈Eδx \in E_\delta, we have that xi≤(1+δ)πikdx_i \le(1+\delta)\pi_i k^d for all ii. Hence, Y⪯(Z′∣X=x)Y \preceq(Z' \mid X=x) stochastically for any x∈Eδx \in E_\delta, which implies that P(Z′<t∣X=x)≤P(Y<t)\mathbb{P}(Z' < t \mid X=x) \le\mathbb{P}(Y < t) for any x∈Eδx \in E_\delta. In light of (7), we obtain that P(Z′<t)≤P(Y<t)\mathbb{P}(Z' < t) \le\mathbb{P}(Y < t), which also implies that

P(Z<t)≤P(Y<t).(8)\mathbb{P}(Z < t) \le\mathbb{P}(Y < t). \tag*{(8)}

Now, we compute an upper bound for P(Y<t)\mathbb{P}(Y < t) using the Chernoff bound. We first compute E[Y]\mathbb{E}[Y], which yields

E[Y]=ndkd∏i=1rπi(1+δ)πikd=ndkdexp⁡((1+δ)kd∑i=1rπilog⁡πi)=ndkde−(1+δ)kdH(π).\begin{aligned} \mathbb{E}[Y] = \frac{n^d}{k^d}\prod_{i=1}^{r}\pi_i^{(1+\delta)\pi_i k^d} = \frac{n^d}{k^d}\exp\left((1+\delta)k^d\sum_{i=1}^{r}\pi_i\log\pi_i\right) \\ &= \frac{n^d}{k^d}e^{-(1+\delta)k^d H(\pi)}. \end{aligned}

Under the condition kd≤(1−ϵ)dlog⁡nH(π)k^d \le\frac{(1-\epsilon)d\log n}{H(\pi)}, we have that

ndkd≥ndH(π)(1−ϵ)dlog⁡n=ndClog⁡n,\frac{n^d}{k^d} \ge\frac{n^d H(\pi)}{(1-\epsilon)d\log n} = \frac{n^d}{C\log n},

where C:=(1−ϵ)dH(π)C := \frac{(1-\epsilon)d}{H(\pi)} is a constant. Under this condition, we also have that

e−(1+δ)H(π)kd≥e−(1+δ)(1−ϵ)dlog⁡n=n−(1+δ)(1−ϵ)d>n−(1−3ϵ/4)d,e^{-(1+\delta)H(\pi)k^d} \ge e^{-(1+\delta)(1-\epsilon)d\log n} = n^{-(1+\delta)(1-\epsilon)d} > n^{-(1-3\epsilon/4)d},

where the last inequality follows from δ=ϵ/4\delta= \epsilon/4. Therefore,

E[Y]≥ndClog⁡nn−(1−3ϵ/4)d=n3ϵd/4Clog⁡n≳n2ϵd/3.\mathbb{E}[Y] \ge\frac{n^d}{C\log n}n^{-(1-3\epsilon/4)d} = \frac{n^{3\epsilon d/4}}{C\log n} \gtrsim n^{2\epsilon d/3}.

Now, we use the Chernoff bound to upper-bound P(Y<t)\mathbb{P}(Y < t) where t=nϵd/2t = n^{\epsilon d/2}, which yields

P(Y≤nϵd/2)≤P(Y≤12n2ϵd/3)≤P(Y≤12μ)≤exp⁡(−18μ)≤exp⁡(−18n2ϵd/3).\mathbb{P}\left(Y \le n^{\epsilon d/2}\right) \le\mathbb{P}\left(Y \le\frac{1}{2}n^{2\epsilon d/3}\right) \le\mathbb{P}\left(Y \le\frac{1}{2}\mu\right) \le\exp\left(-\frac{1}{8}\mu\right) \le\exp\left(-\frac{1}{8}n^{2\epsilon d/3}\right).

From (8), we see that P(Z≤nϵd/2)≤exp⁡(−18n2ϵd/3)\mathbb{P}(Z \le n^{\epsilon d/2}) \le\exp\left(-\frac{1}{8}n^{2\epsilon d/3}\right) as well. Substituting this into (5), we obtain that

E[1Z]≤n−ϵd/2+exp⁡(−n2ϵd/3/8)≤n−ϵd/3.\mathbb{E}\left[\frac{1}{Z}\right] \le n^{-\epsilon d/2} + \exp\left(-n^{2\epsilon d/3}/8\right) \le n^{-\epsilon d/3}.

Consequently, the expected encoding length of the deck is at most

nd(1−ϵ/3)(log⁡(knd)+log⁡(nd))≲nd(1−ϵ/4)=o(nd),n^{d(1-\epsilon/3)}\left(\log(k^{n^d})+\log(n^d)\right)\lesssim n^{d(1-\epsilon/4)}=o(n^d),

which shows that H(D)=o(nd)H(D)=o(n^d).

Using Lemma 3.9, we can now prove Property 3.

Lemma 3.10 (Property 3). If kd≤(1−ϵ)log⁡ndH(π)k^d\leq\frac{(1-\epsilon)\log n^d}{H(\pi)}, then H(D~)=o(nd)H(\widetilde{D})=o(n^d).

Proof. We first use the coupling inequality (Lemma 4.1.11 in [18]) to bound the total variation distance between DD and D~\widetilde{D}, which yields

dTV(D,D~)≤P(D≠D~)d_{\mathrm{TV}}(D,\widetilde{D})\leq\mathbb{P}(D\neq\widetilde{D})

for any coupling of DD, D~\widetilde{D}. Consider the coupling between GG, G~\widetilde{G} described in Lemma 3.7; since DD, D~\widetilde{D} are determined by GG, G~\widetilde{G} respectively, this also induces a coupling between DD, D~\widetilde{D}. Furthermore, we note that if G=G~G=\widetilde{G}, then D=D~D=\widetilde{D} as well. Therefore, we obtain

dTV(D,D~)≤P(D≠D~)≤P(G≠G~)≤2rexp⁡(−2δn2nd),d_{\mathrm{TV}}(D,\widetilde{D})\leq\mathbb{P}(D\neq\widetilde{D})\leq\mathbb{P}(G\neq\widetilde{G})\leq2r\exp(-2\delta_n^2n^d),

where the last inequality follows from (4). Then, applying the Fannes-Audenaert inequality and repeating the argument used in Lemma 3.7 shows that ∣H(D)−H(D~)∣=o(1)\lvert H(D)-H(\widetilde{D})\rvert=o(1). Since H(D)=o(nd)H(D)=o(n^d) from Lemma 3.9, we obtain that H(D~)=o(nd)H(\widetilde{D})=o(n^d) as well.

Proof of Non-identifiability for d=1d=1

In this section, we provide an alternative proof of non-identifiability in the 1-dimensional case. We first state the threshold established by Dyer, Frieze, and Suen [8] and Mossel and Ross [15].

Theorem 4.1. Let d=1d=1 and fix ϵ>0\epsilon>0. Then, the lattice is identifiable with high probability if

k≥2(1+ϵ)log⁡nlog⁡(1/q),(9)k\geq\frac{2(1+\epsilon)\log n}{\log(1/q)}, \tag*{(9)}

and non-identifiable with high probability if

k≤2(1−ϵ)log⁡nlog⁡(1/q),(10)k\leq\frac{2(1-\epsilon)\log n}{\log(1/q)}, \tag*{(10)}

where q:=∑i=1rπi2q:=\sum_{i=1}^{r}\pi_i^2 is the probability that two vertices have the same color.

We note that this threshold corresponds to all (k−1)(k-1)-cards being unique. Above this threshold, all (k−1)(k-1)-cards are unique with high probability; this allows us to identify adjacent kk-cards by looking for subgrids of length k−1k-1 which appear in both cards, and then reconstruct the lattice by piecing together adjacent cards. Meanwhile, below that threshold, many kk-cards are not unique, which allows us to produce multiple distinct lattices with the same kk-deck through a swapping procedure.

To prove non-identifiability under Condition (10), we extend a technique from Ding and Liu [7] that showed non-identifiability in the uniform case. Let I1,…,I6I_1,\ldots,I_6 be disjoint, consecutive intervals in the 1-dimensional lattice Zn1\mathbb{Z}_n^1 with m:=⌊n/6⌋m:=\lfloor n/6\rfloor vertices each. For each IjI_j, let Γj\Gamma_j be a collection of ℓ:=⌊m/k⌋\ell:=\lfloor m/k\rfloor disjoint kk-cards within IjI_j. We claim the following proposition holds.

Proposition 4.2. Suppose that k≤2(1−ϵ)log⁡nlog⁡(1/q)k\leq\frac{2(1-\epsilon)\log n}{\log(1/q)}. With high probability, there exist Bj∈ΓjB_j\in\Gamma_j for j=1,3,4,6j=1,3,4,6 such that

σ∣B1=σ∣B4andσ∣B3=σ∣B6(11)\sigma|_{B_1}=\sigma|_{B_4}\quad\text{and}\quad\sigma|_{B_3}=\sigma|_{B_6} \tag*{(11)}

and that

σ∣J[1,m]≠σ∣J′[1,m],(12)\sigma|_{J[1,m]}\neq\sigma|_{J'[1,m]}, \tag*{(12)}

where JJ is the interval strictly between B1B_1 and B3B_3 and J′J' is the interval strictly between B4B_4 and B6B_6, and J[1,m]J[1,m] is the first mm vertices in JJ and J′[1,m]J'[1,m] is the first mm vertices in J′J'.

Proposition 4.2 is sufficient to show non-identifiability because JJ and J′J' can be swapped to produce different lattices while keeping the same deck; we refer the reader to Section 2.1 in [7] for full details. Therefore, we obtain the non-identifiability result in Theorem 4.1 as a corollary.

Proof of Proposition 4.2. We first show (11) using the second moment method. Let ZZ be the number of pairs B∈Γ1,B′∈Γ4B \in\Gamma_1, B' \in\Gamma_4 such that σ∣B=σ∣B′\sigma|_B = \sigma|_{B'}. Formally,

Z=∑B∈Γ1,B′∈Γ41σ∣B=σ∣B′.(13)Z = \sum_{\substack{B\in\Gamma_1,B'\in\Gamma_4}} \mathbf{1}_{\sigma|_B=\sigma|_{B'}}. \tag*{(13)}

We will show that P(Z=0)→0\mathbb{P}(Z=0) \to0 as n→∞n \to\infty using Chebyshev’s inequality. Observe that for any disjoint cards BB and B′B',

P(σ∣B=σ∣B′)=qk\mathbb{P}(\sigma|_B=\sigma|_{B'})=q^k

because the probability that any two given vertices match is qq. Hence,

E[Z]=ℓ2(∑i=1rπi2)k=ℓ2qk.\mathbb{E}[Z]=\ell^2\left(\sum_{i=1}^r\pi_i^2\right)^k=\ell^2q^k.

Now we compute the second moment. First, observe that

E[Z2]=E[∑B∈Γ1,B′∈Γ4,C∈Γ1,C′∈Γ41σ∣B=σ∣B′1σ∣C=σ∣C′]=ℓ2qk+2ℓ2(ℓ−1)(∑i=1rπi3)k+ℓ2(ℓ−1)2q2k≤ℓ2qk+2ℓ3(∑i=1rπi3)k+ℓ4q2k.(14)\begin{aligned} \mathbb{E}[Z^2] &=\mathbb{E}\left[\sum_{\substack{B\in\Gamma_1,B'\in\Gamma_4,C\in\Gamma_1,C'\in\Gamma_4}} \mathbf{1}_{\sigma|_B=\sigma|_{B'}}\mathbf{1}_{\sigma|_C=\sigma|_{C'}}\right]\\ &=\ell^2q^k+2\ell^2(\ell-1)\left(\sum_{i=1}^r\pi_i^3\right)^k+\ell^2(\ell-1)^2q^{2k}\\ &\le\ell^2q^k+2\ell^3\left(\sum_{i=1}^r\pi_i^3\right)^k+\ell^4q^{2k}. \tag*{(14)} \end{aligned}

We will explain where each term in the second equality comes from. The first term comes from the case where B=CB=C and B′=C′B'=C'. There are ℓ2\ell^2 ways to choose such B,B′,C,C′B,B',C,C'. To obtain σ∣B=σ∣B′\sigma|_B=\sigma|_{B'} and σ∣C=σ∣C′\sigma|_C=\sigma|_{C'}, we need one subinterval of kk vertices to have the same coloring as another subinterval of kk vertices, which occurs with probability qkq^k.

The second term comes from the case where either B=CB=C or B′=C′B'=C', but not both. Assume for now that B=CB=C and B′≠C′B'\ne C'. There are ℓ⋅ℓ(ℓ−1)=ℓ2(ℓ−1)\ell\cdot\ell(\ell-1)=\ell^2(\ell-1) ways to choose such B,B′,C,C′B,B',C,C' (the ℓ\ell factor comes from choosing BB and the ℓ(ℓ−1)\ell(\ell-1) factor comes from choosing B′,C′B',C'). To obtain σ∣B=σ∣B′\sigma|_B=\sigma|_{B'} and σ∣C=σ∣C′\sigma|_C=\sigma|_{C'}, we need three subintervals of kk vertices to all have the same coloring (since BB must have the same coloring as both B′B' and C′C'), which occurs with probability (∑i=1rπi3)k\left(\sum_{i=1}^r\pi_i^3\right)^k. The same logic holds for when B≠CB\ne C and B′=C′B'=C'.

The third term comes from the case where both B≠CB\ne C and B′≠C′B'\ne C'. There are ℓ(ℓ−1)⋅ℓ(ℓ−1)=ℓ2(ℓ−1)2\ell(\ell-1)\cdot\ell(\ell-1)=\ell^2(\ell-1)^2 ways to choose such B,B′,C,C′B,B',C,C'. Then, σ∣B=σ∣B′\sigma|_B=\sigma|_{B'} occurs with probability qkq^k and σ∣C=σ∣C′\sigma|_C=\sigma|_{C'} also occurs with probability qkq^k; since these events are independent, the probability of σ∣B=σ∣B′\sigma|_B=\sigma|_{B'} and σ∣C=σ∣C′\sigma|_C=\sigma|_{C'} is q2kq^{2k}.

Now, we apply Chebyshev’s inequality, which yields

P(Z=0)≤E[Z2]E[Z]2−1≤ℓ2qk+2ℓ3(∑i=1rπi3)k+ℓ4q2kℓ4q2k−1=1ℓ2qk+2(∑i=1rπi3)kℓq2k.\begin{aligned} \mathbb{P}(Z=0)\le\frac{\mathbb{E}[Z^2]}{\mathbb{E}[Z]^2}-1 \\ &\le\frac{\ell^2q^k+2\ell^3\left(\sum_{i=1}^r\pi_i^3\right)^k+\ell^4q^{2k}}{\ell^4q^{2k}}-1 \\ &=\frac{1}{\ell^2q^k}+\frac{2\left(\sum_{i=1}^r\pi_i^3\right)^k}{\ell q^{2k}}. \end{aligned}

We will show that both terms go to zero. For the first term, recall that ℓ=n/(6k)\ell=n/(6k) and observe that k≤2(1−ϵ)log⁡nlog⁡(1/q)k\le\frac{2(1-\epsilon)\log n}{\log(1/q)} implies qk≥n−2(1−ϵ)q^k\ge n^{-2(1-\epsilon)}. Hence, we obtain

1ℓ2qk≤1n236k2n−2(1−ϵ)=36k2n2ϵ→0.\frac{1}{\ell^2q^k}\le\frac{1}{\frac{n^2}{36k^2}n^{-2(1-\epsilon)}}=\frac{36k^2}{n^{2\epsilon}}\to0.

For the second term, we use the monotonicity of pp-norms [12] to obtain that (∑iπi3)1/3≤q1/2(\sum_i \pi_i^3)^{1/3} \le q^{1/2}, which implies that (∑iπi3)≤q3/2(\sum_i \pi_i^3) \le q^{3/2}. In addition, observe that k≤2(1−ϵ)log⁡nlog⁡(1/q)k \le\frac{2(1-\epsilon)\log n}{\log(1/q)} implies qk/2≥n−(1−ϵ)q^{k/2} \ge n^{-(1-\epsilon)}. Thus,

2(∑i=1rπi3)kℓq2k≤2q3k/2ℓq2k=12kℓq2k≤12knqk/2≤12knn−(1−ϵ)=12knϵ→0.\frac{2(\sum_{i=1}^r \pi_i^3)^k}{\ell q^{2k}} \le\frac{2q^{3k/2}}{\ell q^{2k}} = \frac{12k}{\ell q^{2k}} \le\frac{12k}{nq^{k/2}} \le\frac{12k}{nn^{-(1-\epsilon)}} = \frac{12k}{n^\epsilon} \to0.

Therefore, with high probability, there exist B1∈Γ1,B4∈Γ4B_1 \in\Gamma_1, B_4 \in\Gamma_4 such that σ∣B1=σ∣B4\sigma|_{B_1} = \sigma|_{B_4}. Identical reasoning shows that with high probability, there exist B3∈Γ3,B6∈Γ6B_3 \in\Gamma_3, B_6 \in\Gamma_6 such that σ∣B3=σ∣B6\sigma|_{B_3} = \sigma|_{B_6}. Hence, (11) holds with high probability.

Now, we show (12) using a straightforward calculation and the union bound, following the same reasoning as [7]. For any given J,J′J, J', we have that

P(σ∣J[1,m]=σ∣J′[1,m])=qm=qn/6,\mathbb{P}(\sigma|_{J[1,m]} = \sigma|_{J'[1,m]}) = q^m = q^{n/6},

which is exponentially decreasing in nn. The number of possible choices for JJ and J′J' is ℓ4=n4/(6k)4\ell^4 = n^4/(6k)^4 (coming from ℓ\ell choices for each of B,B′,C,C′B, B', C, C'), which is polynomially increasing in nn. By the union bound, (12) holds with high probability.

Discussion on the Threshold

In this section, we propose two possible values for the threshold and discuss why each might be the true threshold. One possible value for the threshold is kd=log⁡ndH(π)k^d = \frac{\log n^d}{H(\pi)}. There are a couple of reasons for this: First, this value coincides with the threshold in the uniform case, as H(π)=log⁡rH(\pi) = \log r in the uniform case. In addition, we have already proven non-identifiability below this value, and despite our attempts, we were unable to extend our proof to larger values of kdk^d.

However, we do not rule out this possibility. Our proof depends on finding an encoding of the deck such that H(D)=o(nd)H(D) = o(n^d) to prove Property 3 in Proposition 3.6, and the threshold is used to show that such an encoding is possible. We think that it may be possible to find a better encoding of the deck such that H(D)=o(nd)H(D) = o(n^d) even when kd≥(1+ϵ)log⁡ndH(π)k^d \ge\frac{(1+\epsilon)\log n^d}{H(\pi)}, which would prove non-identifiability of the lattice for a higher value (and disqualify kd=log⁡ndH(π)k^d = \frac{\log n^d}{H(\pi)} as a possibility for the true threshold).

Another possible value for the threshold is kd=log⁡ndlog⁡(1/q)k^d = \frac{\log n^d}{\log(1/q)}, where q=∑iπi2q = \sum_i \pi_i^2. This value also coincides with the threshold in the uniform case, as q=∑i=1r(1/r)2=1/rq = \sum_{i=1}^r (1/r)^2 = 1/r, so 1/q=r1/q = r. Furthermore, in the uniform case, the threshold for d≥2d \ge2 is exactly half of the threshold for d=1d = 1, which are kd=log⁡ndlog⁡rk^d = \frac{\log n^d}{\log r} and kd=2log⁡ndlog⁡rk^d = \frac{2\log n^d}{\log r} respectively. From [8], we know that the threshold for the non-uniform case with d=1d = 1 is kd=2log⁡ndlog⁡(1/q)k^d = \frac{2\log n^d}{\log(1/q)}; taking half of this value suggests that the threshold for d≥2d \ge2 could be kd=log⁡ndlog⁡(1/q)k^d = \frac{\log n^d}{\log(1/q)}.

To compare these two possible thresholds, we observe that H(π)≥log⁡(1/q)H(\pi) \ge\log(1/q) with equality holding if and only if π\pi is uniform. This can be shown using Jensen’s inequality: Let XX be the random variable which equals πi\pi_i with probability πi\pi_i. Using the fact that f(x)=log⁡(1/x)f(x) = \log(1/x) is convex, we obtain

H(π)=∑i=1rπilog⁡(1πi)=E[log⁡(1X)]≥log⁡(1E[X])=log⁡(1∑i=1rπi2)=log⁡(1q).H(\pi) = \sum_{i=1}^r \pi_i \log\left(\frac{1}{\pi_i}\right) = \mathbb{E}\left[\log\left(\frac{1}{X}\right)\right] \ge\log\left(\frac{1}{\mathbb{E}[X]}\right) = \log\left(\frac{1}{\sum_{i=1}^r \pi_i^2}\right) = \log\left(\frac{1}{q}\right).

Consequently, we see that

log⁡ndH(π)≤log⁡ndlog⁡(1/q).\frac{\log n^d}{H(\pi)} \le\frac{\log n^d}{\log(1/q)}.

where equality holds if and only if π\pi is uniform. Note that since H(π)=log⁡(1/q)H(\pi) = \log(1/q) in the uniform case, the difference between these two possible thresholds only appears in the non-uniform case.

There is a qualitative transition in the behavior of the lattice at each of these values for kdk^d. If kd≥(1+ϵ)log⁡ndlog⁡(1/q)k^d \ge\frac{(1+\epsilon)\log n^d}{\log(1/q)}, then the expected number of times a randomly chosen kk-card repeats goes to 0.

Lemma 5.1. If kd≥(1+ϵ)log⁡ndlog⁡(1/q)k^d \ge\frac{(1+\epsilon)\log n^d}{\log(1/q)}, then the expected number of cards with the same coloring as a randomly chosen kk-card is o(1)o(1).

Proof. We will consider cards which overlap with the chosen card separately from the cards which do not overlap with the chosen card.

Observe that the probability that two fixed, non-overlapping cards have the same coloring is qkdq^{k^d}, since the probability two vertices have the same color is qq, and each card has kdk^d vertices. Thus, the expected number of non-overlapping cards with the same coloring as a randomly chosen card is at most ndqkdn^d q^{k^d}. This is o(1)o(1) when kd≥(1+ϵ)log⁡ndlog⁡(1/q)k^d \ge\frac{(1+\epsilon)\log n^d}{\log(1/q)} because qkd≤n−(1+ϵ)dq^{k^d} \le n^{-(1+\epsilon)d}.

Meanwhile, there are less than (2k)d(2k)^d cards which overlap the chosen card. Since each card does not overlap with the chosen card on a region of size at least kd−1k^{d-1} vertices, the probability that two fixed, overlapping cards have the same coloring is at most qkd−1q^{k^{d-1}}. Thus, the contribution of overlapping cards to the expectation is at most (2k)dqkd−1=o(1)(2k)^d q^{k^{d-1}} = o(1).

On the other hand, if (1+ϵ)log⁡ndH(π)≤kd≤(1−ϵ)log⁡ndlog⁡(1/q)\frac{(1+\epsilon)\log n^d}{H(\pi)} \le k^d \le\frac{(1-\epsilon)\log n^d}{\log(1/q)} (i.e., in between the two proposed values), then a randomly chosen card is unique with high probability, but the expected number of repeats diverges to infinity, as established by the following two lemmas.

Lemma 5.2. If kd≤(1−ϵ)log⁡ndlog⁡(1/q)k^d \le\frac{(1-\epsilon)\log n^d}{\log(1/q)}, then the expected number of cards with the same coloring as a randomly chosen card is ω(1)\omega(1).

Proof. The probability that any two fixed cards have the same coloring is at least qkdq^{k^d} (including cards which overlap). Therefore, the expected number of repeats is at least ndqkdn^d q^{k^d}, which tends to infinity when kd≤(1−ϵ)log⁡ndlog⁡(1/q)k^d \le\frac{(1-\epsilon)\log n^d}{\log(1/q)}.

Lemma 5.3. If kd≥(1+ϵ)log⁡ndH(π)k^d \ge\frac{(1+\epsilon)\log n^d}{H(\pi)}, then a randomly chosen card is unique with high probability.

Proof. Fix δ=ϵ/2\delta= \epsilon/2. Let X=(X1,…,Xr)X = (X_1, \ldots, X_r), where XiX_i is the number of vertices of color ii. We use the law of total probability, conditioning on XX. Furthermore, we divide the sum into two parts depending on whether the card is δ\delta-typical, in the sense of the event EδE_\delta defined in (6). Let AA be the event that a randomly chosen card is unique. Then,

P(A)=∑x∈EδP(A∣X=x)P(X=x)+P(A∩{X≠Eδ})=∑x∈EδP(A∣X=x)P(X=x)+o(1)\begin{aligned} \mathbb{P}(A) = \sum_{x \in E_\delta} \mathbb{P}(A \mid X = x)\mathbb{P}(X = x) + \mathbb{P}(A \cap\{X \ne E_\delta\}) \\ &= \sum_{x \in E_\delta} \mathbb{P}(A \mid X = x)\mathbb{P}(X = x) + o(1) \end{aligned}

because EδE_\delta occurs with high probability. Therefore, it is sufficient to show that P(A∣X=x)=1−o(1)\mathbb{P}(A \mid X = x) = 1 - o(1) when x∈Eδx \in E_\delta (i.e. that a random typical card is unique with high probability).

Recall that the probability that any given card has color count xx equals ∏i=1rπixi\prod_{i=1}^r \pi_i^{x_i}. Under the event EδE_\delta, we have

∏i=1rπixi≤(∏i=1rπi(1−δ)πi)kd\prod_{i=1}^r \pi_i^{x_i} \le\left(\prod_{i=1}^r \pi_i^{(1-\delta)\pi_i}\right)^{k^d}

Then, taking a union bound over all ndn^d cards in the deck, we obtain

P(A∣X=x)≥1−nd(∏i=1rπi(1−δ)πi)kd.\mathbb{P}(A \mid X = x) \ge1 - n^d \left(\prod_{i=1}^r \pi_i^{(1-\delta)\pi_i}\right)^{k^d}.

We want to show this probability goes to 1. Therefore, it is sufficient to show that

log⁡(nd)+kd∑i=1r(1−δ)πilog⁡πi→−∞.\log(n^d) + k^d \sum_{i=1}^r (1-\delta)\pi_i \log\pi_i \to-\infty.

Observe that when kd≥(1+ϵ)log⁡ndH(π)k^d \ge\frac{(1+\epsilon)\log n^d}{H(\pi)}, we have

log⁡(nd)+kd∑i=1r(1−δ)πilog⁡πi=log⁡(nd)−(1−δ)kdH(π)≤log⁡(nd)−(1−δ)(1+ϵ)log⁡(nd)≤log⁡(nd)−(1+ϵ/2)log⁡(nd)=(−ϵ/2)log⁡(nd)→−∞\begin{aligned} \log(n^d)+k^d\sum_{i=1}^{r}(1-\delta)\pi_i\log\pi_i &=\log(n^d)-(1-\delta)k^dH(\pi)\\ &\le\log(n^d)-(1-\delta)(1+\epsilon)\log(n^d)\\ &\le\log(n^d)-(1+\epsilon/2)\log(n^d)\\ &=(-\epsilon/2)\log(n^d)\\ &\to-\infty \end{aligned}

as desired, where the second inequality follows from δ=ϵ/2\delta=\epsilon/2.

We know that in the uniform case, if the expected number of times a randomly chosen kk-card appears goes to zero (as in Lemma 5.1) then the lattice is identifiable. We expect the same to hold in the non-uniform case as well, so we believe that the lattice should be identifiable when kd≥(1+ϵ)log⁡ndlog⁡(1/q)k^d \ge\frac{(1+\epsilon)\log n^d}{\log(1/q)}.

Meanwhile, when (1+ϵ)log⁡ndH(π)≤kd≤(1−ϵ)log⁡ndlog⁡(1/q)\frac{(1+\epsilon)\log n^d}{H(\pi)} \le k^d \le\frac{(1-\epsilon)\log n^d}{\log(1/q)}, a randomly chosen card is unique with high probability, while the expected number of repeats goes to infinity. Consequently, we have a small number of cards which repeat many times throughout the lattice. This potentially creates a barrier for reconstruction because we might have many regions, centered around these repeated cards, that look similar. This could provide opportunities to swap two cards to create a different lattice but keep the same deck. Therefore, whether the true threshold is log⁡ndH(π)\frac{\log n^d}{H(\pi)} or log⁡ndlog⁡(1/q)\frac{\log n^d}{\log(1/q)} depends on whether this barrier can be overcome to reconstruct the lattice.

Conclusion and Future Work

In this paper, we studied the problem of shotgun assembly on the non-uniform labeled lattice model. Our main contribution is establishing a sufficient condition for non-identifiability which matches the known threshold in the uniform case. This work gives rise to some natural open questions.

  1. What is the true threshold for identifiability? Is it one of the two candidates proposed in § 5?

  1. When the lattice is identifiable, what algorithm can be used to reconstruct the lattice?

References

  1. [1]Koenraad M R Audenaert. A sharp continuity estimate for the von Neumann entropy. Journal of Physics A: Mathematical and Theoretical, 40(28):8127–8136, 2007.DOI
  2. [2]Paul Balister, Béla Bollobás, and Bhargav Narayanan. Reconstructing random jigsaws. In Multiplex and Multilevel Networks. Oxford University Press, 2017.
  3. [3]Charles Bordenave, Uriel Feige, and Elchanan Mossel. Shotgun assembly of random jigsaw puzzles. Random Structures & Algorithms, 56(4):998–1015, 2020.arxiv.org/abs/1605.03086
  4. [4]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Hoboken, N.J, 2nd edition, 2006.
  5. [5]Yury Demidovich, Yaroslav Panichkin, and Maksim Zhukovskii. Reconstruction of graph colourings. arXiv preprint arXiv:2308.01671, 2023.arxiv.org/abs/2308.01671
  6. [6]Jian Ding, Yiyang Jiang, and Heng Ma. Shotgun Threshold for Sparse Erdős–Rényi Graphs. IEEE Transactions on Information Theory, 69(11):7373–7391, 2023.DOI
  7. [7]Jian Ding and Haoyu Liu. Shotgun assembly threshold for lattice labeling model. Probability Theory and Related Fields, 187:423–442, 2023.arxiv.org/abs/2205.01327
  8. [8]Martin Dyer, Alan Frieze, and Stephen Suen. The Probability of Unique Solutions of Sequencing by Hybridization. Journal of Computational Biology, 1(2):105–110, 1994.pubmed.ncbi.nlm.nih.gov/8790457
  9. [9]Julia Gaudio and Elchanan Mossel. Shotgun assembly of Erdős-Rényi random graphs. Electronic Communications in Probability, 27:1–14, 2022.DOI
  10. [10]Julia Gaudio, Miklós Z. Rácz, and Anirudh Sridhar. Average-case and smoothed analysis of graph isomorphism. The Annals of Applied Probability, 35(2):1373–1406, 2025.arxiv.org/abs/2211.16454
  11. [11]Han Huang and Konstantin Tikhomirov. Shotgun assembly of unlabeled Erdős-Rényi graphs. Probability Theory and Related Fields, 2025.DOI
  12. [12]Nathaniel Johnston. Advanced Linear and Matrix Algebra. Springer, 2021.DOI
  13. [13]Tom Johnston, Gal Kronenberg, Alexander Roberts, and Alex Scott. Shotgun assembly of random graphs. Probability Theory and Related Fields, 2025.DOI
  14. [14]Anders Martinsson. A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles. Combinatorics, Probability and Computing, 28(2):287–302, 2019.
  15. [15]Elchanan Mossel and Nathan Ross. Shotgun Assembly of Labeled Graphs. IEEE Transactions on Network Science and Engineering, 6(2):145–157, 2019.
  16. [16]Bhargav Narayanan and Corrine Yap. Reconstructing Random Pictures. Random Structures & Algorithms, 66(1), 2025.DOI
  17. [17]Rajko Nenadov, Pascal Pfister, and Angelika Steger. Unique reconstruction threshold for random jigsaw puzzles. Chicago Journal of Theoretical Computer Science, 2017.arxiv.org/abs/1605.03043
  18. [18]Sébastien Roch. Modern Discrete Probability: An Essential Toolkit. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024.
  19. [19]Daniel Soudry, Suraj Keshri, Patrick Stinson, Min-hwan Oh, Garud Iyengar, and Liam Paninski. Efficient “Shotgun” Inference of Neural Connectivity from Highly Sub-sampled Activity Data. PLOS Computational Biology, 11(10):1–30, 2015.DOI

Paper details

vlnc:W_5zx5ge8q
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents