How to prove that a dynamic programming algorithm is a monotonic function

I've written an algorithm, which is based on the Needleman-Wunsch algorithm for matching sequences of proteins. This algorithm is a dynamic programming approach, where the optimal matching of two sequences A and B, with length m and n is being calculated by first solving the same problem for the respective substrings.

Currently I'm working on a proof of optimality and one lemma I (think I) need to prove first, is that my algorithm (lets call it A) always yields a score which is higher or equal to the score, than when applying the algorithm to substrings of A and B.

These are my main problems:

• The algorithm/function has two dimensions (the "size" of the two substrings)
• Every cell value of the value matrix used in the algorithm is defined to be the maximum of some values, based on values calculated before (overlapping subproblems)

I've found some help regarding multidimensional induction in a blogpost, but I don't know how to approach the max-function.

It would be great if you could give me a hint or a topic I should read about!

das_weezul

EDIT:

Here is a simplified version of the algorithm (Lets call it MATCH). $a_m$ is the m-th symbol of string A, and $b_n$ is the n-th symbol of string B. $SIM(a_m,b_n)$ is the similarity of $a_m$ and $b_n$, which is 1 if $a_m$ and $b_n$ are equal and -1 if not:

$SIM(a_m,b_n) = \begin{cases} 1, a_m = b_n\\ -1, otherwise \end{cases}\\ MATCH(0,0) = 0\\ MATCH(0,n) = 0\\ MATCH(m,0) = 0\\ MATCH(m,n) = max \begin{cases} MATCH(m-1,n-1)+ sim(a_m,b_n)\\ MATCH(m,n-1)\\ MATCH(m-1,n) \end{cases}$

What I want to show is something like this:

$MATCH(m-i,n-j) \leq MATCH(m,n), 0 \leq i \lt m \wedge 0 \leq j \lt n$

-
Can you tell the exact mathematical statement of your problem? –  fedja Nov 11 '12 at 15:23

Isn't that obvious? $$MATCH(m,n) = max \begin{cases} (a): MATCH(m-1,n-1)+ sim(a_m,b_n)\\ (b): MATCH(m,n-1)\\ (c): MATCH(m-1,n). \end{cases}$$ Apply (b) recursively, we get \begin{align} MATCH(m,n) &\ge MATCH(m,n-1)\\ &\ge MATCH(m,n-2)\\ &\ge \ldots\\ &\ge MATCH(m,n-j). \end{align} Now apply (c) recursively and get \begin{align} MATCH(m,n-j) &\ge MATCH(m-1,n-j)\\ &\ge MATCH(m-2,n-j)\\ &\ge \ldots\\ &\ge MATCH(m-i,n-j). \end{align} Put this two sequences of inequalities together, we obtain $$MATCH(m,n)\ge MATCH(m-i,n-j).$$ In other words, you first traverse from the node $(m,n)$ horizontally to the left until you reach $(m,n-j)$, then traverse vertically down to the node $(m-i,n-j)$. By the defintion of the $MATCH$ function, the value of the node will decreases along this path.

-
I agree, by looking at the function, one concludes that the progression ought to be monotonic. But by writing $MATCH(m,n) \leq MATCH(m,n-1)$ you have not proved yet why $MATCH(m,n-1)$ must be smaller or equal than $MATCH(m,n)$. Or am I missing something? I'm really not that experienced when it comes to proofs, so bear with me ;) –  das_weezul Nov 15 '12 at 17:15
@das_weezul Maybe I am the one who is missing something. I thought $MATCH(m,n)\ge MATCH(m,n-1)$ is part of the definition of the function $MATCH$, am I correct? $MATCH(m,n)$, by defintion, is the maximum of three quantities a, b, c, with $b=MATCH(m,n-1)$. And the maximum of three numbers is necessarily greater than or equal to every one of them. So, $MATCH(m,n)\equiv\max\{a,b,c\}\ge b=MATCH(m,n-1)$. –  user1551 Nov 15 '12 at 17:57
Yes, that is the definition, but what is still bugging me is that in the case of $MATCH(m-1,n-1) + sim(a_m,b_n)$ the expression $sim(a_m,b_n)$ could be negative, but the whole expression could still be greater than the other options. In this case it could be that $MATCH(m,n) \lt MATCH(m-1,n-1)$. I mean that will never be the case, but I don't know how to prove that. –  das_weezul Nov 15 '12 at 18:47
@das_weezul No, it doesn't matter if $sim(a_m,b_n)<0$ or not. To illustrate, let us say $m=n=i=j=1$ and $sim(a_m,b_n)=-1$. Now $a=MATCH(m-1,n-1)+sim(a_m,b_n)=-1$, $b=MATCH(m,n-1)=0$ and $c=MATCH(m-1,n)=0$. Then $MATCH(m,n)=\max\{a,b,c\}=\max\{0,-1,0\}=0$. So we still have $MATCH(m,n)\ge MATCH(m-1,n-1)$. –  user1551 Nov 15 '12 at 20:47
@user1151 You got me wrong. Let's say $MATCH(m-1,n-1) = 2$, $sim(a_m,b_n) = -1$, and the other cases are like you stated them. Then $MATCH(m-1,n-1)+sim(a_m,b_n) = 1$ and $max(1,0,0) = 1$ and therefore we found a counterexample because that means $MATCH(m-1,n-1) \gt MATCH(m,n)$. Again, by thinking through the recursion bottom up, I know that this can never happen, but I just cannot show it using my formula. –  das_weezul Nov 15 '12 at 21:05

user1151 showed a lot of patience and pushed me into the right direction, so this answer is just for the sake of completeness. Here is the proof I'm using now, feel free to add comments on how to improve it!

Lemma (Monotonicity)

$MATCH(m,n) \geq MATCH(m-1,n-1), 0 \lt i \leq m \wedge 0 \lt j \leq n$

Proof

Case 2 max

Per definition: $MATCH(m,n) = MATCH(m-1,n)$

Case 3 max

Per definition: $MATCH(m,n) = MATCH(m,n-1)$

Case 1 ($a_m \equiv b_n \Rightarrow SIM(a_m,b_n) = 1$) max

$MATCH(m,n) = MATCH(m-1,n-1) + 1 \Rightarrow MATCH(m,n) \gt MATCH(m-1,n-1)$

Case 1 ($a_m \neq b_n \Rightarrow SIM(a_m,b_n) = -1$) max

$MATCH(m,n) = MATCH(m-1,n-1) - 1 \\$

$\Rightarrow MATCH(m-1,n-1) -1 \geq MATCH(m-1,n) \\ \wedge MATCH(m-1,n-1) -1 \geq MATCH(m,n-1)$

$\Rightarrow MATCH(m-1,n-1) \gt MATCH(m-1,n) \\ \wedge MATCH(m-1,n-1) \gt MATCH(m,n-1) \\$

$MATCH(m-1,n) \lt MATCH(m-1,n-1) \\ \Rightarrow\Leftarrow MATCH(m-1,n) = MATCH(m-1,n-1)$ (Contradiction to Case 2 max)

$MATCH(m,n-1) \lt MATCH(m-1,n-1) \\ \Rightarrow\Leftarrow MATCH(m,n-1) = MATCH(m-1,n-1)\\$ (Contradiction to Case 3 max)

Q.E.D

The last part of the proof shows that the algorithm will never match two different symbols.

-