The Yule Walker Equations for the AR Coefficients

1 The Yule Walker Equations for the AR Coefficients Gidon Eshel If you assume a given zero-mean discrete timeseries {xi }N 1 is an AR process, you will naturally want to estimate the appropriate order p of the AR(p), xi+1 = 1 xi + 2 xi 1 + + p xi p+1 + i+1 (1). and the corresponding coefficients { j }. There are (at least) 2 methods, and those are described in this section. 1 Direct Inversion The first possibility is to form a set of direct inversions, p=1. With xi+1 = 1 xi + i+1 , one can form the over-determined system .. x2 . x1 .. x3 .. x2 . =.. 1.. xN xN 1. | {z } | {z }. b A. which can be readily solve using the usual least-squares estimator PN 1. i=1 xi xi+1 c1. 1. 1 = AT A T.. A b= PN 1 2 = = r1. i=1 xi co where ci and ri are the ith autocovariance and autocorrelation coefficients, respec- tively. 1. p=2. With xi+1 = 1 xi + 2 xi 1 + i+1 , start by forming the over-determined system .. x3 . x2 . x1 .. x4.

2 X3 . x2. 1. =.. | {z2 }.. xN xN 1 xN 2 . | {z } | {z }. b A. Unlike the previous p = 1 case, trying to express the solution 1. = AT A AT b . analytically is not trivial. We start with 1. x2 x1.. T. 1 x2 x3 xN 1 . A A = x3 x2 . x1 x2 xN 2.. xN 1 xN 2. 1. N 1 2 PN 1. P. i=2 xi i=2 x x i i 1 . = .. N 1 PN 2 2. P . i=2 xi xi 1i=1 x i N 2 2 PN 1. P . i=1 xi i=2 x x i i 1 . 1 . = PN 1 2 PN 2 2 PN 1 PN 1.. i=2 xi i=1 xi i=2 xi xi 1 i=2 xi xi 1 P 1 PN 1 2. N.. i=2 xi xi 1 i=2 x i Next, let's use the fact that the timeseries is stationary, so that autocovariance elements are a function of the lag only, not the exact time limits. In this case, . 1 1 co c1. AT A.. = 2 , co c21 c1 co . 1 1 co c1. AT A.. = 2 2. , co (1 r1 ) c1 co .. T. 1 1 ro r1. A A = 2.. co (1 r1 ) r1 ro 2. Similarly, . x3 P. N.. i=3 xi xi 1.. x2 x3 xN 1 x4 . AT b = .. = . x1 x2 xN 2 .. P . N. i=3 xi xi 2 , . xN. which, exploiting again the stationarity of the timeseries, becomes.

3 C1. AT b = . c2. Combining the 2 expressions, we have .. T. 1. T 1 ro r1 c1. A A A b= 2.. co (1 r1 ) r1 ro c2.. 1 1 r1 r1. = . 1 r12 r1 1 r2. Breaking this into individual components, we get r1 (1 r2 ). 1 =. 1 r12. and r2 r12. 2 =. 1 r12. Of course it is possible to continue to explore p 3 cases in this fashion. However, the algebra, while not fundamentally different from the p = 2 case, quickly becomes quite nightmarish. For example, for p = 3, .. co c1 c2 . AT A = .. c1 co c1 , .. c2 c1 co whose determinant, required for the inversion, is the cumbersome-looking c21 c2.. T 2 2 2 2 2 2. h i det A A = co co 2c1 + 2. c2 = co co + 2c1 (r2 1) c2 , co which, on pre-multiplying by the remainder matrix, yields very long expressions. Fortunately, there is a better, easier way to obtain the AR coefficient for the arbitrary p, the Yule- Walker Equations . 3. 2 The Yule- Walker Equations Consider the general AR(p). xi+1 = 1 xi + 2 xi 1 + + p xi p+1 + i+1.

4 Lag 1. multiply both sides of the model by xi , p X. xi xi+1 = ( j xi xi j+1 ) + xi i+1 , j=1. where i and j are the time and term indices, respectively, take expectance, p X. hxi xi+1 i = ( j hxi xi j+1 i) + hxi i+1 i j=1. where the { j }s are kept outside the expectance operator because they are deterministic, rather than statistical, quantities. note that hxi i+1 i = 0 because the shock (or random perturbation) of the current time is unrelated to and thus uncorrelated with previous values of the process, p X. hxi xi+1 i = ( j hxi xi j+1 i). j=1. divide through by (N 1), and use the evenness of the autocovariance, c l = cl , p X. c1 = j cj 1. j=1. divide through by co , p X. r1 = j rj 1 . j=1. 4. Lag 2. multiply by xi 1 , p X. xi 1 xi+1 = ( j xi 1 xi j+1 ) + xi 1 i+1 , j=1. take expectance, p X. hxi 1 xi+1 i = ( j hxi 1 xi j+1 i) + hxi 1 i+1 i j=1. eliminate the zero correlation forcing term p X. hxi 1 xi+1 i = ( j hxi 1 xi j+1 i).

5 J=1. divide through by (N 1), and use c l = cl , p X. c2 = j cj 2. j=1. divide through by co , p X. r2 = j rj 2 . j=1. Lag k multiply by xi k 1 , p X. xi k+1 xi+1 = ( j xi k+1 xi j+1 ) + xi k+1 i+1 , j=1. take expectance, p X. hxi k+1 xi+1 i = ( j hxi k+1 xi j+1 i) + hxi k+1 i+1 i j=1. eliminate the zero correlation forcing term p X. hxi k+1 xi+1 i = ( j hxi k+1 xi j+1 i). j=1. 5. divide through by (N 1), and use c l = cl , p X. ck = j cj k j=1. divide through by co , p X. rk = j rj k . j=1. Lag p multiply by xi p 1 , p X. xi p+1 xi+1 = ( j xi p+1 xi j+1 ) + xi p+1 i+1 , j=1. take expectance, p X. hxi p+1 xi+1 i = ( j hxi p+1 xi j+1 i) + hxi p+1 i+1 i j=1. eliminate the zero correlation forcing term p X. hxi p+1 xi+1 i = ( j hxi p+1 xi j+1 i). j=1. divide through by (N 1), and use c l = cl , p X. cp = j cj p j=1. divide through by co , p X. rp = j rj p . j=1. 6. Putting it All Together Rewriting all the Equations together yields r1 = 1 ro + 2 r1 + 3 r2 + + p 1 rp 2 + p rp 1.

6 R2 = 1 r1 + 2 ro + 3 r1 + + p 1 rp 3 + p rp 2.. rp 1 = 1 rp 2 + 2 rp 3 + 3 rp 4 + + p 1 ro + p r1. rp = 1 rp 1 + 2 rp 2 + 3 rp 3 + + p 1 r1 + p ro which can also be written as .. r 1 . ro r1 r2 rp 2 rp 1 . 1 . r2 .. r1.. ro r1 rp 3 rp 2 . 2 .. = .. rp 1 rp 2 rp 3 rp 4 ro r1 p 1.. rp rp 1 rp 2 rp 3 r1 ro p Recalling that ro = 1, the above equation is also .. r1 . 1 r1 r2 rp 2 rp 1 . 1 .. r2 .. r1 1 r1 rp 3 rp 2 . 2 .. =.. rp 1 rp 2 rp 3 rp 4 1 r1 p 1.. rp rp 1 rp 2 rp 3 r1 1 p | {z } | {z }| {z }. r R . or succinctly R = r. (2). Note that this is a well-posed system (with a square coefficients matrix R), , with the same number of constraints ( Equations , R's rows) as unknowns (the elements j of the unknown vector ). Further, R is full-rank and symmetric, so that invertability is guaranteed, = R 1 r. 3 The Yule- Walker Equations and the Partial Autocorre- lation Function Equation 2 provides a convenient recursion for computing the pacf.

7 The first step is to compute the acf up to a reasonable cutoff, say p ' N/4. Next, let r(i) denote 7. Equation 2's rhs for the p = i case. Similarly, let R(i) denote the coefficient matrix for the same case. Then loop on i, 1 i p compute R(i) and r(i). invert for (i) , . 1 . 2.. 1 . (i) = R(i) r(i) =.. i discard all j for 1 j i 1. retain i , pacf(i) = i end loop on i plot pacf(i) as a function of i. 8.