Consider doing inference in an m x n lattice Bayes net, as shown in Figure S13.43. The network consists of mn binary variables V_i,j , and you have observed that V_m,n = _+vm,n.

You wish to calculate P(V_1,1 | + _vm,n) using variable elimination. To maximize computational efficiency, you wish to use a variable elimination ordering for which the size of the largest generated factor is as small as possible. 

a. First consider the special case where m = 4 and n = 5. What is the optimal elimination order? 

b. Now consider the general case (assume m > 2 and n > 2). What is the size of the largest factor generated under the most efficient elimination ordering?

Figure S13.43

V1.1 V2,1 : Vm,1 V12 V22 : Vm.2 V1,3 V2.3 Vm,3 V1.n V2.n : Vm.n