# A Unified Weight Formula for Calculating the Sample Variance from Weighted Successive Differences

Authors: Kuo-Hung Lo; Tien-Lung Sun; Juei-Chao Chen
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

The basic formula to calculate sample variance is based on the sum of squared differences from mean. From computational perspective, mean calculation is nondesired as it can introduce computing errors. Previous researches have proposed to use weighted formula of the successive differences to calculate sample variance to avoid mean calculation. But their weighted formula is not in a unified format in the sense that it has to be represented as two formulas. This paper proposes a unified weight formula for sample variance calculation from weighted successive differences. A proof is provided to show that sample variance calculated using the proposed unified weighted formula is mathematically equivalent to the basic definition.


---

## Body

## 1. Introduction

Sample variance calculation is a fundamental task in many data analysis applications. The basic formula for calculating a sample variance is based on the sum of squared differences from mean. Given that a set of data isx
1
,
x
2
,
…
,
x
n, the sample variance, denoted as S
n
2, is calculated as follows:
(1)
S
n
2
=
S
S
n
(
n
-
1
)
,
n
≥
2
,
where SS
n
=
∑
i
=
1
n
(
x
i
-
x
-
n
)
2 is the sum of squared differences from the mean and x
-
n
=
(
1
/
n
)
∑
i
=
1
n
x
i is the sample mean. Von Neumann et al. [1] pointed out that (1) does not take into account the order of the observations. They proposed to instead use successive differences of data so that the order can be considered. Specifically, they used
(2)
D
n
2
=
1
2
(
n
-
1
)
∑
i
=
2
n
d
i
2
,
where the subscript i refers to temporal order of the data and d
i
=
x
i
-
x
i
-
1. Define {
x
0
,
d
1
,
…
,
d
n
} as the successive differences of the input data. From computational perspective, von Neumann’s formula is also advantageous as it avoids a mean calculation that may introduce rounding errors.The problem withD
n
2 is that it is not mathematically equivalent to the basic definition. This problem was independently solved by Eilon and Chowdhury [2] and Joarder [3] where weighted successive differences were used to derive a formula that is mathematically equivalent to the basic definition.Eilon and Chowdhury [2] considered a job scheduling problem where they wanted to minimize the variance of the job’s waiting time. Let y
i be the waiting time of the ith job. By definition, y
1
=
0, as the first job does not have waiting time, and y
i
=
∑
j
=
1
i
-
1
p
j, for i
=
1,2
,
…
,
n, where n is the number of jobs and p
j is the processing time of job j. The objective is to minimize the variance of the waiting time, or equivalently SS
n
=
∑
i
=
1
n
(
y
i
-
y
-
n
)
2. For this purpose, there is a need to quickly update SS
n when job i and j are swapped. Notice that when job i and j are swapped, most of the jobs’ waiting time will change accordingly, and y
-
n and SS
n have to be recalculated. To avoid recalculating y
-
n when updating SS
n, Eilon and Chowdhury derived a formula to calculate SS
n from successive differences. By definition, the successive differences of the waiting time are the processing time; that is, p
i
=
y
i
+
1
-
y
i, i
=
1
,
2
,
…
,
n
-
1. So,
(3)
∑
i
=
1
n
(
y
i
-
y
-
n
)
2
=
1
n
(
∑
i
=
1
n
-
1
(
n
-
i
)
i
p
i
2
+
∑
i
,
j
=
1
,
i
≠
j
n
-
1
(
n
-
i
)
j
p
i
p
j
)
=
1
n
∑
i
=
1
n
-
1
∑
j
=
1
n
-
1
c
i
j
*
p
i
p
j
,
where
(4)
c
i
j
*
=
{
(
n
-
i
)
j
,
i
≥
j
,
(
n
-
j
)
i
,
i
<
j
,
i
,
j
=
1
,
2
,
…
,
n
-
1
.
Equation (3) is not a general formula for calculating SS
n as y
1 is zero. Vani and Raghavachari [4] gave a more general formula by considering the job’s completion time rather than waiting time. Let z
i
=
∑
j
=
1
i
p
j be the completion time of job i. They rewrote (3) as follows:
(5)
∑
i
=
1
n
(
z
i
-
z
-
n
)
2
=
1
n
∑
i
=
1
n
(
n
-
i
+
1
)
(
i
-
1
)
p
i
2
+
2
n
∑
i
=
1
n
(
i
-
1
)
p
i
∑
j
=
i
+
1
n
(
n
-
j
+
1
)
p
j
=
1
n
∑
i
=
1
n
∑
j
=
1
n
c
i
j
p
i
p
j
,
where
(6)
c
i
j
=
{
(
n
-
i
+
1
)
(
j
-
1
)
,
i
≥
j
,
(
n
-
j
+
1
)
(
i
-
1
)
,
i
<
j
,
for i
,
j
=
1
,
2
,
…
,
n. In an independent work, Joarder [3] also derived a formula similar to (5). He then converted its double sum structure into a quadratic form wherein
(7)
∑
i
=
1
n
(
x
i
-
x
-
n
)
2
=
1
n
d
1
×
n
T
c
n
×
n
d
n
×
1
,
where d
1
×
n
T
=
[
d
1
d
2
⋯
d
n
]
1
×
n is a vector of the successive differences and c
n
×
n
=
[
c
i
j
]
n
×
n is a weight matrix with c
i
j as defined in (6).One problem with the weight formula in (6) is that it is not in a unified format but has to be represented as two formulas. This deficiency prohibits a compact representation that would facilitate further derivations. To solve this problem, we derive a unified weight formula for sample variance calculations from weighted successive differences. Joarder [3] derived an updating formula to calculate a variance from weighted successive differences. But, his formula contains a dynamically increased number of updating items. Using the unified weight formula, we show [5] that we can improve Joarder’s formula by reducing the updating items to a fixed number of only two items.


## 2. Main Results

Theorem 1.
Given that a temporally order of the observationsx
1
,
x
2
,
…
,
x
n the sum of squared differences about the mean can be represented as
(8)
S
S
n
=
∑
i
=
1
n
(
x
i
-
x
-
n
)
2
=
1
n
d
1
×
n
T
w
n
×
n
d
n
×
1
,
where d
1
×
n
T
=
[
d
1
d
2
⋯
d
n
]
1
×
n, {
d
i
=
x
i
-
x
i
-
1
}, for x
0
=
0, i
=
1
,
2
,
…
,
n, and w
n
×
n
=
[
w
i
j
]
n
×
n are the n
×
n symmetric matrix with
(9)
w
i
j
=
(
n
+
1
)
(
i
+
j
-
1
)
-
i
j
-
n
2
(
i
+
j
+
|
i
-
j
|
)
,
i
,
j
=
1
,
2
,
…
,
n
.Proof.
First write(10)
∑
i
=
1
n
(
x
i
-
x
-
n
)
2
=
(
x
n
×
1
-
x
-
n
×
1
)
T
(
x
n
×
1
-
x
-
n
×
1
)
,
for x
T
=
[
x
1
x
2
⋯
x
n
]
1
×
n. Now, x can be presented as
(11)
x
T
=
[
d
1
∑
i
=
1
2
d
i
⋯
∑
i
=
1
n
d
i
]
1
×
n
=
P
n
×
n
d
n
×
1
,
for
(12)
P
n
×
n
=
[
1
0
⋯
0
1
1
⋱
⋮
⋮
⋮
⋱
0
1
1
⋯
1
]
n
×
n
,
that is, the row i column j element of P
n
×
n is
(13)
p
i
j
=
{
1
,
j
≤
i
0
,
j
>
i
,
for i
,
j
=
1
,
2
,
…
,
n.
Next, the mean ofx can be written as
(14)
x
-
n
=
1
n
∑
i
=
1
n
x
i
=
1
n
∑
i
=
1
n
(
n
-
i
+
1
)
d
i
.
In vector form this is
(15)
x
-
n
×
1
=
Q
n
×
n
d
n
×
1
,
where
(16)
Q
n
×
n
=
1
n
[
n
n
-
1
⋯
1
n
n
-
1
⋯
1
⋮
⋮
⋯
⋮
n
n
-
1
⋯
1
]
n
×
n
;
the row i column j element of Q
n
×
n is
(17)
q
i
j
=
[
1
n
(
n
-
j
+
1
)
]
n
×
n
,
i
,
j
=
1
,
2
,
…
,
n
.
Now observe that
(18)
(
x
n
×
1
-
x
-
n
×
1
)
T
(
x
n
×
1
-
x
-
n
×
1
)
=
[
(
P
n
×
n
-
Q
n
×
n
)
d
n
×
1
]
T
[
(
P
n
×
n
-
Q
n
×
n
)
d
n
×
1
]
=
d
1
×
n
T
(
P
n
×
n
-
Q
n
×
n
)
T
(
P
n
×
n
-
Q
n
×
n
)
d
n
×
1
=
d
1
×
n
T
(
P
n
×
n
T
P
n
×
n
-
P
n
×
n
T
Q
n
×
n
-
Q
n
×
n
T
P
n
×
n
+
Q
n
×
n
T
Q
n
×
n
)
d
n
×
1
.
Thus we need to obtain expressions for calculating P
n
×
n
T
P
n
×
n, P
n
×
n
T
Q
n
×
n, Q
n
×
n
T
P
n
×
n, and Q
n
×
n
T
Q
n
×
n.
First(19)
L
n
×
n
=
P
n
×
n
T
P
n
×
n
=
[
1
1
⋯
1
0
1
⋯
1
⋮
⋮
⋱
⋮
0
0
⋯
1
]
n
×
n
·
[
1
0
⋯
0
1
1
⋯
⋮
⋮
⋮
⋱
0
1
1
⋯
1
]
n
×
n
=
[
∑
m
=
1
n
p
i
m
p
m
j
]
n
×
n
=
[
l
i
j
]
n
×
n
,
where
(20)
l
i
j
=
{
n
-
j
+
1
,
i
≤
j
n
-
i
+
1
,
i
>
j
=
n
-
1
2
(
i
+
j
+
|
i
-
j
|
-
2
)
,
i
,
j
=
1
,
2
,
…
,
n
.
Then
(21)
B
n
×
n
=
P
n
×
n
T
Q
n
×
n
=
[
1
1
⋯
1
0
1
⋯
1
⋮
⋮
⋱
⋮
0
0
⋯
1
]
n
×
n
·
1
n
[
n
n
-
1
⋯
1
n
n
-
1
⋯
1
⋮
⋮
⋱
⋮
n
n
-
1
⋯
1
]
n
×
n
=
[
∑
m
=
1
n
p
i
m
q
m
j
]
n
×
n
=
[
b
i
j
]
n
×
n
,
where
(22)
b
i
j
=
1
n
(
n
-
j
+
1
)
(
n
-
i
+
1
)
,
i
,
j
=
1
,
2
,
…
,
n
,
b
i
j
=
(
b
i
j
)
T
=
1
n
(
n
-
i
+
1
)
(
n
-
j
+
1
)
,
i
,
j
=
1
,
2
,
…
,
n
.
That is,
(23)
P
n
×
n
T
Q
n
×
n
=
(
P
n
×
n
T
Q
n
×
n
)
T
=
Q
n
×
n
T
P
n
×
n
.
Finally,
(24)
R
n
×
n
=
Q
n
×
n
T
Q
n
×
n
=
1
n
[
n
n
⋯
n
n
-
1
n
-
1
⋯
n
-
1
⋮
⋮
⋱
⋮
1
1
⋯
1
]
n
×
n
·
1
n
[
n
n
-
1
⋯
1
n
n
-
1
⋯
1
⋮
⋮
⋱
⋮
n
n
-
1
⋯
1
]
n
×
n
=
[
∑
m
=
1
n
q
i
m
q
m
j
]
n
×
n
=
[
r
i
j
]
n
×
n
,
where
(25)
r
i
j
=
1
n
(
n
-
i
+
1
)
(
n
-
j
+
1
)
,
i
,
j
=
1
,
2
,
…
,
n
.
We now can see that P
n
×
n
T
Q
n
×
n
=
Q
n
×
n
T
P
n
×
n
=
Q
n
×
n
T
Q
n
×
n and, hence,
(26)
P
n
×
n
T
P
n
×
n
-
P
n
×
n
T
Q
n
×
n
-
Q
n
×
n
T
P
n
×
n
+
Q
n
×
n
T
Q
n
×
n
=
P
n
×
n
T
P
n
×
n
-
Q
n
×
n
T
Q
n
×
n
.
A direct calculation produces as follows:
(27)
l
i
j
-
r
i
j
=
n
-
1
2
(
i
+
j
+
|
i
-
j
|
-
2
)
-
1
n
(
n
-
j
+
1
)
(
n
-
i
+
1
)
=
1
n
(
n
2
-
n
2
(
i
+
j
+
|
i
-
j
|
)
+
n
-
(
n
-
i
+
1
)
(
n
-
j
+
1
)
)
=
1
n
(
(
n
+
1
)
(
i
+
j
-
1
)
-
i
j
-
n
2
(
i
+
j
+
|
i
-
j
|
)
)
=
1
n
w
i
j
.
Thus, P
n
×
n
T
P
n
×
n
-
Q
n
×
n
T
Q
n
×
n
=
w
n
×
n and the proof is complete.


## 3. Numerical Example

This section gives a numerical example to illustrate sample variance calculation using the nonunified weight formulac
i
j given in (6) and the unified formula w
i
j given in (9). We take a sample data set x
1
=
5, x
2
=
14, x
3
=
9, and x
4
=
6 from Ross [6, Page 145] where the data are used to illustrate the variance updating process using the one-pass algorithm proposed in van Reeken [7]. The successive differences for this data set are
(28)
d
1
=
5
,
d
2
=
14
-
5
=
9
,
d
3
=
9
-
14
=
-
5
,
d
4
=
6
-
9
=
-
3
,
and the successive differences vector is d
1
×
4
T
=
[
5
9
-
5
-
3
]
1
×
4. Using the nonunified weight formula, the weight matrix c
4
×
4
=
[
c
i
j
]
4
×
4 is constructed using two formulas: one for the lower triangular matrix and one for the strictly upper triangular matrix. For the lower triangular matrix with i
≥
j, c
i
j
=
(
n
-
i
+
1
)
(
j
-
1
). For example, c
11
=
(
4
-
1
+
1
)
(
1
-
1
)
=
0, c
21
=
(
4
-
2
+
1
)
(
1
-
1
)
=
0, c
31
=
(
4
-
3
+
1
)
(
1
-
1
)
=
0, and c
32
=
(
4
-
3
+
1
)
(
2
-
1
)
=
2. For the strictly upper triangular matrix with i
<
j, the weight formula is c
i
j
=
(
n
-
j
+
1
)
(
i
-
1
). For example, c
12
=
(
4
-
2
+
1
)
(
1
-
1
)
=
0, c
13
=
(
4
-
3
+
1
)
(
1
-
1
)
=
0, and c
23
=
(
4
-
3
+
1
)
(
2
-
1
)
=
2. Combining the lower triangular matrix and the strictly upper triangular matrix we can get
(29)
c
4
×
4
=
[
0
0
0
0
0
3
2
1
0
2
4
2
0
1
2
3
]
.
The variance is then calculated as
(30)
S
4
2
=
1
4
-
1
·
1
4
d
1
×
4
T
c
4
×
4
d
4
×
1
=
1
12
[
5
9
-
5
-
3
]
[
0
0
0
0
0
3
2
1
0
2
4
2
0
1
2
3
]
[
5
9
-
5
-
3
]
=
49
3
.Now with our approach, the weight matrixW
4
×
4
=
[
w
i
j
]
4
×
4 is constructed using the unified weight formula given in (9). For example, w
12
=
(
4
+
1
)
(
1
+
2
-
1
)
-
1
×
2
-
(
4
/
2
)
(
1
+
2
+
|
1
-
2
|
)
=
0 and w
21
=
(
4
+
1
)
(
2
+
1
-
1
)
-
2
×
1
-
(
4
/
2
)
(
2
+
1
+
|
2
-
1
|
)
=
0. Similarly, w
23 and w
32 are calculated as w
23
=
(
4
+
1
)
(
2
+
3
-
1
)
-
2
×
3
-
(
4
/
2
)
(
2
+
3
+
|
2
-
3
|
)
=
2 and w
32
=
(
4
+
1
)
(
3
+
2
-
1
)
-
3
×
2
-
(
4
/
2
)
(
3
+
2
+
|
3
-
2
|
)
=
2. The other weights are calculated in a similar manner to produce
(31)
W
4
×
4
=
[
0
0
0
0
0
3
2
1
0
2
4
2
0
1
2
3
]
.
The variance is then calculated as
(32)
S
4
2
=
1
4
-
1
·
1
4
d
1
×
4
T
w
4
×
4
d
4
×
1
=
1
12
[
5
9
-
5
-
3
]
[
0
0
0
0
0
3
2
1
0
2
4
2
0
1
2
3
]
[
5
9
-
5
-
3
]
=
49
3
.


## 4. Conclusions

Sample variance calculation using weighted successive differences is advantageous from a computational perspective as it avoids a mean calculation which may introduce rounding errors. However, the weight formula that has been proposed in previous research is not in a unified format. Instead, it has to be represented as two formulas. This deficiency prohibits compact representation of further derivations. This paper derives a unified weight formula for calculating a sample variance from weighted successive differences. We have employed this compute formula to improve variance updating formula in Vani and Raghavachari [4] or Joarder [3].



---

*Source: 210761-2014-08-27.xml*