
Introduction to Data Streams 17
as follows:
m :=
2
1/|W
0
| + 1/|W
1
|
cut
:=
r
1
2m
· ln
4|W |
δ
.
where m is the harmonic mean of |W
0
| and |W
1
|.
Algorithm 1: The ADWIN Algorithm.
begin
Initialize Window W ;
foreach (t) > 0 do
W ← W ∪{x
t
} (i.e., add x
t
to the head of W );
repeat
Drop elements from the tail of W
until |ˆµ
W
0
− ˆµ
W
1
| <
cut
holds for every split of W into
W = W
0
· W
1
Output ˆµ
W
end
The main technical result in Bifet and Gavald`a (2006, 2007) about the
performance of ADWIN is the following theorem, that provides bounds on the
rate of false positives and false negatives for ADWIN:
Theorem 2.2.4 With
cut
defined as above, at every time step we have:
1. (False positiv ...