Probability of matching a set of modules. Example cases as for Figure 4, but note change in numbering (positions are now relative to the first position that the module can occupy under any circumstance, rather than relative to the first position that it can occupy relative to the positions of the other modules in the current case). The top line in each set shows the left-most position each module can take (given a particular state of the first module), and hence, the left-most possible match for each module. The position of the left-most match for the first module determines the size of the problem to solve for the remaining modules (in one fewer dimension). Pn is the probability of a match in the nth module; Qn = (1 − Pn). For m = 1 (top), the probability of a match at the ith position is P1Q1(i − 1). For m = 2 (middle), the probabilities for the first module remain the same; however, depending on the position, a different size subproblem must be solved in one dimension to find the probability that the second module also matched. Similarly, for m = 3 (bottom), the position of the left-most match of the first module determines the size of the two-dimensional subproblem that needs to be solved to find the probability that all three modules matched. In general, to solve for m modules, it is necessary to solve all smaller problems in (m − 1) dimensions, and to weight each of these solutions by the probability that the first module matched in a position compatible with it. The diagrams to the right show the probabilities of each of the allowed combinations of positions (order the same as the ordering of the lines to the left); to find the probability that a particular combination was the left-most set of matches (e.g., first module at its second position, second module at its second position, third module at its fourth position), multiply the individual terms together (here, P1Q1 × P2 × P3Q32, as can be seen either by examining the individual line corresponding to this case or by examining the relevant cell in the table). Arrows show the correspondence of terms in lower dimensions as parts of higher dimensional problems.
