Return to Question

[Hoping that this is the right Stackexchange site; inspired from a true story seen at work]

Joe has a measuring instrument and $n$ objects to be measured (say, a scale and $n$ weights). He measures each one, obtaining a list of measurements $X=\left[x_1 \dots,x_n\right] \in\mathbb R^n$.

Later on, he sends me the objects. I want to find the correspondence between each object and its respective measured value $x_i$, but Joe forgot to number the objects or to sort them in any way that allows me to find which one is the $i$-th object. I therefore measure them again with a similar instrument, obtaining a list of values $Y=\left[y_1 \dots,y_n\right] \in\mathbb R^n$.

If our instruments were perfectly accurate, then $Y$ would be a permutation of $X$. However, our instruments are not perfect; while they both have perfect trueness, they have imperfect precision. In other words, if we measure the same object many times, the average value of the repeated measurements tends to the true value, but the results have (known) standard deviations $\sigma_J$ and $\sigma_I$ (for Joe's instrument and for mine, respectively). Therefore, the values in $X$ will in general be different from the values in $Y$.

In the limiting case where all values are distinct from each other (that is, $\displaystyle\min_{x_i,x_j\in X}\{|x_i-x_j|\}\gg\sigma_J$ and similarly $\displaystyle\min_{y_i,y_j\in Y}\{|y_i-y_j|\}\gg\sigma_I$), finding the correct permutation (that is, the correspondence between a value in $X$ and the corresponding value in $Y$) is trivial. When this is not the case, however, how would one go to find the most likely permutation from $X$ to $Y$ from the data available?

Bonus questions: does the answer change if I no longer assume perfect trueness? Is the case $\sigma_J=\sigma_I$ easier?

EDIT Forgot to ask: how do I compute the probability of a given permutation, that is, the probability that it is the correct one among the space of $n!$ possible permutations? Is there a simple (preferably closed-form) expression for the probability of the optimal permutation (which appears to be the one corresponding to sorting both vectors, see whuber's solution below - at least if the errors are normally distributed)?

[Hoping that this is the right Stackexchange site; inspired from a true story seen at work]

Joe has a measuring instrument and $n$ objects to be measured (say, a scale and $n$ weights). He measures each one, obtaining a list of measurements $X=\left[x_1 \dots,x_n\right] \in\mathbb R^n$.

Later on, he sends me the objects. I want to find the correspondence between each object and its respective measured value $x_i$, but Joe forgot to number the objects or to sort them in any way that allows me to find which one is the $i$-th object. I therefore measure them again with a similar instrument, obtaining a list of values $Y=\left[y_1 \dots,y_n\right] \in\mathbb R^n$.

If our instruments were perfectly accurate, then $Y$ would be a permutation of $X$. However, our instruments are not perfect; while they both have perfect trueness, they have imperfect precision. In other words, if we measure the same object many times, the average value of the repeated measurements tends to the true value, but the results have (known) standard deviations $\sigma_J$ and $\sigma_I$ (for Joe's instrument and for mine, respectively). Therefore, the values in $X$ will in general be different from the values in $Y$.

In the limiting case where all values are distinct from each other (that is, $\displaystyle\min_{x_i,x_j\in X}\{|x_i-x_j|\}\gg\sigma_J$ and similarly $\displaystyle\min_{y_i,y_j\in Y}\{|y_i-y_j|\}\gg\sigma_I$), finding the correct permutation (that is, the correspondence between a value in $X$ and the corresponding value in $Y$) is trivial. When this is not the case, however, how would one go to find the most likely permutation from $X$ to $Y$ from the data available?

Bonus questions: does the answer change if I no longer assume perfect trueness? Is the case $\sigma_J=\sigma_I$ easier?

EDIT Forgot to ask: how do I compute the probability of a given permutation, that is, the probability that it is the correct one among the space of $n!$ possible permutations? Is there a simple (preferably closed-form) expression for the probability of the optimal permutation (which appears to be the one corresponding to sorting both vectors, see whuber's solution below - at least if the errors are normally distributed)?

EDIT 2 Per Aksakal observation (see comments to the question): assume that all true weights are strictly distinct (the measurements, both for me and for Joe, can be non-distinct values due to measurement error).

[Hoping that this is the right Stackexchange site; inspired from a true story seen at work]

Joe has a measuring instrument and $n$ objects to be measured (say, a scale and $n$ weights). He measures each one, obtaining a list of measurements $X=\left[x_1 \dots,x_n\right] \in\mathbb R^n$.

Later on, he sends me the objects. I want to find the correspondence between each object and its respective measured value $x_i$, but Joe forgot to number the objects or to sort them in any way that allows me to find which one is the $i$-th object. I therefore measure them again with a similar instrument, obtaining a list of values $Y=\left[y_1 \dots,y_n\right] \in\mathbb R^n$.

If our instruments were perfectly accurate, then $Y$ would be a permutation of $X$. However, our instruments are not perfect; while they both have perfect trueness, they have imperfect precision. In other words, if we measure the same object many times, the average value of the repeated measurements tends to the true value, but the results have (known) standard deviations $\sigma_J$ and $\sigma_I$ (for Joe's instrument and for mine, respectively). Therefore, the values in $X$ will in general be different from the values in $Y$.

In the limiting case where all values are distinct from each other (that is, $\displaystyle\min_{x_i,x_j\in X}\{|x_i-x_j|\}\gg\sigma_J$ and similarly $\displaystyle\min_{y_i,y_j\in Y}\{|y_i-y_j|\}\gg\sigma_I$), finding the correct permutation (that is, the correspondence between a value in $X$ and the corresponding value in $Y$) is trivial. When this is not the case, however, how would one go to find the most likely permutation from $X$ to $Y$ from the data available?

Bonus questions: does the answer change if I no longer assume perfect trueness? Is the case $\sigma_J=\sigma_I$ easier?

EDIT Forgot to ask: how do I compute the likelihood of a given permutation? Is there a simple (preferably closed-form) expression for the likelihood of the optimal permutation (which appears to be the one corresponding to sorting both vectors, see whuber's solution below)?

[Hoping that this is the right Stackexchange site; inspired from a true story seen at work]

Joe has a measuring instrument and $n$ objects to be measured (say, a scale and $n$ weights). He measures each one, obtaining a list of measurements $X=\left[x_1 \dots,x_n\right] \in\mathbb R^n$.

Later on, he sends me the objects. I want to find the correspondence between each object and its respective measured value $x_i$, but Joe forgot to number the objects or to sort them in any way that allows me to find which one is the $i$-th object. I therefore measure them again with a similar instrument, obtaining a list of values $Y=\left[y_1 \dots,y_n\right] \in\mathbb R^n$.

If our instruments were perfectly accurate, then $Y$ would be a permutation of $X$. However, our instruments are not perfect; while they both have perfect trueness, they have imperfect precision. In other words, if we measure the same object many times, the average value of the repeated measurements tends to the true value, but the results have (known) standard deviations $\sigma_J$ and $\sigma_I$ (for Joe's instrument and for mine, respectively). Therefore, the values in $X$ will in general be different from the values in $Y$.

In the limiting case where all values are distinct from each other (that is, $\displaystyle\min_{x_i,x_j\in X}\{|x_i-x_j|\}\gg\sigma_J$ and similarly $\displaystyle\min_{y_i,y_j\in Y}\{|y_i-y_j|\}\gg\sigma_I$), finding the correct permutation (that is, the correspondence between a value in $X$ and the corresponding value in $Y$) is trivial. When this is not the case, however, how would one go to find the most likely permutation from $X$ to $Y$ from the data available?

Bonus questions: does the answer change if I no longer assume perfect trueness? Is the case $\sigma_J=\sigma_I$ easier?

EDIT Forgot to ask: how do I compute the probability of a given permutation, that is, the probability that it is the correct one among the space of $n!$ possible permutations? Is there a simple (preferably closed-form) expression for the probability of the optimal permutation (which appears to be the one corresponding to sorting both vectors, see whuber's solution below - at least if the errors are normally distributed)?

[Hoping that this is the right Stackexchange site; inspired from a true story seen at work]

Joe has a measuring instrument and $n$ objects to be measured (say, a scale and $n$ weights). He measures each one, obtaining a list of measurements $X=\left[x_1 \dots,x_n\right] \in\mathbb R^n$.

Later on, he sends me the objects. I want to find the correspondence between each object and its respective measured value $x_i$, but Joe forgot to number the objects or to sort them in any way that allows me to find which one is the $i$-th object. I therefore measure them again with a similar instrument, obtaining a list of values $Y=\left[y_1 \dots,y_n\right] \in\mathbb R^n$.

If our instruments were perfectly accurate, then $Y$ would be a permutation of $X$. However, our instruments are not perfect; while they both have perfect trueness, they have imperfect precision. In other words, if we measure the same object many times, the average value of the repeated measurements tends to the true value, but the results have (known) standard deviations $\sigma_J$ and $\sigma_I$ (for Joe's instrument and for mine, respectively). Therefore, the values in $X$ will in general be different from the values in $Y$.

In the limiting case where all values are distinct from each other (that is, $\displaystyle\min_{x_i,x_j\in X}\{|x_i-x_j|\}\gg\sigma_J$ and similarly $\displaystyle\min_{y_i,y_j\in Y}\{|y_i-y_j|\}\gg\sigma_I$), finding the correct permutation (that is, the correspondence between a value in $X$ and the corresponding value in $Y$) is trivial. When this is not the case, however, how would one go to find the most likely permutation from $X$ to $Y$ from the data available?

Bonus questions: does the answer change if I no longer assume perfect trueness? Is the case $\sigma_J=\sigma_I$ easier?

[Hoping that this is the right Stackexchange site; inspired from a true story seen at work]

Joe has a measuring instrument and $n$ objects to be measured (say, a scale and $n$ weights). He measures each one, obtaining a list of measurements $X=\left[x_1 \dots,x_n\right] \in\mathbb R^n$.

Later on, he sends me the objects. I want to find the correspondence between each object and its respective measured value $x_i$, but Joe forgot to number the objects or to sort them in any way that allows me to find which one is the $i$-th object. I therefore measure them again with a similar instrument, obtaining a list of values $Y=\left[y_1 \dots,y_n\right] \in\mathbb R^n$.

If our instruments were perfectly accurate, then $Y$ would be a permutation of $X$. However, our instruments are not perfect; while they both have perfect trueness, they have imperfect precision. In other words, if we measure the same object many times, the average value of the repeated measurements tends to the true value, but the results have (known) standard deviations $\sigma_J$ and $\sigma_I$ (for Joe's instrument and for mine, respectively). Therefore, the values in $X$ will in general be different from the values in $Y$.

In the limiting case where all values are distinct from each other (that is, $\displaystyle\min_{x_i,x_j\in X}\{|x_i-x_j|\}\gg\sigma_J$ and similarly $\displaystyle\min_{y_i,y_j\in Y}\{|y_i-y_j|\}\gg\sigma_I$), finding the correct permutation (that is, the correspondence between a value in $X$ and the corresponding value in $Y$) is trivial. When this is not the case, however, how would one go to find the most likely permutation from $X$ to $Y$ from the data available?

Bonus questions: does the answer change if I no longer assume perfect trueness? Is the case $\sigma_J=\sigma_I$ easier?

EDIT Forgot to ask: how do I compute the likelihood of a given permutation? Is there a simple (preferably closed-form) expression for the likelihood of the optimal permutation (which appears to be the one corresponding to sorting both vectors, see whuber's solution below)?