尋找最可能的排列
[希望這是正確的 Stackexchange 站點；靈感來自工作中看到的真實故事]
喬有一個測量儀器和 $ n $ 要測量的對象（例如，一個刻度和 $ n $ 權重）。他測量每一個，得到一個測量列表 $ X=\left[x_1 \dots,x_n\right] \in\mathbb R^n $ .
後來，他把物品寄給我。我想找到每個對象與其各自測量值之間的對應關係 $ x_i $ ，但喬忘記給物品編號或以任何能讓我找到哪個是 $ i $ -th 對象。因此，我用類似的儀器再次測量它們，獲得一個值列表 $ Y=\left[y_1 \dots,y_n\right] \in\mathbb R^n $ .
如果我們的儀器完全準確，那麼 $ Y $ 將是一個排列 $ X $ . 然而，我們的儀器並不完美。雖然它們都具有完美的真實性，但它們卻具有不完美的精確度。換句話說，如果我們多次測量同一個物體，重複測量的平均值趨於真實值，但結果有（已知的）標準偏差 $ \sigma_J $ 和 $ \sigma_I $ （分別用於 Joe 的樂器和我的樂器）。因此，在 $ X $ 通常將不同於中的值 $ Y $ .
在所有值彼此不同的極限情況下（即， $ \displaystyle\min_{x_i,x_j\in X}{|x_i-x_j|}\gg\sigma_J $ 同樣地 $ \displaystyle\min_{y_i,y_j\in Y}{|y_i-y_j|}\gg\sigma_I $ ），找到正確的排列（即，一個值之間的對應關係 $ X $ 和相應的值 $ Y $ ) 是微不足道的。但是，如果不是這種情況，如何從 $ X $ 到 $ Y $ 從現有數據？
額外問題：如果我不再假設完全正確，答案會改變嗎？是這樣嗎 $ \sigma_J=\sigma_I $ 更輕鬆？
編輯忘了問：我如何計算給定排列的概率，即它是空間中正確排列的概率 $ n! $ 可能的排列？對於最優排列的概率是否有一個簡單的（最好是封閉形式）表達式（這似乎是對應於對兩個向量進行排序的表達式，請參見下面的 whuber 的解決方案 - 至少如果錯誤是正態分佈的）？
EDIT 2 Per Aksakal 觀察（參見問題的評論）：假設所有真實重量都是嚴格不同的（對於我和喬來說，測量值可能是由於測量誤差而導致的非明顯值）。
假設每個儀器的測量誤差是獨立的且相同的正態分佈， 則解決方案是按排序順序匹配兩組測量值。 儘管這在直觀上很明顯（問題發布後不久發布的評論說明了此解決方案），但仍有待證明。
為此，讓排序後的第一組測量為 $ x_1\le x_2\le \cdots \le x_n $ 並讓第二組測量按排序順序為 $ y_1\le y_2\le \cdots \le y_n. $ 讓誤差分佈的均值和方差為零 $ \sigma^2 $ 對於 X 儀器和 $ \tau^2 $ 對於 Y 儀器。（我發現這個符號比問題中的下標更合適。）
為了找到最可能的排列，我們解決了最大似然問題。 它的參數是 (a) $ n $ 真實重量 $ \theta_i $ 對應於每個測量的對象 $ x_i $ (b) 排列 $ s $ 這使得 $ y_{s(i)} $ 物體的第二次測量 $ i. $ 只要可能性取決於 $ (\theta) $ 和 $ s, $ 這些觀察的可能性與指數成正比
$$ \mathcal{L}(\theta,s) = -\frac{1}{2}\sum_{i=1}^n \left(\frac{x_i-\theta_i}{\sigma}\right)^2 + \left(\frac{y_{s(i)}-\theta_i}{\tau}\right)^2. $$
對於任何給定的 $ s, $ 這個表達式（因此它的指數）通過採取逐項最大化
$$ \hat\theta_i = \frac{\tau^2 x_i + \sigma^2 y_{s(i)}}{\sigma^2 + \tau^2}. $$
對於這些最佳值 $ \theta, $ 的價值 $ -2\mathcal{L} $ （我們希望最小化）是
$$ -2\mathcal{L}(\hat\theta,s) = \frac{1}{\sigma^2+\tau^2}\sum_{i=1}^n \left(x_i - y_{s(i)}\right)^2. $$
當每個平方表達式展開時，我們得到 (a) $ x_i^2, $ (b) 總和 $ y_{s(i)}^2 $ （等於總和 $ y_i^2 $ 因為 $ s $ 是一個排列），和（c）交叉項，
$$ -2\sum_{i=1}^n x_i y_{s(i)}. $$
重排不等式表明這樣的產品總和最大化（從而最大化 $ \mathcal{L}(\hat\theta, s) $ ） 當。。。的時候 $ y_{s(i)} $ 是按遞增順序排列的，QED。
該分析依賴於正態性假設。儘管可以放寬，但需要一些分佈假設，正如@fblundun 在對該問題的評論中敏銳地指出的那樣。