{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# A Review of Welford's Paper\n", "\n", "In 1962, B.P. Welford published a paper titled [Note on a Method for Calculating Corrected Sums of Squares and Products](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.302.7503&rep=rep1&type=pdf). Let's review some important identities/derivations from this paper as they will come in handy later. Note that we use zero-based indexing when referencing elements of our time series." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Deriving Equation (1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " \\mu_{Q_{i,n}} ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n} \\frac{q_{i+j}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{q_{i}}{n} + \\frac{q_{i+1}}{n} + \\ldots + \\frac{q_{i+n-2}}{n} + \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " 1 \\cdot \\frac{q_{i}}{n} + 1 \\cdot \\frac{q_{i+1}}{n} + \\ldots + 1 \\cdot \\frac{q_{i+n-2}}{n} + \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{n-1}{n-1} \\frac{q_{i}}{n} + \\frac{n-1}{n-1} \\frac{q_{i+1}}{n} + \\ldots + \\frac{n-1}{n-1} \\frac{q_{i+n-2}}{n} + \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{n-1}{n} \\frac{q_{i}}{n-1} + \\frac{n-1}{n} \\frac{q_{i+1}}{n-1} + \\ldots + \\frac{n-1}{n} \\frac{q_{i+n-2}}{n} + \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{n-1}{n}\n", " \\left(\n", " \\frac{q_{i}}{n-1} + \\frac{q_{i+1}}{n-1} + \\ldots + \\frac{q_{i+n-2}}{n-1}\n", " \\right)\n", " + \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{n-1}{n}\n", " \\sum \\limits _{0 \\leq j \\lt n-1} \\frac{q_{i+j}}{n-1}\n", " + \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " + \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " \\mu_{Q_{i,m}} ={}&\n", " \\frac{m-1}{m}\n", " \\mu_{Q_{i,m-1}}\n", " + \\frac{q_{i+m-1}}{m}\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Deriving Equation (2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " j < n-1, \\;\\;\\;\\;\\;\n", " q_{i+j} - \\mu_{Q_{i,n}} ={}& \n", " q_{i+j} - \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " - \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " q_{i+j} \n", " - \\frac{n}{n} \\mu_{Q_{i,n-1}}\n", " + \\frac{\\mu_{Q_{i,n-1}}}{n}\n", " - \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " + \\frac{1}{n}\n", " \\left(\n", " -q_{i+n-1} + \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\\\\n", " q_{i+j} - \\mu_{Q_{i,m}} ={}& \n", " q_{i+j} \n", " - \\mu_{Q_{i,m-1}}\n", " - \\frac{1}{m}\n", " \\left(\n", " q_{i+m-1} - \\mu_{Q_{i,m-1}}\n", " \\right)\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Deriving Equation (3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " j = n-1, \\;\\;\\;\\;\\;\n", " q_{i+n-1} - \\mu_{Q_{i,n}} &= \n", " q_{i+n-1} - \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " - \\frac{q_{i+n-1}}{n}\n", " \\\\\n", " &=\n", " - \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " - \\frac{q_{i+n-1}}{n} + q_{i+n-1}\n", " \\\\\n", " &=\n", " - \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " + q_{i+n-1}\n", " \\left(\n", " -\\frac{1}{n} + 1\n", " \\right)\n", " \\\\\n", " &=\n", " - \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " + q_{i+n-1}\n", " \\left(\n", " -\\frac{1}{n} + \\frac{n}{n}\n", " \\right)\n", " \\\\\n", " &=\n", " - \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " + q_{i+n-1}\n", " \\left(\n", " -\\frac{1}{n} + \\frac{n}{n}\n", " \\right)\n", " \\\\\n", " &=\n", " - \\frac{n-1}{n}\n", " \\mu_{Q_{i,n-1}}\n", " + q_{i+n-1}\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)\n", " \\\\\n", " &=\n", " \\frac{n-1}{n}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\\\\n", " q_{i+m-1} - \\mu_{Q_{i,m}} &= \\frac{m-1}{m}\n", " \\left(\n", " q_{i+m-1}\n", " - \n", " \\mu_{Q_{i,m-1}}\n", " \\right)\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Deriving Equation (I) - The Corrected Sum of Squares" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "for $n = 1, 2, \\ldots, m$\n", "\n", "\\begin{align}\n", " S(Q_{i,n}) ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n}\n", " \\left(\n", " q_{i+j} - \\mu_{Q_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " (q_{i+j} - \\mu_{Q_{i,n}})^2\n", " +\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left[\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\right] ^2\n", " +\n", " \\left[\n", " \\frac{n-1}{n}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\right] ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt m-1}\n", " \\left[\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\right] ^2\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right) ^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left[\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " - \\frac{2}{n}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " + \\frac{1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\right]\n", " +\n", " \\frac{(n-1)^2}{n^2}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " - \n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\frac{2}{n}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " +\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\frac{1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " +\n", " \\frac{(n-1)^2}{n^2}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " - \n", " 2 \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\frac{1}{n}\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " +\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\frac{1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " +\n", " \\frac{(n-1)^2}{n^2}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " - \n", " 2 \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\cdot 0\n", " +\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\frac{1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " +\n", " \\frac{(n-1)^2}{n^2}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " + \n", " \\frac{n-1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " +\n", " \\frac{(n-1)^2}{n^2}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " +\n", " \\left[\n", " \\frac{n-1}{n^2}\n", " +\n", " \\frac{(n-1)^2}{n^2}\n", " \\right]\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " +\n", " \\left[\n", " \\frac{n-1+n^2-2n+1}{n^2}\n", " \\right]\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} \n", " - \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " +\n", " \\left[\n", " \\frac{n^2-n}{n^2}\n", " \\right]\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1})\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right) ^2\n", " \\\\\n", " S(Q_{i,m}) ={}&\n", " S({Q_{i,m-1}})\n", " +\n", " \\left(\n", " \\frac{m-1}{m}\n", " \\right)\n", " \\left(\n", " q_{i+m-1}\n", " - \n", " \\mu_{Q_{i,m-1}}\n", " \\right) ^2\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Deriving Equation (II) - The Corrected Sum of Products" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " S(Q_{i,n}, T_{i,n}) ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n}\n", " \\left(\n", " q_{i+j} - \\mu_{Q_{i,n}}\n", " \\right)\n", " \\left(\n", " t_{i+j} - M_{T_{i,n}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} - \\mu_{Q_{i,n}}\n", " \\right)\n", " \\left(\n", " t_{i+j} - M_{T_{i,n}}\n", " \\right)\n", " +\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left[\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " - \\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\right]\n", " +\n", " \\left[\n", " \\frac{n-1}{n}\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i+n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\frac{n-1}{n}\n", " \\left(\n", " t_{i+n-1}\n", " - \n", " M_{T_{i,n-1}}\n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left[\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " - \\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\right]\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1}\n", " - \n", " M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left[\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " -\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " +\n", " \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\right]\n", " \\\\\n", " {}& \n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1}\n", " - \n", " M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " -\\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " +\\frac{1}{n^2}\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " {}&\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " -\\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " +\\frac{n-1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " {}&\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1}\n", " - \n", " M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1}, T_{i,n-1})\n", " -\\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j}\n", " - M_{T_{i,n-1}}\n", " \\right)\n", " +\\frac{n-1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " {}&\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1}\n", " - \n", " M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1}, T_{i,n-1})\n", " -\\frac{1}{n}\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\cdot 0\n", " - \\frac{1}{n}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\cdot 0\n", " +\\frac{n-1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1}\n", " - \n", " M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1}, T_{i,n-1})\n", " +\\frac{n-1}{n^2}\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\left(\n", " q_{i+n-1}\n", " - \n", " \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1}\n", " - \n", " M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1}, T_{i,n-1})\n", " +\n", " \\left[\n", " \\frac{n-1}{n^2}\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right)^2\n", " \\right]\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1}, T_{i,n-1})\n", " +\n", " \\left[\n", " \\frac{n-1}{n^2}\n", " +\n", " \\frac{n^2-2n+1}{n^2}\n", " \\right]\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i+n-1}, T_{i,n-1})\n", " +\n", " \\left(\n", " \\frac{n-1+n^2-2n+1}{n^2}\n", " \\right)\n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1}, T_{i,n-1})\n", " +\n", " \\left(\n", " \\frac{n^2-n}{n^2}\n", " \\right) \n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1}, T_{i,n-1})\n", " +\n", " \\left(\n", " \\frac{n-1}{n}\n", " \\right) \n", " \\left(\n", " q_{i+n-1} - \\mu_{Q_{i,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+n-1} - M_{T_{i,n-1}}\n", " \\right)\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " S(Q_{i,m}, T_{i,m}) ={}& \n", " S(Q_{i,m-1}, T_{i,m-1})\n", " +\n", " \\left(\n", " \\frac{m-1}{m}\n", " \\right) \n", " \\left(\n", " q_{i+m-1} - \\mu_{Q_{i,m-1}}\n", " \\right)\n", " \\left(\n", " t_{i+m-1} - M_{T_{i,m-1}}\n", " \\right)\n", " \\\\\n", " S(Q_{i-1,m}, T_{i-1,m}) ={}& \n", " S(Q_{i-1,m-1}, T_{i-1,m-1})\n", " +\n", " \\left(\n", " \\frac{m-1}{m}\n", " \\right) \n", " \\left(\n", " q_{i+m-2} - \\mu_{Q_{i-1,m-1}}\n", " \\right)\n", " \\left(\n", " t_{i+m-2} - M_{T_{i-1,m-1}}\n", " \\right)\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Building on Equation (II) and also the fact that: \n", "\n", "\\begin{align}\n", " \\mu_{Q_{i-1,n}} \n", " ={}& \\frac{n-1}{n} \\mu_{Q_{i-1,n-1}} + \\frac{q_{i+n-2}}{n}\n", " \\\\\n", " ={}& \\mu_{Q_{i-1,n-1}} - \\frac{1}{n} \\mu_{Q_{i-1,n-1}} + \\frac{q_{i+n-2}}{n}\n", " \\\\\n", " ={}& \\mu_{Q_{i-1,n-1}} + \\frac{q_{i+n-2}}{n} - \\frac{\\mu_{Q_{i-1,n-1}}}{n}\n", " \\\\\n", " ={}& \\frac{1}{n} \\sum \\limits _{0 \\leq j \\lt n-1}\n", " q_{i+j-1}\n", " + \\frac{q_{i+n-2}}{n}\n", " - \\frac{\\mu_{Q_{i-1,n-1}}}{n}\n", " \\\\\n", " ={}& \n", " \\frac{q_{i-1}}{n} \n", " +\n", " \\frac{1}{n} \\sum \\limits _{1 \\leq j \\lt n-1}\n", " q_{i+j-1}\n", " + \\frac{q_{i+n-2}}{n}\n", " - \\frac{\\mu_{Q_{i-1,n-1}}}{n}\n", " \\\\\n", " ={}& \\frac{q_{i-1}}{n} \n", " + \\frac{1}{n} \\sum \\limits _{0 \\leq j \\lt n-1} q_{i+j}\n", " - \\frac{\\mu_{Q_{i-1,n-1}}}{n}\n", " \\\\\n", " ={}& \\frac{q_{i-1}}{n} + \\mu_{Q_{i,n-1}} - \\frac{\\mu_{Q_{i-1,n-1}}}{n}\n", " \\\\\n", " ={}& \\mu_{Q_{i,n-1}} + \\frac{1}{n} \\left( q_{i-1} - \\mu_{Q_{i-1,n-1}} \\right)\n", " \\\\\n", "\\end{align}\n", "\n", "we can actually express $S(Q_{i-1,n},T_{i-1,n})$ with respect to $S(Q_{i,n-1},T_{i,n-1}) = \\sum \\limits _{0 \\leq j \\lt n-1} \\left( q_{i+j} - \\mu_{Q_{i,n-1}} \\right) \\left( t_{i+j} - M_{T_{i,n-1}} \\right)$ and $\\left( q_{i-1} - \\mu_{Q_{i,n-1}} \\right) \\left( t_{i-1} - M_{T_{i,n-1}} \\right)$:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " S(Q_{i-1,n}, T_{i-1,n}) ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n}\n", " \\left(\n", " q_{i+j-1} - \\mu_{Q_{i-1,n}}\n", " \\right)\n", " \\left(\n", " t_{i+j-1} - M_{T_{i-1,n}}\n", " \\right)\n", " \\\\\n", " ={}& \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n}}\n", " \\right)\n", " \\left(\n", " t_{i-1} - M_{T_{i-1,n}}\n", " \\right)\n", " +\n", " \\sum \\limits _{1 \\leq j \\lt n}\n", " \\left(\n", " q_{i+j-1} - \\mu_{Q_{i-1,n}}\n", " \\right)\n", " \\left(\n", " t_{i+j-1} - M_{T_{i-1,n}}\n", " \\right)\n", " \\\\\n", " ={}& \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n}}\n", " \\right)\n", " \\left(\n", " t_{i-1} - M_{T_{i-1,n}} \n", " \\right)\n", " +\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} - \\mu_{Q_{i-1,n}}\n", " \\right)\n", " \\left(\n", " t_{i+j} - M_{T_{i-1,n}}\n", " \\right)\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j} - \\mu_{Q_{i-1,n}}\n", " \\right)\n", " \\left(\n", " t_{i+j} - M_{T_{i-1,n}}\n", " \\right)\n", " +\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n}}\n", " \\right)\n", " \\left(\n", " t_{i-1} - M_{T_{i-1,n}} \n", " \\right)\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left[\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\right]\n", " +\n", " \\left[\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left[\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " +\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right) \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\right]\n", " \\\\\n", " &+\n", " \\left[\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " -\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " +\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right) \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " &+\n", " \\left[\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " - \n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " - \n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1},T_{i,n-1})\n", " -\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " +\n", " \\frac{n-1}{n^2}\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " &+\n", " \\left[\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " - \n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\cdot 0\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\cdot 0\n", " +\n", " \\frac{n-1}{n^2}\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " &+\n", " \\left[\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\right]\n", " \\left[\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " q_{i+j}\n", " -\n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i+j}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " +\n", " \\frac{n-1}{n^2}\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " &+\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\frac{1}{n} \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " +\n", " \\frac{1}{n^2} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1},T_{i,n-1})\n", " +\n", " \\frac{n-1}{n^2}\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " &+\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n}\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right) \n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " -\n", " \\frac{n}{n^2} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " +\n", " \\frac{1}{n^2} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1},T_{i,n-1})\n", " +\n", " \\frac{n-1}{n^2}\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " -\n", " \\frac{n}{n^2} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " +\n", " \\frac{1}{n^2} \n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " &+\n", " \\frac{n}{n}\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " -\n", " \\frac{1}{n} \n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1},T_{i,n-1})\n", " +\n", " \\frac{n-1-n+1}{n^2}\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " +\n", " \\frac{n-1}{n}\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1},T_{i,n-1})\n", " +\n", " 0 \\cdot\n", " \\left(\n", " q_{i-1} - \\mu_{Q_{i-1,n-1}}\n", " \\right)\n", " \\left( \n", " t_{i-1} - M_{T_{i-1,n-1}} \n", " \\right)\n", " +\n", " \\frac{n-1}{n}\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1},T_{i,n-1})\n", " +\n", " \\frac{n-1}{n}\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " \\\\\n", " ={}&\n", " S(Q_{i,n-1},T_{i,n-1})\n", " +\n", " \\frac{n-1}{n}\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,n-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,n-1}} \n", " \\right)\n", " \\\\\n", "S(Q_{i-1,m}, T_{i-1,m})\n", " ={}&\n", " S(Q_{i,m-1},T_{i,m-1})\n", " +\n", " \\frac{m-1}{m}\n", " \\left(\n", " q_{i-1} \n", " - \n", " \\mu_{Q_{i,m-1}} \n", " \\right)\n", " \\left(\n", " t_{i-1}\n", " -\n", " M_{T_{i,m-1}} \n", " \\right)\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Deriving Rolling Window Variance (or Standard Deviation) with Welford's Method\n", "\n", "For any sequence $T$, we can compute the mean, $\\mu_{T_{i,n}}$, for any subsequence starting at position $i$ in $T$ and with subsequence length $n$ according to the following definition:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " \\mu_{T_{i,n}} ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n} \\frac{t_{i+j}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{t_{i}}{n} + \\frac{t_{i+1}}{n} + \\ldots + \\frac{t_{i+n-2}}{n} + \\frac{t_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " 0 + \\frac{t_{i}}{n} + \\frac{t_{i+1}}{n} + \\ldots + \\frac{t_{i+n-2}}{n} + \\frac{t_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " \\left(\\frac{t_{i-1}}{n} - \\frac{t_{i-1}}{n}\\right) + \\frac{t_{i}}{n} + \\frac{t_{i+1}}{n} + \\ldots + \\frac{t_{i+n-2}}{n} + \\frac{t_{i+n-1}}{n}\n", " \\\\\n", " ={}&\n", " \\frac{t_{i-1}}{n} + \\frac{t_{i}}{n} + \\frac{t_{i+1}}{n} + \\ldots + \\frac{t_{i+n-2}}{n} + \\frac{t_{i+n-1}}{n} - \\frac{t_{i-1}}{n}\n", " \\\\\n", " ={}&\n", " \\sum \\limits _{-1 \\leq j \\lt n-1} \\frac{t_{i+j}}{n}\n", " + \\frac{t_{i+n-1}}{n} - \\frac{t_{i-1}}{n}\n", " \\\\\n", " ={}&\n", " \\mu_{T_{i-1,n}} + \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " \\\\\n", " ={}&\n", " \\mu_{T_{i-1,n}} + \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then, it follows that:\n", "\n", "\\begin{align}\n", " t_{i+j} - \\mu_{T_{i,n}} ={}& \n", " t_{i+j} - \\mu_{T_{i-1,n}} - \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " \\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we can derive the rolling window variance, $S$, by first calculating the correctect sum-of-squares, $CSS$:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\begin{align}\n", " CSS(T_{i,n}) ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + 0\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{0 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}} - \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " \\right) ^2\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left[\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)\n", " - \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " \\right] ^2\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left[\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)^2\n", " - 2 \\left(t_{i+n-1} - t_{i-1} \\right)\\frac{1}{n} \n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)\n", " + \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n^2}\n", " \\right]\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)^2\n", " -\n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " 2 \\left(t_{i+n-1} - t_{i-1} \\right)\\frac{1}{n} \n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)\n", " +\n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n^2}\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)^2\n", " - 2 \\left(t_{i+n-1} - t_{i-1} \\right)\\frac{1}{n}\n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)\n", " +\n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n^2}\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " \\sum \\limits _{-1 \\leq j \\lt n-1}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i-1,n}}\n", " \\right)^2\n", " - 2 \\left(t_{i+n-1} - t_{i-1} \\right) \\cdot 0\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n}\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n}\n", " + \\left(\n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " - \\left(\n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n}\n", " + \\left(\n", " t_{i+n-1}^2 - 2t_{i+n-1}\\mu_{T_{i,n}} + \\mu_{T_{i,n}}^2\n", " \\right)\n", " - \\left(\n", " t_{i-1}^2 - 2t_{i-1}\\mu_{T_{i,n}} + \\mu_{T_{i,n}}^2\n", " \\right)\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n}\n", " + t_{i+n-1}^2 - 2t_{i+n-1}\\mu_{T_{i,n}} + \\mu_{T_{i,n}}^2\n", " - t_{i-1}^2 + 2t_{i-1}\\mu_{T_{i,n}} - \\mu_{T_{i,n}}^2\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n}\n", " + t_{i+n-1}^2 - 2t_{i+n-1}\\mu_{T_{i,n}} - t_{i-1}^2 + 2t_{i-1}\\mu_{T_{i,n}}\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n}\n", " + \n", " \\left( \n", " t_{i+n-1}^2 - t_{i-1}^2 \n", " \\right) \n", " - \n", " \\left(\n", " 2t_{i+n-1}\\mu_{T_{i,n}} - 2t_{i-1}\\mu_{T_{i,n}}\n", " \\right)\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)^2}{n}\n", " + \n", " \\left( \n", " t_{i+n-1} - t_{i-1}\n", " \\right)\n", " \\left( \n", " t_{i+n-1} + t_{i-1}\n", " \\right)\n", " - 2\\mu_{T_{i,n}} \\left( t_{i+n-1} - t_{i-1} \\right)\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " + \n", " \\left( \n", " t_{i+n-1} + t_{i-1}\n", " \\right)\n", " - 2\\mu_{T_{i,n}}\n", " \\right]\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " + \n", " \\left( \n", " t_{i+n-1} + t_{i-1}\n", " \\right)\n", " - \\mu_{T_{i,n}}\n", " - \\mu_{T_{i,n}}\n", " \\right]\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " + \n", " \\left( \n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right)\n", " +\n", " \\left( \n", " t_{i-1} - \\mu_{T_{i,n}}\n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " + \n", " \\left( \n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right)\n", " +\n", " \\left( \n", " t_{i-1} - \\mu_{T_{i-1,n}} - \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " - \n", " \\frac{t_{i+n-1} - t_{i-1}}{n}\n", " + \n", " \\left( \n", " t_{i+n-1} - \\mu_{T_{i,n}}\n", " \\right)\n", " +\n", " \\left( \n", " t_{i-1} - \\mu_{T_{i-1,n}}\n", " \\right)\n", " \\right]\n", " \\\\\n", " ={}& \n", " CSS(T_{i-1,n})\n", " +\n", " \\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " t_{i+n-1} - \\mu_{T_{i,n}} + t_{i-1} - \\mu_{T_{i-1,n}}\n", " \\right]\n", " \\\\\n", " S^2(T_{i,n}) ={}& \n", " \\frac{\\sum \\limits _{0 \\leq j \\lt n}\n", " \\left(\n", " t_{i+j} - \\mu_{T_{i,n}}\n", " \\right) ^2\n", " }{n}\n", " \\\\\n", " ={}& \n", " \\frac{CSS(T_{i,n})}{n}\n", " \\\\\n", " ={}& \n", " \\frac{CSS(T_{i-1,n})}{n}\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " t_{i+n-1} - \\mu_{T_{i,n}} + t_{i-1} - \\mu_{T_{i-1,n}}\n", " \\right]}{n}\n", " \\\\\n", " ={}& \n", " S^2(T_{i-1,n})\n", " +\n", " \\frac{\\left(t_{i+n-1} - t_{i-1}\\right)\n", " \\left[\n", " t_{i+n-1} - \\mu_{T_{i,n}} + t_{i-1} - \\mu_{T_{i-1,n}}\n", " \\right]}{n}\n", " \\\\\n", "\\end{align}" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.9" } }, "nbformat": 4, "nbformat_minor": 4 }