Two nights ago, an astronomer took a picture of a small portion of the sky containing 10,000
stars. Last night, the astronomer took a picture of the same portion of sky (containing the same
10,000 stars). The stars have all moved, and by measuring the distance they have moved the
astronomer can estimate their speed.
Unfortunately, it’s not quite that easy. Because the astronomer does not know the speed (or
direction of motion) of the stars beforehand, all she sees are two pictures with 10,000 dots on
them. There is no way for her to be sure which dot in the second picture is the same star as a
certain dot in the first picture!
Although the astronomer can’t be sure which dot is which, she can make some educated
guesses. Based on the size and brightness of each dot, she can estimate the probability pij that
star i in the first picture is the same as star j in the second picture. (Assume that all
probabilities are independent.) Using these probabilities, she would like to make her best guess
as to which star is which.
a. Draw this scenario as a network problem.
b. Specify the costs on each arc. (Hint: Remember from your probability classes that the
joint probability is the product of each probability, not the sum. One way to minimize the
product of some numbers is to minimize the sum of their logs.)
c. If it is a special type of network problem, specify what type it is.