Rapidly Computing the Standard Deviation for a Fixed Period (Length of Data)

Wikipedia’s page for Standard Deviation presents a formula for rapidly calculating the standard deviation of a growing set of numbers:

[1] Qk = Qk-1 + (xk – Ak-1)(xk – Ak) where xk is the kth element in the set and Ak is the mean of the first kth numbers.

The standard deviation squared of the first n numbers of a set is Qn / n.

From this, it is easy to compute the standard deviation for a growing set of numbers without having to read through all numbers in the set a second time.  Recomputing the mean requires only an addition of (xk – Ak-1) / k to the prior mean of Ak-1 — so this does not require looking back through all the elements of the set.

Therefore recomputing Q does not require looking back through all the elements in the set since it only depends on xk, Qk-1, Ak, and Ak-1.  We’ve deduced that Ak can be derived from Ak-1 without having to look back through all elements of the set, so new values of Q can be computed likewise.

Now how would one rapidly calculate the standard deviation if the set was not growing, but rather was a moving window of fixed length?  This is useful in finance or science when we want to keep an up to date standard deviation for a set of constant size with numbers changing one at a time.  For example, in finance, when calculating Bollinger Bands, we want to always know the standard deviation in stock prices for the last 20 periods.  So the set of stock prices isn’t growing in our set, instead it is of constant size, removing the oldest stock price and replacing it with the latest one at every tick interval.  We can adapt formula [1] above for growing sets to meet our needs here by realizing that a moving window is a set that grows by one at one end, and shrinks by one at the other.

Without loss of generality, let’s assume the beginning of our window is element a of a given set (and we will be discarding the a-th element when the window moves by one), the second element is b, the last element of the window is c, and the element to be added is d.  We are moving from a window of data that encompasses elements a through c, to a window of data one over that encompasses elements b through d.  Our window length is constant, that is d – b = c – a.

So if our data set looks like … 1, 2, 3, 5, 8, 11, 13 … and our period is 4, the a-th element might have a value of 2, b-th is 3, c-th 8 and d-th 11.  We moved from a window looking at [2, 3, 5, 8] to [3, 5, 8, 11].

If we grow our set from b to c to b to d by adding the d-th element, the Q formula would look like the following:

[2] Qbd = Qbc + (xd – Abc)(xd – Abd)

Now this formula looks the same as growing a set from b to c to a to c by adding the a-th element:

[3] Qac = Qbc + (xa – Abc)(xa – Aac)

Rearranging [3], we find out that shrinking a set, in this case, from a to c to b to c, is simply reducing Q by the product of terms on the RHS:

[4] Qbc = Qac – (xa – Abc)(xa – Aac)

Substituting [4] into [2], we find out how to get Q (and consequently the standard deviation) for the new window b to d, from the Q (or standard deviation) of our old window a to c:

[5] Qbd = Qac – (xa – Abc)(xa – Aac) + (xd – Abc)(xd – Abd)

We arrive at [5], a formula where we can compute new values of Q for a moving window (and we can easily calculate standard deviation from that) without having to go through a second pass of all numbers in the set.  The derivation is simple after realizing a moving window is simply a set that grows and shrinks by one element.

List of MSN Gaming Zone Backgammon Cheaters

[Update: MSN has removed Backgammon from its games. Probably because of the rampant cheating. For a more fair place to play Backgammon that minimizes the chance of cheating (particularly because of the availability of instant replays) try https://www.gameslush.com/backgammon]

Figured I’d compile this list after seeing several cheaters that exploit the “repeated-undo stall/timeout” bug. Hopefully this list will help legitimate players safely quit the game before entering a match with these sociopaths. Don’t know why these cheaters spend so much time on such fruitless (and mindless) idiocy when they could instead devote their efforts to learning how to play properly. It becomes obviously fishy when these players rated 2000 and higher play so poorly … you can smell the undo-stall cheat coming from a mile.

Here’s the list so far and I’ll update it as it grows:

nabnabnab8
Long_TeaBagger
rollierocket
OP91
Tricked_Safe1
yambag7
PerfectBalance5
SlowerLeech
BestInTheWest67
Deadly_Timing
Monteceito
StainableMetal
Master_of_Dice
quickie1913
SteadierPig6
OBX_7
TempFormula6
Emilian11

2015-01-07: WirierCloth

More as of 2014-07-31:
opticstwo
prancing_horse2
GogglesPaisano5

More as of 2014-06-13:
EnamoretedAunt
HitByABus
Length_Axis

More courtesy of the Microsoft community forums thread:
Ciscoman9
filini
smuglight
future_seer
sprite
Elephant__
LolaBadGirl
George1772
Guest (with 23,000+ games)
Guest (with 10,000+ games)
RiskQueen

Edit — thanks to Bob_Who for the following update:

Novy22
CrazyFastTD
TutorialCoder
Tigermartin7890
Sieeeeeeeb
MD_Danny
Tradable_Toast
ErrantMarlin
eastcoast_poker
Burdened_Steet
PADDLES__
Peak_Wizard0
Gammon4all
Eqlant
BobbyJ30
PSstarman1
Barmy_Quotient

Courtesy of this video (link):
CulichiGuapo

Prior to 2012-10-14:
Stereo_Chart
NathDan0615
Cursive_Tiger
BCCFMPTN
hunter_gunter