Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit

This paper establishes that for Bayesian inference of planted matchings between correlated 1D point sets under critical scaling, the posterior distribution admits a local approximation with a well-defined infinite-volume limit in the partial matching case, whereas the exact matching case requires global sorting and a flow-based indexing to define its asymptotic marginal statistics.

The Gist

Imagine you are at a massive, chaotic dance party. You have two groups of people: Group X (let's call them the "Dancers") and Group Y (the "Partners").

In a perfect world, every Dancer has exactly one Partner, and they are standing right next to each other. But in this paper's scenario, the music is loud, the lights are dim, and the floor is crowded. The partners are close, but not perfectly aligned. Some people might be missing from the list entirely (in the "partial" version of the problem).

Your goal is to figure out: "Who is dancing with whom?"

This is the Planted Matching problem. The "Planted" part means there is a true, hidden truth (the real couples), but you only see the blurry, noisy positions of everyone on the dance floor.

The paper by Fan, Wee, and Yang asks two big questions about how to solve this puzzle using Bayesian Inference (a fancy way of saying "using probability to guess the truth based on evidence"):

1. The Local Question: Can I figure out who a specific dancer is paired with just by looking at the few people standing right next to them? Or do I need to see the entire dance floor to make a good guess?
2. The Infinite Question: If the dance floor keeps getting bigger and bigger (infinite size), does the pattern of our guesses settle down into a predictable, stable rule?

Here is the breakdown of their findings, using simple analogies.

---

1. The Two Scenarios: The "Perfect" vs. The "Messy" Party

The authors study two versions of this party:

• Scenario A: The Exact Matching (The Perfect Party)

  • The Rule: Every single person in Group X must be paired with exactly one person in Group Y. No one is left out.
  • The Problem: Because everyone must be paired, the choices are tightly linked. If Person A takes Partner B, then Person C cannot take Partner B. This creates a "chain reaction" across the whole room.
  • The Finding: You cannot just look at the neighbors to solve this. The decisions are too interconnected.
  • The Solution: To guess correctly, you first have to do a Global Sort. Imagine lining up all the Dancers from left to right and all the Partners from left to right. Once you know that "The 5th person on the left is the 5th person on the right," you can then zoom in and look at the local neighborhood to make fine-tuned guesses.
  • The Metaphor: It's like trying to match socks in a dark laundry room. If you know the socks are sorted by color and size, you can just look at the pile next to you. But if they are mixed up, you have to scan the whole room to know which sock belongs to which pair.

• Scenario B: The Partial Matching (The Messy Party)

  • The Rule: Some people might be missing. Maybe a Dancer has no Partner, or a Partner has no Dancer.
  • The Problem: Because people can be "unmatched," the chain reaction is broken. If Person A takes Partner B, it doesn't force Person C to do anything specific; Person C might just be single.
  • The Finding: Here, the "chain reaction" dies out quickly. The decision for Person A has almost no effect on Person Z who is standing far away.
  • The Solution: You can solve this using a Local Algorithm. You just look at the small circle of people around you, calculate the probabilities, and you are done. You don't need to see the whole room.
  • The Metaphor: It's like a game of "Hot Potato." In the messy party, the potato (the decision) gets dropped quickly. In the perfect party, the potato is passed all the way around the circle before anyone can stop.

2. The "Flow" Concept (The Hidden River)

For the "Perfect Party" (Exact Matching), the authors introduce a concept called Flow.

Imagine the dance floor is a river. In the "Perfect" scenario, the number of people crossing a specific line from left to right must equal the number crossing from right to left. This creates a conserved "Flow."

• Why it matters: Even if you look at a tiny local area, you can't be sure of the matching unless you know the "Flow" of the whole river. Is the river flowing fast? Is it stagnant? This global property (the Flow) dictates the local behavior.
• The "Flow" Obstruction: This is why you can't just look locally in the Exact Matching model. The local area is "stuck" in a specific state determined by the global river flow.

In the "Messy Party" (Partial Matching), people can drop out of the river. The flow isn't conserved. The river can change speed or direction locally without breaking the whole system. This is why local guesses work there.

3. The Infinite Limit (The Never-Ending Party)

The second big question was: "If the party goes on forever, do our guesses become predictable?"

• The Answer: Yes.
• How: As the number of people ($n$) goes to infinity, the chaotic dance floor starts to look like a Poisson Point Process.
  • Analogy: Imagine sprinkling sand on a table. At first, it looks random and clumpy. But if you zoom out far enough, the sand looks like a smooth, uniform texture with a specific density.
• The Result: The authors proved that the "guessing rules" (the posterior probabilities) settle down into a stable, mathematical limit.
  • For the Messy Party, this limit is a simple, local rule.
  • For the Perfect Party, this limit is a local rule plus a specific "Flow" value (usually zero flow relative to the true matching).

Summary of the "Takeaway"

1. If everyone must be paired (Exact Matching): You need a "Global Sort" (line everyone up) before you can make local guesses. The whole room affects the local decisions because of a conserved "Flow."
2. If people can be unmatched (Partial Matching): You can just look at your neighbors. The influence of distant people fades away quickly (Decay of Correlations).
3. In the long run: Both scenarios eventually settle into a predictable, mathematical pattern that can be described using "Infinite Volume" limits (like a perfect, endless grid of sand).

Why does this matter?
In real life, this helps us understand how to process data in fields like:

• Genomics: Matching cells from different samples.
• Image Processing: Aligning two photos of the same scene.
• Databases: Linking records of the same person across different systems.

The paper tells us: If your data is "messy" (some records missing), you can use fast, local algorithms. If your data is "perfect" (every record must match), you need to do a global sort first, or your local guesses will be wrong.

Technical Summary

Here is a detailed technical summary of the paper "Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit" by Zhou Fan, Timothy L. H. Wee, and Kaylee Y. Yang.

1. Problem Statement

The paper addresses the problem of Bayesian inference for an unknown matching (or alignment) $\pi^*$ between two correlated random point sets, $\{X_i\}_{i=1}^n$ and $\{Y_i\}_{i=1}^n$, located in $[0, 1]^d$. The points are generated under a "planted" model where $X_i = \bar{X}_{\pi^*(i)}$ and $Y_i = \bar{Y}_i$, with $(\bar{X}_i, \bar{Y}_i)$ being i.i.d. pairs.

The study focuses on the critical scaling regime where the typical distance between matched points scales as $\|\bar{Y}_i - \bar{X}_i\| \asymp n^{-1/d}$. In this regime, as $n \to \infty$, the posterior distribution does not concentrate on a single matching; instead, each point $X_i$ has non-vanishing probability of matching to multiple $Y_j$'s.

The authors investigate two fundamental questions in the limit $n \to \infty$ (specifically for dimension $d=1$):

1. Algorithmic: Can the posterior marginals (the probability that $X_i$ matches to $Y_j$) be approximated efficiently by a local algorithm that only observes a neighborhood of $O(1)$ points around $X_i$?
2. Statistical: Do the empirical distributions of these posterior marginals converge to a well-defined infinite-volume limit?

The authors analyze two distinct models:

• Exact Matching: All points are observed, and the goal is to find a bijection $\pi: [n] \to [n]$.
• Partial Matching: A fraction of points may be missing (unobserved), and the goal is to find a partial bijection.

2. Methodology and Models

Data Model

The joint density of a pair $(\bar{X}, \bar{Y})$ is defined as:
$$p_n(x, y) \propto \sqrt{\Lambda(x)\Lambda(y)} \exp\left(-V(n^{1/d}(x-y))\right)$$
where $\Lambda$ is a density on $[0,1]^d$ and $V$ is a symmetric noise potential. The scaling $n^{1/d}$ ensures the noise is of order $n^{-1/d}$.

The Two Models

1. Exact Matching Model:
   • Observations: Complete sets $X$ and $Y$.
   • Prior: Uniform over all permutations $S_n$.
   • Posterior: Gibbs measure with Hamiltonian $H(\pi) = \sum V(n^{1/d}(X_i - Y_{\pi(i)}))$.
2. Partial Matching Model:
   • Observations: Subsets of $X$ and $Y$ are observed independently with probability $p$.
   • Prior: Uniform over partial bijections.
   • Posterior: Gibbs measure with a modified Hamiltonian that includes "unmatched" terms (penalizing points left unmatched).

Key Technical Tools

• Local Approximation Algorithms: The authors propose algorithms that restrict the Gibbs measure to a local window of size $O(n^{-1})$ around each point.
  • For Partial Matching, the algorithm simply computes the posterior within a spatial window.
  • For Exact Matching, the algorithm first performs a global sorting of $X$ and $Y$, then computes the local posterior over permutations of the sorted indices within a window.
• Correlation Decay: The proofs rely on establishing that correlations between the matching decisions of distant points decay exponentially. This is analyzed using boundary variables (flow of edges crossing a cut) and coupling arguments.
• Infinite-Volume Limits: The authors define limiting point processes (Poisson Point Processes) on $\mathbb{R}$ and characterize the limiting posterior as a Gibbs measure on these infinite sets.
• Flow Concept (Exact Matching): A crucial concept introduced for the exact matching case is the flow of a permutation relative to the planted matching. It measures the net number of edges crossing a cut in the sorted index space.

3. Key Contributions and Results

A. Partial Matching Results

For the partial matching model in $d=1$:

1. Local Approximation: The posterior marginals can be accurately approximated by a purely local algorithm (Algorithm 1) that ignores global information. The Total Variation (TV) error between the true marginal and the local approximation vanishes as the window size increases.
2. Correlation Decay: The system exhibits decay of correlations. The influence of boundary conditions on the local posterior decays exponentially with distance.
3. Infinite-Volume Limit: The empirical distribution of the posterior marginals converges weakly to a limit defined over a coupled Poisson Point Process (PPP). This limit is unique and does not depend on global constraints.

B. Exact Matching Results

For the exact matching model in $d=1$, the results are more nuanced due to the global constraint of bijectivity:

1. Necessity of Global Sorting: A naive local algorithm (matching nearest neighbors without sorting) fails to approximate the posterior. The authors prove that a global sorting step is required. The local algorithm (Algorithm 2) must compute the posterior over permutations of sorted indices within a window.
2. Incomplete Correlation Decay: Unlike the partial case, the exact matching Gibbs measure does not exhibit full decay of correlations in the infinite-volume limit. Instead, it possesses a conserved quantity called flow.
   • The set of extremal infinite-volume Gibbs measures is indexed by an integer $k$ (the flow).
   • The planted matching $\pi^*$ has a specific flow (defined as 0 relative to itself).
   • The posterior concentrates on matchings with zero flow relative to $\pi^*$.
3. Infinite-Volume Limit: The empirical distribution of marginals converges to a limit defined over the PPP, but this limit is conditioned on the flow being zero. The authors provide a rigorous construction of this limit using the flow concept.

C. Technical Proofs

• Mean Potential Bounds: The authors establish bounds on the expected energy (potential) of the posterior to ensure stability.
• Regularity of Point Processes: They prove that the point processes are "regular" (points are not too clustered or sparse) with high probability, which is essential for defining local windows.
• Coupling and Correlation Decay: Using a coupling argument (similar to [8]), they show that two independent posterior samples can be coupled to agree on local marginals if the boundary conditions (flow) are fixed to be empty in a sufficiently large window.

4. Significance and Implications

• Algorithmic Feasibility of Uncertainty Quantification: The paper demonstrates that while finding the exact MAP matching in this critical regime is computationally hard (related to the assignment problem), computing the posterior marginals (uncertainty quantification) is feasible via local algorithms, provided the correct global structure (sorting) is accounted for in the exact case.
• Phase Transitions in Matching: The work highlights a fundamental difference between partial and exact matching in the critical regime. The global bijectivity constraint in exact matching introduces a "long-range" order (flow) that prevents simple local decay of correlations, whereas the partial model behaves like a standard local Gibbs measure.
• Infinite-Volume Theory: The paper provides a rigorous characterization of the infinite-volume limit for spatial random permutations, extending previous work on Bose-Einstein condensates and spatial permutations to non-convex potentials and two distinct point sets.
• Open Questions: The authors leave the extension to dimensions $d \ge 2$ as an open problem. In higher dimensions, the concept of "sorting" does not exist, and the boundary variables form a Markov Random Field rather than a Markov Chain, potentially leading to new phase transition phenomena.

Summary

This paper resolves the theoretical feasibility of Bayesian inference for planted matchings in the critical scaling regime. It establishes that local algorithms work for partial matching but require global sorting for exact matching due to a conserved flow variable that obstructs correlation decay. The results provide a rigorous foundation for understanding the statistical properties of uncertainty in high-dimensional alignment problems.