Daniil Ryabko
email: daniil@ryabko.net

Clustering processes

The problem of clustering is considered, for the case when each data point is a sample generated by a stationary ergodic process. We propose a very natural asymptotic notion of consistency, and show that simple consistent algorithms exist, under most general non-parametric assumptions. The notion of consistency is as follows: two samples should be put into the same cluster if and only if they were generated by the same distribution. With this notion of consistency, clustering generalizes such classical statistical problems as homogeneity testing and process classification. We show that, for the case of a known number of clusters, consistency can be achieved under the only assumption that the joint distribution of the data is stationary ergodic (no parametric or Markovian assumptions, no assumptions of independence, neither between nor within the samples). If the number of clusters is unknown, consistency can be achieved under appropriate assumptions on the mixing rates of the processes. (again, no parametric or independence assumptions). In both cases we give examples of simple (at most quadratic in each argument) algorithms which are consistent.

Introduction

Given a finite set of objects, the problem is to "cluster" similar objects together. This intuitively simple goal is notoriously hard to formalize. Most of the work on clustering is concerned with particular parametric data generating models, or particular algorithms, a given similarity measure, and (very of-ten) a given number of clusters. It is clear that, as in almost learning problems, in clustering finding the right similarity measure is an integral part of the problem. However, even if one assumes the similarity measure known, it is hard to define what a good clustering is [START_REF] Kleinberg | An impossibility theorem for clustering[END_REF]; [START_REF] Zadeh | A uniqueness theorem for clustering[END_REF]. What is more, even if one assumes the similarity measure to be simply the Euclidean distance (on the plane), and the number of clusters k known, then clustering may still appear intractable for computational reasons. Indeed, in this case finding k centres (points which minimize the cumulative distance from each point in the sample to one of the centres) seems to be a natural goal, but this problem is NP-hard [START_REF] Mahajan | The planar k-means problem is NP-hard[END_REF].

In this work we concentrate on a subset of the clustering problem: clustering processes. That is, each data point is itself a sample generated by a certain discrete-time stochastic process. This version of the problem has numerous applications, such as clustering biological data, financial observations, or behavioural patterns, and as such it has gained a tremendous attention in the literature.

The main observation that we make in this work is that, in the case of clustering processes, one can benefit from the notion of ergodicity to define what appears to be a very natural notion of consistency. This notion of consistency is shown to be satisfied by simple algorithms that we present, which are polynomial in all arguments. This can be achieved without any modeling assumptions on the data (e.g. Hidden Markov, Gaussian, etc.), without assuming independence of any kind within or between the samples. The only assumption that we make is that the joint distribution of the data is stationary ergodic. The assumption of stationarity means, intuitively, that the time index itself bares no information: it does not matter whether we have started recording observations at time 0 or at time 100. By virtue of the ergodic theorem, any stationary process can be represented as a mixture of stationary ergodic processes. In other words, a stationary process can be thought of as first selecting a stationary ergodic process (according to some prior distribution) and then observing its outcomes. Thus, the assumption that the data is stationary ergodic is both very natural and rather weak. At the same time, ergodicity means that, in asymptotic, the properties of the process can be learned from observation.

This allows us to define the clustering problem as follows.

N samples are given:

x 1 = (x 1 1 , . . . , x 1 n1 ), . . . , x N = (x N 1 , . . . , x N nN )
. Each sample is drawn by one out of k different stationary ergodic distributions. The samples are not assumed to be drawn independently; rather, it is assumed that the joint distribution of the samples is stationary ergodic. The target clustering is as follows: those and only those samples are put into the same cluster that were generated by the same distribution. The number k of target clusters can be either known or unknown (different consistency results can be obtained in these cases). A clustering algorithm is called asymptotically consistent if the probability that it outputs the target clustering converges to 1, as the lengths (n 1 , . . . , n N ) of the samples tend to infinity (a variant of this definition is to require the algorithm to stabilize on the correct answer with probability 1). Note the particular regime of asymptotic: not with respect to the number of samples N , but with respect to the length of the samples n 1 , . . . , n N .

Similar formulations have appeared in the literature before. Perhaps the most close approach is mixture models [START_REF] Smyth | Clustering sequences with hidden markov models[END_REF]; [START_REF] Zhong | A unified framework for model-based clustering[END_REF]: it is assumed that there are k different distributions that have a particular known form (such as Gaussian, Hidden Markov models, or graphical models) and each one out of N samples is generated independently according to one of these k distributions (with some fixed probability). Since the model of the data is specified quite well, one can use likelihoodbased distances (and then, for example, the k-means algorithm), or Bayesian inference, to cluster the data. Clearly, the main difference from our setting is in that we do not assume any known model of the data; not even between-sample independence is assumed.

The problem of clustering in our formulation generalizes two classical problems of mathematical statistics. The first one is homogeneity testing, or the twosample problem. Two samples x 1 = (x 1 1 , . . . , x 1 n1 ) and x 2 = (x 2 1 , . . . , x 2 n2 ) are given, and it is required to test whether they were generated by the same distribution, or by different distributions. This corresponds to clustering just two data points (N = 2) with the number k of clusters unknown: either k = 1 or k = 2. The second problem is process classification, or the three-sample problem. Three samples x 1 , x 2 , x 3 are given, it is known that two of them were generated by the same distribution, while the third one was generated by a different distribution. It is required to find out which two were generated by the same distribution. This corresponds to clustering three data points, with the number of clusters known: k = 2. The classical approach is of course to consider Gaussian i.i.d. data, but general nonparametric solutions exist not only for i.i.d. data [START_REF] Lehmann | Testing Statistical Hypotheses[END_REF], but also for Markov chains [START_REF] Gutman | Asymptotically optimal classification for multiple tests with empirically observed statistics[END_REF], and under certain mixing rates conditions. What is important for us here, is that the three-sample problem is easier than the two-sample problem; the reason is that k is known in the latter case but not in the former. Indeed, in Ryabko (2010b) it is shown that in general, for stationary ergodic (binary-valued) processes, there is no solution to the two-sample problem, even in the weakest asymptotic sense. However, a solution to the threesample problem, for (real-valued) stationary ergodic processes was given in Ryabko & Ryabko (2010).

In this work we demonstrate that, if the number k of clusters is known, then there is an asymptotically consistent clustering algorithm, under the only assumption that the joint distribution of data is stationary ergodic. If k is unknown, then in this general case there is no consistent clustering algorithm (as follows from the mentioned result for the twosample problem). However, if an upper-bound α n on the α-mixing rates of the joint distribution of the processes is known, and α n → 0, then there is a consistent clustering algorithm. Both algorithms are rather simple, and are based on the empirical estimates of the so-called distributional distance. For two processes ρ 1 , ρ 2 a distributional distance d is defined as

∞ k=1 w k |ρ 1 (B k )-ρ 2 (B k )|
, where w k are positive summable real weights, e.g. w k = 2 -k , and B k range over a countable field that generates the sigma-algebra of the underlying probability space. For example, if we are talking about finite-alphabet processes with the binary alphabet A = {0, 1}, B k would range over the set A * = ∪ k∈N A k ; that is, over all tuples 0, 1, 00, 01, 10, 11, 000, 001, . . . (of course, we could just as well omit, say, 1 and 11); therefore, the distributional distance in this case is the weighted sum of differences of probabilities of all possible tuples. In this work we consider real-valued processes, so B k have to range through a suitable sequence of intervals, all pairs of such intervals, triples, etc. (see the formal definitions below). This distance has proved a useful tool for solving various statistical problems concerning ergodic processes Ryabko & Ryabko (2010); Ryabko (2010a).

Although this distance involves infinite summation, we show that its empirical approximations can be easily calculated. For the case of a known number of clusters, the proposed algorithm (which is shown to be consistent) is as follows. (The distance in the algorithms is a suitable empirical estimate of d.) The first sample is assigned to the first cluster. For each j = 2..k, find a point that maximizes the minimal distance to those points already assigned to clusters, and assign it to the cluster j. Thus we have one point in each of the k clusters. Next, assign each of the remaining points to the cluster that contains the closest points from those k already assigned. For the case of an unknown number of clusters k, the algorithm simply puts those samples together that are not farther away from each other than a certain threshold level, where the threshold is calculated based on the known bound on the mixing rates. In this case, besides the asymptotic result, finite-time bounds on the probability of outputting an incorrect clustering can be obtained. Each of the algorithms is shown to be at most quadratic in each argument.

Therefore, we show that for the proposed notion of consistency, there are simple algorithms that are con-sistent under most general assumptions. While these algorithms can be easily implemented, we have left the problem of trying them out on particular applications, as well as optimizing the parameters, for future research. It may also be suggested that the empirical distributional distance can be replaced by other distances, for which similar theoretical results can be obtained. An interesting direction, that could preserve the theoretical generality, would be to use data compressors. These were used in [START_REF] Ryabko | Universal codes as a basis for time series testing[END_REF] for the related problems of hypotheses testing, leading both to theoretical and practical results. As far as clustering is concerned, compression-based methods were used (without asymptotic consistency analysis) in [START_REF] Cilibrasi | Clustering by compression[END_REF], and (in a different way) in [START_REF] Bagnall | A bit level representation for time series data mining with shape based similarity[END_REF]. Combining our consistency framework with these compression-based methods is a promising direction for further research.

Preliminaries

Let A be an alphabet, and denote A * the set of tuples ∪ ∞ i=1 A i . In this work we consider the case A = R; extensions to the multidimensional case, as well as to more general spaces, are straightforward. Distributions, or (stochastic) processes, are measures on the space (A ∞ , F A ∞ ), where F A ∞ is the Borel sigmaalgebra of A ∞ . When talking about joint distributions of N samples, we mean distributions on the space ((A N ) ∞ , F (A N ) ∞ ).

For each k, l ∈ N, let B k,l be the partition of the set A k into k-dimensional cubes with volume h k l = (1/l) k (the cubes start at 0). Moreover, define

B k = ∪ l∈N B k,l and B = ∪ ∞ k=1 B k . The set {B × A ∞ : B ∈ B k,l , k, l ∈ N} generates the Borel σ-algebra on R ∞ = A ∞ . For a set B ∈ B let |B| be the index k of the set B k that B comes from: |B| = k : B ∈ B k .
We use the abbreviation X 1..k for X 1 , . . . , X k . For a sequence x ∈ A n and a set B ∈ B denote ν(x, B) the frequency with which the sequence x falls in the set B.

ν(x, B) := 1 n-|B|+1 n-|B|+1 i=1 I {(X i ,...,X i+|B|-1 )∈B} if n ≥ |B|, 0 otherwise.
A process ρ is stationary if ρ(X 1..|B| = B) = ρ(X t..t+|B|-1 = B) for any B ∈ A * and t ∈ N. We further abbreviate ρ(B) := ρ(X 1..|B| = B). A stationary process ρ is called (stationary) ergodic if the frequency of occurrence of each word B in a sequence X 1 , X 2 , . . . generated by ρ tends to its a priori (or limiting) probability a.s.: ρ(lim n→∞ ν(X 1..n , B) = ρ(B)) = 1. Denote E the set of all stationary ergodic processes.

Definition 1 (distributional distance). The distributional distance is defined for a pair of processes ρ 1 , ρ 2 as follows (e.g. [START_REF] Gray | Probability, Random Processes, and Ergodic Properties[END_REF])

d(ρ 1 , ρ 2 ) = ∞ m,l=1 w m w l B∈B m,l |ρ 1 (B) -ρ 2 (B)|,
where w j = 2 -j .

(The weights in the definition are fixed for the sake of concreteness only; we could take any other summable sequence of positive weights instead.) In words, we are taking a sum over a series of partitions into cubes of decreasing volume (indexed by l) of all sets A k , k ∈ N, and count the differences in probabilities of all cubes in all these partitions. These differences in probabilities are weighted: smaller weights are given to larger k and finer partitions. It is easy to see that d is a metric. We refer to [START_REF] Gray | Probability, Random Processes, and Ergodic Properties[END_REF] for more information on this metric and its properties.

The clustering algorithms presented below are based on empirical estimates of the distance d:

d(X 1 1..n1 , X 2 1..n2 ) = ∞ m,l=1 w m w l B∈B m,l |ν(X 1 1..n1 , B) -ν(X 2 1..n2 , B)|, (1)
where

n 1 , n 2 ∈ N, ρ ∈ S, X i 1..ni ∈ A ni .
Although the expression (1) involves taking three infinite sums, it will be shown below that it can be easily calculated.

Lemma 1 ( d is consistent). Let ρ 1 , ρ 2 ∈ E and let two samples x 1 = X 1 1..n1 and x 2 = X 2 1..n2 be generated by a distribution ρ such that the marginal distri-bution of X i 1..n1 is ρ i , i = 1, 2, and the joint distribution ρ is stationary ergodic. Then

lim n1,n2→∞ d(X 1 1..n1 , X 2 1..n2 ) = d(ρ 1 , ρ 2 ) ρ-a.s.
Proof. The idea of the proof is simple: for each set B ∈ B, the frequency with which the sample x 1 falls into B converges to the probability ρ 1 (B), and analogously for the second sample. When the sample sizes grow, there will be more and more sets B ∈ B whose frequencies have already converged to the probabilities, so that the cumulative weight of those sets whose frequencies have not converged yet, will tend to 0.

For any ε > 0 we can find an index J such that ∞ i,j=J w i w j < ε/3. Moreover, for each m, l we can find such elements B m,l 1 , . . . , B m,l t m,l , for some t m,l ∈ N, of the partition B m,l that ρ i (∪

t m,l i=1 B m,l i ) ≥ 1 -ε/6Jw m w l . For each B m,l j , where m, l ≤ J and j ≤ t m,l , we have ν((X 1 1 , . . . , X 1 n1 ), B m,l j ) → ρ 1 (B m,l j ) a.s., so that |ν((X 1 1 , . . . , X 1 n1 ), B m,l j ) -ρ 1 (B m,l j )| < ρ 1 (B m,l j )ε/(6Jw j )
for all n 1 ≥ u, for some u ∈ N; define U m,l j := u. Let U := max m,l≤J,j≤t m,l U m,l j (U depends on the realization X 1 1 , X 1 2 , . . . ). Define analogously V for the sequence (X 2 1 , X 2 2 , . . . ). Thus for n 1 > U and n 2 > V we have

| d(x1, x2) -d(ρ1, ρ2)| = ∞ m,l=1 wmw l B∈B k,l |ν(x1, B) -ν(x2, B)| -|ρ1(B) -ρ2(B)| ≤ ∞ m,l=1 wmw l B∈B k,l wi |ν(x1, B) -ρ1(B)| + |ν(x2, B) -ρ2(B)| ≤ J m,l=1 wmw l t k,l i=1 |ν(x1, B m,l i ) -ρ1(B m,l i )| + |ν(x2, B m,l i ) -ρ2(B m,l i )| + 2ε/3 ≤ J m,l=1 wmw l t k,l i=1 (ρ1(B m,l i )ε/(6Jwmw l ) + ρ2(B m,l i )ε/(6Jwmw l )) + 2ε/3 ≤ ε,
which proves the statement.

Main results

The clustering problem can be defined as follows. We are given N samples x 1 , . . . , x N , where each sample x i is a string of length n i of symbols from A:

x i = X i 1..ni .
Each sample is generated by one out of k different unknown stationary ergodic distributions ρ 1 , . . . , ρ k ∈ E. Thus, there is a partitioning

I = {I 1 , . . . , I k } of the set {1..N } into k disjoint sub- sets I j , j = 1..k {1..N } = ∪ k j=1 I j ,
such that x j , 1 ≤ j ≤ N is generated by ρ j if and only if j ∈ I j . The partitioning I is called the target clustering and the sets I i , 1 ≤ i ≤ k, are called the target clusters. Given samples x 1 , . . . , x N and a target clustering I, let I(x) denote the cluster that contains x.

A clustering function F takes a finite number of samples x 1 , . . . , x N and an optional parameter k (the target number of clusters) and outputs a partition

F (x 1 , . . . , x N , (k)) = {T 1 , . . . , T k } of the set {1..N }.
Definition 2 (asymptotic consistency). Let a finite number N of samples be given, and let the target clustering partition be I. Define n = min{n 1 , . . . , n N }. A clustering function F is strongly asymptotically consistent if F (x 1 , . . . , x N , (k)) = I from some n on with probability 1. A clustering function is weakly asymptotically consistent if P (F (x 1 , . . . , x N , (k)) = I) → 1.

Note that the consistency is asymptotic with respect to the minimal length of the sample, and not with respect to the number of samples.

Known number of clusters

Algorithm 1 is a simple clustering algorithm, which, given the number k of clusters, will be shown to be consistent under most general assumptions. It works as follows. The point x 1 is assigned to the first cluster. Next, find the point that is farthest away from x 1 in the empirical distributional distance d, and assign this point to the second cluster. For each j = 3..k, find a point that maximizes the minimal distance to those points already assigned to clusters, and assign it to the cluster j. Thus we have one point in each of the k clusters. Next simply assign each of the remaining points to the cluster that contains the closest points from those k already assigned. One can notice that Algorithm 1 is just one iteration of the k-means algorithm, with so-called farthest-point initialization [START_REF] Katsavounidis | A new initialization technique for generalized Lloyd iteration[END_REF], and a specially designed distance.

Algorithm 1 The case of known number of clusters k

INPUT: The number of clusters k, samples x 1 , . . . , x N . Initialize:

j := 1, c 1 := 1, T 1 := {x c1 }. for j := 2 to k do c j := argmax{i = 1, . . . , N : min j-1 t=1 d(x i , x ct )} T j := {x cj } end for for i = 1 to N do Put x i into the set T argmin k j=1 d(xi,xc j )
end for OUTPUT: the sets T j , j = 1..k.

Proposition 1 (calculating d(x 1 , x 2 )). For two samples x 1 = X 1 1..n1 and x 2 = X 2 1..n2 the computational complexity (time and space) of calculating the empirical distributional distance d(x 1 , x 2 ) (1) is O(n 2 log s -1 min ), where n = max(n 1 , n 2 ) and

s min = min i=1..n1,j=1..n2,X 1 i =X 2 j |X 1 i -X 2 j |.
Proof. First, observe that for fixed m and l, the sum

T m,l := B∈B m,l |ν(X 1 1..n1 , B) -ν(X 2 1..n2 , B)| (2)
has not more than n 1 + n 2 -2m + 2 non-zero terms (assuming m ≤ n 1 , n 2 ; the other case is obvious). Indeed, for each i = 0, 1, in the sample x i there are

n i -m + 1 tuples of size k: X i 1..m , X i 2..m+1 , . . . , X i n1-m+1..n1 . Therefore, the complexity of calculating T m,l is O(n 1 + n 2 -2m + 2) = O(n).
Furthermore, observe that for each m, for all l > log s -1 min the term T m,l is constant. Therefore, it is enough to calculate T m,1 , . . . , T m,log s -1 min , since for fixed m

∞ l=1 wmw l T m,l = wmw log s -1 min T m,log s -1 min + log s -1 min l=1 wmw l T m,l
(that is, we double the weight of the last nonzero term). Thus, the complexity of calculating

∞ l=1 w m w l T m,l is O(n log s -1 min ). Finally, for all m > n we have T m,l = 0. Since d(x 1 , x 2 ) = ∞ m,l=1 w m , w l T m,
l , the statement is proven. Theorem 1. Let N ∈ N and suppose that the samples x 1 , . . . , x N are generated in such a way that the joint distribution is stationary ergodic. If the correct number of clusters k is known, then Algorithm 1 is strongly asymptotically consistent. Algorithm 1 makes O(kN ) calculations of d(•, •), so that its computational complexity is O(kN n 2 max log s -1 min ), where n max = max k i=1 n i and

s min = min u,v=1..N,u =v,i=1..nu,j=1..nv ,X u i =X v j |X u i -X v j |.
Observe that the samples are not required to be generated independently. The only requirement on the distribution of samples is that the joint distribution is stationary ergodic. This is perhaps one of the mildest possible probabilistic assumptions.

Proof. By Lemma 1, d(x i , x j ), i, j ∈ {1..N } converges to 0 if and only if x i and x j are in the same cluster. Since there are only finitely many samples x i , there exists some δ > 0 such that, from some n on, we will have d(x i , x j ) < δ if x i , x j belong to the same target cluster (I(x i ) = I(x j )), and d(x i , x j ) > δ otherwise (I(x i ) = I(x j )). Therefore, from some n on, for every j ≤ k we will have max{i = 1, . . . , N : min j-1 t=1 d(x i , x ct )} > δ and the sample x cj , where c j = argmax{i = 1, . . . , N : min j-1 t=1 d(x i , x ct )}, will be selected from a target cluster that does not contain any x ci , i < j. The consistency statement follows.

Next, let us find how many pairwise distance estimates d(x i , x j ) the algorithm has to make. On the first iteration of the loop, it has to calculate d(x i , x c1 ) for all i = 1..N . On the second iteration, it needs again d(x i , x c1 ) for all i = 1..N , which are already calculated, and also d(x i , x c2 ) for all i = 1..N , and so on: on jth iteration of the loop we need to calculate d(x i , x cj ), i = 1..N , which gives at most kN pairwise distance calculations in total. The statement about computational complexity follows from this and Proposition 1: indeed, apart from the calculation of d, the rest of the computations is of order O(kN ).

Complexity-precision trade-off. The bound on the computational complexity of Algorithm 1, given in Theorem 1, is given for the case of precisely calculated distance estimates d(•, •). However, precise estimates are not needed if we only want to have an asymptotically consistent algorithm. Indeed, following the proof of Lemma 1, it is easy to check that if we replace in (1) the infinite sums with sums over any number of terms m n , l n that grows to infinity with n = min(n 1 , n 2 ), and if we replace partitions B m,l by their (finite) subsets B m,l,n which increase to B m,l , then we still have a consistent estimate of d(•, •).

Definition 3 ( ď). Let m n , l n be some sequences of numbers, B m,l,n ⊂ B m,l for all m, l, n ∈ N, and denote

n := min{n 1 , n 2 }. Define ď(X 1 1..n1 , X 2 1..n2 ) := mn m=1 ln l=1 w m w l B∈B m,l,n |ν(X 1 1..n1 , B) -ν(X 2 1..n2 , B)|. (3)
Lemma 2 ( ď is consistent). Assume the conditions of Lemma 1. Let l n and m n be any sequences of integers that go to infinity with n, and let, for each m, l ∈ N, the sets B m,l,n , n ∈ N be an increasing sequence of subsets of B m,l , such that ∪ n∈N B m,l,n = B m,l . Then

lim n1,n2→∞ ď(X 1 1..n1 , X 2 1..n2 ) = d(ρ 1 , ρ 2 ) ρ-a.s.. Proof. It is enough to observe that lim n1,n2→∞ mn m=1 ln l=1 w m w l B∈B m,l,n |ρ 1 (B) -ρ 2 (B)| = d(ρ 1 , ρ 2 ),
and then follow the proof of Lemma 1.

If we use the estimate ď(•, •) in Algorithm 1 (instead of d(•, •)), then we still get an asymptotically consistent clustering function. Thus the following statement holds true.

Proposition 2. Assume the conditions of Theorem 1. For all sequences m n , l n of numbers that increase to infinity with n, there is a strongly asymptotically consistent clustering algorithm, whose computational complexity is O(kN n max m nmax l nmax ).

On the one hand, Proposition 2 can be thought of as an artifact of the asymptotic definition of consistency; on the other hand, in practice precise calculation of d(•, •) is hardly necessary. What we get from Proposition 2 is the possibility to select the appropriate trade-off between the computational burden, and the precision of clustering before asymptotic.

Note that the bound in Proposition 2 does not involve the sizes of the sets B m,l,n ; in particular, one can take B m,l,n = B m,l for all n. This is because, for every two samples X 1 1..n and X 2 1..n , this sum has no more than 2n non-zero terms, whatever are m, l. However, in the following section, where we are after clustering with an unknown number of clusters k, and thus after controlled rates of convergence, the sizes of the sets B m,l,n will appear in the bounds.

Unknown number of clusters

So far we have shown that when the number of clusters is known in advance, consistent clustering is possible under the only assumption that the joint distribution of the samples is stationary ergodic. However, under this assumption, in general, consistent clustering with unknown number of clusters is impossible. Indeed, as was shown in Ryabko (2010b), when we have only two binary-valued samples, generated independently by two stationary ergodic distributions, it is impossible to decide whether they have been generated by the same or by different distributions, even in the sense of weak asymptotic consistency (this holds even if the distributions come from a smaller class: the set of all B-processes). Therefore, if the number of clusters is unknown, we have to settle for less, which means that we have to make stronger assumptions on the data. What we need is known rates of convergence of frequencies to their expectations. Such rates are provided by assumptions on the mixing rates of the distribution generating the data. Here we will show that under rather mild assumptions on the mixing rates (and, again, without any modeling assumptions or assumptions of independence), consistent clustering is possible when the number of clusters is unknown.

In this section we assume that all the samples are [0, 1]-valued (that is, X j i ∈ [0, 1]); extension to arbitrary bounded (multidimensional) ranges is straightforward. Next we introduce mixing coefficients, mainly following [START_REF] Bosq | Nonparametric Statistics for Stochastic Processes[END_REF] in formulations. Informally, mixing coefficients of a stochastic process measure how fast the process forgets about its past. Any one-way infinite stationary process X 1 , X 2 , . . . can be extended backwards to make a two-way infinite process . . . , X -1 , X 0 , X 1 , . . . with the same distribution. In the definition below we assume such an extension. Define the α mixing coefficients as

α(n) = sup A∈σ(...,X-1,X0),B∈σ(Xn,Xn+1,... )) |P (A ∩ B) -P (A)P (B)|, (4)
where σ(..) stays for the sigma-algebra generated by random variables in brackets. These coefficients are non-increasing. A process is called strongly α-mixing if α(n) → 0. Many important classes of processes satisfy the mixing conditions. For example, if a process is a stationary irreducible aperiodic Hidden Markov process, then it is α-mixing. If the underlying Markov chain is finite-state, then the coefficients decrease exponentially fast. Other probabilistic assumptions can be used to obtain bounds on the mixing coefficients, see e.g. [START_REF] Bradley | Basic properties of strong mixing conditions. A survey and some open questions[END_REF] and references therein. Algorithm 2 is very simple. Its inputs are: samples x 1 , . . . , x N ; the threshold level δ ∈ (0, 1), the parameters m, l ∈ N, B m,l,n . The algorithm assigns to the same cluster all samples which are at most δ-far from each other, as measured by ď(•, •). The estimate ď(•, •) can be calculated in the same way as d(•, •) (see Proposition 1 and its proof). We do not give a pseudo code implementation of this algorithm, since it's rather obvious.

The idea is that the threshold level δ is selected If, for every pair i, j of samples, ď(x i , x j ) < δ n if and only if I(x i ) = I(x j ), then Algorithm 2 gives a correct answer. Therefore, taking the bounds ( 7) and ( 10) together for each of the N (N + 1)/2 pairs of samples, we obtain (5). The complexity statement can be established analogously to that in Theorem 1.

While Theorem 2 shows that α-mixing with a known bound on the coefficients is sufficient to achieve asymptotic consistency, the bound (5) on the probability of error includes as multiplicative terms all the parameters m n , l n and b n of the algorithm, which can make it large for practically useful choices of the parameters. The multiplicative factors are due to the fact that we take a bound on the divergence of each individual frequency of each cell of each partition from its expectation, and then take a union bound over all of these. To obtain a more realistic performance guarantee, we would like to have a bound on the divergence of all the frequencies of all cells of a given partition from their expectations. Such uniform divergence estimates are possible under stronger assumptions; namely, they can be established under some assumptions on β-mixing coefficients, which are defined as follows

β(n) = E sup
B∈σ(Xn,... ))

|P (B) -P (B|σ(. . . , X 0 ))|.

These coefficients satisfy 2α(n) ≤ β(n) (see e.g. [START_REF] Bosq | Nonparametric Statistics for Stochastic Processes[END_REF]), so assumptions on the speed of decrease of β-coefficients are stronger. Using the uniform bounds given in [START_REF] Karandikara | Rates of uniform convergence of empirical means with mixing processes[END_REF], one can obtain a statement similarto that in Theorem 2, with α-mixing replaced by β-mixing, and without the multiplicative factor b n .

Conclusion

We have proposed a framework for defining consistency of clustering algorithms, when the data comes as a set of samples drawn from stationary processes.

The main advantage of this framework is its generality: no assumptions have to be made on the distribution of the data, beyond stationarity and ergodicity.

The proposed notion of consistency is so simple and natural, that it may be suggested to be used as a basic sanity-check for all clustering algorithms that are used on sequence-like data. For example, it is easy to see that the k-means algorithm will be consistent with some initializations (e.g. with the one used in Algorithm 1) but not with others (e.g. not with the random one).

While the algorithms that we presented to demonstrate the existence of consistent clustering methods are computationally efficient and easy to implement, the main value of the established results is theoretical. As it was mentioned in the introduction, it can be suggested that for practical applications empirical estimates of the distributional distance can be replaced with distances based on data compression, in the spirit of [START_REF] Ryabko | Universal codes as a basis for time series testing[END_REF]; [START_REF] Cilibrasi | Clustering by compression[END_REF]; [START_REF] Ryabko | Compression-based methods for nonparametric prediction and estimation of some characteristics of time series[END_REF].

Another direction for future research concerns optimal bounds on the speed of convergence: while we show that such bounds can be obtained (of course, only in the case of known mixing rates), finding practical and tight bounds, for different notions of mixing rates, remains open.

Finally, here we have only considered the setting in which the number N of samples is fixed, while the asymptotic is with respect to the lengths of the samples. For on-line clustering problems, it would be interesting to consider the formulation where both N and the lengths of the samples grow.

according to the minimal length of a sample and the (known bounds on) mixing rates of the process ρ generating the samples (see Theorem 2).

The next theorem shows that, if the joint distribution of the samples satisfies α(n) ≤ α n → 0, where α n are known, then one can select (based on α n only) the parameters of Algorithm 2 in such a way that it is weakly asymptotically consistent. Moreover, a bound on the probability of error before asymptotic is provided.

Theorem 2 (Algorithm 2 is consistent, unknown k). Fix sequences α n ∈ (0, 1), m n , l n , b n ∈ N, and let B m,l,n ⊂ B m,l be an increasing sequence of finite sets, for each m, l ∈ N. Set b n := max l≤ln,m≤mn |B m,l,n |. Let also δ n ∈ (0, 1). Let N ∈ N and suppose that the samples x 1 , . . . , x N are generated in such a way that the (unknown) joint distribution ρ is stationary ergodic, and satisfies α n (ρ) ≤ α n , for all n ∈ N. Then for every sequence q n ∈ [0..n/2], Algorithm 2, with the above parameters, satisfies

where

T is the partition output by the algorithm, I is the target clustering, ε ρ is a constant that depends only on ρ, and n = min i=1..N n i .

In particular, if α n = o(1), then, selecting the parameters in such a way that

n → ∞, for all m, l ∈ N, and, finally,

as is always possible, Algorithm 2 is weakly asymptotically consistent (with the number of clusters k unknown). The computational complexity of Algorithm 2 is O(N 2 m nmax l nmax b nmax ), and is bounded by O(N 2 n 2 max log s -1 min ), where n max and log s -1 min are defined as in Theorem 1.

Proof. We use the following bound from [START_REF] Bosq | Nonparametric Statistics for Stochastic Processes[END_REF]: for any zero-mean random process Y 1 , Y 2 , . . . , every n ∈ N and every q ∈ [1..n/2] we have

For every j = 1..N , every m < n, l ∈ N, and B ∈ B m,l , define the processes Y j 1 , Y j 2 , . . . , where

It is easy to see that α-mixing coefficients for this process satisfy α(n) ≤ α n-2m . Thus,

Then for every i, j ∈ [1.

.N ] such that I(x i ) = I(x j ) (that is, x i and x j are in the same cluster) we have

Using the union bound, summing over m, l, and B, we obtain

Next, let i, j be such that I(x i ) = I(x j ). Then, for some m i,j , l i,j ∈ N there is B i,j ∈ B mi,j ,li,j such that |ρ(X i 1..|Bi,j | ∈ B i,j )ρ(X j 1..|Bi,j | ∈ B i,j )| > 2τ i,j for some τ i,j > 0. Then for every ε < τ i,j /2 we have

Moreover, for ε < w mi,j w li,j τ i,j /2 ρ( ď(x i , x j ) > ε) ≤ 2γ n (w mi,j w li,j τ i,j ). ( 9)

Define ε ρ := min i,j=1..N :I(xi) =I(xj ) w mi,j w li,j τ i,j /2. Clearly, from this and (8), for every ε < 2ε ρ we obtain ρ( ď(x i , x j ) > ε) ≤ 2γ n (ε ρ ).

(10)


Helgi Björnsson

Philip Owens

Olav Slaymaker

) Arnold

JÖKULHLAUPS IN ICELAND: SOURCES, RELEASE AND DRAINAGE

Jökulhlaups in Iceland may originate from marginal or subglacial sources of water melted by atmospheric processes, permanent geothermal heat or volcanic eruptions. Glacier-volcano interactions produce meltwater that either drains toward the glacier margin or accumulates in subglacial lakes. Accumulated meltwater drains periodically in jökulhlaups from the subglacial lakes and occasionally during volcanic eruptions. During the 20 th century 15 subglacial volcanic eruptions (10 major and 5 minor events) took place, about one-third of all eruptions in Iceland during that century.

The release of meltwater from glacial lakes can take place as a result of two different conduit initiation mechanisms and the subsequent drainage from the lake occurs by two different modes. Drainage can begin at pressures lower than the ice overburden in conduits that expand slowly over days or weeks due to melting of the ice walls by frictional and sensible heat in the water. Alternatively, the lake level may rise until the glacier is lifted along the flowpath to make space for the water and water discharges rise linearly, peaking in a time interval of several hours to 1-2 days. In this case, discharge rises faster than can be accommodated by melting of the conduits. The rapidly-rising floods are often associated with large discharges and floods following rapid filling of subglacial lakes during subglacial eruptions or dumping of one marginal lake into another. Jökulhlaups during eruptions in steep ice and snowcovered stratovolcanoes are swift and dangerous and may become lahars and debris-laden floods. Normally jökulhlaups do not lead to glacier surges but eruptions in ice-capped stratovolcanoes have caused rapid and extensive glacier sliding.

Jökulhlaups have significant landscaping potential: they erode large canyons and transport and deposit enormous quantities of sediment and icebergs over vast outwash plains and sandur deltas. Jökulhlaups from subglacial lakes may transport on the order of 10 7 tons of sediment per event but during violent volcanic eruptions the sediment load has been 10 8 tons. Pleistocene glacial river canyons may have been formed in such catastrophic floods from subglacial lakes. Jökulhlaups have threatened human populations, farms and hydroelectric power plants on glacier-fed rivers. They have damaged cultivated and vegetation areas, disrupted roads on the outwash plains and have even generated flood waves in coastal waters.

Iceland is a unique and valuable study-site for glaciovolcanic interactions. This applies to the heat exchange between magma and the glacier, the dynamical response of the glacier to subglacial eruptions, the structure and growth sequence of hyaloclastite ridges and tuyas formed by subglacial eruptions, and jökulhlaups due to volcanic eruptions. The jökuhlaups can be seen as modern analogues of past megafloods on the Earth and their exploration may improve understanding of icevolcano processes on other planets.

Introduction

Floods can happen where glaciers dam lakes in mountainous areas. Occurring in both the temperate and subpolar regions of the Earth, such floods are called débâcles in the European Alps, aluviones in South America and jökulhlaups in Iceland. A dam of ice or sediment blocks the water to form a lake, while drainage is initiated by an opening of the hydraulic seal, which can be broken either suddenly or gradually. The impounded water is released directly into river channels, and has a typical discharge that is orders of magnitude higher than when running as a direct result of intense ablation. In regions with active, ice-covered volcanoes, meltwater is repeatedly released in floods from lakes that collect at subglacial hydrothermal areas. Occasionally, these floods take place without any significant prior storage of water, since ice melts instantaneously in volcanic eruptions. During the largest glacial floods in history, discharges reached 106 m3 s_1. For comparison, the meltwater that was temporarily stored in lakes at the edges of downwasting Pleistocene ice sheets was released in bursts that were only one order of magnitude larger than this, even though the enormous volumes involved may have altered the circulation of deep water in the North Atlantic Ocean of the late Pleistocene era.

Glacial outbursts can have pronounced geomorphological impacts, since they scour river courses and inundate floodplains. Outbursts result in enormous erosion, for they carry huge loads of sediment and imprint the landscape, past and present, with deep canyons, channelled scabland, ridges standing parallel to the direction of flow, sediment deposited on outwash plains, coarse boulders strewn along riverbanks, kettleholes where massive ice blocks have become stranded and have melted, and breached terminal moraines. Some modern outbursts have produced flood waves in coastal waters (tsunamis). In the North Atlantic, outburst sediments dumped onto the continental shelf and slope have been transported great distances by turbid currents. Outburst floods wreak havoc along their paths, threatening people and livestock, destroying vegetated lowlands, devastating farms, disrupting infrastructure such as roads, bridges and power lines, and threatening hydroelectric plants on glacially fed rivers.

Knowledge of jökulhlaup behaviour is essential for recognizing potential or imminent hazards, predicting and warning of occurrences, enacting preventive measures, assessing consequences and responding for the purpose of civil defence. The goal of this chapter is to outline and describe the following:

(1) the location and geometry of glacial flood sources, including the properties of dams that impound the water;

(2) the accumulation of water leading to outbursts and the conditions in which they begin; (3) the mechanisms and discharge characteristics of outbursts; and (4) case histories of floods, illustrating potential hazards.

Anatomy of glacial lakes and their outburst floods 2.1 Sources of glacial outbursts

Glacial lakes are found in various topographic settings. Meltwater may be impounded within the glacier (englacially and subglacially), on the surface of the glacier (supraglacially) or in lakes formed by dams at the glacier's margin (proglacially). The general characteristics, geometry and filling of glacial lakes can be described by the basic physics of hydrology. The movement of a thin film of water along the glacier base follows the gradient in the fluid potential which is the sum of terms expressing the gravitational potential and the water pressure, pw, assuming the effects of kinetic energy to be negligible. The symbol w represents the density of water and equals 1000 kg m 3 , whereas g equals 9.81 ms -2 and represents the acceleration due to gravity, while z b is the elevation of the glacier substrate above sea level (Figure 8.1). When describing the regional flow of basal water, it has proved useful to present a static approximation of water pressure, equal to the overburden pressure from the ice, where i equals 916 kg m 3 and represents the density of ice, H equals z s -z b and is the thickness of the glacier and z s is the elevation of the ice surface in relation to sea level [START_REF] Shreve | Movement of water in glaciers[END_REF]. Thus the gradient driving the water is This formula predicts that the surface slope of the glacier is some ten times more influential than the slope of its bed in determining the flow of basal water.Glacial lakes may be situated at points where water flows towards a minimum in the total fluid potential. Trapped in such a lake, water is surrounded by a hydraulic seal. As the overlying glacier floats in a state of static equilibrium, and the vertical force balance is reflected by the shape of the lake. The roof of a subglacial lake slopes approximately ten times more steeply than the surface of the ice, and in the opposite direction (Figure 8.2). While resembling a grounded ice shelf, the ice on the perimeter of the lake essentially comprises an ice dam. The state in which there is no gradient driving water inside the lake, , can be used to define the location and geometry of a subglacial reservoir. Hence describes the relationship of the slope in the ice/water outline of the lake to the slope at the upper surface of the glacier (note that there might also be lakes with equal inflow and outflow which would not meet the condition of a zero gradient in relation to fluid potential). Given the glacier's surface and the bedrock geometry, it is possible to assess whether a water reservoir is likely to exist on the glacier bed.

_

The general relationship in eq. ( 3) applies to all types of glacial lakes (Figure 8.2, Table 8.1). Water may gather in a bedrock hollow beneath a relatively flat or dome-shaped glacial surface, (Figure 8.2(a)) -in a type of reservoir which has been delineated beneath today's Antarctic Ice Sheet [START_REF] Oswald | Lakes beneath the Antarctic Ice Sheet[END_REF][START_REF] Ridley | Identification of subglacial lakes using ERS-1 radar altimeter[END_REF][START_REF] Siegert | Physical, chemical and biological processes in Lake Vostok and other Antarctic subglacial lakes[END_REF] and was presumably widespread during the Quaternary glaciations. Another type of lake can form a cupola above the glacier bed, accompanied by a depression in the glacier's surface (Figure 8.2(b),(c)). Subglacial water reservoirs of this sort are common in Iceland, owing to volcanic and geothermal activity which causes the ice to melt and thereby creates depressions in the glacier surface [START_REF] Björnsson | Explanation of jökulhlaups from Grímsvötn, Vatnajökull, Iceland[END_REF][START_REF] Björnsson | Hydrology of ice caps in volcanic regions[END_REF]. Meltwater flows along the bed and accumulates beneath the depression.

Subaerial glacial lakes (marginal or proglacial lakes) are confined by ice on one side and by topographic barriers on the other, for instance by the edges of ravines, riverbeds or main valleys (Figure 8.2(d)). The glacier's surface slopes toward the lake, which stores meltwater from the glacier along with runoff from the surrounding terrain. The lakes formed during the summer at the margins of subpolar glaciers may be sealed by an ice dam frozen to the bed (e.g., [START_REF] Maag | Ice dammed lakes and marginal glacial drainage on Axel Heiberg Island, Canadian Arctic Archipelago[END_REF].

In other instances, a proglacial lake may lie in a depression behind moraine at the front of the glacier, which is typically retreating rapidly, while sediment is deposited too slowly to fill up the over-deepened bed. This happened in the case of the receding late Pleistocene ice sheets and applies to many shrinking twentieth century glaciers. Supraglacial lakes are isolated in depressions on the glacier surface (Figure 8.2(e)), hydrologically separated from the basal drainage system. A final addition to our list might be water stored in cavities located here and there inside the glacier [START_REF] Kamb | Glacier surge mechanism: 1982-1983 surge of Variegated Glacier[END_REF][START_REF] Walder | Hydraulics of subglacial cavities[END_REF][START_REF] Kamb | Glacier surge mechanism based on linked cavity configuration of the basal water conduit system[END_REF].

Drainage of glacial lakes

In general, glacial lakes of every type can drain either continuously or in episodic bursts. Marginal and proglacial lakes sometimes drain constantly via subaerial spillways over the rock or sediment barrier that contains them. Such barriers might consist of moraine, volcanic material or landslides. Nevertheless, lakes held back by these materials may break forth abruptly if the dams fail. Floods released suddenly when sediment or ice impoundments are breached rise almost linearly over a period of minutes or hours. They reach a high, sharp discharge peak and then fall along a steep recession limb (Figure 8.3(b)). Sediment dams can fail because of overtopping or accelerated fluvial erosion, which results in retrogressive incision enlarging the point of outflow. Moreover, a break in sediment dams can be caused by seepage and piping (progressive groundwater movement) within the sediment barrier, resulting in liquefied flows and embankment slips that weaken or disintegrate the dam. Tectonic activity and landslides are further threats to sediment dams, while breaching may also be triggered by flood water entering the lake or by heavy rain leading to a rapid rise in the lake level.

Finally, dam failure can be generated by waves from landslides, rock falls, ice avalanches, calving icebergs or glacier surges into the lake. Providing the topographic barriers hold, on the other hand, proglacial lakes serve to dampen jökulhlaups from other areas. Any outburst that does occur may be a one-time event if it ruins the dam. Where the barrier is a wall of ice, it may break down mechanically, similarly to a sediment dam. Marginal lakes at subpolar glaciers, where the ice barricade is frozen to the bed, are typically breached as lake water spills over the top of the dam into a supraglacial channel that melts into a bigger breach -commonly at the juxtaposition of the glacier and a rock wall (e.g., [START_REF] Schytt | Lateral drainage channels along the northern side of the Moltke glacier, North-West Greenland[END_REF][START_REF] Maag | Ice dammed lakes and marginal glacial drainage on Axel Heiberg Island, Canadian Arctic Archipelago[END_REF]. The rate of ice melt, the level of the lake in relation to the outlet and the hypsometry of the water reservoir dictate the progress of lake drainage. As the lake surface falls, the breach may broaden and deepen, even undercutting the ice wall so as to cause calving. When subglacial lakes are situated in bedrock hollows under flat or dome-shaped glacial surfaces, they are not expected to expand and drain in sudden outbursts, except perhaps during rapid deglaciation which drastically alters glacier geometry and drainage [START_REF] Goodwin | The nature and origin of a jökulhlaup near Casey Station, Antarctica[END_REF]. In contrast, when icedammed lakes, regardless of whether they are positioned subglacially or marginally, receive water inflow and are gradually made to expand, basal water pressure will increase and the overlying ice will be raised. Eventually, the hydraulic seal of the ice dam will be ruptured, so that water will begin to drain from the lake via a basal pathway. Seepage beginning beneath the ice blockage causes enlargement of the drainage system, initiating a flood under the surrounding ice. In a typical case, though for reasons not yet fully understood, leakage starts before the lake has reached the level which would cause flotation of the ice dam [START_REF] Björnsson | Subglacial water reservoirs, jökulhlaups and volcanic eruptions[END_REF][START_REF] Björnsson | Hydrology of ice caps in volcanic regions[END_REF]. After discharge has begun, pressure from the ice constricts the passageway, and water flow at an early stage in the jökulhlaup correlates primarily with enlargement of the ice tunnel owing to heat from friction against the flowing water and to thermal energy stored in the lake [START_REF] Nye | Water flow in glaciers: jökulhlaups, tunnels and veins[END_REF]Spring andHutter, 1981, 1982;[START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF][START_REF] Björnsson | Jökulhlaups in Iceland: prediction, characteristics and simulation[END_REF]. Increasing as an approximate exponent of time over a matter of hours or days, the discharge falls quickly after peaking (Figure 8.3(a)). The recession stage of the hydrograph sets in when tunnel deformation begins to exceed enlargement by melting. The overlying ice may collapse abruptly into the tunnel and seal the lake again, sometimes before it is empty, with new water beginning to accumulate until another jökulhlaup occurs. The timing of bursts depends on what lake level will provide the subglacial water pressure necessary for breaking the hydraulic seal affected by the overburden pressure at the ice dam; therefore, if long-term records of lake levels are available, the elevation at which a jökulhlaup will begin can be predicted with some precision. Since the frequency of outbursts depends on the rate at which a lake is filled, marginal lakes often experience them at the end of the ablation season, when meltwater storage climaxes. Fluctuations in the thickness of the blocking ice, resulting from climatic variations or surges, may modify the outburst cycle or even stop bursts completely. Occasionally, jökulhlaups are triggered by flotation of the ice dam. Rather than initial drainage from the lake being localized in one narrow conduit, the water is suddenly released as a sheet flow, surging downhill and propagating a subglacial pressure wave, which exceeds the ice overburden and lifts the glacier in order to create space for the water. In this instance, discharge increases faster than can be explained by conduits expanding through melting [START_REF] Björnsson | Jökulhlaups in Iceland: prediction, characteristics and simulation[END_REF][START_REF] Björnsson | Grímsvatnahlaup fyrr og nú[END_REF][START_REF] Björnsson | Subglacial lakes and jökulhlaups in Iceland[END_REF][START_REF] Björnsson | The extraordinary 1996 jökulhlaup from Grímsvötn, Vatnajökull, Iceland[END_REF][START_REF] Jóhannesson | Propagation of a subglacial flood wave during the initiation of jökulhlaup[END_REF]. The resulting hydrograph (Figure 8.3(b)) presents a rapid rise to its peak, succeeded by a more gentle waning stage. While sheet flows may be followed by drainage through high-capacity conduits, swift floods may instead manage to cause hydrofracturing and force their way englacially from the base of the glacier to its surface [START_REF] Liestøl | Setevatnet, a glacier dammed lake in Spitsbergen[END_REF][START_REF] Roberts | Ice fracturing during jökulhlaups: implications for englacial floodwater routing and outlet development[END_REF][START_REF] Russell | Flash flood at Sólheimajökull heralds the reawakening of an Icelandic subglacial volcano[END_REF][START_REF] Roberts | Controls on supraglacial outlet development during glacial outburst floods[END_REF].

Supraglacial lakes, on the other hand, are usually transient features (e.g., [START_REF] Björnsson | Marginal and supraglacial lakes in Iceland[END_REF], because they form englacial channels and drain down to the subglacial water system. Water that collects in lakes on polar ice masses frequently freezes and unites with the ice during the winter. Where glacial surges occur, floods may come about when a surge terminates and drainage of the water from subglacial cavities switches from a distributed system -conducting water slowly downglacier -to a quickly effective network of tunnels [START_REF] Kamb | Glacier surge mechanism: 1982-1983 surge of Variegated Glacier[END_REF][START_REF] Kamb | Glacier surge mechanism based on linked cavity configuration of the basal water conduit system[END_REF]. While the outlets for these bodies of water are not fixed, they may be expected to empty into rivers running from the glacier before the surge. As a final case, there have been reports of frequent abrupt releases of water, lasting from minutes to some hours, from diminutive amounts of subglacial or englacial storage, but the nature of these releases is poorly described [START_REF] Haeberli | Frequency and characteristics of glacier floods in the Swiss Alps[END_REF]Drieger and Fountain, 1989;Walder and Diedger, 1995).

Impacts of jökulhlaups

The impact of outbursts corresponds to their discharge rate, the peak and nature of the flow, sediment load, routeway topography and frequency. Depending on the concentration of sediment, jökulhlaups range across a continuum from water floods to hyperconcentrated flows and debris flows. Most jökulhlaups from lakes dammed by ice contain relatively small concentrations of sediment (<40% by weight and 20% by volume) and can be described adequately in terms of standard hydraulics in turbulent water flow (calculating flow by Manning's equation and sediment transport by Einstein's equation). In the most catastrophic floods, intense erosion may occur through cavitation; the enormous velocity of flow reduces absolute pressure, causing air bubbles to form, which collapse and generate shock waves. Conditions for this are favourable in constricted channels at low water depths, producing channelled scabland features, whereas more uniform flow produces a topography of subdued erosion.

Jökulhlaups triggered by the failure of a sediment dam or by volcanic eruptions may temporarily contain high concentrations of sediment. Hyperconcentrated jökulhlaups represent moderately turbulent to laminar flow of non-Newtonian fluids, with sediment concentrations varying between 40% and 70% by weight (20% and 47% by volume). Debris flows are laminar, containing a uniform sediment concentration ranging from 70% to 90% by weight and from 47% to 77% by volume [START_REF] Costa | Rheologic, geomorphic, and sedimentologic differentiation of water floods, hyperconcentrated flows, and debris flows[END_REF]. Hyperconcentrated flows produce crudely stratified, less finely sorted deposits than water floods, and the deposits from debris flows are composed of poorly sorted clasts. River courses and landforms on outwash plains have adjusted to the magnitude of frequent or cyclic jökulhlaups, i.e., those occurring with annual regularity or at intervals of several years. During rare extensive floods, however, erosion, transportation and downstream deposition modify river courses extensively. During the aftermath, flood channels remain destabilized, which may lead to slumping and debris flows.

Estimating the discharge of jökulhlaups 3.1 Measured and calculated discharge

Direct measurements of water current velocity and discharge are usually precluded in major jökulhlaups. Conventional stream-gauging stations are rarely set up for recording extreme floods, and even if the streams have been gauged no developed curves are available for comparing stage and streamflow. Large-scale floods overflow the normal riverbanks, distort river courses and damage or destroy instruments. Although a number of jökulhlaups have been gauged some distance downstream from glacier margins, the flood wave may have been significantly attenuated in the intervening interval by passing through such storage bodies as braided channels or lakes.

Indirect methods can be applied to estimate average stream velocity, using hydraulic calculations along with field evidence of channel geometry (including cross-sectional area, heights and dates of flood levels, and channel roughness). This approach employs Manning's equation, which was developed empirically for open, canalized waterways and which relates energy dissipation to the roughness of flood paths. In such an approximation, the surface slope at high water becomes the basis for determining the energy slope. Because of nonuniform flow, computations must take into account the conservation of mass and energy as the flood moves forward [START_REF] Webb | One-dimensional estimation techniques for discharges of paleofloods and historical floods[END_REF]. The maximum flood stages are reconstructed by inspecting eroded channel margins, finding the highest flotation elevation of the largest boulders that were encased by ice and drifted downstream (ice-rafted erratics), and locating water divides where floodwater spilled over cols. The reconstruction of flood discharge obviously may be complicated when sedimentation at the end of the flood changes the area of the channel crosssection as well as the roughness of the flood course.

Prediction of discharge by theoretical and empirical methods

For the purpose of risk assessment, both empirical and theoretical methods can be relevant to predicting the probable rate of change of discharge, peak discharge and duration of jökulhlaups.

Subglacial drainage

Theoretical models of jökulhlaups discharging through water tunnels in the glacier base have been derived by [START_REF] Nye | Water flow in glaciers: jökulhlaups, tunnels and veins[END_REF]), [START_REF] Spring | Numerical studies of jökulhlaups[END_REF] and [START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF]. These models are based on the physics of mass continuity, momentum, energy conservation and heat transfer, and they describe how water is driven by a fluid potential radient through a tunnel of given roughness. From his general model, [START_REF] Nye | Water flow in glaciers: jökulhlaups, tunnels and veins[END_REF] derived an analytical solution, which predicted discharge, Q, to rise asymptotically with time as Q (t)_k (1/t)4, if confinement by the overburden was neglected and expansion of the ice tunnel was solely attributed to the instantaneous transfer of frictional heat (i.e., the dissipation of potential energy) from the flowing water to the enclosing ice. Numerical models for simulating the entire hydrograph were derived by [START_REF] Spring | Numerical studies of jökulhlaups[END_REF], who included lake temperature, and [START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF], who added lake geometry. [START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF] successfully simulated jökulhlaups from Lake Hazard (the Yukon, Canada) and Summit Lake (British Columbia, Canada), which are dammed by marginal ice. [START_REF] Björnsson | Jökulhlaups in Iceland: prediction, characteristics and simulation[END_REF] tested [START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF] modification of [START_REF] Nye | Water flow in glaciers: jökulhlaups, tunnels and veins[END_REF] general model, applying it to Icelandic jökulhlaups and concluding that the amended model in some respects successfully simulated jökulhlaups from the subglacial lake Grímsvötn in Vatnajökull. In general, the ascending slopes simulated in the graph corresponded to the measured ones. The peak in the computed hydrographs, however, was not as sharp as the actual climaxes, rendering the simulation of the descending limbs unsatisfactory. This presumably happens because, in the model, the tunnel is assumed to be cylindrical. It was only possible to simulate the rapid rise of some outbursts in Iceland (from subglacial as well as marginal lakes) by assuming a lake temperature several degrees above the melting point, which may suggest that thermal energy stored in these bodies of water contributes to tunnel expansion and thereby affects the discharge rate. The values computed for lake temperatures, however, should not be taken seriously, as the theory of heat transfer is questionable. The simulation of such swift jökulhlaups completely failed to illustrate the closure of tunnels and the recession of discharge.

An empirically based regression relation between the peak discharge Qmax (in m 3 s-1 ) and the total volume Vt (in 10 6 m 3 ) of water passing through subglacial tunnels in jökulhlaups was formulated by [START_REF] Clague | The magnitude of jökulhlaups[END_REF]:

For jökulhlaups emerging from ten marginal ice-dammed lakes, which ranged in volume from 10 6 to 10 9 m 3 , Clague and Mathews obtained K=75/s m -0.99 and the power coefficient b=0.67. A recent update for 26 marginal ice-dammed lakes throughout the world yielded K=46

s-1 m -1.02 and b=0.66 [START_REF] Walder | Outburst floods from glacier-dammed lakes: the effect of mode of lake drainage on flood magnitude[END_REF]. Referring to eleven jökulhlaups from the Icelandic lake Grímsvötn, [START_REF] Björnsson | Jökulhlaups in Iceland: prediction, characteristics and simulation[END_REF] found K=4.15 10 3 /s m -2.52 and the power coefficient b=1.84. [START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF] derived theoretical relationships for predicting peak discharge, suggesting that b depended on the lake's contribution of stored thermal energy in proportion to the frictional energy dissipated in the jökulhlaup. The outcome of his calculations was that b=0.8 when the thermal energy originating in the lake was dominant in melting the tunnel and b=1.33 when its share was negligible. [START_REF] Ng | On the Clague-Matthews relation for jökulhlaups[END_REF] point out that incomplete lake draining, a phenomenon contrasting with common behaviour in marginal lakes dammed by ice, may explain the deviation of Grímsvötn from statistically derived value.

There is neither a theory nor sufficient empirical data yet available for describing how jökulhlaups drain subglacially at a faster rate than can be explained by the expansion of conduits through melting. This quicker drainage involves the ice overburden being exceeded by water pressure, which lifts the glacier and allows space for the water. Initially propagated as a pressure wave, the water then moves forward in a sheet flow, prior to draining through conduits [START_REF] Björnsson | Grímsvatnahlaup fyrr og nú[END_REF][START_REF] Björnsson | Subglacial lakes and jökulhlaups in Iceland[END_REF][START_REF] Björnsson | The extraordinary 1996 jökulhlaup from Grímsvötn, Vatnajökull, Iceland[END_REF][START_REF] Jóhannesson | Propagation of a subglacial flood wave during the initiation of jökulhlaup[END_REF].

Subaerial drainage

A subaerial burst following the sudden breaching of an ice dam is typically over sooner than a flood exiting through a basal ice tunnel. Discharge in the former outburst may increase linearly with time and, for a given lake volume, peak discharges are significantly higher than for drainage through subglacial tunnels. The size of the outlet and the quantity of the impounded water body determine the peak discharge through the breach.

Physical models of drainage over a subaerial breach have been drawn up along similar lines to those for drainage through subglacial tunnels. [START_REF] Walder | Outburst floods from glacier-dammed lakes: the effect of mode of lake drainage on flood magnitude[END_REF] successfully simulated hydrographs for Lake George in Alaska. The widening of the opening is assumed to be controlled by melting, while the lake discharge spilling over the breach is dictated by the hydraulic conditions of critical flow through an open channel.

Furthermore, an empirical power-law was derived in the form of eq. ( 4), with K=1100/s m 1.69 and b=0.44, i.e., similar figures to those for regression during known outbursts that breached man-made earthen dams, in which instances K=1200/s m -1.56 and b=0.48 [START_REF] Costa | Rheologic, geomorphic, and sedimentologic differentiation of water floods, hyperconcentrated flows, and debris flows[END_REF]. [START_REF] Raymond | Drainage of a glacial lake through an ice spillway[END_REF] made the first attempt to identify and describe by a physical model the processes controlling unstable drainage over a spillway with an ice floor; in other words, they formulated criteria for when discharge water would melt the spillway path down faster than the lake level dropped. Their work successfully explained observations of supraglacial drainage from Black Rapids Glacier, Alaska.

Case studies 4.1 Floods from sediment-dammed lakes

Floods in which lakes breach sediment dams carry large amounts of debris. Generally unpredictable, they are regarded as the most dangerous kind of outbursts, but have been successfully prevented at many hazardous locations by artificial drains through the sediment dams, which restrict lake depths. Advances and subsequent retreats of glaciers in the Little Ice Age created many unstable moraine dams, with examples reported from the European Alps, the Himalaya and Peru. An Austrian valley was flooded in 1874 when the terminal moraine of the Madatschferner glacier gave way and the lake escaped from in front of the retreating ice. The French Tête Rousse débâcle of 1892, released 2 .10 5 m 3 of water and 8.10 5 m 3 of sediment, killed 175 people [START_REF] Lliboutry | Les Catastrophes glaciaires[END_REF]. In 1926 a flood released from the Himalayan Shyok glacier devastated a village and cultivated land 400 km from the source [START_REF] Mason | Indus floods and Shyok glaciers[END_REF], while the Peruvian Jancarurish outburst of 1950 discharged 2 .10 6 m 3 of water and 3 10 6 m 3 of sediment [START_REF] Lliboutry | Glaciological problems set by the control of dangerous lakes in the Cordillera Blanca, Peru. I. Historical failures of morainic dams, their causes and prevention[END_REF]. In British Columbia, debris flows up to 20 m thick have travelled as far as 20 km downvalley after breaching terminal moraines [START_REF] Evans | Recent climatic change and catastrophic geomorphologic processes in mountain environments[END_REF]). As still another example, an ice avalanche from the Langmoche glacier in Nepal broke a moraine dam in 1985, resulting in a flood that destroyed bridges, houses and a hydroelectric plant (Vuichard andZimmermann, 1986, 1987)

Floods from marginal ice-dammed lakes

Jökulhlaups from ice-dammed lakes at glacial edges have posed a serious threat to roads, power lines and the human population in many countries of Europe, North and South America, Asia and New Zealand. In most countries, however, thinning of the ice dams by the warm climate of the twentieth century has led to smaller and more frequent outbursts from marginal lakes dammed by ice. [START_REF] Walder | Outburst floods from glacier-dammed lakes: the effect of mode of lake drainage on flood magnitude[END_REF] recently compiled a comprehensive review of outburst floods from glacially dammed lakes.

Some of the best-documented modern lakes blocked by ice are found in North America. [START_REF] Maag | Ice dammed lakes and marginal glacial drainage on Axel Heiberg Island, Canadian Arctic Archipelago[END_REF] identified 125 lakes with ice dams on Axel Heiberg Island, Canada, and studies of several icedammed lakes in that country have been of major importance for the scientific understanding of jökulhlaups, for example, investigations of Tulsequah Lake, British Columbia [START_REF] Marcus | Periodic drainage of glacier-dammed Tukequant Lake, British Columbia[END_REF]; Summit Lake, British Columbia [START_REF] Mathews | Two self-dumping ice-dammed lakes in British Columbia[END_REF][START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF][START_REF] Mathews | The record of jökulhlaups from Summit Lake, northwestern British Columbia[END_REF]; Hazard Lake, Yukon Territory [START_REF] Clarke | Glacier outburst flood from "Hazard Lake", Yukon Territory, and the problem of flood magnitude prediction[END_REF]; and Flood Lake, British Columbia [START_REF] Clarke | Simulation of the August 1979 sudden discharge of glacier-dammed Flood Lake, British Columbia[END_REF]. [START_REF] Post | Glacier dammed lakes and outburst floods in Alaska[END_REF] identified 750 lakes behind marginal ice dams in Alaska; of these, many have been thoroughly researched, such as Lake George [START_REF] Stone | Alaskan ice-dammed lakes[END_REF][START_REF] Hulsing | The breakout of Alaska's Lake George[END_REF][START_REF] Lipscomb | Flow and hydraulic characteristics of the Knik-Matanuska River estuary, Cook Inlet, southcentral Alaska[END_REF], Snow River [START_REF] Chapman | Jökulhlaups on Snow River in southeastern Alaska: a compilation of recorded and inferred hydrographs and a forecast procedure[END_REF] and Strandline Lake [START_REF] Sturm | A history of jökulhlaups from Strandline Lake, Alaska, U.S.A[END_REF]. The largest observed terrestrial flood from a breached impoundment took place on 8 October 1986, below the ice-dammed Lake Russell, Alaska. A surge had caused Hubbard Glacier, North America's largest tidewater glacier, to advance across the entrance of Russell Fjord, turning it into Lake Russell. A moraine was pushed up infront of the advancing glacier, raising inland water 25.5 m asl before the lake overflowed and cut the dam at the junction of the ice and the valley wall. The entire ice dam was removed within a few hours, with released water amounting to 5.4 10 9 m 3 and the peak discharge reaching 1.5 10 6 m 3 s -1 [START_REF] Mayo | Hubbard Glacier near Yakutat, Alaska -the ice damming and breakout of Russel Fiord/Lake[END_REF][START_REF] Mayo | Advances of Hubbard Glacier and 1986 outburst of Russel Fiord, Alaska, U. S. A[END_REF]. A similar event, though somewhat smaller, occurred in the summer of 2002.

In the Swiss Alps, damage from glacial floods occurs, on average, biennially; 60-70% of the outbursts originate in lakes at glacial margins and 30-40% in pockets of water within glaciers [START_REF] Haeberli | Frequency and characteristics of glacier floods in the Swiss Alps[END_REF]. Nowadays, about 15 ice-marginal lakes in Iceland drain by means of jökulhlaups [START_REF] Thorarinsson | The ice dammed lakes of Iceland with particular reference to their values as indicators of glacier oscillations[END_REF][START_REF] Björnsson | Grímsvatnahlaup fyrr og nú[END_REF] and frequently cause problems for bridges and other road structures. A pioneering thesis was written by [START_REF] Liestøl | Glacier dammed lakes in Norway[END_REF] on glacially dammed lakes in Norway. Outburst floods have been scientifically described in Greenland [START_REF] Schytt | Lateral drainage channels along the northern side of the Moltke glacier, North-West Greenland[END_REF]Lister and Willie, 1957;[START_REF] Dawson | Glacier-dammed lake investigations in the Hullet Lake area, South Greenland. Meddelelser om Grönland[END_REF][START_REF] Russell | A comparison of two recent jökulhlaups from an ice-dammed lake, Söndre Strömfjord, West Greenland[END_REF], Argentina [START_REF] Heinsheimer | Der Durchbruch des Morengletschers, Lago Argentino, Patagonien[END_REF][START_REF] Heinsheimer | Zur Hydrologie und Glaziologie des Lago Argentino und Ventisquero Moreno III[END_REF][START_REF] Fernández | Simulation of flood waves from outburst of glacierdammed lake[END_REF], Pakistan [START_REF] Gunn | The Shyok flood, 1929[END_REF][START_REF] Hewitt | Natural dams and outburst floods of the Karakoram Himalaya[END_REF], and the former USSR [START_REF] Glazyrin | Forecasting of flood characteristics caused by glacier lake outbursts[END_REF][START_REF] Krenke | USSR case study: catastrophic floods[END_REF][START_REF] Konovalov | Methods for computing the onset date and daily discharge hydrograph of the outburst from Mertzbacher Lake, Northern Inylchek Glacier, Tien Shan[END_REF].

The largest outbursts from ice-marginal lakes known through geological records occurred at the end of the last glaciation [START_REF] Bretz | The Lake Missoula floods and Channeled Scabland[END_REF][START_REF] Baker | Paleohydrology and sedimentology of Lake Missoula flooding in Eastern Washington[END_REF][START_REF] Baker | Large scale paleohydrology[END_REF]Teller and Clayton, 1983;[START_REF] Waitt | Prehistoric jökulhlaups from Pleistocene glacial Lake Missoula -new evidence from varved sediment in Northern Idaho and Washington[END_REF]Clarke et al., 1984;[START_REF] Bond | Evidence for massive discharges of icebergs into the North Atlantic Ocean during the last glacial period[END_REF][START_REF] Shaw | A meltwater model for Laurentide subglacial landscapes[END_REF][START_REF] Shaw | The meltwater hypothesis for subglacial landforms[END_REF]. Jökulhlaups drained lakes that were dammed by margins of the Laurentide ice sheet in North America (Lake Agassiz and others) and by the Fennoscandinavian ice sheet (situated over the Baltic Sea). The Eurasian ice sheet had blocked off lakes, the outbursts of which emptied into northward-draining rivers in Siberia. Pulses of meltwater amassed in major proglacial lakes were released into the Mississippi and St Lawrence Rivers and the Arctic and Hudson Straits, eventually to enter the North Atlantic Ocean. These floods emitted enormous amounts of freshwater, which may have affected ocean circulation and deep-water production in the North Atlantic [START_REF] Teller | Volume and routing of Late-Glacial runoff from the southern Laurentide ice sheet[END_REF]. Giant jökulhlaups from the Laurentide ice sheet during the last glacial cycle may have played a part in depositing the Heinrich layers in the North Atlantic [START_REF] Heinrich | Origin and consequences of cyclic ice rafting in the northeast Atlantic Ocean during the past 130,000 years[END_REF][START_REF] Alley | Ice-rafted debris associated with binge/purge oscillations of the Laurentide Ice Sheet[END_REF][START_REF] Colman | A fresh look at glacial floods[END_REF]. Floods from glacial Lake Missoula at the border of the Laurentide ice sheet repeatedly transported around 2_1012 m3 (2000 km3) of water in less than four days, with flow velocities of up to 30 m s_1 and estimated peak discharges of 2_107 m3 s_1 [START_REF] Baker | Paleohydrology and sedimentology of Lake Missoula flooding in Eastern Washington[END_REF][START_REF] Baker | Cataclysmic late Pleistocene flooding from glacial Lake Missoula: a review[END_REF][START_REF] O'connor | Magnitudes and implications of peak discharges from glacial Lake Missoula[END_REF], so that they comprise the greatest discharges of freshwater known in geological history.

The Lake Missoula floods lasted approximately one week, and the magnitude of their peak discharge indicates either supraglacial release or suddenly failing barriers, because such discharges cannot be explained by the gradual enlargement of basal ice tunnels. The floods from Lake Missoula produced the huge channelled scablands on the Columbia Plateau, Washington State.

Floods from subglacial lakes

The best-documented floods from subglacial lakes occur in Iceland, where jökulhlaups regularly drain six lakes of this type. They are located in hydrothermal areas, where geothermal activity continuously melts ice on the glacier bed, creating a depression in the glacier surface, under which water accumulates until released in floods. The best-known jökulhlaups drain the lake Grímsvötn in Vatnajökull glacier [START_REF] Björnsson | Explanation of jökulhlaups from Grímsvötn, Vatnajökull, Iceland[END_REF][START_REF] Björnsson | Hydrology of ice caps in volcanic regions[END_REF][START_REF] Thorarinsson | Vötnin stri_. Saga Skei_arárhlaups og Grímsvatnagosa[END_REF] and occur at 1-to 10-year intervals. Their peak discharge ranges from 600 to 4-5_105 m3 s_1 at the outwash plain, their duration is two days to four weeks and their total volume at each event is 0.5-4.0_109 m3. The greatest floods have peaked in less than one week and subsided in two days, whereas the smaller ones peak in two to three weeks, after which they usually terminate in approximately one week (Figures 8.4,8.5 and 8.6). Jökulhlaups from Grímsvötn flow a distance of some 50 km beneath the ice to the glacier terminus by the Skeiđarársandur outwash plain (Figure 8.7). The most violent Grímsvötn jökulhlaups have flooded this entire plain, measuring 1000 km2 (e.g., [START_REF] Björnsson | Hydrology of ice caps in volcanic regions[END_REF]. Typically, lake drainage begins at water pressures 6-7 bar lower than those exerted by the overburden at the ice dam. Conduits are enlarged in the course of several days or up to three weeks, so that the floods develop from small initial discharges which have been explained by classic jökulhlaup theories. Occasionally, nevertheless, the lake level rises until the ice dam floats; in this case, discharge increases faster than can be accommodated by the melting of conduits, and the glacier is lifted along the flow path as the water forces open space for itself. An outburst of this type took place in November 1996, when meltwater from the Gjálp eruption collected in Grímsvötn before flowing out in a disastrous flood: this is discussed below in connection with volcanism.

Other well-known jökulhlaups from subglacial Icelandic lakes originate at the Skaftá cauldrons (Figure 8.8), 10-15 km northwest of Grímsvötn, and result in floods of 50-350 10 6 m 3 . They rise over one to three days to a peak discharge of 200-1500 m 3 s-1 , before receding slowly for one to two weeks. So far, the hydrographs of these outbursts have not been simulated theoretically. Although their speedy rise suggests a water temperature at the reservoir well above the melting point (10-20°C), this must not be considered definite, because the theory of heat transfer is debatable.

Floods related to subglacial volcanic eruptions

In active volcanic areas of Iceland and of North and South America, eruptions frequently trigger catastrophic glacial floods [START_REF] Thorarinsson | The jökulhlaup from the Katla area in 1955 compared with other jökulhlaups in Iceland[END_REF][START_REF] Thorarinsson | The Öraefajökull eruption of 1362[END_REF][START_REF] Sturm | Effects of the 1966-68 eruptions of Mount Redoubt on the flow of Drift Glacier, Alaska, U.S.A[END_REF][START_REF] Björnsson | Hydrology of ice caps in volcanic regions[END_REF]Trabant and eyer, 1992;[START_REF] Pierson | Flow characteristics of large eruption-triggered debris flows at snow-clad volcanoes. Constraints for debrisflow models[END_REF][START_REF] Gu_Mundsson | Ice-volcano interaction of the 1996 Gjálp subglacial eruption, Vatnajökull, Iceland[END_REF]Thouret, this volume). Lava erupts directly into water stored under the ice and the boiling water transfers heat readily. Meltwater created by subglacial eruptions may discharge instantly toward the glacier margins, depending on the rate of volcanic melting. The bursts may either travel subglacially in tunnels or spread out in a broad sheet, heaving up the ice. Moreover, the water may overtop the glacier, melt channels on its surface, and crack off giant blocks of ice. Alternatively, the meltwater forming beneath substantial ice massesmay accumulate in subglacial lakes, eventually to exit from them in jökulhlaups. A recent example of such a flood occurred when meltwater from the 1996 Gjálp eruption gathered in the subglacial lake Grímsvötn, enteringat a rate of up to 5 10 3 m 3 s-1 , before draining from the lake in a catastrophic flood, with discharge increasing almost linearly to a peak of 4 10 4 m 3 s-1 in 16 hours. Within a period of 40 hours, 3.2 10 9 m 3 of water had left the lake. Even though the outburst had begun as a flood wave, so that the initial discharge was of the order of 5 10 3 to 5 10 4 m 3 s-1 , an exponential increase would have taken around two days to reach the estimated peak.

Eruptions of snow-clad volcanoes may generate huge floods when pyroclastic, turbulent fluid melts the icy cover, producing slushy, debris-rich flows which speed down valley slopes. Thouret (this volume) describes how a relatively small eruption from the snow-capped volcano Nevado del Ruiz (5400 m high) in Colombia in 1985 caused disastrous lahars that killed more than 23 000 inhabitants of the town Armero, 72 km away. In 1966-68 an eruption at Mt Redoubt, Alaska, melted or washed away 6 10 7 m3 of glacial ice [START_REF] Sturm | Effects of the 1966-68 eruptions of Mount Redoubt on the flow of Drift Glacier, Alaska, U.S.A[END_REF] and in 1989-90 another eruption achieved double that amount [START_REF] Trabant | Flood generation and destruction of Drift Glacier by 1989-90 eruption of Redoubt Volcano, Alaska[END_REF]. A contemporary description of the outburst during the 1362 Öraefajökull eruption in Iceland provides an example of abrupt, destructive jökulhlaups from an ice-capped stratovolcano [START_REF] Thorarinsson | The jökulhlaup from the Katla area in 1955 compared with other jökulhlaups in Iceland[END_REF][START_REF] Thorarinsson | The Öraefajökull eruption of 1362[END_REF]. In less than one day, the flood may have reached its peak of at least 10 5 m 3 /s [START_REF] Thorarinsson | The Öraefajökull eruption of 1362[END_REF]. Water originating in the 2000 m high vicinity of the summit streamed subglacially down the slopes before bursting out to wash away several farmsteads and to leave dead ice, sediment and hummocks covering the lowlands at a depth of 2-4 m. Outwash plains appeared where sea depths had previously measured 50 m. A contemporary record (report by Rev. Jón Thorláksson, cited by Henderson (1818); Thorarinsson, 1958: p. 31) describes how "several floods of water gushed out, the last of which was the greatest. When these floods were over, the glacier itself slid forwards over the plane ground, just like melted metal poured out of a crucible. The water now rushed down on the earth side without intermission, and destroyed what little of the pasture grounds remained . . . Things now assumed quite a different appearance. The glacier itself burst and many icebergs were run down [sic] quite to the sea, but the thickest remained on the plain at a short distance from the foot of the mountain . . . We could only proceed with the utmost danger, as there was no other way except between the ice-mountain and the glacier that had slid forwards over the plain, where the water was so hot that the horses almost got unmanageable".

A less devastating eruption took place in AD 1727 [START_REF] Thorarinsson | The Öraefajökull eruption of 1362[END_REF]. The swiftest, greatest outbursts of glacial meltwater noted in world history accompany volcanic eruptions in the Katla caldera, which rests under the Icelandic ice cap My´ rdalsjökull. Occurring on average twice per century, the outbursts have durations of 3-5 days, peak discharges estimated at 10 5 -10 6 m 3 /s, and total volumes of 1-8_109 m3 [START_REF] Thorarinsson | The jökulhlaup from the Katla area in 1955 compared with other jökulhlaups in Iceland[END_REF][START_REF] Thorarinsson | Kalta og Annáll Kötlugosa[END_REF][START_REF] Maizels | Sedimentology and paleohydrology of Holocene flood deposits in front of a jökulhlaup glacier, south Iceland[END_REF][START_REF] Maizels | Sediments and landforms of modern proglacial terrestrial environments[END_REF][START_REF] Tómasson | The jökulhlaup from Katla in 1918[END_REF][START_REF] Larsen | Holocene eruptions within the Katla volcanic system, Iceland: notes on characteristics and environmental impact[END_REF]. Immense blocks of ice break off the glacial margins, and a mixture of water, ice, volcanic emissions and sediment surges over the outwash plain at velocities of 5-15 m /s. During a segment of the flow event, the water may consist of a hyperconcentrated fluid-sediment mixture. The amount of volcanic debris produced per event and carried away by the water has been estimated to range from 0.7 to 1.6_109 m3, or be of the order of 2_109 t [START_REF] Tómasson | The jökulhlaup from Katla in 1918[END_REF][START_REF] Larsen | Holocene eruptions within the Katla volcanic system, Iceland: notes on characteristics and environmental impact[END_REF]. During the last eruption in 1918, the neighbouring coastline advanced 3 km into the sea. Although many loose deposits have been washed away in succeeding years, the affected seashore remains 2.2-2.5 km further south than its position in 1660.

Jökulhlaups have played a dominant role in building up the outwash plain, which like other such plains in Iceland is called a sandur -a term that has acquired international use. Marine sediments containing debris transported from the eruption site are found in the ocean several hundred kilometres to the south. Jökulhlaups from Katla have threatened local communities, damaged vegetation, ruptured roads on the alluvial flats surrounding the ice cap and even generated flood waves in coastal waters. On the northern side of My´ rdalsjökull, the outbursts have eroded deep canyons in the bedrock.

The largest, most catastrophic jökulhlaups in Iceland, with peak discharges of the order of 10 6 m 3 /s were caused by prehistoric eruptions in the voluminous, ice-filled calderas of Bárđarbunga and Kverkfjöll in the northern reaches of Vatnajökull (see [START_REF] Tómasson | Hamfarahlaup í Jökulsá á Fjöllum[END_REF][START_REF] Björnsson | Hydrology of ice caps in volcanic regions[END_REF][START_REF] Björnsson | Volcanoes beneath Vatnajökull, Iceland. Evidence from radio echosounding, earthquakes and jökulhlaups[END_REF][START_REF] Knudsen | Jökulhlaup deposits at Ásbyrgi, northern Iceland: sedimentology and implications of flow type[END_REF][START_REF] Waitt | Great Holocene floods along Jökulsá á Fjöllum, north Iceland[END_REF]. Floods sweeping down Jökulsá á Fjöllum carved a conspicuous scabland and a deep canyon Jökulsárgljúfur; Figure 8.9); erosion by cavitation is considered to have been a significant factor in their creation.

Concluding remarks and future prospects

This chapter has reviewed the current knowledge of glacial floods and their sources in impounded glacial meltwater, and on the dams holding back the water and dam failure. Also, I have described the characteristics of flood discharges, their impact in the proglacial zone, and their significance for society. Despite some outburst sources lying hidden, field inspection or remote sensing can detect most of them. Potential jökulhlaup hazards can be recognized by examining the properties of reservoir dams and evaluating their stability. While the onset of outbursts cannot be timed exactly, those stemming from ice-dammed lakes may be predicted empirically -though no more precisely than to the nearest month, based on records of lake levels at the beginning of previous outbursts. The discharge rates of change and impacts of jökulhlaups depend on their release mechanisms, i.e., whether a sediment dam suddenly fails, an ice dam is abruptly lifted or overtopped, or the dam seal begins to leak through a subglacial tunnel at gradually increasing rates. The nature of the flood hazard depends on reservoirvolume and the temperature of the fluid, along with the character and content of the sediment that is entrained in the flow. Empirical and theoretical relations help to forecast the possible magnitude of jökulhlaups. Theoretical models of flood discharge may help to predict the slopes of the ascending limbs of the hydrograph if the drainage occurs through tunnels under an ice dam. However, formulating such models requires information on water temperature and bottom roughness, and these data are rarely available. At present, theoretical models are unreliable for predicting peak discharge, although empirical relationships may provide some estimate, given the total volume of the reservoir at the beginning of the outburst. Once the flood has started, the subsequent discharge rate may be predicted on the grounds of reservoir volume and of flow measured during the initial phase of the flood. No theory is yet available for subglacially draining jökulhlaups, which increase faster than can be explained by conduits widening through melting. Glacier lakes are ephemeral features, dependent on variable conditions such as the advance or recession of glacial termini. Continuous monitoring of impounded water and inflow rates is needed for assessing risks and delineating danger zones. Outbursts from lakes behind sediment dams at glacial margins can be prevented by installing drainage pipes to control water levels. Some englacial sources of floods may be difficult to detect, and subglacial volcanic eruptions are hard to predict, but maps of bedrock topography and the glacier surface can be used to identify potential hazard zones with regard to jökulhlaups. Field studies of landforms, sediments and other evidence of varying flow processes would improve understanding of the outburst mechanism. At present, both empirical and theoretical calculations suffer from inaccurate estimates of discharges and particularly of peak flows. Further studies are required on the physics of how jökulhlaups begin to enable more precise timing of their onset. Additionally, studies of supraglacial outbursts that melt gorges through ice dams and of subglacial bursts that lift the glacier to propagate a flood wave are still at an early stage. Studies of the physics of modern glacial floods of every magnitude may fundamentally improve our understanding of palaeofloods in the late Pleistocene and early Holocene. They released enormous amounts of freshwater into the ocean, perhaps altering deep-water circulation and the global climate. In this respect, the glacial floods of today may become a key to the past.