An Entropy Measure of Non-Stationary Processes

Abstract

Shannon’s source entropy formula is not appropriate to measure the uncertainty of non-stationary processes. In this paper, we propose a new entropy measure for non-stationary processes, which is greater than or equal to Shannon’s source entropy. The maximum entropy of the non-stationary process has been considered, and it can be used as a design guideline in cryptography.

1. Introduction

Information science considers an information process, uses the probability measure for random states and Shannon’s entropy as the uncertainty function of these states [1–3]. For a stationary source, the probability and the Shannon’s entropy can be determined by using statistical physics methods, while for a non-stationary source, all the statistical physics methods fail, thus the Shannon entropy measure may not be available. Till now, the entropy of non-stationary process is still not fully understood, except for some specific types of non-stationary process [4] that use the following entropy formula to measure the uncertainty:

$$H=-\int P(x,t)\hspace{0.17em}\text{ln\hspace{0.17em}}P(x,t)dx$$

(1)

This kind of non-stationary process requires a known probability function, and the probability function is deterministically varied. This formula will fail if the probability function of the non-stationary process is stochastically varied. For a non-stationary process, if its parametric is a stationary random variable, then this kind of non-stationary process can be considered as a piecewise stationary process, and many papers use the following source entropy formula, proposed by Shannon, to measure the uncertainty [5–9]:

$$H=\sum _i{p}_i{H}_i=-\sum _{i,j}{P}_i{p}_i(j)\hspace{0.17em}\text{log\hspace{0.17em}}{p}_i(j)$$

(2)

where for each possible state i there will be a set of probabilities p_i(j) of producing the various possible symbols j.

In this paper, we will consider the non-stationary process, with its parametric be a stationary random variable. We will show that the entropy of this kind of non-stationary process should not be measured by Shannon’s source entropy (Equation (2)). Actually, Shannon’s source entropy Equation (2) is only used for a stationary process with multiple-states, not for non-stationary processes. In our paper, we will propose an entropy formula to measure the uncertainty of non-stationary processes. Our entropy measure is greater than or equal to Shannon’s source entropy formula. These two measures are equal if and only if the process is stationary. Our entropy measure can be used as a complexity criterion of non-stationary processes and as a design guideline for cryptographic uses.

The rest of this paper is organized as follows: Section 2 shows that Shannon’s source entropy formula is not appropriate to measure the uncertainty of non-stationary processes. In Section 3, a new entropy formula is proposed to measure the uncertainty of non-stationary processes and some properties are presented. In Section 4, the maximum entropy of the non-stationary process is considered. Section 5 concludes the paper.

2. The Limitation of Shannon’s Source Entropy in Non-Stationary Process

First, let’s consider the following two examples, one is for discrete source and the other is for continuous source:

• Example 1. Consider a discrete source of two kinds of symbol 0 and 1. This discrete source varies between the states “1” and “2” randomly with probabilities P₁ = 0.2 and P₂ = 0.8. For state “1”, the probability of producing the symbol 0 is 0.4, and producing the symbol 1 is 0.6. For state “2”, the probability of producing the symbol 0 is 0.3, and producing the symbol 1 is 0.7. Obviously, this discrete source is non-stationary. By using Shannon’s source entropy Equation (2), we have H = 0.6233. By calculating the entropy of the 01 sequences which generated by this discrete source, we have H approaches to 0.629 with the sequence length increased, which is bigger than Shannon’s source entropy measure.

• Example 2. Consider a continuous source of a parameter-varied normal distribution N(μ, 1), which parameter μ varies between μ₁, μ₂, …, μ_n randomly with probabilities p₁, p₂, … ,p_n. Obviously, this continuous source is non-stationary. By using Shannon’s source entropy Equation (2), we have H = 0.5ln2πe, which is not relevant to μ. Then, the uncertainty of this non-stationary source equals to the uncertainty of normal distribution source with fixed μ as N(0, 1), which is not convinced (the variation of parameter μ also brings some of uncertainty when determining the states).

Therefore, Shannon’s source entropy formula is not appropriate to measure the uncertainty of a non-stationary process. The entropy of non-stationary processes is always bigger than Shannon’s source entropy measure. Next, we will analyze why this happens.

Let s₁s₂…s_i(1)s_i(1)+1…s_i(2)s_i(2)+1…s_N be a symbol sequence generated by the source of Example 3, which s₁s₂…s_i(1) is generated by a fixed random parameter, s_i(1)+1…s_i(2) is generated by a fixed random parameter, and so on. For the first symbol s₁, its uncertainty can be written as h(p) o H¹. Here, h(p) is the uncertainty of varying parameter, and H¹ is the uncertainty of symbol s₁ with a known parameter. “o” is an operator which has the following properties:

(1)

0 o a = a.

(2)

a o b = b o a ≥ max(a, b).

(3)

a o b = a if and only if b = 0.

For the symbol s₂, its uncertainty is H², without h(p) for its parameter is determined. For the symbol s_i(1)+1, its uncertainty is h(p) o Hⁱ⁽¹⁾⁺¹, …. Then the average uncertainty of this non-stationary source can be written as:

$$\underset{N\to \infty }{\text{lim}}\frac{1}{N}(\frac{N}{E|s_{i(j)+1}\dots s_{i(j+1)}|}h(p)\circ \sum H^i)=\frac{1}{E|s_{i(j)+1}\dots s_{i(j+1)}|}h(p)\circ \sum _i{p}_i{H}_i\ge \sum _i{p}_i{H}_i$$

(3)

here, E|s_i(j)+1…s_i(j+1)| is the average length of symbol sequence by each parameter. The “=” holds if and only if the source is stationary, which degenerate to Shannon’s source entropy measure.

3. The Entropy of Non-Stationary Process and Its Properties

According to the Boltzmann-Gibbs theorem, we should consider all the possible states and their probabilities when we measure the uncertainty of a source. Consider a non-stationary process which varies randomly in n kinds of possible states. The probabilities of each states are p₁, p₂, …, and p_n respectively. For the state i, the output variable satisfies the probability density function f_i. The probability of generating a N-length sequence by this non-stationary source is:

$$\prod _{i=1}^N(\sum _j{p}_j{f}_j)$$

(4)

Then, the uncertainty of the N-length sequence is:

$$h=-\int \prod _{i=1}^N(\sum _{j=1}{p}_j{f}_j)\text{log}(\prod _{i=1}^N(\sum _{j=1}{p}_j{f}_j))dx$$

(5)

The average uncertainty of this non-stationary process is:

$$H=\underset{N\to \infty }{\text{lim}}h/N$$

(6)

Theorem 1. $\int {\displaystyle \prod _{i=1}^N}{f}_i\hspace{0.17em}\text{log}({\displaystyle \prod _{i=1}^N}{f}_i)dx={\displaystyle \sum _{i=1}^N}\int f_i\hspace{0.17em}\text{log\hspace{0.17em}}{f}_{i}dx$

Proof

First, we consider the case N = 2. We have:

$$\begin{array}{l}\int \int f_1{f}_2\hspace{0.17em}\text{log\hspace{0.17em}}{f}_1{f}_{2}d{x}_{1}d{x}_2=\int \int (f_1{f}_2\hspace{0.17em}\text{log\hspace{0.17em}}{f}_1+f_1{f}_2\hspace{0.17em}\text{log\hspace{0.17em}}{f}_2)d{x}_{1}d{x}_2\\ =\int f_1\hspace{0.17em}\text{log\hspace{0.17em}}{f}_{1}d{x}_1+\int f_2\hspace{0.17em}\text{log\hspace{0.17em}}{f}_{2}d{x}_1\end{array}$$

Assume the equation holds when N = k. Then for N = k + 1, denote ${\displaystyle \prod _{i=1}^k}{f}_i=f(k)$, then we have:

$$\begin{array}{c}\int \prod _{i=1}^{k+1}{f}_i\hspace{0.17em}\text{log}(\prod _{i=1}^{k+1}{f}_i)dx=\int f(k)f_{k+1}\hspace{0.17em}\text{log}(f(k)f_{k+1})dx=\int f(k)\hspace{0.17em}\text{log\hspace{0.17em}}f(k)+\int f_{k+1}\hspace{0.17em}\text{log\hspace{0.17em}}{f}_{k+1}\\ =\sum _{i=1}^{k+1}\int f_i\hspace{0.17em}\text{log\hspace{0.17em}}{f}_{i}dx\end{array}$$

Thus, concluding our proof.

According to Equations (5) and (6) and theorem 1, the entropy of the non-stationary process can be written as:

$$H=-\int (\sum _i{p}_i{f}_i)\hspace{0.17em}\text{log}(\sum _i{p}_i{f}_i)dx$$

(7)

Equation (7) is the entropy formula of the non-stationary process when the states vary discretely. For a continuously case, the entropy formula can be written as:

$$H=-\int (\int g(y)f_{y}dy)\hspace{0.17em}\text{log}(\int g(y)f_{y}dy)dx$$

(8)

Here, g(y) is the probability density function of the varying state and f_y is the probability density function of the output variable for each state y. We have that by using the entropy equations (7) and (8) instead of Shannon’s source entropy, there are no such inconsistencies as proposed in examples 1 and 2.

Theorem 2

Let H_S and H be the Shannon’s entropy measure and our entropy measure of a non-stationary process respectively, H(p) be the Shannon’s entropy of the varying states. We have the following inequality hold:

$$H_s\le H<H_s+H(p)$$

Proof

We use Equation (7) as our entropy formula (states vary discretely). For the continuous case, it can be proven similarly.

We consider H – H_s, and have:

$$\begin{array}{l}H-H_s=-(\int (\sum _i{p}_i{f}_i)\hspace{0.17em}\text{log}(\sum _i{p}_i{f}_i)dx+\sum _{i=1}^n{p}_i{H}_i)\\ =-\int ((\sum _i{p}_i{f}_i)\hspace{0.17em}\text{log}(\sum _i{p}_i{f}_i)-\sum _{i=1}^n{p}_i{f}_i\hspace{0.17em}\text{log\hspace{0.17em}}{f}_i)dx\\ =-\int \sum _i{p}_i{f}_i\hspace{0.17em}\text{log}(\frac{\sum p_i{f}_i}{f_i})dx\end{array}$$

Due to $\frac{\sum p_i{f}_i}{f_i}>p_i$, we have:

$$H-H_s<-\int \sum _i{p}_i{f}_i\hspace{0.17em}\text{log\hspace{0.17em}}{p}_{i}dx=\sum _i(-\int f_i{p}_i\hspace{0.17em}\text{log\hspace{0.17em}}{p}_{i}dx)=-\sum _i{p}_i\hspace{0.17em}\text{log\hspace{0.17em}}{p}_i=H(p)$$

Thus, we have H < H_s + H(p). Additionally, consider the following functional F:

$$F=H-H_s=-\int \sum _i{p}_i{f}_i\hspace{0.17em}\text{log}(\frac{\sum p_i{f}_i}{f_i})dx$$

It is easily to prove that functional F reaches its minimum when f₁ = f₂ = … = f_n, we have:

$$F\ge -\int \sum _i{p}_i{f}_i\hspace{0.17em}\text{log}(\frac{f_1\sum p_i}{f_1})dx=-\int \sum _i{p}_i{f}_1\hspace{0.17em}\text{log}(\sum p_i)dx=0$$

Thus, we have H ≥ H_s, which concluding our proof.

Theorem 2 shows that the entropy of non-stationary process is greater than or equal to the Shannon’s entropy measure. These two measures are equal if and only if the process is stationary. Furthermore, H < H_s + H(p) means that the entropy of non-stationary process cannot be written as the sum of H_s and H(p), although its uncertainty is brought by these the aspects. In another word, they are not independent of each other.

4. Maximum Entropy and Its Application in Cryptography

In recent years, chaotic systems were regarded as an important pseudorandom source in the design of random number generators [10–12]. As we know, chaotic systems may be attacked by phase space reconstruction and nonlinear prediction techniques. If the system is abiding references [13–15] propose a chaotic system with varying parameters to resist these attacks. However, the varying method is rather simple. A more secure method is to vary the parameters in a random-like way, then the output sequence come to be non-stationary. Entropy is an important criterion in cryptographic use. With our entropy formula of non-stationary process, we can compare the different varying methods and guide us to design a varying method in order to make the entropy maximum. It can be expressed as the following mathematical problem.

P1

The maximum of functional:

$$H=-\int (\sum _i{p}_i{f}_i)\hspace{0.17em}\text{log}(\sum _i{p}_i{f}_i)dx$$

under the condition ${\displaystyle \sum _i}{p}_i=1$ and 0 ≤ p_i ≤ 1.

Design a Lagrange functional:

$$L=-\int (\sum _i{p}_i{f}_i)\hspace{0.17em}\text{log}(\sum _i{p}_i{f}_i)dx+\lambda (p_1+p_2+\dots +p_n-1)$$

Solve the following equations:

$$\{\begin{array}{l}\frac{\partial L}{\partial p_i}=0\hfill \\ \frac{\partial L}{\partial \lambda }=0\hfill \end{array}$$

Compare these extreme values in order to get the maximum entropy and the corresponding p_i.

Consider the discrete case (the output variables of each states are discrete). Assume the non-stationary process is varying in n kinds of possible states a₁, a₂, … , a_n with probabilities p₁, p₂, … , p_n. For each state a_i, the output variables are b₁, b₂, … , b_N and the probabilities are f_i1, f_i2, … , f_iN respectively. Then, the entropy of this non-stationary process is:

$$H=-\sum _{j=1}^N(\sum _{i=1}^n{p}_i{f}_{ij}\hspace{0.17em}\text{log}\sum _{i=1}^n{p}_i{f}_{ij})$$

(9)

By using the above Lagrange method, we have that the entropy (9) reach its maximum value when the following equation holds:

$$\sum _{i=1}^n{p}_i{f}_{i1}=\sum _{i=1}^n{p}_i{f}_{i2}=\cdots =\sum _{i=1}^n{p}_i{f}_{iN}=\frac{1}{N}$$

The maximum entropy is logN which equals to the stationary uniform distribution.

For the continuous case (the output variables of each states are continuous), the method is similar. Next, we show two simple examples.

• Example 3. Consider a non-stationary process which varies between two possible states a₁ and a₂ with probabilities p₁ and p₂ respectively. For state a₁, the output variables are b₁ and b₂ with probabilities f₁₁ = 0.75 and f₁₂ = 0.25. For state a₂, the output variables are b₁ and b₂ with probabilities f₂₁ = 1/3 and f₂₂ = 2/3. By solving the maximum entropy problem, we have that the entropy reaches its maximum value when p₁ = 0.4, p₂ = 0.6, and H_max = log2.

• Example 4. Consider a non-stationary process which varies in two states a₁ and a₂ with probabilities p₁ and p₂ respectively. For state a₁, the output variables satisfy the normal distribution N(0, 1). For state a₂, the output variables satisfy the normal distribution N(1, 1). By solving the maximum entropy problem, we have that the entropy reaches its maximum value when p₁ = 0.5, and H_max = 1.5304. Figure 1 shows the relation between the Entropy and p₁.

5. Conclusions

In this paper, we first prove that Shannon’s source entropy is not appropriate to measure the uncertainty of non-stationary processes. Then, we propose an entropy formula to measure the uncertainty of such non-stationary processes. Our entropy measure is greater than or equal to Shannon’s source entropy formula. These two measures are equal if and only if the process is stationary. Furthermore, we study the maximum entropy of our entropy formula. The maximum entropy can be used as a guideline for constructing a non-stationary source in cryptographic uses.