9, no. 1 (1966): 139–190.Ross, Stephen A. “The Arbitrage Theory of Capital Asset Pricing.” Journal of Economic Theory 13 (1976): 341–360.Jarrow, Robert and Andrew Rudd. “A Comparison of the APT and CAPM: ANote.” Journal of Banking and Finance 7, no. 3 (1983): 295–303.Grinold, Richard C. and Ronald N. Kahn, Active Portfolio Management, SecondEdition. (New York: McGraw-Hill, 1999).
CHAPTER
4
Kalman Filtering
INTRODUCTIONControl theory is a branch of engineering that deals with the control of engineering systems. The engineering systems could be from diverse domains,and the applications include controlling the power output of an automotiveengine, stabilizing the rate of rotation of an electric motor, and controllingthe “rate of reaction” (or the speed of a chemical process). The control ofthese systems is exercised by the manipulation of so-called control variables.For example, in the case of controlling the power output of an automotiveengine, the control variable could be the amount of fuel injected into the engine. This would control the thrust of the piston and therefore the poweroutput from the engine. Similarly, in the other two examples, the controlvariables could be the amount of current flowing through the motor coils orthe ambient temperature of a chemical process. Thus, the control variablesprovide a harness that helps us to control the system effectively.Prior to the proposal of Kalman filtering, the typical approach for system control involved the specification of a fully comprehensive mathematical model describing the system dynamics. The model is usually formulatedin the form of a differential equation. This helps to determine in a quantitative manner the effects of the control variables on system dynamics. Control is then effected by manipulating the variables as prescribed by themodel.Along with the preceding approach also came a painful realization of itslimitations. The mathematical models may not be 100-percent accurate, asthere may be some approximations used in the modeling process. Additionally, the instruments used to measure the system parameters may have somebuilt-in inaccuracies that could result in measurement error. To compoundthings even further, there may also be some extraneous disturbances to thesystem that cannot be anticipated and modeled in a deterministic fashion.Hence, the aforementioned methodology becomes increasingly harder toimplement as the systems grow in complexity.52
Kalman Filtering
53
It was under these circumstances that the Kalman filter was proposed byR. E. Kalman. He addressed these issues in a direct and practical manner andpresented his ideas in a ground-breaking article1 titled “A New Approach toLinear Filtering and Prediction Problems.” The approach caught the attention and imagination of the engineering community, and the ideas found application in multiple domains.One of the key contributions of Kalman’s article is the notion of systemstate,” or the current state of the system. It is represented as a vector of thecurrent values of various system parameters. The vector itself is deducedfrom a set of measurements on the system that is in turn translated intosystem-state terms. This translation is typically modeled as a linear equation.Thus, the means to make observations and the equation translating the observation into the system state fully characterize the notion of system state.Having established the notion of system state, Kalman proceeded tocast a dynamical system in terms of system states. A dynamical system inthe Kalman-filtering approach is modeled as a sequence of transitions fromone system state to another. These transitions are also modeled as linearequations.Next, he asserted that to monitor the system effectively (for purposes ofcontrol) it makes sense to make an assessment of the state that we are currently in and the state that we expect to transition to in the next time step.In other words, we are in a situation where we are constantly predicting thenext system state and taking measurements to verify the predictions. TheKalman filter provides a prescription to reconcile this sequence of predictions followed by measurements to arrive at a sequence of optimal estimatesfor system states. This approach to thinking of systems as a sequence of statetransitions was a radical departure from the thinking at the time. It starteda revolution of sorts in the field of control theory and marks the beginningof a new era in the field commonly referred to by many as Modern ControlTheory.So, how does this fit into our scheme of things? For one, we use theKalman-filtering technique to filter the noise from the observed spread in thecase of risk arbitrage. Describing this in the introduction therefore helps provide the context for its application later in the book.To help to illustrate the Kalman-filtering ideas and also as a matter ofinterest, we apply the Kalman-filtering concepts to smooth out a randomwalk. Now, many practitioners of technical analysis make use of so-calledmoving averages to smooth out or filter price series. This method of usingmoving averages may be thought of as an attempt to estimate the sequenceof stock prices (states) after filtering out the noise. The common peeve1
Kalman, R. E. ( 1960). “A New Approach to Filtering and Prediction Problems.”Transaction of the ASME Journal of Basic Engineering, 82(Series D), 35–45.
BACKGROUND MATERIAL
54
The practical nature of the modeling process and solution approachmade the Kalman filter immediately applicable to a wide variety of situations. In fact, one of the first applications of the Kalman filter wasin the lunar module of Apollo 11, the spacecraft for the first landing onthe Moon. Therefore, if anything in the book should qualify as rocketscience, this definitely fits the bill. ☺
against the moving averages has always been that they tend to lag whenthere is a sharp and sudden change in price movement. The Kalman filtercan help construct better smoothers. Although we do not delve deeply intothe matter, we believe that this approach may very well contain the seeds ofreasoning for the observation of the so-called Fibonacci retracements, whichis well documented in the area of technical analysis.
THE KALMAN FILTERContinuing on the theme of the previous section, the Kalman-filteringprocess can best be described as a three-step process of prediction, observation, and reconciliation or correction. In the prediction step, we predict thenext system state based on our knowledge of the current system state. Alongwith it, we also estimate the error in our prediction. This completes the prediction step.
Kalman Filtering
55
Next we take a reading of the state of the system after allowing for afixed amount of time to elapse, the idea being that the system would nowhave transitioned to the new state. The readings can be translated in systemstate terms based on a mathematical model. Similar to the prediction step,we also estimate the error associated with our observation. The observationalong with an estimate of the error constitutes the observation step.We now have two estimates for the states involved: one based on ourprediction and the other based on our observation. The natural next step isthen to reconcile the two state estimates, taking into account the magnitudeof the associated errors. Stating it differently, the predicted estimate is corrected based on the observation. This is therefore called the correction step.This reconciled estimate of the system state from the correction step is thefinal estimate of the current system state.The preceding process is then repeated again for the state at the nexttime instance, making the Kalman filter a recursive prediction–correctionmethod. The preceding steps are also illustrated in the form of a diagram inFigure 4.1.The reader is probably now curious as to how the correction to the predicted value is effected. Let us discuss that briefly. Note that it is possible totranslate the prediction of the next state into a set of expected observations.
Estimate ObservationError Variance
Observation StepTake Measurements
Get ReconciledState Estimate+Variance ofEstimate
Prediction StepPredict Next State
Estimate Prediction ErrorVariance
Use Reconciled State Estimate for Prediction
FIGURE 4.1
The Kalman Filtering Process.
BACKGROUND MATERIAL
56
Let us call this as the predicted observation. The equation for the correctedstate in a Kalman filter is given ascorrected State = predicted state + k (actual observation –– predicted observation)The difference between the actual observation and the predicted observation is called the observation innovation. Note that a fraction of the observation innovation is added as a correction to the predicted state. Thevalue of this fraction k is known as the Kalman gain. The Kalman-filteringapproach provides a prescription on what would be the most appropriatevalue to use for k. This value is decided such that the corrected state has theleast amount of error variance associated with it.Besides providing the prescription to reconcile the prediction and observation, Kalman also provided definitive proof that the process is indeedoptimal in the case where the mathematical models of state and observationare both linear and the errors are drawn from independent Gaussian distributions. We will, of course, not delve into the proofs, but rather try to explain the basic idea by way of illustrations. With that said, we introducesome notation and formally list the steps involved in the Kalman-filteringprocess.Let Xt denote the state at time t. Note that the value for the state canalso be a vector; that is, the state has a multidimensional representation. Themathematical model used to predict the state at time t in a Kalman filter setting is typically of the formXt = AXt–1 + ut
(4.1)
where A is a matrix, Xt and Xt–1 are the state vectors at time t and t – 1, respectively, and ut is the error vector that accounts for the impreciseness ofthe model. Next we make an observation at time t. Let us call this observation Yt. The measurements made are a linear combination of the state elements and therefore can be written asYt = HXt + vt
(4.2)
In this scenario the values of the matrices A and H are known. Initiallywe make a prediction of the state at time t, knowing all the state information up to time t – 1. Let us denote this estimate Xˆ t | t −1. The error is measuredas the variance in the case of a single dimensional state and as a covariancematrix in the case of a multidimensional state.Let us denote it generally as Pˆt | t −1. Just as in the case of the predictedvalue, the measurement also has an error variance/covariance matrix associated
Kalman Filtering
57
with it. Let us call that R. We are now ready to formally list the steps in theKalman-filtering process as follows:1. Evaluate Xˆ t | t −1 and Pˆt | t −1 using the state equation.2. Find the observation Yt and R by observing the system.3. Evaluate Kt, also known as the Kalman gain, which will be used to obtain the linear minimum error variance estimate.4. Evaluate Xˆ t | t given by Xˆ t | t −1 + Kt Yt − HXˆ t |t −1 .5. Finally, evaluate Pt, the error variance/covariance of Xˆ t | t.
(
)
These steps are repeated again for the next time step. The formulas forthe evaluations at each step are relegated to the appendix at the end of thischapter. Upon examining the equations in the appendix, one can say thatthey do seem a little cryptic, and the reasoning and rationale behind them isnot evident. In the subsequent sections we will illustrate the ideas behind theequations.
THE SCALAR KALMAN FILTERIn this section, we will discuss the estimation of the value of a constant. Letus first examine how to do it in normal course. The typical method wouldbe to take multiple measurements of the value and use the average of themeasured values as an estimate of the constant. The reasoning behind theapproach is that the measurements could have errors associated with them;that is, some measured values could be greater than the true value of theconstant, and others could be lower. By taking an average of the values, weexpect the errors to cancel each other out. More precisely, the standard deviation of the error in the average goes down by a square root of n factor,where n is the number of measurements.The consequence of this method is in fact a well-known statistical concept. By increasing the number of observations of a constant variable andtaking averages, we can make the error in our estimate of the constant assmall as desired.However, a caveat to that approach is that we will need to wait until thelast of the n measurements have been completed before coming up with anestimate of the constant (which may not be a bad idea at all). The Kalmanfilter, however, makes an estimate of the value of the constant based on thecurrent available information and updates the estimate as and when moreobservations are made. Of course, the result after n observations in bothcases will be the same.
BACKGROUND MATERIAL
58
Note that if the error variances associated with different observationsare the same, then a simple average will be fine. However, in the case wherethe observed values have different levels of accuracy, we would like to assignmore weight to the observations with greater accuracy. In such cases, insteadof taking a simple average that weights each point uniformly, a weighted average solution would be more appropriate. We will illustrate how to addressthe weighted average situation using the Kalman filter concepts and therebyhope to provide some insight to the calculation of the Kalman gain.In the estimation of the constant value, the system state is the onedimensional constant value itself. Let us say that our current estimate of theconstant value is x̂i with error in the estimate being ei, that is,xˆ i | i = x + ε i
(4.3)
x is the true value of the constant. Although we do not know what the exactvalue of ei is, we do know that it has a zero mean and known variance givenby σ ε2,i . Let us now do the prediction step. Since the value stays a constant,our prediction for the next state is the current value itself. Therefore, we have
(
)
xˆ i +1| i = xˆ i , var xˆ i +1| i = σ ε2, i
(4.4)
Next we make a measurement. Let us call the measurement of the constantvalue yi and the error associated with it hi with zero mean and known variance given as σ η2,i. Therefore at the end of the measurement step, we have theobservation
( )
yi = x + ηi , var yi = σ η2, i
(4.5)
We now have a prediction and an observation, and we wish to reconcile thetwo values. We do this in the reconciliation/correction step where we correctthe predicted value based on the observation. Writing out the correctionequation, we have
(
xˆ i +1| i +1 = xˆ i +1| i + k yi − xˆ i +1| i
)
(4.6)
Note that this can be rewritten as
(
)
xˆ i +1| i +1 = 1 − k xˆ i +1| i + kyi
(4.7)
That is, the corrected state estimate is a weighted average of the two stateestimates, with k, the Kalman gain, being the weight. The choice for the
Kalman Filtering
59
Kalman gain must be such that the error variance of the final estimatedstate is minimized. Writing out the variance for the final state estimate wehave
(
) (
) var(xˆ ) + k var(y ) = (1 − k) σ
var xˆ i +1| i +1 = 1 − k
2
2
2
i +1| i
i
22 2ε ,i + k σ η,i
(4.8)
The task is now to find the value of k that minimizes the variance. Instead of doing the derivation mathematically, we will arrive at the value ofk by analogy to some high school circuit theory. Consider the parallel circuitas shown in Figure 4.2.The fraction of current flowing into each arm of the circuit k and 1 – kis shown in Equation 4.10. According to Ohm’s law, the current flowchooses the path of least resistance, and the flow on each arm is inverselyproportional to the resistance of that arm. According to Kirchoff’s law, thesum of the current flowing through each arm of the circuit must be equal tothe total current flow I. Also, the flow of current is such that minimum energy is expended in the process. The energy of the circuit is given as
(
)
2E = I 2  1 − k Rε + k2Rη 
(4.9)
Equating Rε = σ ε2 and Rη = σ η2, it is now easy to see the similarity betweenthe two situations. The fraction of current and the Kalman gain is given ask=
I(1-k)
σ ε22σ η + σ ε2
Re
I
I.k
FIGURE 4.2
Rh
A Parallel Circuit.
(4.10)
BACKGROUND MATERIAL
60
The effective resistance of the circuit or the equivalent variance of the combination is given as
(
)
R = var xˆ i +1| i +1 =
Rε RηRε + Rη
=
σ ε2σ η2σ ε2 + σ η2
(4.11)
Having determined the value of k, we can now compute the correctedstate and the variance of the corrected state. The process is now repeatedagain for the next measurement until we reach the last of the planned nmeasurements. The final outcome of taking a weighted average after making all the measurements will work out to be the same value calculated usingthe Kalman procedure.
FILTERING THE RANDOM WALKLet us now discuss the application of the Kalman filter to the random walk.From Chapter 2, on time series, we know that a random walk series is a simple sum of white noise realizations up to the current time. In other words,the next point in the random walk series is evaluated by adding to the current point a random drawing from a Gaussian distribution. Also note thatthis has relevance to stock prices, as the logarithm of stock prices is typicallymodeled as a random walk.Now suppose we are assigned the task of watching the random walk.The outcome of the watching exercise is to come up with the random walkseries. In stock price terms, the watching exercise translates to coming upwith a time series of stock prices. To do that, we observe the prices at regular time intervals and record them. The resulting sequence of values constitutes a random walk, and our mission is accomplished. Note that the lasttraded price at each instance is known without error, and it is therefore possible to observe the series without error. And if there is no error in the observation, then the Kalman filter model does not apply. So why do we evenattempt such an exercise?We address this matter in the following discussion. Broadly speaking,the price at any given time instance may be construed as the price at whichthe supply meets demand. Let us call this the equilibrium price. Let us nowframe the aim of the watching exercise as generating the sequence of equilibrium prices over consecutive time intervals. In this context, the periodicmeasurement approach amounts to using the observed price at a specifictime as the equilibrium price for the time interval. It is now easy to makethe case that the prices at the end of regular chunks of time are indeed ap-
Kalman Filtering
61
proximations of the equilibrium price for the time chunk, and the notion ofobservation error begins to make sense. It is therefore definitely reasonableto apply Kalman-filtering ideas to stock price series with the logarithm ofprices modeled as a random walk.Summarizing the discussions so far, we have assigned ourselves the taskof watching a random walk and making observations at regular time intervals. Each of the observations has a measure of error associated with it. Thepurpose of the exercise is to come up with a plausible set of system states.Keeping with the notational conventions already established, let us denote the sequence of observations starting from time t = 0, the beginning ofour watching exercise as yt, and the true states as xt. The observation equation may be written yt = xt + et; that is, the observation is the true state plussome error. Now, according to the definition of the random walk, we alsohave xt = xt–1 + et (the current state is the previous state plus an innovation).Writing this as a sequence of predictions and observations, we havey0 = x0 + e0x1 = x0 + e1y1 = x1 + e1x2 = x1 + e2y2 = x2 + e2...
(observation)(prediction)(observation)(prediction)(observation)
Writing the equations in matrix form, we havey 0   1 0   0  −1 1y  =  0 1 1  0   0 −1y   0 0 2 
 e0 0  x0 0 − ε1  0  x1  +  e1   1  x2  −ε 2 e 1 2 
For notational convenience let us denote the system of equations asY2 = H2X2 + h2The 2 in the subscript is the index of the state and is indicative of the number of state estimates used in forming the equations. The above is a set of fiveequations with three unknown values x0, x1, x2. Given that there are moreequations than unknowns, the system is also referred to as an overdetermined set. If the errors at each stage are drawn from identical, independent
BACKGROUND MATERIAL
62
normal distributions, then the typical solution to the overdetermined set isobtained by applying the least squares method:
(
X2 = H 2T H 2
) HY−1
T2 2
(4.12)
That is, we multiply both sides by the transpose of H2, to get a system ofthree equations with three unknowns and then solve the system of equations. This would be our solution method in the normal course.Now let us move on to the next observation y3. Upon obtaining the newdata point, the estimate of our state is determined by the solution of theequationY3 = H3X3 + h3a system of seven equations with four unknown variables. We could then usethe typical approach to solve the overdetermined equations and obtain anestimate for the value of x3. Note, however, that as the number of observations increases, the size of the matrices grows, and the computational costscould potentially go up. It is here that the Kalman-filtering algorithm comesto our rescue. The results from the previous computations are used in an iterative fashion to estimate the value of the next state. The value of x2 and itsvariance as calculated in the previous step is used in the evaluation of thestate x3, thereby keeping the computational cost of evaluating the next stepthe same regardless of how far down the time scale we are.Regardless, the end result of the state estimate in the Kalman-filteringcase is the same as solving the set of equations using the least squares approach. Note that we have made an important assumption in the process;that is, the state variance at each time step is equal to the observation variance. (This is in addition to the assumption of independence of the error distributions.) Thus, with the preceding assumptions, the Kalman filter boilsdown to a least squares solution of equations. The twist is that the solutionis calculated in a recursive fashion. This version of the Kalman filter is therefore known as the recursive least squares method.The assumption of identical and independent error distributions manifests itself in the covariance matrix of the errors. The independence also implies that the errors are not correlated. Therefore, the off-diagonal elementsin the covariance matrix are all zero. The diagonal elements in the covariance matrix are the variances of the error terms. If they are drawn from identical distributions, then the variances should be the same. Therefore, thecovariance matrix in this case may be represented as the identity matrix multiplied by a constant.Let us now turn our attention back to the solution of the precedingmodel. It turns out that the estimated state at a given time for that set of
Kalman Filtering
63
equations can be represented as a weighted linear combination of the observations. Additionally, the weights are actually ratios of Fibonacci numbers.The Fibonacci sequence of numbers is constructed starting from two seednumbers, F0 = 0 and F1 = 1. The next number in the series is generated byadding the last two numbers in the series, Fn = Fn–1 + Fn–2. Applying the formula in an iterative fashion, we obtain the Fibonacci sequence as follows:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . .There are a variety of situations in which the Fibonacci numbers appear.Some sources of information on Fibonacci numbers are listed in the reference section. In any case, the solution to our problem, that is, the estimateof state x2, is given asx2 =
521y + y + y8 2 8 1 8 0
Similarly, x3 is given asx3 =
13521y +y +y +y21 3 21 2 21 1 21 0
In general, if we are to estimate xT, thenxT = w0yT + w1yT–1 + w2yT–2 + . . . .
(4.13)
where F2 T +1 −1 F2 T +1 − 3 F2 T +1 − 5F1 ( )( )( )w0 , w1 , w2 , … , wT = ,,,…, (4.14) F2 T +1F2(T +1)F2(T +1)F2(T +1)  ( )
)
Note that the first weight is the ratio of two consecutive Fibonacci numbers.FThe ratio 2(T +1) approaches the value g. The value g is famously known asF2(T +1) −1the golden mean ratio. It is given by the formula g = 1 + 5 / 2 and hasan approximate value of 1.618. The first weight in the observation is actually the reciprocal of the ratio 1⁄g ≈ 0.618. The subsequent weights are 1⁄g ,1g⁄ , . . . . and so on. To see that the second ratio is 1⁄g , consider the following:3
5
3
F2(T +1) − 3F2(T +1)
=
F2(T +1) − 3 F2(T +1) − 2 F2(T +1) −1F2(T +1) − 2 F2(T +1) −1 F2(T +1)
≈
1g3
(4.15)
64
BACKGROUND MATERIAL
We will once again draw attention to the fact that the solution presentedin Equation 4.15 stays valid only when the state variance is equal to the observation variance. In other situations, we need to obtain an estimate of thestate and observation variance at each time step. We will therefore concludethis section with a brief discussion on the estimation of the state and observation variances.In general random walk terms, the state variance can be estimated as thevariance of the innovations. Modeling the stock price series as a randomwalk, the innovations correspond to the period returns of the price series.The state variance in this case is therefore the variance of the period returns.This calculation is rather commonplace in financial circles and is often referred to as historic volatility. The observation variance is, however, a trickyissue. Let us assume that in addition to the closing price in a time interval,we also observe the high and low stock prices within the interval. The variance of the error in the observation must be the volatility of the stock pricein the time period. This volatility is characterized by high and low values.Several methods to estimate the volatility based on the high–low prices exist,and the references are provided in the reference section. One may use anyone of the methods described in the papers in the appendix to estimate theobservation variance. Once the state and observation variances are known,we are ready to apply the Kalman-filtering approach.
APPLICATION: EXAMPLE WITH THESTANDARD & POOR INDEXIs it conceivable that the observation and innovation variance will be thesame? Why not? After all, they are both representative of the volatility of thesame underlying random walk. Let us therefore see how we fare in practice.We apply the random walk-filtering process with all its assumptions on theStandard & Poor (S&P) index. We use the closing prices of the S&P indexdepository receipt (spidr) with ticker SPY in our example. As discussed inthe section Filtering the Random Walk, we use Equation 4.13 to determinethe state of the process at a given time. The weights in Equation 4.15 aredetermined using Fibonacci numbers. Note that if we decide to use T + 1observations in the state estimation process, the weight of the last data1point according to Equation 4.14 is given by. This is the fractionF2(T +1)of the oldest data point used in the estimate. It turns out that this value approaches zero rather quickly, and its contribution to the value of the statebecomes insignificant as T increases. In order to demonstrate the point, weconstructed a plot of the reciprocals of the Fibonacci series in Figure 4.3.
Kalman Filtering
65
Reciprocals of Fibonacci Numbers
1.0
0.8
0.6
0.4
0.2
0.00
2
4
6
FIGURE 4.3
8
10Index
12
14
16
18
20
Reciprocals of Fibonacci Numbers.
Therefore, numerically speaking, it may be sufficient to use, say, the last10 observations in the state estimation process. Table 4.1 lists the weightingsto use for the 10 observations.With the available weights and the observations, the computationprocess becomes a simple calculation of the weighted average of the observed values, resulting in a unique sequence of states. This set of states isoptimal under the assumptions discussed.Although this is all nice, note that the typical user of moving averagesprobably works with them over multiple time periods. The time periods areused to modify the coarseness of the approximation, and it may be arguedthat looking at moving averages calculated over multiple time frames gives
TABLE 4.1
Reciprocals of Fibonacci Numbers.
1
2
3
4
5
6
7
8
9
10
0.6180
0.2360
0.0901
0.0344
0.0131
0.0050
0.0019
0.0007
0.0002
0.0001
BACKGROUND MATERIAL
66
the technical analyst additional information. The question before us now is,therefore, how can we fine-tune the coarseness of the approximations usingthe Kalman filter?To achieve varying levels of coarseness using the Kalman filter, we makeuse of an important property that relates to the sampling of a random walksequence; that is, the random walk sequence sampled at any frequency resultsin a random walk sequence. To see why that is, consider a random walk sequence with observations at times 1, 2, 3, and so on. By definition, the observation at time 1 plus a value drawn from a normal distribution gives theobservation at time 2, and so on. Now let us sample the random walk at halfof the original observation frequency. This results in a new sequence withthe values for the times 1, 3, 5, and so on. Note that the value at time 3 isgiven by the value at time 1 plus a drawing from a normal distribution to getit to time 2, and then again by adding another drawing from a normal distribution to get it to time 3. Thus, the transition from time 1 to time 3 is effected by summing two random drawings from independent normaldistributions and, in turn, adding it to the value at time 1. But the sum of
4.60
4.55
4.50
4.45
Log of S&P daily closeSmoothing with two-period sampling
4.40
0
10
20
30
40
50
60
Days
FIGURE 4.4
Kalman Smoothing of Random Walk.
70
Kalman Filtering
67
two independent normal random variables may itself be treated as a drawing from a normal distribution with an adjustment to the variance of the distribution. Therefore, the transition from time 1 to time 3 is also effected byadding the value at time = 1 to a drawing from a normal distribution. Thistherefore fits the definition of a random walk sequence. We only need toapply this idea in an iterative fashion to see that the random walk sequencesampled at any frequency results