## Abstract

Transition patterns between different sleep stages are analysed in terms of probability distributions of symbolic sequences for young and old subjects with and without sleep disorder. Changes of these patterns due to ageing are compared with variations of transition probabilities due to sleep disorder.

## 1. Introduction

Humans spend a third of their life asleep. Sleep is a time of non-consciousness with its own structure and microstructure consisting of sleep stages, which may be identified by analysing brain waves. For this purpose, brain waves are recorded in a standardized way according to the manual of the American Academy of Sleep Medicine [1]. The recordings include an electroencephalogram (EEG) from at least three leads with well-defined positions on the cortex, an electrooculogram (EOG) from two leads near the eyes and an electromyogram (EMG) with two leads from a submental or mental muscle. Sleep stages are associated with distinct wave patterns, which may be classified according to the Rechtschaffen and Kales scheme [2] as summarized in table 1.

Classification of sleep stages (sleep staging) based on EEG signals is obtained by visual inspection by trained technicians. In order to reduce the effort related to visual scoring, sleep stages are scored in 30 s epochs, effectively limiting the temporal resolution of visual classification. Another limitation of visual scoring is the uncertainty introduced during the classification process [4]. Especially sleep stages that had been scored by different sleep laboratories often show some differences. This ambiguity can be reduced by systematic training of sleep staging personnel, which indeed improves the visual classification [5]. Furthermore, efforts are made to improve sleep classification through new internet-based sleep scoring [6].

Sleep stages occur in a systematic manner during night sleep. First, a short period of wakefulness (W) is observed with eyes closed before the subject falls asleep. This may last for 5–20 min in healthy subjects. Then follows a short period of N1 as a transitional state and then stage N2, which may be longer. Stage N2 is typically followed by N3 (and N4), deep-sleep stages that are needed for physical recreation. After that a short period of REM sleep is observed and then often a very short awakening. This sequence is called a sleep cycle with a duration of roughly 90 min and it is repeated five to six times during the night. Sleep is often interrupted by very brief awakenings. Usually, they are so short that they are not remembered and good sleep is experienced. The longer the awakenings are the more likely they are realized and memorized which leads to a feeling of disturbed sleep.

Current evaluations of sleep consider mainly the following periods of time:

— sleep onset latency=duration of wakefulness before first occurrence of sleep stages,

— REM sleep latency=time until first occurrence of REM sleep,

— time in bed=time between intention to sleep/lights off and wake up/lights on,

— total sleep time=all sleep stages together except wake times, and

— the percentages spent in the different sleep stages.

In general, we know that healthy middle-aged people spend approximately 5–10% of the night awake, 10% in N1, 50% in N2, 15–20% in N3/N4 and 15–20% in REM sleep. Other quantities which are sometimes considered in publications take the number of awakenings or the number of transitions between sleep stages into account. The current focus in sleep science, however, is on durations and latencies of sleep stages that may change due to ageing and sleep disorder. This is reflected in clinical reports of sleep recordings which only present percentages of sleep stages and sleep latencies.

Many sleep disorders, however, also result in changes of sleep transitions. These sleep transitions and the time spent in a specific sleep stage have been analysed previously [7], not only in humans but also in animals and some universal laws have been found and described [8]. It is also known that sleep changes with age. A meta-analysis of sleep studies presented the changes in parameters that are commonly reported [9]. From this analysis, we know that the duration of slow wave sleep (N3 and N4) and the percentage of dream sleep (REM) decreases with age. We know that the amount of light sleep (N1 and N2) as well as time spent awake (W) increases with age. This seems to be a normal ageing process. But how does the frequency and the pattern of transitions between sleep stages change during ageing or with sleep disorder?

Single-step transitions between sleep stages have been previously studied by Kemp *et al.* [10], who investigated transition probabilities between stages. A different approach, with a more global perspective, is the overall analysis of spectral entropy measures for sleep-stage transitions provided by Kirsch *et al.* [11]. In their study, they relate the Walsh spectral entropy (WSE) and the Haar spectral entropy (HSE) to traditional sleep quality parameters such as arousal index and sleep efficacy. They also compare the new parameters to daytime sleepiness and correlate them with traditional sleep quality measures. Lo *et al.* [8] investigated transitions between wakefulness and sleep during the sleep period in order to derive models for the process of sleep stages (where Lo *et al.* reduced the transitions to wake–sleep transitions, only, by lumping all sleep stages into one class). To gain further insight into transition patterns including multistep transitions between sleep stages we analyse in the following sleep data employing symbolic dynamics.

Symbolic dynamics enables flexible data-driven strategies for signal analysis and classification, thus providing a solid basis for the quantification of the complexity of dynamical processes [12,13] with many applications in different scientific fields [14,15]. In those cases where the raw data are given by time series of real-valued samples (e.g. blood pressure, beat-to-beat intervals, EEG channels) some method of coarse graining is required to transform the data into a sequence of symbols aiming at enhancing certain signal features while discarding unessential details. By contrast, the sleep stages considered here already provide a natural symbolic representation (table 1) determined by human sleep staging based on the original EEG, EOG and EMG recordings.

This symbolic representation of the sleep process is the starting point of the sleep analysis presented in the following. In §2, the dataset is introduced and an overview of the periods of time spent in different sleep stages is presented. Then in §3a, we focus on an analysis of one-step transition probabilities between sleep stages using transition matrices and joint entropies. In §3b, we present results obtained employing spectral entropy measures. In §3c, changes of transition patterns due to ageing and sleep disorders are discussed using network representations. Section 4 expands the concept of transition probabilities to two-step transitions and visualizes differences between groups. Finally, in §5, the general question of the appropriate number of steps needed in this type of symbolic analysis of sleep stages is addressed by performing a Markov order test. In §6, all results are summarized and discussed.

## 2. Data

In order to investigate statistics for sleep stages and sleep transitions, it is important to have high-quality data. This means signals have to be recorded without artefacts and then human sleep scoring using these signals has to be correct and reliable. The latter is done by trained sleep technicians as a typical medical classification task with all kinds of limitations inherent to visual medical classification. From previous studies, it is known that there is a considerable human error in the classification of sleep stages [16]. Therefore, the Siesta project [17,18] funded by the European Community was initiated to record high-quality sleep in humans and provide an accurate and robust sleep classification. In order to compare the sleep of healthy subjects to clinical findings, the Siesta project recorded the sleep of patients with sleep disorders as well. Patients with sleep disorders accounted for half the number of healthy subjects, however. The sleep classification was performed independently by two sleep technicians and thereafter checked by a third sleep scorer. The third scorer made a final decision only at those epochs where the two initial scorers disagreed.

The sleep recordings for this analysis were recorded from 196 healthy subjects, who were more or less equally distributed over four age classes. An effort was made to include a similar number of male and female subjects. All subjects were recorded in a sleep center for two subsequent nights using cardiorespiratory polysomnography with EEG, EOG, EMG for at least 6 h and usually 8 h, if possible [18]. In addition to this, 98 subjects with different sleep disorders were recorded using the same protocol including subjects with sleep apnoea, insomnia, restless legs syndrome, periodic leg movements, depression and anxiety disorders.

Figure 1 shows relative durations of sleep stages for four age quartiles, distinguishing subjects with normal sleep from those with sleep disorder. For all age quartiles the fraction of N1 sleep is larger for patients suffering from sleep disorder compared with normal subjects. The fractions of sleep stages reflect well what has been described previously. With increasing age the percentage of R sleep decreases steadily. This observation has already been described by Ohayon *et al*. in their meta-analysis [9]. In addition, in all age classes the percentage of REM sleep is lower in patients with sleep disorders compared with healthy subjects. The percentage of wakefulness (W) during the sleep period steadily increases with age. However, the percentages of wakefulness in healthy subjects and patients with sleep disorders differ only slightly. Only for the oldest subjects were marked differences observed between normal subjects and patients with sleep disorders. This is a clear indication that among elderly subjects more patients with insomnia were observed whereas among the younger subjects more patients with sleep disordered breathing and other sleep disorders are seen.

## 3. One-step transitions

### (a) Transition probabilities and transition entropies

In this section, we analyse the one-step transition probabilities between sleep stages. These probabilities are computed as the number of transitions between one source and one destination stage divided by the total number of transitions in the symbolic sequence of sleep stages (of a given dataset). Note that in §3a,c only transitions observed in the time series are counted, which results in the loss of information about the duration of sleep stages. By contrast, the spectral entropies presented in §3b explicitly cover information about durations. It is also important to point out that the analysis has been performed on a per-dataset basis, where transition matrices are computed for each night of each individual. From these transition matrices of different datasets mean transition matrices are computed by averaging the probabilities of all transitions over all datasets in the group of interest.

Figure 2 shows transition matrices obtained by averaging the transition probabilities between different sleep stages in each of the four classes: Young/Normal, Young/Sleep Disorder, Old/Normal, and Old/Sleep Disorder. One can see that the cells next to the diagonal have highest probability which shows that usually transitions occur into the neighbouring stage, except for stage R. Another apparent feature is the asymmetry between the upper and the lower diagonals which reflect the general tendency to pass the sleep stages from wakefulness to deep sleep in the order of adjacent stages. In the opposite direction, transitions to REM sleep, wakefulness or lighter sleep stages which are non-adjacent are more likely. Young healthy subjects have the highest probabilities for transitions in and out of N3 and N4. This corresponds to figure 1, which shows that these subjects have the highest percentage of N3 and N4 in the night and therefore it is likely that they also have the highest transition rates.

To characterize the transition patterns shown in figure 2, we compute the normalized joint entropies of the corresponding probability distributions {*p*_{ij}}
3.1
where *N*=6 is the number of sleep stages W, N1, N2, N3, N4 and REM. The normalization by the entropy of a uniform two-dimensional distribution renders *H* to lie in the range [0,1]. The normalized joint entropy *H* is computed for each subject and low values of *H* indicate less complex transition patterns.

Figure 3*a* shows the distributions of *H*-values for the four classes of subjects whose average transition patterns are shown in figure 2. In table 2, *p*-values of a Wilcoxon rank-sum test (also known as Wilcoxon–Mann–Whitney test) performed for all pairs of distributions are given, indicating significant differences. These *p*-values have to be interpreted carefully, because of the relatively high number of individual tests that have been carried out which lead to accumulation of type-1 errors. Nevertheless, the differences between cases with and without sleep disorders in the young and old age groups as well as the difference between the Young and Normal versus Old and Sleep Disorder groups can be detected at a high significance level.

Figure 3*b* and *c* shows comparisons of the distributions Normal versus Sleep Disorder and Young versus Old, respectively. The lower entropy values for subjects with sleep disorder (figure 3*b*) indicate lower complexity due to missing sleep transitions involving deep sleep.

### (b) Spectral entropy measures

Kirsch *et al.* [11] proposed two spectral entropy measures specially suited for application to categorical time series: the WSE and the HSE. These spectral entropy measures can be interpreted as a quantification of the joint frequency distributions of all symbols contained in the original dataset. The names of the entropies are derived from the underlying Walsh- and Haar transformations, respectively. These quantities are computed as follows (the procedure is explained more in detail in [11]).

The original time series consisting of symbols *s*_{t}∈*S*,*t*∈[1,*n*],*S*={*c*_{1},…,*c*_{m}} is in the first step transformed into *m* binary time series
3.2

In the second step, either the Walsh transform or the Haar transform is applied to moving temporal windows , *t*∈[*w*,*w*+*l*−1] of the binary time series. Both transforms make use of a corresponding matrix : the Hadamard matrix in the case of the Walsh transform or the Haar matrix in the case of the Haar transform, each of size *l*×*l*, *l*=2^{N} (see appendix for definitions of the matrices)
3.3

The elements of the *l*×*m* matrix are called Walsh/Haar transform coefficients and they are used to compute the corresponding *l*×*m* periodogram matrix of the temporal window [*w*,*w*+*l*−1]
3.4

This matrix *P*_{w} is then used to define a two-dimensional (normalized) entropy
3.5
with being a normalized version of *P*_{w}
3.6

In [11], these entropies are called 2D-WSE and 2D-HSE depending on the applied transform. In the following, we will refer to these quantities simply as WSE and HSE, as only the two-dimensional versions are employed here.

Both quantities are calculated for matrices of size *l*×*l*, *l*=2^{6} for every successive overlapping window [*w*,*w*+*l*−1] of each dataset. This leads to an entropy distribution for each dataset. In order to be able to compare the entropies between groups, we use the mean value of the distribution of each dataset. These mean values lead to the entropy distributions shown in figures 4 and 5. Each pair of distributions in figures 4*a* and 5*a* is compared using Wilcoxon rank-sum tests. These results are given in tables 3 and 4.

The results for the WSE and the HSE are very similar, the distributions show a nearly identical shape. Tables 3 and 4 confirm what already can be seen in figures 4 and 5. The age effect on the spectral entropies can be differentiated at a high significance level. However, a differentiation does not seem possible for the sleep disorder effect, as the *p*-values clearly exceed the significance threshold for the comparisons Young and Normal versus Young and Sleep Disorder and Old and Normal versus Old and Sleep Disorder.

### (c) Transition graphs

In this section, the difference of transition probability matrices of different groups of subjects is used to analyse the impact of age and sleep disorder on one-step transition probabilities. These differences are visualized using pruned graphical representations where links between the sleep stages are plotted only if the distributions underlying the mean values of the particular transition in both groups are significantly different (*p*<0.01). Links can also be missing if the probabilities involved are too small. Note that the interpretability of *p*-values in this context must not be overestimated, as they are used here solely to choose relevant links for pruning the graph.

First, we consider changes of transition probabilities due to ageing. Figure 6 shows a comparison of transition patterns of normal old and young subjects. The matrices show the transition probabilities for each group (given as numbers in per mille, compare with figure 2). The graph shows all significant differences of both transition patterns. The links are annotated with the difference values of the corresponding transition probabilities from both matrices. Here, a transition is considered to be significantly different if the *p*-value obtained when comparing the distributions of the transition probability values from both groups is smaller than 0.01. With ageing we see an increase of transitions between light sleep stages N1 and N2 and between N1 and W. On the other hand, for elderly subjects fewer transitions occur between deep-sleep stages N3 and N4, and between N2 and R. There is no significant difference of transitions N2–N3 between young and old subjects. Elderly subjects wake up more often and exhibit fewer transitions to deep-sleep stage N4 and to REM sleep stage R.

To investigate the impact of sleep disorders on the transition probabilities, figure 7 shows a comparison of young subjects with and without sleep disorders. Similar to elderly subjects (figure 6), patients suffering from sleep disorders exhibit a higher probability of transitions within light sleep N1–N2, less transitions within slow wave sleep N3–N4 and no significant change in N2–N3 transitions. Also transitions from N2 to REM sleep are reduced. This can be an expression of reduced slow wave sleep and reduced REM sleep as well in elderly subjects. As a difference we see no significant increase in transitions N1–W. This reflects that young subjects with sleep disorders do not wake up more often compared with normal subjects without any sleep disorder.

## 4. Two-step transitions

To learn more about sleep-stage transition patterns, we consider now multistep transitions consisting of *K* steps starting with *K*=2. Figure 8 shows ranked probabilities of two-step transitions (the largest 25 values, only). The grey vertical bars give the 25 largest transition probabilities of two-step transitions averaged over all subjects under study. Most probable are transitions N2 N1 N2 and N2 N1 N2 corresponding to light sleep. These transitions occur more often in patients suffering from sleep disorder as can be seen from the dashed lines indicating transition probabilities of both groups Young/Sleep Disorder and Old/Sleep Disorder, respectively. The transition probabilities of Old/Normal subjects equal the total mean, while Young/Normal exhibit a relatively low probability of such light sleep transitions.

The situation is slightly different for two-step transitions including the wake state W. Here transitions N1 W N1 and W N1 W are most probable for old subjects with sleep disorder, followed by the Old/Normal and the Young/Sleep Disorder group. The lowest probability of this transition scenario occurs with young healthy subjects. Transition patterns N4 N3 N4 of deep-sleep transitions or N1 N2 R including REM sleep occur with relatively high probability with young normal subjects and with reduced probability in the groups Old/Sleep Disorder.

## 5. Markov order tests

Figure 8 clearly indicates that an investigation of multiple transitions instead of single transitions can reveal subtle information about the sleep process. This raises the question which number of transition can be considered as appropriate for further analysis of symbolic dynamics. We are going to investigate this question in the framework of Markov chains.

A Markov chain is a model assuming probabilistic transitions between states with a dependency on a specific number of temporarily previous states. A Markov chain of order *k* is defined as a probabilistic process where the current transition probability depends on the past *k* states. A symbolic chain involving *n* states can therefore be interpreted as a Markov chain of order *k*=*n*−1.

Pethel & Hahs [19] developed an exact significance test for determining the order of such a Markov process. This test makes use of the observed data in order to generate surrogates that match the properties of the data under the assumption of a Markov chain with a specific order *k*. This surrogate generation procedure is done using Whittle's formula [20]. Using an exact hypothesis test a *p*-value is calculated, which leads in the case of a small *p*-value to the rejection of the respective null hypothesis. The null hypothesis states that our process is indeed a Markov process of order *k*. To determine the order of the Markov chain the authors propose to run the test for ascending *k* starting with *k*=0 and choose the first *k* for which the *p*-value is larger than a significance threshold *p*_{th} [21].

We applied this Markov order test to each dataset individually using the algorithm published in [22]. We chose as the maximum Markov order and used 1000 surrogates for each test. The method was applied to time series containing only the sleep-stage transitions, the durations were taken out. Figure 9 shows the resulting *p*-value distributions for four different group comparisons. As mean values of *p*-values can be misleading we show the fraction of all cases with a *p*-value larger than the significance threshold *p*_{th}=0.05.

The distributions show a very similar pattern for all group comparisons exhibiting a very strong increase in the fraction of non-significant cases for Markov order *k*=2. On the other hand, the null hypothesis assuming a first-order Markov process has to be rejected in more than 80% of the cases. No clear difference between all groups is visible in the group comparisons. Especially, the comparison of individual nights shows an almost identical shape of the curve.

These results indicate very clearly that the time series of transitions of sleep stages seems to follow a second-order Markov process.

## 6. Conclusion

Typical patterns of sleep-stage transitions of 196 healthy subjects and 98 patients suffering from different sleep disorders have been identified and quantified in terms of transition probabilities. We compared four groups: Young/Normal, Young/Sleep Disorder, Old/Normal and Old/Sleep Disorder. For each subject, the structure of one-step sleep-stage transitions is characterized by the resulting transition matrices representing the corresponding transition probabilities. To characterize these transition matrices, we computed their (normalized) joint entropy. Entropy distributions of the four classes of subjects studied here showed slightly different patterns (figure 3), which might allow for a distinction of healthy subjects and subjects with sleep disorder. By contrast, the spectral entropy distributions (WSE and HSE) which have been presented in figures 4 and 5 indicate a relatively clear distinction between young and old subjects. Furthermore, one-step transitions are visualized and analysed using (pruned) transition graphs (figures 6 and 7). This new presentation provided evidence that changes in transitions are slightly different with the ageing process and with the presence of sleep disorders. In particular, with ageing more transitions to and from the wake stage (W) occur. We conjecture that more specific details and differences between ageing and sleep disorder may be found when studying multistep transitions. Investigations of two-step transition patterns (figure 8) clearly indicate valuable information contained in the corresponding symbolic sequence of multistep sleep transitions. Markov order tests have been carried out (figure 9) and reveal that a Markov order of 2 is suitable for sleep-stage transition analysis. This result is stable across all group comparisons performed in this publication.

In this study, we also analysed transitions between N3 and N4 because we used scorings from a large study which used Rechtschaffen & Kales [2] scorings. We observe a considerable number of transitions between stages N3 and N4 and in this, we also observe differences between normal subjects and patients with sleep disorders. However, these differences between normal subjects and patients with sleep disorders may be just fluctuations within slow wave sleep and have no further clinical impact. All sleep staging had been performed by three scorers and, therefore, we expect that the fluctuations are not the effect of scoring variability but due to physiology with more and less high amplitude delta waves.

With the low number of patients with sleep disorders (*n*=98) and with the high number of diverse sleep disorders in this set of studies the presented results are to be considered as preliminary providing only weak evidence for differences. Clinically, well-defined datasets with specific sleep disorders should be used with this analysis in order to show whether the proposed and applied methods allow to distinguish the specific characteristics for pathological sleep-stage transitions for sleep apnoea, periodic limb movement disorders, narcolepsy and also physiological normal ageing.

## Funding statement

The authors thank the European Union DG XII for funding the Siesta Project (Biomed-2 BMH4-CT97-2040-SIESTA) through which the database was provided. This work received support through Deutsche Forschungsgemeinschaft (SFB 1002) and the German Center for Cardiovascular Research (DZHK).

## Appendix A

**(a) Hadamard matrix**

The Hadamard matrix is used to compute the Walsh transform. is an *n*×*n* matrix containing only the elements −1 and +1. Furthermore, all rows and columns, respectively, are pairwise orthogonal to each other.

We use the so-called Sylvester construction to build an Hadamard matrix of order *n*
A 1
and
A 2

**(b) Haar matrix**

The Haar matrix is a matrix representation of discretized Haar wavelets and is used to compute the Haar transform. Its rows and columns, respectively, are pairwise orthogonal to each other. The Haar matrix of order *n* can be constructed as follows:
A 3
and
A 4
with being the identity matrix of order *n* and ⊗ being the Kronecker product defined for *n* *p*×*q* matrix **A** and a matrix **B** as follows:
A 5

The Haar matrix has to be normalized if it is used for the Haar transform.

## Footnotes

One contribution of 12 to a theme issue ‘Enhancing dynamical signatures of complex systems through symbolic computation’.

- © 2014 The Author(s) Published by the Royal Society. All rights reserved.