Optimal action. In detector design, we are given a matrix P∈Rn×m (whose columns are probability distributions), and then design a matrix T∈Rm×n (whose columns are probability distributions), so that D=TP has large diagonal elements (and small off-diagonal elements). In this problem we study the dual problem: Given P, find a matrix S∈Rm×n (whose columns are probability distributions), so that D~=PS∈Rn×n has large diagonal elements (and small off-diagonal elements). To make the problem specific, we take the objective to be maximizing the minimum element of D~ on the diagonal.
We can interpret this problem as follows. There are n outcomes, which depend (stochastically) on which of m inputs or actions we take: Pij is the probability that outcome i occurs, given action j. Our goal is find a (randomized) strategy that, to the extent possible, causes any specified outcome to occur. The strategy is given by the matrix S: Sji is the probability that we take action j, when we want outcome i to occur. The matrix D~ gives the action error probability matrix: D~ij is the probability that outcome i occurs, when we want outcome j to occur. In particular, D~ii is the probability that outcome i occurs, when we want it to occur.
Show that this problem has a simple analytical solution. Show that (unlike the corresponding detector problem) there is always an optimal solution that is deterministic.
Hint. Show that the problem is separable in the columns of S.