Number of states in the K-path Viterbi algorithm ------------------------------------------------ In the multitarget tracking problem, with MM measurements and K tracks, C(MM,K) is the number of ways of selecting K of the measurements, where C(MM,K) = MM!/((K!)*(MM-K)!). Each of these combinations corresponds to a state in the K-path Viterbi algorithm, i.e. C(MM,K) is the number of states. If missed target events are considered, then we may use less then K of the measurements. We assign the nonexistant measurement index MM+1 for tracks which do not use a measurement (and whose current position and velocity is therefore based soley on a Kalman filter prediction). The number of missed target events can be 0, 1, .., K. We would like to derive a formula for the number of states in this case. For example, with MM=4 and K=3, C(4,3) = 4!/(3!1!) = 4 and the measurement combinations are: 1 2 3 1 2 4 1 3 4 2 3 4 Those are the first four rows of the complete set of combinations when missed target events are included: m:1488> combos combos = 1 2 3 1 2 4 1 3 4 2 3 4 1 2 5 1 3 5 1 4 5 2 3 5 2 4 5 3 4 5 1 5 5 2 5 5 3 5 5 4 5 5 5 5 5 m:1489> sizeof(combos) ans = 15 3 m:1490> MM MM = 4 m:1491> K K = 3 The extra rows corresponding to missed target events each include one or more 5's, The actual measurement indices are 1, 2, 3, 4; so 5 does not correspond to an actual measurement and is used to indicate a missed target event. In rows 5..10 #5 occurs once, in rows 11..14 #5 occurs twice, and in row 15 #5 occurs three times. The total number of combinations, rows(combos), is: NC = C(4,3) + C(4,2) + C(4,1) + 1 = 4 + 6 + 4 + 1 = 15 Another example: m:1492> MM=5 m:1493> K=3 m:1494> setup_combos m:1495> combos combos = 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 1 2 6 1 3 6 1 4 6 1 5 6 2 3 6 2 4 6 2 5 6 3 4 6 3 5 6 4 5 6 1 6 6 2 6 6 3 6 6 4 6 6 5 6 6 6 6 6 m:1496> sizeof(combos) ans = 26 3 Here #6 is the item which is allowed to occur more than once in the combinations. The total number of rows is: NC = C(5,3) + C(5,2) + C(5,1) + 1 = 10 + 10 + 5 + 1 = 26 Another example: m:1497> K=4 m:1498> setup_combos m:1499> combos combos = 1 2 3 4 1 2 3 5 1 2 4 5 1 3 4 5 2 3 4 5 1 2 3 6 1 2 4 6 1 2 5 6 1 3 4 6 1 3 5 6 1 4 5 6 2 3 4 6 2 3 5 6 2 4 5 6 3 4 5 6 1 2 6 6 1 3 6 6 1 4 6 6 1 5 6 6 2 3 6 6 2 4 6 6 2 5 6 6 3 4 6 6 3 5 6 6 4 5 6 6 1 6 6 6 2 6 6 6 3 6 6 6 4 6 6 6 5 6 6 6 6 6 6 6 m:1500> sizeof(combos) ans = 31 4 The total number of rows is: NC = C(5,4) + C(5,3) + C(5,2) + C(5,1) + 1 = 5 + 10 + 10 + 5 + 1 = 31 Another example: m:1501> K=2 m:1502> setup_combos m:1503> combos combos = 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 1 6 2 6 3 6 4 6 5 6 6 6 m:1504> sizeof(combos) ans = 16 2 The total number of rows is: NC = C(5,2) + C(5,1) + 1 = 10 + 5 + 1 = 16 We would like to have a closed-form equation for the total number of rows. In summation form it is: NC = C(MM,K) + C(MM,K-1) + ... + C(MM,1) + 1 = sum i=0..K { C(MM,i) } where 1 <= K <= MM --- Hai Chen figured out that when K=MM the binomial theorem yields: NC = sum i=0..MM { C(MM,i) * p**i * q**(MM-i) } = (p + q)**MM = 2**MM where p = q = 1. Also, if K=MM-1 then NC = 2**MM - 1 And if MM is odd and K=(MM-1)/2, then symmetry of the binomial coefficients yields: NC = 2**MM / 2 = 2**(MM-1) Another special case of interest is K=2 for which we can reduce the summation to: NC = C(MM,2) + C(MM,1) + 1 = MM!/(2!(MM-2)!) + MM!/(MM-1)! + 1 = MM*(MM-1)/2 + MM + 1 = MM*(MM+1)/2 + 1 Having closed forms for these cases (K = 2, (MM-1)/2, MM-1, MM) may be sufficient for use in comparing the complexity of this algorithm with reduced-complexity alternatives.