MS&E 351 Stochastic Decision Models 14 Spring 2008
M. O'Sullivan & A. Veinott, Jr. MATLAB OVERVIEW
The CONVOLUTION C = A o B of two finite sequences A = (A(j)) and B = (B(j)) is
the sequence C = (C(k)) for which C(k) is the sum of A(k-i) * B(i) over i. If
A(a) and B(b)) are respectively the first elements of A and B, then the first
element of C is C(c) = A(a) * B(b) where c = a + b. In the sequel, the term
convolution (or true convolution) is used as just defined.
The MATLAB CONVOLUTION conv(A,B) is slightly different. MATLAB assumes that the
first elements of A and B are A(1) and B(1) respectively. Then it follows
from the above that a = b = 1 and c = a + b = 2, so the first element of C is
C(2). But MATLAB wants all sequences to have first index one. For this reason, the
MATLAB convolution conv(A,B) takes the true convolution A o B and shifts it to
the left one position so its first index is also c - 1 = a + b - 1 = 1.
CAN MATLAB DO TRUE CONVOLUTIONS A o B ? Absolutely. To explain how, it is necessary
to examine the relationship between true convolutions and MATLAB convolutions.
Suppose a true convolution C = A o B is desired. MATLAB in effect shifts the
sequence A (resp., B) to the left a-1 (resp., b-1) positions, takes the true
convolution and shifts the resulting convolution left one more position. The result
of these operations by MATLAB is to shift the true convolution to the left a-1 + b-
1 + 1 = a + b - 1 positions. Thus to obtain the true convolution from the MATLAB
convolution, it suffices to shift the MATLAB convolution back to the right a + b -
1 positions. That's all there is to it. Of course in the above discussion, shifting
k < 0 positions to the right (resp., left) is the same as shifting -k > 0 posi-
tions to the left (resp., right).
EXAMPLE. Suppose g is a storage-and-shortage cost vector with indices the interval
[-15:45] and pr is a demand probability vector with indices [5:15]. Then the true
convolution g o pr of g and pr has indices [-15+5:45+15] = [-10:60] obtained
by adding the intervals of indices for g and pr. The MATLAB convolution
conv(g,pr) instead has indices [1:71]. Thus, all that is required is to shift the
MATLAB convolution back to the right (-15 + 5 - 1) = -11 positions, i.e., to the
left 11 positions.
EXPECTED STORAGE AND SHORTAGE COST G. The expected storage-and-shortage cost vector
G is the restriction of the convolution g o pr to the interval [0:50], i.e., the
values of y for which y - D is in the domain [-15:45] for ALL values of the
demand D. The interval [0:50] is formed from [-15:45] by adding the maximum
demand 15 to the left end point and adding the minimum demand 5 to the right end
Why isn't G equal to the convolution on the entire interval [-10,60]? The answer
is that the convolution does not correctly calculate G outside of the interval
[0:50] because the domain of g is restricted so that not all demands are
accounted for outside that interval. For example, the value (g o pr)(-10) of
g o pr at -10 is
(g o pr)(-10) = g(-10-5) * pr(5)
and is not equal to G(-10) because the former includes the contribution of the
demand equal to 5, but not any other values. To extend the definition of G(y) to
y < 0, it would be necessary to extend the domain of definition of g to include
the values g(y - 5),...,g(y - 15).
Here are two applications. First define the following in MATLAB. In each case the
"M" is appended to a symbol to indicate that it is the MATLAB version thereof.
GM = conv(g,pr)
Y = [0:50]
YM = Y + 11
G = GM(YM)
* PLOT G ON Y. Use the MATLAB function plot(Y,G)