Communication patterns in a psychotherapy following traumatic brain injury: A quantitative case study based on symbolic dynamics

Traumatic brain injury is a significant cause of acute and long-term disability. Neurobehavioral sequelae encompass cognitive, social and psychiatric domains. Major depressive disorder is the most prevalent psychiatric disorder following traumatic brain injury regardless of the severity of the injury [1‐9]. Estimates of prevalence are highly varied. Iverson, et al. [10] reviewed six studies of depression following traumatic brain injury and found reports of prevalence ranging from 12% to 44%. While prevalence rates are uncertain, a critical conclusion can be made. The treatment of neuropsychiatric disorders following traumatic brain injury is a significant clinical need that presents unique clinical challenges.

As commonly conceptualized, the clinical response to traumatic brain injury has four components: neuroprotection (preserve injured neurons), plastic modification (reconstruct neural networks with surviving neurons by promoting dendritic arborization and synaptogenesis), neurogenesis (stimulate the maturation of new neurons from stem cell populations), and neurointegration (facilitate the integration of newly formed neurons into the central nervous system). It is increasingly recognized, however, that psychotherapy is an important complement to this neurological response. Cope [11] has argued that "the majority of recovering survivors of TBI are now seen as potentially benefiting from some form of psychotherapeutic/rehabilitation treatment." Nonetheless, most individuals experiencing a head injury do not receive psychotherapy. In a review of the early history of psychotherapy following TBI, Prigatano [12] addressed the question, "Why has the role of psychotherapeutic interventions in the rehabilitation care of TBI patients gone unrecognized?" He suggests that "the answer seems to lie in the assumption that TBI patients could not benefit from psychotherapy because of their permanent cognitive, linguistic and affective disturbances." While this argument might be advanced when considering severe TBI, it does not seem plausible in cases of mild TBI. But is it even applicable in the case of severe TBI? Results reported by Ben-Yishay et al. [13] and by Ezrachi, et al. [14] indicate that psychotherapy following moderate or severe TBI has a positive effect on post-injury employment.

While psychotherapy is the preferred approach to the treatment of mood disorders following traumatic brain injury [1, 2, 15‐17] there is limited research to help guide the selection of the specific therapeutic method [18, 19]. The heterogeneity of this population demands a varied response. In part, the appropriate therapy will be determined by the physical injury, particularly the residual neurological and cognitive deficits. Individuals with TBI may benefit from treatments that take post-injury cognitive distortions into account [20‐22]. The choice of therapy should also be responsive to pre-injury psychopathology [23, 24]. There is an emerging literature detailing the benefits of cognitive behavior therapy across a variety of medical patients with acquired brain injuries of various severities comorbid with mood disorders [15‐18, 25, 26]. Psychodynamic psychotherapy has also been considered. While cognitive deficits following head injury can limit the individual's ability to profit from psychodynamic psychotherapy, this is not invariably the case. As Lewis and Rosenberg [27] observed in a paper describing psychoanalytic psychotherapy following brain injury, "the overriding principle that guides such psychotherapeutic work is that acquired brain lesions do not ablate the patient's psyche or unconscious." These authors have identified five criteria that can help identify candidates for psychoanalytic psychotherapy following brain injury. (1.) The patient must be motivated to enter and remain in therapy. (2.) Patients who have had at least one positive significant relationship in the past are better able to form a therapeutic alliance. (3.) Patients who have had previous successes resulting from active effort are more likely to benefit from individual therapy. (4.) Patients in extreme psychological distress may require a more supportive intervention, including hospitalization, before initiating psychoanalytic therapy. (5.) The degree and form of brain injury can affect the appropriateness of analytic treatment. Patients with significant expressive or receptive language deficits are not appropriate candidates. In addition to outlining the potential benefits of a psychodynamically oriented therapy for appropriately selected patients, Lewis and Rosenberg make two points that are generically applicable to the consideration of psychotherapy following traumatic brain injury. First, unaddressed psychological problems can be an impediment to meaningful participation in physical, cognitive and occupational rehabilitation, thus providing an additional argument for including psychotherapy in the treatment of some presentations of traumatic brain injury. Second, the patient's altered experience of self should not be viewed as an entirely neurological symptom. Brain injuries have psychological meaning.

"Although such disruptions (brain injury) can significantly affect the patient's self-esteem, and often represent a major focus for family work, they may represent a more basic and profound disturbance in the patients' sense of self. That is, beyond their difficulties in performing social roles, patients also struggle with the more fundamental question of who they are; the brain injury appears to disrupt severely their previously acquired self-image and sense of self [28]. Thus, a primary task of psychotherapy is to help the patient consolidate a new sense of self that successfully incorporates a realistic appraisal of strengths and weaknesses" [27].

In presentations where this alteration of sense of self is a significant element of the clinical presentation and the patient has sufficient ego development to tolerate an insight directed therapy, a psychodynamically informed therapy is indicated.

On reviewing psychotherapies appropriate for TBI patients, Folzer [29] made the following observation, "If 'immature' defenses and coping patterns are removed too early, the therapist may precipitate a catastrophe. Instead of directly confronting the patient, the therapist can introduce the focus on reality gradually." This would argue for a supportive therapy [30] instead of insight-oriented therapy. There is not, however, a strict division between these forms of therapy. As Werman [30] observed, "Although in the following pages these two forms of treatment (supportive therapy and insight-oriented therapy) are compared as if they were not only different from each other but virtually dichotomous in their aims and techniques, in reality they rarely exist in pure forms. Typically, over a period of time, most patients in supportive psychotherapy gain some insight into their behavior; similarly it is difficult to conceive of a course of insight-oriented psychotherapy in which some supportive measures are not utilized."

Psychotherapy following traumatic brain injury should not necessarily be limited to individual therapy. Several authors have emphasized the value of group therapy with TBI patients [29, 31, 32], and family involvement in therapy can be particularly important [12, 23].

The discussion of psychotherapy with TBI patients and indeed psychotherapy in general has been conducted largely in the absence of quantitative data concerning the therapy itself. While standardized instruments for assessing baseline symptoms and treatment outcomes are increasingly being used in clinical research [33], these instruments do not quantify the fine structure of the therapeutic interaction. This contribution continues the development of quantitative methods for the characterization of patient-therapist communication with the long term objective of improving the effectiveness of psychotherapy following traumatic brain injury. Communication between patients and therapist during psychotherapy has many components including posture, eye contact, verbal tone, verbal production (the number of words exchanged irrespective of their meaning) and the manifest content of the communication. All of these interactions can be examined quantitatively [34, 35]. For example non-verbal communication in the therapist-patient interaction has been analyzed by Yaynal-Reymond, et al. [36] and by Merten and Schwab [37] using a form of quantification developed by Magnusson [38, 39]. While all components of patient-therapist communication are important, this paper focuses on content analysis. Using methods of symbolic dynamics this investigation extends previous analyses of the frequency of content by quantifying the temporally dependent, sequence-sensitive structure of the dialog. As long-term goals, the questions addressed in this research program follow those enumerated in Rapp, et al. [40].

1. Are there nonrandom patterns in the sequential structure of patient-therapist communication?

2. Do these patterns, should they exist, change during the course of therapy?

3. Do changes in the patterns of patient-therapist communication correlate with the clinically perceived success or failure of the therapy?

4. Can this type of analysis identify more effective forms of therapist intervention?

This case study is limited to an examination of the first three questions in three therapy sessions recorded from one patient. Generalized conclusions cannot therefore be made. The limited results do, however, indicate that there is a nonrandom structure in patient-therapist communication in these protocols. Additionally, quantifiable structures changed during the course of therapy in a manner that correlated with the clinically perceived success of the therapy.

This is a case study, and therefore any results must be regarded as inconclusive until confirmed by a more systematic investigation. In this therapy the rate of complexity generation increased across the three sessions investigated. This increase in variability is consistent with the statistically significant faster decorrelation time observed in the K = 1 mutual information calculation and in the increase in n-th order entropy and conditional entropy for n = 1. It is also consistent with the clinically observed changes in the flexibility of patient communication during the course of treatment. Additionally, using two measures of complexity we have demonstrated that the sequential structure of patient-therapist dialog in these sessions has a nonrandom structure (P_NULL = .002). These results are consistent with results of previous investigations summarized by Leroy, et al. [57]:

As previously noted, the contrast between the consistency of normalized complexity (both Lempel-Ziv and context free grammar complexity) over the three sessions and the increase in complexity generation (complexity per unit time) requires examination. Possible insights into this question can be gained by examining the quantitative literature investigating hierarchical structures in language [98‐101]. Based on this research we wish to suggest that the normalized complexity quantifies an invariant structure intrinsic to language when characterized by this form of symbolic restatement, while complexity per unit time quantifies pragmatic language use. Some measure of support for this hypothesis can be obtained by consideration of work by Montemurro and Zanette [102]. Montemurro and Zanette examined the sequential structure of word ordering in 7,097 texts drawn from eight languages (English, French, German, Finnish, Tagalog, Summarian, Old Egyptian and Chinese). They computed a measure of entropy based on Lempel-Ziv complexity and a normalized relative entropy based on comparisons with randomly shuffled sequences of equal length. They found that "while a direct estimation of the overall entropy of language yielded values that varied for the different families considered, the relative entropy quantifying word ordering presented an almost constant value for all these families. ... Therefore our evidence suggests that quantitative effects of word order correlations on the entropy of language emerges as a universal statistical feature." The Montemurro and Zanette study examined the sequential structure of word ordering. It is recognized that word ordering is not identical to the concept sequencing uncovered by the symbolic coding process used in our study, but the presence of near constant normalized complexity in the presence of a highly variable complexity offers support, albeit indirect support, for our hypothesis of a dissociation between pragmatic complexity (bits/minute) and intrinsic structure (normalized complexity). This is a case study of a single patient. Any further speculation must be deferred until additional data are available.

A systematic research effort will be required to address the other questions raised in the introduction to this paper. In addition to acquisition of longitudinal data obtained from a large, clinically homogeneous population, the introduction of additional measures of sequential structure can be considered. The inverted-U measures of complexity [103] are theoretically important but have received little application with observational data (as distinct from computationally generated symbol sequences). These measures of complexity give low values for both highly regular sequences and for random sequences but high values for chaotic sequences (where the word chaos is being used here in the technical sense). This is an interesting possibility since it has been suggested that patient-therapist communication can be chaotic [104‐109]. More general reviews of dynamical metaphors in psychopathology and psychotherapy are given in [110‐113].

An analysis of the computational results identified the limitations of the approach taken in this paper. The large number of symbols in the alphabet and the comparatively short message lengths severely limit the kinds of analyses that can be applied. An alternative approach can be implemented using Stiles' Verbal Mode Analysis. In this analysis, each utterance is scored by three forced choice questions called principles of classification (source of experience, frame of reference, and presumption). These three binary scores are used to specify one of eight mutually exclusive categories. The eight celled classification process is applied to each utterance twice. The first classification is determined by grammatical form. The second is based on pragmatic intent. Several analysis options are thus available. The sequential structure of the form (grammatical) coding and the intent (pragmatic) coding can be analyzed separately. In these cases, N_α = 8. At a finer scale, the three principles of classification each generate a binary sequence, N_α = 2 that can be examined. These scoring methodologies make it possible to perform mathematical analyses that are not feasible for large N_α. The analyses of ordered triples reported here does, however, indicate that the rich content introduced by a large N_α can reveal important insights into the evolving dynamic of patient-therapist communication. In the ideal case, protocols can be scored by more than one procedure and analyses performed with the widest possible collection of mathematical methods.

Psychotherapy, even when the treatment is concretized in treatment manuals is, by nature, transactional, flexible and often highly individualized. As such, the field of psychotherapy research standardly employs a 'technology model' [114] in conducting treatment development and evaluation research. Psychotherapy process researchers also employ a methodology for measuring complex, deterministic, and dynamic processes within the therapy experience. Core to both models is the application of highly specified behavioral coding systems to recoded samples of therapy sessions. A discussion of this literature is beyond the scope of the current article. Also, it should be noted that our experience suggests that the procedures presented here are not only generically applicable to the field of psychotherapy research but are also of value in training therapists. The discipline of examining each verbal exchange at this level of detail and the process of identifying recurring patterns of communication (the words change, but the symbol sequence recurs) helps trainees to identify maladaptive communication strategies and encourages them to view a therapy not as separated exchanges but as a larger scale dynamical process. Independently of the subsequent mathematical analysis, the process of sequential symbolic transcription is a valuable exercise. Additionally, these methods may be of particular value in the examination of therapies following traumatic brain injury. These therapies can, in some instances, be complicated by cognitive deficits that result in distortions of language. As noted by Granacher [115] a distinction is to be made in the language deficits following traumatic brain injury between deficits of speech (the mechanical articulation of language) and deficits in the use of language (generation and comprehension of syntactic and semantic structure) which can be investigated using the methods tested here. In the case of injuries, frank aphasias can result. Their identification does not require sophisticated mathematical analysis. These aphasias typically resolve spontaneously into mild residual anomia [116, 117]. In other cases, however, subtle distortions of language can occur after traumatic brain injury. "The basic structural components of language may be intact but the ability to use language to engage socially is impaired." [117] Deficits in the effective use of language following traumatic brain injury have been reviewed by Coelho [118] and by Coelho and Youse [119]. In addition to complicating therapy, these deficits can have a significant negative impact on post-injury quality of life. These deficiencies in language are commonly described as deficits in pragmatic competence where, as used here, the word pragmatics is defined as the subfield of linguistics which investigates the way in which context contributes to meaning [120, 121]. These deficits are not typically expressed as failures to comprehend single sentences but are observed as failures to understand sequence-dependent, multi-sentence discourse [122]. Sohlberg and Mateer [117] have provided the following summary:

"Pragmatics constitute a comprehensive set of skills required for competence in naturalistic, functional use of language. The term can be broadly defined as the use of language for communication in specific contexts [123]. Pragmatics behaviors transcend isolated word and grammatical structures; they make up the system of rules clarifying the use of language in terms of situational or social contexts. People with brain injury often demonstrate normal basic linguistic skills, but have difficult adapting their communication to specific contexts; for example they may exhibit tangential speech, poor verbal organization, or inadequate turn taking [124]."

Pragmatic deficits are not limited to traumatic brain injury but are also observed in autism [125, 126], attention deficit hyperactivity disorder [127] and schizophrenia [128, 129]. In contrast with these disorders, the presentation of deficits in pragmatic competence following traumatic brain injury is complicated by acute onset followed by a complicated post-injury time course that can result from progressive cognitive loss or improvement due to spontaneous resolution. Highly variable day to day changes in competence can also sometimes be observed.

As reviewed by Martin and McDonald [121], three theories presenting explanations for deficits in pragmatic competence following traumatic brain injury are now under consideration: Social Inference Theory, Weak Central Coherence and Executive Dysfunction. Social Inference Theory argues that pragmatic failures follow from failures of the patient's Theory of Mind. An individual's Theory of Mind is "the capacity to infer mental states of others ... a person's ability to form representations of other people's mental states and to use the representations to understand, predict and judge utterances and behaviors" [130]. Following initial work by Santoro and Spiers [131], a rapidly growing literature has documented Theory of Mind deficits following traumatic brain injury [132‐136]. Weak Central Coherence results in an individual's focus on components and a failure to integrate components into larger scale coherent structures. In addition to being a possible cause of post-injury pragmatic deficits, weak central coherence may be present in autistic patients [137‐139]. The Executive Function system controls and regulates other processes and is particularly important in responding to novel situations requiring planning and decision making. Executive functions are localized in the prefrontal cortex [140, 141], and injury to the prefrontal cortex can cause executive dysfunction which in turn results in deficits in language. Significant correlations between executive function and pragmatic communication difficulties following traumatic brain injury have been reported [142].

While arguments can be made that deficits in any of these capabilities (Theory of Mind, Central Coherence, and Executive Function) can result in pragmatic language deficits, there is no present evidence indicating which of the three is predominant in pragmatic deficits following traumatic brain injury. Indeed, several investigators have results indicating that it is very difficult to ascribe observed deficits to any given cause [143‐146]. Given the heterogeneity of the traumatic brain injury population, it seems probable that pragmatic failures will have different causes in different patients.

Irrespective of the cause, psychotherapists of traumatic brain injury patients must be sensitive to the possible impact of erratically varying language competence in patient-therapist communication. As outlined in Sohlberg and Mateer [117] none of the currently available procedures for assessing pragmatics following brain injury are completely satisfactory. The methods closest to the procedures developed here are conversational analysis studies of language following traumatic brain injury [147‐151]. The analysis employed by Snow, et al. [147] was modified from Damico's Clinical Discourse Method [152, 153]. Seventeen parameters were organized into four groups (Quantity, Quality, Relation, and Manner). A similar study published by Friedland and Miller [149] scored natural conversations in four areas (Repair, Silences, Minimal Turns, Topic). In a study of conversational structure, Coelho, et al. [151] found differences in the flow of conversation of traumatic brain injury patients when compared to healthy controls. They found that patients were more dependent on the investigator to maintain the interaction. Individuals with traumatic brain injury did not initiate and appeared to function primarily as responders. The sequential structure of discourse is not, however, quantified by these methods. It can be noted, however, that it may be possible to apply the sequence sensitive measures presented here to these previous analyses. For example, in the Coelho, et al. [151], study two categories of analysis were applied, Appropriateness and Topic Initiation. The Appropriateness of an utterance was assigned to one of four categories (Obliges, Comments, Adequate Responses, Adequate Plus Responses). The results were reported as between-group means and standard deviations. Significant differences were seen in two of the four categories. This analysis can be viewed as a restatement of the conversation as an eight-symbol alphabet (four Appropriateness categories crossed against Investigator or Patient). The sequential structure of this symbol sequence can be quantified.

How might deficits in pragmatic competence following traumatic brain injury be reflected in complexity and entropy measurements of patient-therapist communication? Deficits in pragmatics are reflected in sequential structures including poor organization, tangential speech and loss of coherence. As documented by Chapman [154, 155] some patients will present a loss, possibly a subtle loss, of coherence in verbal production. This loss of coherent structure would be reflected in an increase in complexity and entropy, a more uniform symbol frequency distribution and a broader spectrum of repeated pairs. Conversely, perseverations of discourse and topic repetitiveness, which can also be observed following brain injury [156], would result in a decrease in complexity and entropy. Pragmatics deficits would therefore be expected to produce bimodally distributed values of sequence sensitive measures. Further research may show that a high degree of variability in complexity within sessions and between sessions is diagnostic of failures of pragmatic competence in traumatic brain injury patients.

The present results suggest that dynamical measures can be used longitudinally to follow the course of treatment. To a degree, it is possible to consider two distinct processes occurring during the course of psychotherapy following a brain injury: psychological change reflecting emotional development and cognitive change having an impact on language due to organic changes in the central nervous system (recovery or continuing deterioration). The longitudinal application of the measures developed here may provide a means of separating and observing these processes quantitatively. Psychological change may be reflected in changes in subject content while cognitive changes may result in changes of linguistic structures that can be captured by complexity measures.

We join with Morris and Bleiberg [157] in arguing that psychotherapy should be integrated with cognitive rehabilitation in the treatment of brain injury patients. We also agree with Judd and Wilson [158] in concluding that modifications of psychotherapy will often be required when working with these patients. The diversity of the traumatic brain injury population makes it impossible to construct a single, generic therapy for these patients. Any conclusions based on the quantitative analyses of protocols from a single patient are clearly provisional. It is suggested, however, that with further development and larger studies, the methods developed here for the quantitative analysis of dynamical structures in patient-therapist communication may become useful on a patient-by-patient basis to inform these clinical decisions.

Classically complexity is defined as the amount of information required to specify the contents of a message [84, 159, 160]. An historical review is given in Li and Vitányi [[161] Section 1.6]. This definition can be operationalized by building an instruction set that can generate the message. The complexity of the message is defined to be the length of the instruction set. This operationalization is implemented in the context free grammar complexity [60, 162]. A systematic procedure (outlined below) is used to construct an algorithm that can reconstruct the original message. The size of the algorithm (also defined below) is the complexity of the message. It is understood that this gives an upper bound to complexity. It is always possible that an alternative construction will give a smaller instruction set. This is true of all complexity measures in this category (randomness finding, nonprobabilistic, model based, [73]). Because the procedure used to construct the algorithm is systematic, complexity is valid as a comparative measure. This consideration also indicates why it is useful to have the results of a complexity analysis confirmed by the application of a second measure. "There is no single value of complexity. These calculations provide a systematic procedure for obtaining an empirical measure of dynamical behavior that can be compared across conditions." [163].

The procedure for determining the context free grammar complexity is best introduced by considering a specific example. Consider the previously introduced message M₂.

The procedure begins with a search for repeated pairs. In this message, the pair AD is the most repeated pair. It is replaced by the new symbol α = AD.

BC is the next most frequently repeated pair. It is replaced by symbol β = BC.

BB is repeated twice, but as will be seen replacing a pair of symbols with a new symbol does not result in a decrease in the size of the instruction set if the pair is only repeated twice. The search for repeated pairs therefore ends, and the search for repeated triples begins. The triple BBD is repeated twice. In the case of triples, replacing a repeated triple does decrease the size of the instruction set even if it is only repeated twice. BBD is replaced by γ

There are no other repeated triples. In the general case, the search for repeated triples is following by a sequential search for repeated n-tuples, n = 4, 5, 6.... until the search is exhausted. In the case of this message there are no higher order repeats. The compression has converged.

In the next step product terms are replaced by exponentials. Thus AA is replaced by A². CCC is replaced by C³ and BB is replaced by B². The instruction set to reconstruct the original message is:

Complexity is determined by calculating the size of this instruction set. Under the definition used here [60] each symbol adds one to the complexity and exponents contribute logarithmically (base 2).

The total is 27.585. Again under this definition, the integer part of the final sum is reported in bits. The context free grammar complexity of M₂ is 27 bits.

Estimating the uncertainty in the complexity of a specific message is problematic when the message is considered in isolation and a large population of messages generated by the identical dynamical process is not available. In Rapp, et al. [164] the uncertainty in C_ORIG is approximated by finding the difference in complexity values obtained in the first half and the second half of the message and expressing this difference as a fraction of their average value. Let C_A be the complexity of the first half of the message. Let C_B be the complexity of the second half of the message. Under this approximation, the uncertainty in C_ORIG is given by

where we use the property C_A and C_B are positive.

This procedure can give an aberrant value of zero when C_A = C_B. An alternative procedure for estimating ΔC_ORIG can be constructed by calculating <C_1/2>, the mean value of complexity calculated from all possible substrings of length L_M/2, and σ_1/2 the standard deviation of that mean. Expressed as a fraction, uncertainty is σ_1/2/<C_1/2>, and ΔC_ORIG is given by

This procedure is, however, computationally insupportable for longer messages. Suppose L_M = 8000. This procedure for estimating <C_1/2> would require averaging 4000 values of complexity calculated from strings of length L_M/2 = 4000. We have adopted the procedure of calculating <C_1/2> from 100 strings of length L_M/2. They are selected randomly from the set of all possible L_M/2 substrings. In cases where L_M < 200, <C_1/2> is calculated from all possible substrings of length L_M/2.

A qualitative understanding of the complexity of a symbols sequence can be obtained by applying these measures to symbol sequences generated by standard systems that are commonly examined in dynamical systems theory. Five examples are considered here: a constant sequence (the same symbol is repeated), sequences generated by the Rössler and Lorenz systems (both three dimensional ordinary differential equations), the Hénon system (a two dimensional difference equation) and a random number generator. The technical specifications of the systems are given in Appendix Three. The Rössler, Lorenz, Hénon and random data are expressed as real variables. In order to apply a symbolic dynamics-based measure of complexity, it is necessary to project these data sets to a discrete symbol set. There are several possible procedures for doing this. Radhakrishnan, et al. [165] used K-means clustering. While conceptually attractive, the results of K-means clustering can be very sensitive to initial conditions. Bradley and Fayyad [166] addressed this sensitivity by constructing a K-means algorithm that produces a refined initial condition that improved performance. Insofar as we know, this method has not been applied to the problem of converting real data to symbolic data. An alternative approach has been published by Hirata, et al. [167] who approximate a generating partition from a time series using tessellations. This is a computationally demanding procedure and there are practical issues concerning the sensitivity of the partition on the initialization. Steuer, et al [86] recommend using the partition that maximizes entropy. In the present examples, the continuous variable time series is partitioned about the median. In this process, the median is computed from the original time series. A real variable is replaced by symbol '0' if it is less than the median and by symbol '1' if it is greater than or equal to the median. The choice of the median rather than the mean is critical to this process. False-positive indications of deterministic structure in random data can result if the mean is used [168]. The partitioning process is depicted in Figure 9. (It should be noted that in the present paper, the consideration of partitioning protocol only applies to the didactic examples presented in the appendices. The psychotherapy data are symbolic and partitioning is not required).

The grammar complexity values computed from one thousand element symbol sequences generated by these model systems are shown in Figure 10. The results are seen to be consistent with our qualitative understanding of complexity. The constant sequence gives the lowest value, and the random number generator produces the largest value. The ordering Rössler less than Lorenz, less than Hénon is also consistent with expectations based on a visual examination of the time series in the left column of Figure 9.

A critical distinction must be made between the complexity of a message, C_ORIG and the intrinsic complexity of the process that generated the message. The value of grammar complexity will depend on two factors, the complexity of the dynamical process generating the symbol sequence and the length of the symbol sequence. This is seen in the upper panel of Figure 11 where grammar complexity is plotted as a function of the length of the data set. The ordering of complexity values seen with 1000 element sequences in Figure 2 is preserved (random > Hénon > Lorenz > Rössler > constant) and the values increase with the size of the data set. It is therefore necessary to find an effective normalization of complexity values that allows comparison of intrinsic complexities without the complication of data set size.

It might be supposed that dividing C_ORIG by the length of the message is an acceptable solution. It has been shown that this is not the case [169]. An effective normalization of C_ORIG can be achieved by comparing it against the values of complexity obtained from random equiprobable messages of the same length. Let N_α be the size of the symbol alphabet (the number of distinct symbols available for message construction, in these examples N_α = 2). N_α is not message length L_M. An equiprobable surrogate is one where each symbol appears with probability 1/N_α. Let <C_S> denote the average value of complexity obtained from random equiprobable surrogates of length L_M (the subscript s denotes a surrogate). The normalized complexity is defined by

C_N ranges from close to zero for messages containing a single repeated symbol to close to one for messages generated by random processes.

As outlined in Rapp [170], C_N cannot be formed by normalizing against random shuffle surrogates. Consider the case of a message that consists of a single repeated symbol selected from an alphabet of size N_α > 1. (Sequences in a message space of N_α = 1 consist of a single symbol and only differ by length. Trivially, their complexity is the number of bits required to encode length L_M.) An effective normalization should give a low value of C_N to a repeated symbol message. Suppose surrogates were formed by a random shuffle. Since the message contains only one symbol, they all have the same value of complexity. In this case, C_ORIG = <C_S> and hence C_N = 1, which is the complexity of a random message. If instead surrogates are equiprobable on N_α, N_α > 1, then <C_S> is greater than C_ORIG and C_N has a low value. A low value of complexity is expected for a constant sequence.

The uncertainty in C_N, ΔC_N, can be estimated by the following argument

The estimation of ΔC_ORIG has been discussed. <C_S> is the mean complexity computed from a distribution of equiprobable surrogates. Δ<C_S> is the standard deviation of that distribution.

Comparison of C_ORIG and the complexity values obtained with surrogates makes it possible to address the following surrogate null hypothesis:

As assessed by this complexity measure, the sequential structure of the original message is indistinguishable from the sequential structure of an equi-probable, random sequence of the same length constructed from the same symbol alphabet.

Several statistical tests of the null hypothesis have been considered [168]. We use here the Monte Carlo probability of the null hypothesis.

N_SURR is the number of surrogates computed. The number of complexity values tested in the numerator includes the complexity of the original symbol sequence as well as the complexity values obtained with surrogates, ensuring that the numerator has a value of at least one. This statistical test was chosen because it is a distribution-agnostic test, that is, it makes no assumptions about the structure of the C_Surrogate distribution. Surrogates have a random structure, and the grammar complexity gives the highest value to random sequences. We therefore expect the values of C_Surrogate to be greater than the value of C_ORIG if a nonrandom structure is present in the original sequence. The smallest value of P_NULL will be obtained when all values of C_Surrogate are greater than C_ORIG. That minimum value is therefore 1/(1 + N_SURR). In the calculations in Figures 10 and 11, N_SURR = 499 and C_Surrogate > C_ORIG in all cases for the constant sequence, Rössler, Lorenz and Hénon data. The null hypothesis is therefore rejected with P_NULL = .002. As expected, the null hypothesis is not rejected by symbol sequences produced by a random number generator. For the ten cases in Figure 11 corresponding to L_M = 1000, 2000, ... 10,000, the average value of P_NULL obtained with random data is P_NULL = .562

Barnard [171] and Hope [172] have proposed a nonparametric test for rejecting the null hypothesis. Under their criterion the null hypothesis is rejected if C_ORIG < C_Surrogate for all of the surrogates. If this criterion is met, as it is in these calculations, the probability of the null hypothesis is again P_NULL = 1/(1 + N_SURR).

As outlined in Watanabe, et al. [163] reported values of complexity obtained with real variable data requires the specification of:

1. the complexity measure used,

2. the number of symbols in the alphabet,

3. the procedure used to partition values onto the symbol set,

4. the procedure used to generate the surrogates used to calculate C_N,

5. the number of surrogates used, and

6. the statistical procedure used to calculate the probability of the surrogate null hypothesis.

As before let message M be a finite symbol sequence of length L_M. The vocabulary of a symbol sequence, denoted by v{M}, is the set of distinct subsequences that can be found in the message. By definition, a message is an element of its own vocabulary. If, for example, M = 00101, then:

A message can be expressed as a concatenation of substrings. Thus M = 000110100 is equivalent to M = X₁X₂X₃X₄, where X₁ = 0, X₂ = 001, X₃ = 10, and X₄ = 100. An additional element of notation is required. For any message M, the message MM_π is the identical message following deletion of the last symbol. M_π therefore has length L_M-1. This deletion operation can be combined with concatenation. If X₁ = 001 and X₂ = 011, then (X₁X₂)_π = 00101.

For any symbol sequence of length L_M ≥ 3, more than one decomposition into substrings is possible. The Lempel-Ziv algorithm [77] prescribes a procedure for decomposing a message into a concatenation of substrings. Only one decomposition is consistent with the algorithm. The Lempel-Ziv complexity is defined as the number of subsequences produced by this decomposition. In a Lempel-Ziv decomposition, the first subsequence consists of the first symbol only. Subsequence X₂ begins at the second symbol. Symbols are added to this subsequence until X₂ is no longer an element of the vocabulary v{(X₁X₂)_π}. When this occurs, X₂ is complete, and the construction of X₃ begins. Consecutive symbols are added to X₃ until X₃ ∉ v{(X₁X₂X₃)_π}. The construction of X₄ then begins. This procedure continues until the entire message is expressed as a concatenation of N subsequences, M = X₁X₂ ......X_N. The Lempel-Ziv complexity is the integer N, C_LZ = N.

This process can be illustrated by a specific example. Suppose M = 000110100.

M = X₁X₂X₃X₄ and C_LZ = 4. On reflection it can be seen that this decomposition will provide a mechanism for compressing messages. For any J, by construction subsequence (X_J)_π appears somewhere earlier in the message. X_J can therefore be completely specified by three quantities:

When very large messages are analyzed, X_J can be very long, perhaps thousands of symbols. This very long substring can now be replaced by these three quantities. Additional examples and pseudo-code for calculating the Lempel-Ziv complexity are given in Appendix A of Watanabe, et al. [163].

The grammar complexity calculations with data generated by model systems reported in Appendix One were repeated with Lempel-Ziv complexity. The same relative ordering was observed random > Hénon > Lorenz > Rössler > constant (Figure 12).

As shown in Figure 13, Lempel-Ziv complexity shows the same dependence on message length that was observed with grammar complexity. The normalization with equi-probable random surrogates was also implemented with Lempel-Ziv complexity. As before, the normalized complexity is independent of L_M. In these calculations, 499 surrogates were computed and the null hypothesis was rejected with probability P_NIULL = .002 in all cases with the exception of random data where the average value of P_NIULL was .450.

As previously reported [169] grammar complexity and Lempel-Ziv complexity are highly correlated. The complexity values computed with Rössler, Lorenz, Hénon and random data for L_M = 1000, 2000, .... 10,000 element data sets were compared. The Pearson linear correlation coefficient was found to be r = .998 (the same value that was obtained with different data in [169]). The probability of the null hypothesis of no correlation was less than 10^-8.

Five model systems are investigated in the calculations presented in Appendices One and Two. The constant symbol sequence is constructed by repeating one symbol for the entire length of the data set. The Rössler system [173] is a three dimensional system of autonomous ordinary differential equations.

The differential equations were integrated with a step length of h = .1 using a sixth order Runge-Kutta-Hutta algorithm [174]. The Lorenz system [175, 176] is specified by

As in the case of the Rössler equations, a Runge-Kutta-Hutta calculation was performed with h = .1. The Hénon system [177, 178] is a two dimensional difference equation.

The random number generator [179] produced uniformly distributed random numbers on [0,1]. It is based on L'Ecuyer's two-sequence generator [180] and incorporates a Bays-Durham shuffle [181].