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

point.

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)