Probabilistic setup

Figure 16: An event observation sequence with a total $20$ shadows in its life cycle. The field of view observations are not marked.

For the probabilistic case, we ran a simulation with the observation sequence in Fig. 16. The sequence contains $14$ component event observations. We also included $32$ FOV events scattered along the sequence, which are not marked in the figure. Shadows $1, 2, 3, 11, 13, 16, 20$ are associated with $10, 7, 8, 9, 6, 9, 4$ targets (with probability $1$ ), respectively. For performance measures, we look at the time for one run of the algorithm to complete, as well as the expectation (mean and standard deviation for randomized methods) of targets in individual shadows at the end ( $s_{17}, s_{18}$ , and $s_{19}$ ). When we randomly pick entries to keep, the time result is averaged over $10$ runs and the accuracy is given in the form of mean and standard deviation. In our implementation, we also make the following choices: 1) for random truncation, the entries are kept based on its probability multiplied with a random number in $(0, 1)$ , 2) for event lookahead, we will not truncate the entries if there is a disappear event within the next four events or a merge event within the next two events. The outcome is summarized in Table VI. The heuristics basic truncation, random truncation, and random truncation with event lookahead are shortened as TR, RT, and RT-LA, respectively. The number following the method is the number of entries kept. By frequent failure, we mean that more than $1/3$ of the times the heuristic fails to give a valid result. These are indicative of minimum number of entries needed for the method to work.

Table VI:

heuristic	$s_{17}$	$s_{18}$	$s_{19}$	t(s)
none, precise	$11.12$	$5.84$	$5.60$	329.5
TR-10000	failure
TR-20000	$10.67$	$4.85$	$5.33$	6.1
TR-50000	$11.00$	$5.38$	$5.52$	15.5
TR-100000	$10.96$	$5.59$	$5.53$	29.4
TR-200000	$11.06$	$5.73$	$5.56$	61.4
RT-10000	frequent failure
RT-20000	$11.38(0.20)$	$5.31(0.23)$	$5.67(0.20)$	6.1
RT-50000	$11.16(0.02)$	$5.36(0.03)$	$5.64(0.02)$	14.6
RT-100000	$11.03(0.01)$	$5.62(0.01)$	$5.56(0.01)$	28.3
RT-LA-2000	frequent failure
RT-LA-5000	$11.32(1.30)$	$6.54(1.46)$	$5.28(1.28)$	2.0
RT-LA-10000	$11.17(0.56)$	$5.87(0.91)$	$5.02(0.48)$	4.2
RT-LA-20000	$11.62(0.26)$	$5.30(0.18)$	$5.57(0.16)$	8.3
RT-LA-50000	$11.32(0.01)$	$5.51(0.01)$	$5.60(0.01)$	17.7
Monte Carlo	$11.16$	$5.58$	$5.57$	42.1

The result shows that when no heuristic is used, the algorithm takes much more time to finish. This is not surprising since the time complexity is induced by the space requirement for storing the probability mass entries. On the other hand, all of the truncation heuristics work reasonably well, with the randomized truncation plus event lookahead greatly reduces the number of entries to retain. The RT-LA-50000 run compares well with the TR-100000 run on accuracy, but uses one third less time. We expect the advantage to become more obvious as more targets are present in the system. The final target distribution from one RT-100000 run is given in figure 17.

Figure 17: Probability masses after a RT-100000 run. Note: The origin is shifted for better display.

For a second test, we change the number of targets in shadows $1, 2, 3, 13, 16, 20$ to $25, 22, 23, 8, 15, 9$ , while leaving other observations unchanged. With the increased number of targets, the basic algorithm runs out of memory after $10$ minutes, before the third split is completed. At the peak of its memory usage during the failed run, there are more than $2\times 10^7$ probability mass entries. On the other hand, it is not a problem for the the randomized methods: Both RT-100000 RT-LA-50000 yield good results compared to Monte Carlo trials, with similar running time. The result is summarized in Table VII.

Table VII:

Heuristic	$s_{17}$	$s_{18}$	$s_{19}$	t(s)
none, exact	out of memory after $10$ mins
Monte Carlo	$18.26$	$22.25$	$11.85$	43.2
RT-100000	$17.78$	$21.83$	$12.34$	66.3
RT-LA-50000	$18.24(0.08)$	$21.99(0.07)$	$12.57(0.07)$	40.6

Comprehensive performance analysis of probabilistic algorithm is hard since the performance depends on external factors such as the implementation of the specific split rule, random number generator, and so on. Nevertheless, for completeness, we discuss the performance at a higher level. To avoid the issue of external factors, we assume that at each step, each probability mass takes constant time to process. Unlike the nondeterministic case, running time of the $PROCESS\_PROBABILITY\_MASS$ algorithm may depend heavily on the number of targets in the system via the split rule. If there are $n$ split events with an average number of targets in the originating shadow being $p$ and also $n_f$ FOV events, with the reasonable additional assumption that merge, appear, and disappear events are on the same order as split events, the $PROCESS\_PROBABILITY\_MASS$ algorithm can take time $O(p^{n}3^{n_f})$ . The running time of the resampling based algorithms has a big constant depending on the number of entries to keep, but otherwise depends only linearly on the number of critical events.