6_521_qian.dvi


EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS

Vol. 3, No. 1, 2010, 51-80

ISSN 1307-5543 – www.ejpam.com

Stochastic Complexity, Histograms and Hypothesis Testing of

Homogeneity

Guoqi Qian

Department of Mathematics and Statistics, University of Melbourne, VIC 3010, Australia.

Abstract. Information contained in a sample of quantitative data may be summarized or described

by a nonparametric histogram density function. An interesting question is how to construct such a

histogram density to express the data information with minimum stochastic complexity. The stochastic

complexity is a pseudonym of Rissanen’s minimum description length (MDL) which gives the length of

a sequence of decipherable binary code resulted from optimally encoding the data information using

a probability distribution based code-book. Here we have derived an optimal generalized histogram

density estimator to provide both predictive and non-predictive coding description of a data sample.

We have also obtained uniform and almost sure asymptotic approximations for the lengths of both

descriptions. As an application of this result to statistical inference a new procedure for hypothesis

testing of distribution homogeneity is proposed and is proved to have an asymptotic power of 1.

2000 Mathematics Subject Classifications: 62G07, 62G20, 60G10

Key Words and Phrases: Histogram density estimation, Minimum description length, Model selection,

Quantization, Stochastic complexity, Test of homogeneity

1. Introduction

In digital data-transmission systems, input signals are first converted into digital form

at the transmitter, then transmitted through a communication channel and finally recon-

structed into output signals at the receiver. At the transmitter a quantization procedure is

often executed in which the whole range of input amplitudes is divided into a finite number

of amplitude sub-ranges and the input amplitudes in each sub-range are converted into the

same digits. Such input digits are further encoded into a sequence of prefix binary digits for

transmission. (Prefix codes are spontaneously and uniquely decipherable to where they are

processed.) In order to achieve a cost-efficient transmission, an optimal encoding system is

necessary by which the input binary digits sequence is as short as possible.

By Rissanen’s stochastic complexity theory or principle of minimum description length

(MDL) [18, 15, 13, 12, 11, 9], finding an optimal encoding system is equivalent to finding

Email address: g.qian�ms.unimelb.edu.au. (G. Qian)

http://www.ejpam.com 51 c© 2009 EJPAM All rights reserved.



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 52

the probability distribution underlying the input signals. [4, 3, 2] has developed an alter-

native theory of prequential analysis which implies the same conclusion. Another related is

Bozdogan’s information complexity criterion (ICOMP) (cf. [1]). However, the probability

distribution for the input signals is mostly unknown and has to be estimated. In the context

of digital data-transmission involving quantization aforementioned, it is sufficient to find a

histogram density estimator of the probability distribution for the input data. A histogram

density estimator is specified by a sequence of subintervals partitioning the range of the data

(as corresponding to the input amplitude sub-ranges in quantization), and the probability

values over all such subintervals.

Once a histogram density estimator is properly obtained, it determines the quantization

of the input data and further enables the construction of an encoding system to encode the

quantized input data. The length of the input binary codes obtained under this encoding

system then measures the amount of information to be transmitted to the receiver, and we

call it a summary description of the input data. The shorter this description is the more cost-

efficient data transmission it would imply. Clearly, the optimal histogram density estimator

is the one that would result in the shortest description of the input data. The discussions so

far manifest the core of stochastic complexity theory — the principle of minimum description

length — in the context of digital data-transmission.

The principles of MDL and maximum likelihood together provide a way for finding the best

histogram density estimator. Suppose the input for digital transmission is a finite data-string

X n = (X1, · · · , Xn) from a system involving chance, and we wish to estimate the probability

distribution of this system by a histogram density for X n. When number and locations of the

subintervals to be used are specified for a histogram density estimator, the optimal probability

over each subinterval can be determined by the maximum likelihood principle. When only

the number of subintervals used in a histogram density estimator is specified, the optimal

locations of the subintervals can also be determined by the maximum likelihood principle

together with a recursive method. Thus for each specified number of the subintervals, a tem-

porary histogram density estimator can be constructed which then provides a description of

X n with an appropriate prefix code-length. The optimal number of subintervals and accord-

ingly the best histogram density estimator are therefore obtained from finding the shortest

prefix code-length for data description.

Having seen the relationship between the best histogram density estimator and the short-

est prefix code-length for data description, we now focus on investigating the shortest de-

scription length of X n. Note that the prefix codewords of X n can be obtained by either a

non-predictive two-step or a predictive manner (see Chapter 3 of [13]). Even though the pre-

dictive coding requires longer codewords for encoding X n, it enables the data-transmission

system for self-adjustment and updating by using the data in a progressive way.

In Section 2 below we first discuss an optimal quantization scheme of the data for optimal

description. The scheme provides a system of recursive equations for determining the optimal

locations of the subintervals in the histogram estimator. Then lengths of both two-step and

predictive codewords for the description of X n are given using the MDL principle. Finally,

uniform almost sure asymptotic expansion and the almost sure lower and upper bounds for

both code lengths are derived and the results are list in Theorem 2 to Theorem 4.



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 53

In [7] and [20], the same type of stochastic complexity based histogram estimation is

considered under the assumption of equal subinterval widths. Our results agree with theirs

when this assumption applies.

As an application of stochastic complexity for optimal data description, in Section 3 we

consider the problem of testing of homogeneity, i.e. the testing of the hypothesis that several

independent samples are generated from the same population. A test procedure is proposed

in which we use difference of the shortest predictive code lengths under the null and the

alternative hypotheses respectively as a universal test statistic. The size of the test procedure

is shown to be determined by the part of the code lengths which is used to describe the

parameters in the histogram densities. The asymptotic power of the test procedure is shown

to be 1.

2. Data Quantization for Optimal Information Description

Suppose X n = (X1, · · · , Xn) is a simple random sample from an unknown density function

f on [s, t], where s and t are finite real numbers. If f were known, the description of the

sample could be accomplished by constructing a string of predictive binary codes for X n un-

der the information source determined by f where the description length is proportional to

− log f (X n). (See [13]; also the logarithm is in base 2 throughout this paper unless stated oth-

erwise.) In other words, describing the sample is the same as finding a predictive probability

density for the sample.

To estimate the unknown density f a frequently used method is based on data quantiza-

tion: first quantize X n by partitioning [s, t] into a sequence of subintervals and then construct

a histogram on the partition. The choice of the partition and the estimate of the probability

for each subinterval may be determined by the maximum likelihood method if the number of

subintervals is fixed.

Let qm = (q0,m,q1,m, · · · ,qm,m) be an increasing sequence of numbers, partitioning the

interval [s, t] into m subintervals [q0,m,q1,m], (q1,m,q2,m], · · · , (qm−1,m,qm,m], written as

Q1,m,Q2,m, · · · ,Qm,m, where q0,m = s, qm,m = t and m is a fixed integer satisfying m ≤ n.

Denote ri,m = qi,m − qi−1,m as the length of Q i,m and r = t − s, the range of X n. Consider the

histogram densities defined by

f (x |pm,qm, s, t) =

m
∑

i=1

pi,m

ri,m

IQi,m
(x) (1)

where pm = (p1,m, p2,m, · · · , pm,m) denotes a sequence of nonnegative parameters with the

sum equal 1, and IQi,m
(·) is the usual indicator function. The class of densities of the form (1)

is denoted by Hm.

With the above notation, the log-likelihood function of the sample X n under Hm is

L(X n; Hm) =

n
∑

j=1

log

 

m
∑

i=1

pi,m

ri,m

IQi,m
(X j)

!

=

m
∑

i=1

ni,m log
pi,m

ri,m

(2)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 54

where ni,m =
∑n

j=1 IQi,m
(X j) is the number of data points falling into Q i,m. If ni,m equals zero,

the corresponding pi,m may not be uniquely optimized through maximization of L(X n; Hm).

This difficulty may be overcome by introducing m numbers y1, · · · , ym (abbreviated as ym,

where yi is regarded as an observation from the uniform distribution on Q i,m, and mixing

them thoroughly with the n observations X n as if both ym and X n were generated from the

same distribution. Then the log-likelihood function of X n and ym is

L1(X
n; Hm) =

m
∑

i=1

(ni,m+ 1) log
pi,m

ri,m

(3)

which does not depend on the particular values of ym, and can, therefore, be regarded as the

log-likelihood function of X n.

Applying the maximum likelihood principle the optimal partition qm and probabilities

pm for a fixed m are the ones which maximize L1(X
n, Hm) subject to the conditions that

∑

pi,m = 1 and
∑

ri,m = r. Denoting

F =

m
∑

i=1

(ni,m+ 1) log
pi,m

ri,m

+λ1(

m
∑

i=1

pi,m− 1)+λ2(

m
∑

i=1

ri,m− r), (4)

differentiating F with respect to pi,m’s and setting the derivatives equal to zero we have

∂ F

∂ pi,m

=
ni,m+ 1

pi,m

log e+λ1 = 0, i = 1,2, · · · , m (5)

from which pi,m = (ni,m + 1)/(n + m). Differentiating F with respect to pi,m’s twice, the

resulting second derivative matrix

�

∂ 2F

∂ pi,m∂ p j,m

�

= (log e)diag

 

−n1,m+ 1

p2
1,m

, · · · ,−nm,m+ 1

p2
m,m

!

≤ 0. (6)

Therefore a necessary condition for the maximization of (4) is that the probabilities pi,m are

equal to the relative frequencies (ni,m+ 1)/(n+m).

Both the allocation of ni,m’s and the ranges ri,m’s depend on the partition qm. Thus the

function F is not continuous with respect to ri,m’s unless the allocation of ni,m’s does not

change. Under such allocation the local maximum/minimum value of L1(X
n; Hm) is achieved

or converged to when ri,m’s approach to their boundary values, i.e. where the resultant al-

location of ni,m’s would just about to change. Therefore, the global maximization of F with

respect to ri,m’s may not exist. In the light of the above discussions and in order to keep the

code length needed for model description short, we may reasonably impose the restriction

that the end points of every subinterval Q i,m, except the two end points s and t, i.e. the se-

quence of the break points qi,m, · · · ,qm−1,m, should be at least d units away from the nearest

observations, where d > 0 is half of the precision of X n. In other words, if the locations of the

sample X n are expressed in an ascending order zN = z1 < z2 < · · ·< zN , where N ≤ n because

of possible ties, then qm is a subsequence of the 2N + 2 long sequence

s, z1 − d , z1 + d , z2 − d , z2 + d , · · · , zN − d , zN + d , t, (7)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 55

denoted as s(X n) = s1, s2, · · · , s2N+2, with q0,m = s and qm,m = t, such that the selected qm

achieves the largest likelihood L1(X
n; Hm) among all the selections.

There are
� 2N

m−1

�

different selections for qm within which the optimal sequence is to be

found. In the following we provide a recursive method for finding the optimal qm as well as

the associated maximum likelihood value. A similar technique is used in [14]. Let

L∗1(X
n; m) = max

qm⊂s(X n)
max

pm:
∑

pi,m=1
L1(X

n; Hm) = max
qm⊂s(X n)

m
∑

i=1

(ni,m+ 1) log
ni,m+ 1

(n+m)ri,m

. (8)

It is easy to see that

L∗1(X
n(τ); m)= max

sm−1≤qm−1,m∈s(X n(τ))

(

max
{q1,m,··· ,qm−2,m}∈s(X n(qm−1,m))

L1(X
n(qm−1,m); Hm−1)

+(n(τ)− n(qm−1,m) + 1) log
n(τ)− n(qm−1,m) + 1

(n(τ)+m)rm,m

«

= max
sm−1≤ν∈s(X n(τ))

¨

L∗1(X
n(ν); m− 1) + (n(τ)− n(ν) + 1) log

n(τ)− n(ν) + 1

(n(τ)+m)rm,m

«

(9)

where X n(ν) denotes the sequence of the observations falling within [s,ν], and n(ν) denotes

the number of the observations in X n(ν). The recursive equation (9) are to be solved for m ≥ 1

and ν ∈ s(X n(τ)) with τ ≤ t until the desired range includes all the observations. That is, the

following maximum log-likelihood functions need to be solved in sequence

L∗1(X
n(s2), 1), L∗1(X

n(s3), 1), · · · , L∗1(X
n(t), 1),

L∗1(X
n(s3), 2), L∗1(X

n(s4), 2), · · · , L∗1(X
n(t), 2),

· · · · · · (10)

L∗1(X
n(sm+1), m), L∗1(X

n(sm+2), m), · · · , L∗1(X
n(t), m),

for m≤ n, where

L∗1(X
n(si), 1) = (n(si) + 1) log

1

si − s
, 2≤ i ≤ 2N + 2 (11)

and

L∗1(X
n(sk), k− 1) =

k−1
∑

i=1

(n(si+1)− n(si) + 1) log
n(si+1)− n(si) + 1

(n(sk) + k− 1)(si+1− si)
, (12)

for 2 ≤ k ≤ n + 1. For any fixed m ≤ n, the evaluation of (9) gives the maximum log-

likelihood for X n as well as the optimal partition {Q̃ i,m} with about m(4N + 3 − m)/2 ≤
2m(n+ 2)− m2/2 operations. The corresponding optimal sequence of break points will be

denoted by q̃m = (q̃1,m, · · · , q̃m,m), and the width of the subintervals by r̃1,m, · · · , r̃m,m. In this



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 56

paper data quantization will always be based on the optimal partition {Q̃ i,m} (except in the

case of equal width quantization). For sake of simple presentation the number of the data

points falling into {Q̃ i,m} will still be denoted as ni,m =
∑n

j=1 IQ̃i,m
(X j).

With an optimal procedure for the quantization of the data, we are now in a position to

find the description of the data X n. Following [13], the description length of the data X n, for

fixed m and corresponding q̃m, is defined as a two-part code length

−L∗1(X
n; m) + L2(q̃

m, m,δ) (13)

where the first part −L∗1(X
n; m) can be interpreted as the code length needed to describe the

data X n under the given partition and histogram density estimator, and the second part L2 is

the code length needed to describe the functional form of the partition and histogram model

employed. L2 can be obtained by first truncating the parameter m and q̃m to a prescribed

precision δ and then encoding the resulting integers with the technique introduced in [5] and

[13]. Denote ā = [a/δ] as the nearest integer to a/δ, then

L2(q̃
m, m,δ) = log

�

∑m−1

i=1

�

�

�r̃i,m− r

m

�

�

�+m− 2

m− 2

�

+ log2.865+ log∗(m̄+ |s̄|+ r̄ + 1) +

log
(m̄+ |s̄|+ r̄ + 3)!

(m̄+ |s̄|+ r̄)!2!
+ log

4!

a+!(3− a+)!
+ | logδ|. (14)

Here log∗(a) = log a+ log log a+ · · · , with the sum including all the positive iterates, and a+
is the number of nonnegative items in {m̄, s̄, r̄}.

The length function (14) consists of three parts. Since the encoding of q̃m is equivalent

to the encoding of r̃1,m − r/m, · · · , r̃m−1,m − r/m, this will be achieved by a binary string

beginning with r̃1,m− r/m 0’s and a 1, followed by r̃2,m − r/m 0’s and a 1, and so on until

r̃m−1,m− r/m 0’s being added, but without attaching a 1 at the end, provided that m, s, t and

d are given. Under this non-prefix encoding procedure the first term of (14) gives the code

length of q̃m. The second to the fifth terms of (14) are the code length needed for encoding

m̄, s̄ and t̄ (equivalent to m̄, s̄ and r̄) in a prefix manner. In general we can encode a set of

integers {θ1, · · · ,θb} in a prefix manner with about

L3(θ1, · · · ,θb) = log2.865+ log∗(θ + 1)+ log
(θ + b)!

θ !(b− 1)!
+ log

(b+ 1)!

b+!(b− b+)!
(15)

bits. Here θ =
∑

i |θi|, and b+ is the number of nonnegative items in {θ1, · · · ,θb}. The last

term of (14) gives us the code length for encoding the truncation precision δ. Since a+ equals

either 2 or 3, the fifth term of (14) can be replaced by 1 reflecting the fact that one digit is

needed to tell if s̄ is negative or nonnegative.

With the description length defined by (13) the shortest code length for the data X n by

the above coding procedure is

min
m
{−L∗1(X

n; m) + L2(q̃
m, m,δ)}



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 57

= −
m∗
∑

i=1

(ni,m∗ + 1) log
ni,m∗ + 1

(n+m∗)r̃i,m∗
+ L2(q̃

m∗ , m∗,δ) (16)

where the minimization is done by searching for an optimal integer m∗ ≤ n and δ is a pre-

scribed precision.

If the sequence of break points are distributed uniformly in the interval [s, t], then r̃i,m =

r/m and the first term of (14) becomes zero. The code length (16) turns out to be

min
m

(

−
m
∑

i=1

(ni,m+ 1) log
(ni,m+ 1)m

(n+m)r
+ L3(m, s̄, r̄) + | logδ|

)

. (17)

An alternative to (16) is to use the idea of the shortest predictive code length. This idea

involves the ordering of the data X n, either by location or by time of arrival, then finding

the histogram density estimate based on the past and making appropriate modifications each

time a new observation comes [13, 20]. In our situation the data X n is ordered by location,

as X(1) ≤ X(2) ≤ · · · ≤ X(n). For any fixed m ≤ n, an optimal sequence of break points q̃m is

obtained by solving the recursive equation (9). Let i(X( j)) be the unique integer i such that

X( j) ∈ Q̃ i,m, and ni,m(ν) =
∑

X l≤ν IQ̃i,m
(X l) be the number of those X l ’s satisfying X l ≤ ν and

falling into the i-th subinterval Q̃ i,m. The histogram density estimator based on the first j

observations X(1), · · · , X( j) can be written as

f̃ (x |X(1), · · · , X( j), m) =

m
∑

i=1

ni,m(X( j)) + 1

( j+m)r̃i,m

IQ̃i,m
(x) (18)

and the likelihood of X n can be constructed in a predictive manner as

f̃ (X n; m) =

n
∏

j=1

f̃ (X( j)|X(1), · · · , X( j−1), m)

=

n
∏

j=1

ni(X( j)),m
(X( j−1)) + 1

( j− 1+m)r̃i(X( j)),m

=
(m− 1)!

(n+m− 1)!

m
∏

i=1

ni,m!

r̃
ni,m

i,m

. (19)

In [14] − log f̃ (X n; m) is defined as the (predictive) stochastic complexity of X n under the

given partition. Now the shortest predictive code length for the data X n is

min
m

¦

− log f̃ (X n; m) + L2(q̃
m, m,δ)

©

= −
m̂
∑

i=1

log ni,m̂!+

m̂
∑

i=1

ni,m̂ log r̃i,m̂− log
(m̂− 1)!

(n+ m̂− 1)!
+ L2(q̃

m, m,δ) (20)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 58

where the minimization is achieved at m̂ ≤ n and δ is a prescribed precision. In particular,

when the subintervals are of equal length, the expression (20) becomes

min
m

¨

n log
r

m
+ log

�

n

n1,m, · · · , nm,m

�

+ log

�

n+m− 1

n

�

+ L3(m, s̄, r̄)+ | logδ|
«

. (21)

Having obtained the shortest code length (16) and shortest predictive code length (20), it

is natural to ask how they differ in values. An asymptotic result is given below with its proof

to be presented in Section 4.

Theorem 1. Let X n be a simple random sample from an unknown density function f on [s, t].

Suppose the following conditions are satisfied:

(i). 0< c1 ≤ f ≤ c2 <∞, where c1 and c2 are constants;

(ii). The number of subintervals m in the quantization of X n satisfies

nγ1 ≤ m≤ nγ2 , (22)

where γ1 and γ2 are two constants satisfying 0< γ1 < γ2 < 1;

(iii). The width r̃i,m of each optimal subinterval Q̃ i,m satisfies

b1m−α1 ≤ r̃i,m ≤ b2m−α2 (23)

uniformly for integers m in [nγ1 , nγ2], where b1, b2, α1,α2 are constants satisfying 1 ≤
α1 <

1

2
+ 1

2γ2
, and max{0,2α1 − 1

γ2
}< α2 ≤ 1.

Then uniformly in m ∈ [nγ1 , nγ2], the difference between the shortest code length and the shortest

predictive code length of X n is

− log f̃ (X n; m) + L∗1(X
n; m) = α′m log m+

1

2
m log n+O(m) a.s. (24)

where −1

2
α1 ≤ α′ ≤ −3

2
+α1.

Note that if the support of the density f is finite, then α2 ≤ 1 ≤ α1 is necessary for

condition (iii) to hold. Also conditions (ii) and (iii) imply that α2 ≤ 1 ≤ α1 <
1

γ2
< 1

γ1
.

Further, the righthand side of (24) becomes 1

2
m log n

m
+O(m) a.s. if α1 = α2 = 1.

From Rissanen (2007) we know that the Shannon complexity is

− log f n(X n) = −∑n

i=1 log f (X i) if X n is a simple random sample. The expectation of Shannon

complexity represents the shortest code length of X n on average if the underlying density f

is known. The following three theorems show how the shortest code length (16) and the

shortest predictive code length (20) differ from the Shannon complexity. The proof of these

theorems will be presented in Section 4.

Theorem 2. In addition to the conditions (i), (ii) and (iii) in Theorem 1, suppose that



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 59

(iv). f is absolutely continuous with derivative ḟ a.e. such that | ḟ (x)| ≤ c3 with c3 a constant.

Then uniformly in m ∈ [nγ1 , nγ2] we have

(1).

−Amα1 + (α2 −α1)m log m+ o(nm−2α2 +m log m)

≤ −L∗1(X
n; m) + L2(q̃

m, m,δ) + log f n(X n)

≤ (α1 − 1)m log m+ C f nm−2α2 + o(nm−2α2 +m log n) a.s. (25)

if either α1 6= 1 or α2 6= 1; and

−L∗1(X
n; m) + L2(q̃

m, m,δ) + log f n(X n) = O(nm−2+m log n) a.s. (26)

if α1 = α2 = 1.

(2).

−Amα1+ 1

2
m log n+ (α2− 3

2
α1)m log m+ o(nm−2α2+m log m)

≤ − log f̃ (X n; m) + L2(q̃
m, m,δ) + log f n(X n)

≤ 1

2
m log n+ (2α1− 5

2
)m log m+ C f nm−2α2 + o(nm−2α2+m log n) a.s. (27)

if either α1 6= 1 or α2 6= 1; and

− log f̃ (X n; m) + L2(q̃
m, m,δ) + log f n(X n) =

1

2
m log

n

m
+ C ′f nm−2 + o(nm−2 +m log n) a.s. (28)

if α1 = α2 = 1.

Here log f n(X n) =
∏n

j=1 f (X j), C f = 24−1b2

∫ t

s
ḟ 2 f −1, A> 0 is a constant and C ′

f
is a constant

between C f b1 b−1
2 and C f .

The upper bounds in (25) and (27) imply that, for a given number of subintervals m,

the shortest predictive code length (20) is likely to involve more redundant code length in

encoding the unknown f than the shortest code length (16).

Theorem 3. Under the conditions of Theorem 1 and Theorem 2 and having either α1 6= 1 or

α2 6= 1, we have

−M1(n
α1γ2 + nγ2 log n)

≤ minm∈[nγ1 ,nγ2 ]{−L∗1(X
n; m) + L2(q̃

m, m,δ)}+ log f n(X n)

≤ M2n
1

1+2α2 (log n)
2α2

1+2α2 a.s. (29)

and

−M3(n
α1γ2 + nγ2 log n)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 60

≤ minm∈[nγ1 ,nγ2 ]{− log f̃ (X n; m) + L2(q̃
m, m,δ)}+ log f n(X n)

≤ M4n
1

1+2α2 (log n)
2α2

1+2α2 a.s. (30)

where M1, M2, M3, M4 are positive constants depending on f .

Theorem 3 implies that, even though for a fixed m the predictive code length (27) may be

longer than the code length (25) by an infinite number of digits as n→∞, both of them have

the minimax bounds of the same order. Theorem 3 can be further refined when α1 = α2 = 1

is assumed, which is given below.

Theorem 4. Under the conditions of Theorem 1 and Theorem 2 and that α1 = α2 = 1, the

following statements hold.

(a).

min
m∈[nγ1 ,nγ2 ]

{−L∗1(X
n; m) + L2(q̃

m, m,δ)}+ log f n(X n) = O(n
1

3 (log n)
2

3 ) a.s. (31)

(b).

min
m∈[nγ1 ,nγ2]

{− log f̃ (X n; m) + L2(q̃
m, m,δ)}+ log f n(X n)

= M5n
1

3 (log n)
2

3 (1+ o(1)) a.s. (32)

(c).

m∗ = O((n/ log n)
1

3 ) a.s. (33)

(d).

m̂= M6(n/ log n)
1

3 (1+ o(1)) a.s. (34)

where M5 and M6 are positive constants depending on f .

Note that α1 = α2 = 1 implies the width of each subinterval in the histogram, although

still being variable, is of the same order as m−1. The results (32) and (34) are the same as

(ii) and (iv) of Theorem 2.4 of [20] where they use predictive histogram estimator of equal

width subintervals. This shows that using a variable subinterval-width optimal histogram

density estimator, if the widths are of the same order, achieves the same order of shortest

code length for description of X n as using an equal width optimal histogram density estimator.

From Theorem 4 we also see that the results for the shortest predictive code length are more

definite than for the shortest code length. Therefore, we will focus our study on the predictive

code length in the next section.



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 61

3. Hypothesis testing for homogeneity

One of the basic problems in statistical inference is testing the equality of two distribu-

tions where two independent samples are observed from; and more generally, testing the

homogeneity of k distributions with k > 2 where k independent samples are observed from.

Using the data quantization method developed in Section 2 we propose a stochastic complex-

ity based procedure for testing the homogeneity of k distributions. First, a shortest predictive

code length, based on a class of histogram density estimators with variable width subintervals,

is computed for each of the k independent samples. This, when minimized, gives the optimal

number of subintervals and their locations, the associated density estimator and the proper

measurement of the information contained in each sample. Second, the shortest predictive

code length is computed for the pooled sample, which when minimized gives the histogram

estimator of the associated mixture distribution. Finally, the shortest predictive code length

of the pooled sample is compared with the sum of the shortest predictive code lengths of all

the k samples. If the former one is smaller, then the hypothesis that the k distributions are the

same is not rejected, but rejected otherwise.

Let (X11, · · · , X1n1
), (X21, · · · , X2n2

), · · · , (Xk1, · · · , Xknk
) (abbreviated as X

n1

1 , X
n2

2 , · · · , X
nk

k
)

be k independent random samples with sizes n1, n2, · · · , nk and
∑k

i=1 ni = n. The respective

unknown population density functions are f1(x), f2(x), · · · , fk(x), all with the same support

[s, t]. The underlying problem is the testing of the hypothesis

H0 : f1 = f2 = · · ·= fk versus

Ha : at least two of them are not equal. (35)

Under the alternative hypothesis Ha, we should describe the information of the k samples

X
n1

1
, X

n2

2
, · · · , X

nk

k
separately, i.e. we should find the shortest code length for each sample X

ni

i

with density fi . By (20) the total predictive code length for the k samples is

min
m1,··· ,mk

(

−
k
∑

i=1

log f̃i(X
ni

i
; mi)+

k
∑

i=1

L2(q̃
mi

i
, mi ,δ)

)

(36)

provided that the parameter truncation is based on the same precision δ. Here f̃i(X
ni

i
; mi) is

the likelihood function of the i-th sample X
ni

i
defined as (19), i.e.

f̃i(X
ni

i
; mi) =

(mi − 1)!

(ni +mi − 1)!

mi
∏

j=1

ni, j,mi
!

r̃
ni, j,mi

i, j,mi

(37)

where r̃i, j,mi
’s are the widths of the optimal partition {Q̃ i, j,mi

} of the i-th sample. These are

obtained by applying the maximum likelihood principle (4) to the i-th sample with fixed

number of subintervals mi . Then ni, j,mi
is the number of data points falling into the j-th

subinterval Q̃ i, j,mi
.



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 62

Because all of the k samples are encoded simultaneously, the second term of (36) could

be further reduced by a more efficient encoding process as given by

L4(q̃
m1

1
, · · · , q̃mk

k
, m1, · · · , mk,δ) =

k
∑

i=1

log

�

∑mi−1

j=1

�

�

�r̃i, j,mi
− r

mi

�

�

�+mi − 2

mi − 2

�

+L3(m1, · · · , mk, s̄, r̄) + | logδ| (38)

where q̃
mi

i
is the sequence of break points corresponding to the optimal partition {Q̃ i, j,mi

}.
The efficiency lies in the fact that the set of integers {m1, · · · , mk, s̄, r̄} is encoded in a prefix

manner, which requires L3(m1, · · · , mk, s̄, r̄) bits instead of
∑k

i=1 L3(mi, s̄, r̄) bits. Therefore

under the hypothesis Ha the total predictive code length (36) for the k samples can be replaced

by a shorter code length

C(X
n1

1
, · · · , X

nk

k
) = min

m1,··· ,mk

{−
k
∑

i=1

log f̃i(X
ni

i
; mi)

+L4(q̃
m1

1 , · · · , q̃mk

k
, m1, · · · , mk,δ)} (39)

where the minimum is attained at m̂1, · · · , m̂k.

If the null hypothesis H0 is true, that is the k samples are drawn from the same unknown

distribution, we can describe the information in the k samples using only the optimal code-

words required to encode the pooled sample X n = (X
n1

1 , · · · , X
nk

k
). By regarding the pooled

sample X n as being drawn from a mixed distribution with density fmix =
∑k

i=1

ni

n
fi, the short-

est predictive code length for encoding X n is the one defined by (20):

C(X n) =min
m
{− log f̃mix(X

n; m) + L2(q̃
m
mix, m,δ)}

= −
m̂
∑

j=1

log n j,m̂!+

m̂
∑

j=1

n j,m̂ log r̃ j,m̂− log
(m̂− 1)!

(n+ m̂− 1)!
+ L2(q̃

m̂
mix, m̂,δ) (40)

where the minimum is attained at m̂.

According to the theory of stochastic complexity, under the right probabilistic model (here

the density function), or the right constraints inside the probabilistic pattern of the observa-

tions, the corresponding encoding process is expected to produce a shorter code length than

the one under a wrong model, or the one that ignores the right constraints in the underlying

model. Therefore, in the problem of testing the hypotheses (35), when H0 is true the shortest

predictive code length (40) is not expected to be greater than (39), the shortest predictive

code length obtained under the encoding process ignoring the constraint f1 = f2 = · · · = fk.

And vise versa, when Ha is true the corresponding code length (39) is expected to be less

than the code length (40), which is obtained by the encoding process ignoring the difference

among the fi ’s. We summarize this property in the following theorem.

Theorem 5. Let X
n1

1 , · · · , X
nk

k
be simple random samples, respectively, drawn from the unknown

density functions f1, · · · , fk on [s, t], and X n = (X
n1

1
, · · · , X

nk

k
) the pooled sample. Suppose that

the conditions (i) to (iv) listed in Theorem 1 and Theorem 2 are satisfied for each X
ni

i
and the

corresponding fi . Then the following statements hold.



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 63

(a). If at least two of f1, · · · , fk are not equal, there exists a constant η < 0 such that

1

n
[C(X

n1

1 , · · · , X
nk

k
)− C(X n)]< η a.s. (41)

as n1→∞, · · · , nk→∞ satisfying lim infn1→∞
n1

n
> 0, · · · , lim infnk→∞

nk

n
> 0.

(b). If f1 = f2 = · · ·= fk a.s., then

1

n
[C(X

n1

1 , · · · , X
nk

k
)− C(X n)]→ 0 a.s. (42)

as n1→∞, · · · , nk→∞.

The proof of Theorem 5 will be given in Section 4.

From part (a) of the above theorem we know that when using the test procedure stated

in the beginning of this section, the asymptotic power is 1 in the limit as the sample sizes

tend to infinity; namely, almost surely the shortest predictive code length under Ha is less

than that under H0 when Ha is true. On the other hand, when the null hypothesis H0 is

true, the difference of the two shortest predictive code lengths per observation converges to

zero almost surely as the sample sizes go to infinity. When the sample sizes are finite, the

size of the test is essentially determined by the part of the code lengths used for encoding

the parameters. In the encoding process corresponding to (39) there are more parameters

(q̃
m1

1 , · · · , q̃mk

k
, m1, · · · , mk,δ) to be encoded than in the encoding process corresponding to

(40) in which only q̃m
mix

, m and δ are to be encoded. Thus the code length (39) has a high

probability to be larger than (40) if the null hypothesis H0 is true, implying the test has a

firm control of type I error. Simulation study could be done to investigate how well the two

types of errors are controlled in the proposed test. But we will not get into the details in this

paper. A simulation study was done in [10] to assess the finite sample performance of the

homogeneity test proposed in this section in the special case of using equal width histogram

density estimators. The results there show that the method is competitive in comparison to

the existent methods such as the two sample t test and Smirnov test when the data can be

analyzed by all these methods. But the proposed method is more efficient and powerful in

some situations such as that the data come from different families of distributions, whereas

the other methods do not perform well.

4. Proofs of the theorems

In this section we provide proofs for all the theorems listed in this paper. For the sake of

simplicity, the logarithms in the proofs are all natural logarithms.

From (8) and (19),

− log f̃ (X n; m) + L∗1(X
n; m) =

− log







(m− 1)!

(n+m− 1)!

m
∏

i=1

ni,m!

r̃
ni,m

i,m







+

m
∑

i=1

(ni,m+ 1) log
ni,m+ 1

(n+m)r̃i,m

. (43)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 64

By Stirling’s formula n!=
p

2πnnne−neθn (0< θn < (12n)−1), (43) can be rewritten as

− log f̃ (X n; m) + L∗1(X
n; m) = −

m
∑

i=1

log r̃i,m+
∑

ni,m>0

log

�

1+
1

ni,m

�ni,m+1

+
1

2

∑

ni,m>0

log ni,m−m log m+O(m). (44)

We will show that the first term of (44) is α12m log m+O(m) where 1≤ α12 ≤ α1, the second

term is O(m) and the third term is m

2
log n

mα22
where 1≤ α22 ≤ α1. The following lemmas will

be needed.

Lemma 1. Suppose that ni,m’s have a multinomial distribution with probabilities πi,m’s such

that
∑m

i=1πi,m = 1, πi,m ≥ b1c1m−α1 and
∑m

i=1 ni,m = n. Then for each integer w, there exists a

constant aw such that

E

(

m
∑

i=1

ni,m− nπi,m

nπi,m

)2w

≤ awn
1

2
−wm2α1w. (45)

Proof. Denote T1 =
∑m

i=1

ni,m−nπi,m

nπi,m
. By the definition of multinomial distribution and from

Stirling’s formula we have

E(T 2w
1 ) =

∑

n1,m+···+nm,m=n

T 2w
1

n!
∏m

i=1 ni,m!

m
∏

i=1

π
ni,m

i,m

=
∑

n1,m+···+nm,m=n

T 2w
1

m
∏

i=1

(nπi,m)
ni,m

ni,m!
e−ni,m
p

2πnecn

≤ p2πne

∞
∑

N=0

∑

n1,m+···+nm,m=N

T 2w
1

m
∏

i=1

(nπi,m)
ni,m

ni,m!
e−ni,m

=
p

2πne

∞
∑

n1,m=0

· · ·
∞
∑

nm,m=0

T 2w
1

m
∏

i=1

(nπi,m)
ni,m

ni,m!
e−ni,m

=
p

2πneE′(T 2w
1 ) (46)

where the final expectation E′(T 2w
1 ) is with respect to a series of independent Poisson ran-

dom variables {ni,m} with parameters {nπi,m}. This technique, used by [16] and [19], of

approximating the multinomial distribution by Poisson distribution is called Poissonization.

The constant cn = o((12n)−1). By Shiryayev’s [17] Theorem 6 of section 2.12, the 2w-th

moment of T1 can be written as a sum of its cumulants:

E′(T 2w
1 ) =

∑

j1+···+ jl=2w

ρ( j1, · · · , jl)

l
∏

k=1

κ jk(T1) (47)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 65

where ρ( j1, · · · , jl) =
1

l!

(2w)!

j1!··· jl ! and jk ≥ 1, l ≤ 2w. Because ni,m’s are independent Poisson

random variables, it follows from the section 1.5 of [8] that the jk-th cumulant of T1

κ jk(T1) =

m
∑

i=1

κ jk

�

ni,m− nπi,m

nπi,m

�

=

m
∑

i=1

nπi,m

(nπi,m)
jk
≤ (b1c1)

− jk n1− jk mα1 jk (48)

if jk > 1 and κ jk(T1) = 0 if jk = 1. Thus

E′(T 2w
1 ) =

∗
∑

ρ( j1, · · · , jl)

l
∏

k=1

κ jk(T1)

≤
∗

∑

ρ( j1, · · · , jl)

l
∏

k=1

(b1c1)
− jk n1− jk mα1 jk ≤ awn−wm2α1w (49)

where the summation
∑∗

is taken over all partitions of 2w such that
∑l

k=1 jk = 2w, jk ≥ 2

and l ≤ w. Using the same notation for possibly different constants and substituting the last

bound into (46) the lemma is proved. ⊳

Lemma 2. Suppose that N is a binomial random variable with mean np. Then for any integer

w > 0, there is a constant aw > 0 such that

E(N − np)2w ≤ awn
1

2
+w pw . (50)

Proof. By the same technique of Poissonization we have

E(N − np)2w ≤ awn
1

2 E(N1 − np)2w (51)

where N1 is a Poisson random variable with mean np. By the equation (47) and the fact that

κk(N1 − np) = np if k > 1 and κ1(N1 − np) = 0 it follows that E(N1 − np)2w is a polynomial

of order w, and therefore (50) must hold. ⊳

Lemma 3. Under the conditions that r̃i,m ≥ b1m−α1 , 1≤ α1 < 1+ (2γ2)
−1 and f ≥ c1 > 0,

m
∑

i=1

ni,m− nπi,m

nπi,m

= o(m) a.s. (52)

uniformly in m ∈ [1, nγ2] as n→∞, where πi,m =
∫

Q̃i,m
f .

Proof. For any ǫ > 0,

P

 

max
m∈[1,nγ2 ]

�

�

�

�

�

m
∑

i=1

ni,m− nπi,m

nπi,m

�

�

�

�

�

≥ ǫm
!

≤
∑

m∈[1,nγ2]

P

 
�

�

�

�

�

m
∑

i=1

ni,m− nπi,m

nπi,m

�

�

�

�

�

≥ ǫm
!



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 66

≤
∑

m∈[1,nγ2]

ǫ−2wm−2w E

(

m
∑

i=1

ni,m− nπi,m

nπi,m

)2w

(53)

where the last inequality comes by using Chebyshev’s inequality. From Lemma 1,

P

 

max
m∈[1,nγ2]

�

�

�

�

�

m
∑

i=1

ni,m− nπi,m

nπi,m

�

�

�

�

�

≥ ǫm
!

≤
∑

m∈[1,nγ2]

ǫ−2wm−2wawn
1

2
−wm2α1w

≤ awǫ
−2wn(2α1γ2−2γ2−1)w+ 1

2
+γ2 . (54)

By the condition that α1 < 1+(2γ2)
−1, the sum of the series defined by the terms of form (54)

converges as n→∞, if w >
3+2γ2

2+4γ2−4α1γ2
. Hence (52) follows from applying the Borel-Cantelli

lemma. ⊳

Lemma 4. Under the conditions that b1m−α1 ≤ r̃i,m ≤ b2m−α2 , where 2α1 − γ−1
2 < α2 ≤ 1 ≤

α1 < 2−1 + (2γ2)
−1 and 0< c1 ≤ f ≤ c2,

max
1≤i≤m

�

�

�

�

mα1 ni,m

n
−mα1πi,m

�

�

�

�

= o(1) a.s. (55)

uniformly in m ∈ [1, nγ2] as n→∞.

Proof. Denote

Im,n = max
1≤i≤m

�

�

�

�

mα1 ni,m

n
−mα1πi,m

�

�

�

�

, (56)

then for any ǫ > 0,

P

�

max
m∈[1,nγ2]

Im,n > ǫ

�

≤
∑

m∈[1,nγ2 ]

P(Im,n > ǫ)

≤
∑

m∈[1,nγ2 ]

m
∑

i=1

P

��

�

�

�

mα1 ni,m

n
−mα1πi,m

�

�

�

�

�

≤
∑

m∈[1,nγ2 ]

m
∑

i=1

ǫ−2w E

�

�

�

�

mα1 ni,m

n
−mα1πi,m

�

�

�

�

2w

=
∑

m∈[1,nγ2 ]

m
∑

i=1

ǫ−2wm2wα1 n−2w E(ni,m− nπi,m)
2w, (57)

where the last inequality is obtained by applying Chebyshev’s inequality. From Lemma 2 and

the property that c1 b1m−α1 ≤ πi,m ≤ c2 b2m−α2 ,

P

�

max
m∈[1,nγ2]

Im,n > ǫ

�

≤
∑

m∈[1,nγ2]

m
∑

i=1

ǫ−2wm2wα1 n−2wawn
1

2
+w(c2 b2m−α2)w



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 67

≤ awn2γ2+
1

2
+(2α1γ2−α2γ2−1)w . (58)

From now on the same notation will be used for possibly different constants. By the condition

that α2 > 2α1 − γ−1
2 , the sum of the series defined by the terms of form (58) converges as

n→∞, if w >
3+4γ2

2+2α2γ2−4α1γ2
. Hence (55) follows from applying the Borel-Cantelli lemma. ⊳

Lemma 5. Under the conditions that r̃i,m ≤ b2m−α2 and f ≤ c2, we have

m
∑

i=1

(ni,m− nπi,m)
2− n= o(n) a.s. (59)

uniformly in m ∈ [nγ1 , n] as n→∞.

Proof. Suppose {Ni,m} are a sequence of independent Poisson random variables with means

{nπi,m}, and denote T2 =
∑m

i=1(Ni,m − nπi,m)
2. We first show that the j-th cumulants of T2

satisfies

|κ j(T2)| ≤ α jn
jm−α2( j−1) (60)

where a j is a constant depending on j.

Because {Ni,m} are independent, it follows that

κ j(T2) =

m
∑

i=1

κ j((Ni,m− nπi,m)
2). (61)

By applying Theorem 6 of section 2.12 of Shiryayev’s [17] again, the j-th cumulants of (Ni,m−
nπi,m)

2 can be written as a sum of its moments:

κ j((Ni,m− nπi,m)
2) =

∑

j1+···+ jl= j

ζ( j1, · · · , jl)

l
∏

k=1

E((Ni,m− nπi,m)
2 jk ) (62)

where ζ( j1, · · · , jl) =
(−1)l−1

l

j!

j1!··· jl ! and jk ≥ 1, l ≤ j. From Lemma 2 we know that E((Ni,m−
nπi,m)

2 jk ) is an order- jk polynomial of nπi,m, therefore

|κ j(T2)| ≤
m
∑

i=1

α j(nπi,m)
j ≤ α jn

jm−α2( j−1) (63)

for some constant a j , hence (60) holds.

By (47) and the identities κ1(T2 − n) = E(T2 − n) = 0 and κ j(T2 − n) = κ j(T2) for j ≥ 2,

it can be seen that

E(T2 − n)2w =

∗
∑

ρ(l1, · · · , lk)

k
∏

j=1

κl j
(T2) (64)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 68

where the summation
∑∗

is taken over all the partitions of 2w such that
∑k

j=1 l j = 2w, l j ≥ 2

and k ≤ w. By (60) it follows that

E(T2 − n)2w ≤
∗

∑

awn2wm−α2(2w−k) ≤ awn2wm−α2w (65)

for some constant aw depending on w.

Now for any ǫ > 0,

P

 

max
m∈[nγ1 ,n]

�

�

�

�

�

m
∑

i=1

(ni,m− nπi,m)
2 − n

�

�

�

�

�

> ǫn

!

≤
∑

m∈[nγ1 ,n]

P

 �

�

�

�

�

m
∑

i=1

(ni,m− nπi,m)
2 − n

�

�

�

�

�

> ǫn

!

≤
∑

m∈[nγ1 ,n]

ǫ−2wn−2w E

�

�

�

�

�

m
∑

i=1

(ni,m− nπi,m)
2 − n

�

�

�

�

�

2w

≤
∑

m∈[nγ1 ,n]

ǫ−2wn−2w+ 1

2 E

�

�

�

�

�

m
∑

i=1

(Ni,m− nπi,m)
2 − n

�

�

�

�

�

2w

(66)

by applying Chebyshev’s inequality and the technique of Poissonization.

From (65) it follows that

P

 

max
m∈[nγ1 ,n]

�

�

�

�

�

m
∑

i=1

(ni,m− nπi,m)
2 − n

�

�

�

�

�

> ǫn

!

≤
∑

m∈[nγ1 ,n]

ǫ−2wn−2w+ 1

2 awn2wm−α2w ≤ awn
3

2
−α2γ1w. (67)

The sum of the series defined by the terms of form (67) converges as n → ∞ if w > 5

2α2γ1
,

hence (59) follows by applying the Borel-Cantelli Lemma. ⊳

Corollary 1. Under the conditions that b1m−α1 ≤ r̃i,m ≤ b2m−α2 and 0< c1 ≤ f ≤ c2,

m
∑

i=1

(ni,m− nπi,m)
2

(nπi,m)
2

= O(n−1m2α1) a.s. (68)

uniformly in m ∈ [nγ1 , n] as n→∞.

Lemma 6. Under the conditions of Lemma 4, the following statement is true:

∑

ni,m>0

log
ni,m

nπi,m

= O(m) a.s. (69)

uniformly in m ∈ [nγ1 , nγ2] as n→∞.



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 69

Proof. First note that

∑

ni,m>0

log
ni,m

nπi,m

=
∑

ni,m>0

log

�

1+
ni,m− nπi,m

nπi,m

�

. (70)

By Taylor expansion,

∑

ni,m>0

log
ni,m

nπi,m

=

m
∑

i=1

ni,m− nπi,m

nπi,m

− 1

2

∑

ni,m>0

(1+ ξi,m)
−2
(ni,m− nπi,m)

2

(nπi,m)
2

+ D (71)

where D = −∑ni,m=0

ni,m−nπi,m

nπi,m
< m and |ξi,m| ≤

�

�

�

ni,m−nπi,m

nπi,m

�

�

�. Thus

max
1≤i≤m

|ξi,m| ≤ max
1≤i≤m

�

�

�

�

ni,m− nπi,m

nπi,m

�

�

�

�

≤ (c1 b1)
−1 max

1≤i≤m

�

�

�

�

mα1 ni,m

n
−mα1πi,m

�

�

�

�

, (72)

and by Lemma 4

max
1≤i≤m

|ξi,m|= o(1) a.s. (73)

uniformly in m ∈ [1, nγ2] as n→∞. By (73) and Corollary 1 it follows that the second term

of the right hand side of (71) is bounded uniformly in m ∈ [nγ1 , nγ2] by O(n−1m2α1) a.s.. The

latter is o(m) because n> m
1

γ2 and α1 <
1

2
+ 1

2γ2
. Therefore by Lemma 3

∑

ni,m>0

log
ni,m

nπi,m

= O(m) a.s. (74)

uniformly in m ∈ [nγ1 , nγ2] as n→∞. ⊳

Proof. [Proof of Theorem 1] By condition (i) and (iii) we can obtain an interval estimate,

respectively, for −∑m

i=1 r̃i,m and
∑m

i=1 log nπi,m as follows

m log m+O(m) ≤ −
m
∑

i=1

log r̃i,m ≤ α1m log m+O(m) (75)

m log n−α1m log m+O(m) ≤
m
∑

i=1

log nπi,m ≤ m log n−m log m+O(m). (76)

Hence there exists an α′ satisfying −1

2
α1 ≤ α′ ≤ −3

2
+α1 such that

−
m
∑

i=1

log r̃i,m+
1

2

m
∑

i=1

log nπi,m−m log m = α′m log m+
1

2
m log n+O(m). (77)

Now we turn to the second term of (44). By Taylor expansion

∑

ni,m>0

log

�

1+
1

ni,m

�ni,m+1



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 70

=
∑

ni,m>0

(ni,m+ 1)

 

1

ni,m

− 1

2
(1+ηi,m)

−2
1

n2
i,m

!

= O(m), (78)

where 0≤ ηi,m ≤ n−1
i,m

.

From Lemma 6, (77), (78) and (44), it is easy to see that

− log f̃ (X n; m) + L∗1(X
n; m) = α′m log m+

1

2
m log n+O(m) a.s. (79)

uniformly in m ∈ [nγ1 , nγ2] as n→∞. ⊳

To prove Theorem 2 we need the following lemmas.

Lemma 7. Under the condition (iii) of Theorem 1,

L2(q̃
m, m,δ) = o(m). (80)

Proof. From b1m−α1 ≤ r̃i,m ≤ b2m−α2 it follows that

�

�

�r̃i,m−
r

m

�

�

� ≤max

�

b2

mα2
− r

m
,

r

m
− b1

mα1

�

≤ b2 + r

mα2
. (81)

From this (80) follows. ⊳

Let f (x |q̃m) denote a density in Hm which assigns the same probability as f to each

subinterval Q̃ i,m, i.e. for x ∈ [s, t] let

f (x |q̃m) =

m
∑

i=1

πi,m

r̃i,m

IQ̃i,m
(x). (82)

By Lemma 7 we have

−L∗1(X
n; m) + L2(q̃

m, m,δ) + log f n(X n)

= −L∗1(X
n; m) +

n
∑

j=1

log f (X j|q̃m) +

n
∑

j=1

log f (X j)

log f (X j|q̃m)
+ o(m). (83)

Lemma 8. Under the condition of Theorem 1, there exist two positive constants A and B such

that

Bmα2 ≤
∑

ni,m>0

ni,m log
ni,m

nπi,m

≤ Amα1 a.s. (84)

uniformly in m ∈ [nγ1 , nγ2] as n→∞.

Proof. By Taylor expansion,

∑

ni,m>0

ni,m log
ni,m

nπi,m

=
∑

ni,m>0

ni,m log

�

1+
ni,m− nπi,m

nπi,m

�



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 71

=

m
∑

i=1

ni,m





ni,m− nπi,m

nπi,m

− 1

2
(1+ θi,k)

−2

�

ni,m− nπi,m

nπi,m

�2




=

m
∑

i=1

(ni,m− nπi,m)
2

nπi,m

+

m
∑

i=1

(ni,m− nπi,m)

−
m
∑

i=1

1

2
(1+ θi,k)

−2

�

(ni,m− nπi,m)
3

(nπi,m)
2

+
(ni,m− nπi,m)

2

nπi,m

�

(85)

where |θi,k| ≤
�

�

�

ni,m−nπi,m

nπi,m

�

�

�, so that max1≤i≤m |θi,k| = o(1) a.s. uniformly in m ∈ [nγ1 , nγ2]. The

argument is similar to the one used to establish (73). By Lemma 4, Lemma 5, the property

πi,m ≥ b1c1m−α1 and the following inequality obtained from (85)

�

�

�

�

�

�

∑

ni,m>0

ni,m log
ni,m

nπi,m

�

�

�

�

�

�

≤
m
∑

i=1

(ni,m− nπi,m)
2

nπi,m

�

1+
1

2
(1+ θi,k)

−2

�

1+ max
1≤i≤m

�

�

�

�

ni,m− nπi,m

nπi,m

�

�

�

�

��

, (86)

the lemma can easily be established. ⊳

The following lemma can similarly be proved using Taylor expansion, Lemma 3, Lemma 4

and Corollary 1.

Lemma 9. Under the conditions of Theorem 1,

∑

ni,m>0

1

ni,m

= o(m) a.s. and (87)

m
∑

i=1

log
ni,m+ 1

nπi,m+ 1
= o(m) a.s. (88)

uniformly in m ∈ [nγ1 , nγ2] as n→∞.

Lemma 10. Under the conditions of Theorem 1, there exists a positive constant A such that

−Amα1 + (α2 −α1)m log m+O(m)≤ −L∗1(X
n; m) +

n
∑

j=1

log f (X j|q̃m)

≤ (α1 − 1)m log m+O(m) a.s. (89)

uniformly in m ∈ [nγ1 , nγ2] as n→∞.

Proof. First note that

−L∗1(X
n; m) +

n
∑

j=1

log f (X j|q̃m) =

m
∑

i=1

ni,m log
πi,m

r̃i,m

−
m
∑

i=1

(ni,m+ 1)
ni,m+ 1

(n+m)r̃i,m



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 72

=

m
∑

i=1

log r̃i,m+

m
∑

i=1

ni,m log
(n+m)πi,m

ni,m+ 1
+

m
∑

i=1

log
nπi,m+ 1

ni,m+ 1

+m log(n+m)−
m
∑

i=1

log(nπi,m+ 1). (90)

The second term of the righthand side of (90)

m
∑

i=1

ni,m log
(n+m)πi,m

ni,m+ 1
=

m
∑

i=1

ni,m log

�

(n+m)πi,m

ni,m+ 1
· ni,m

nπi,m

· nπi,m

ni,m

�

= n log

�

1+
m

n

�

−
∑

ni,m>0

ni,m log

�

1+
1

ni,m

�

−
∑

ni,m>0

ni,m log
ni,m

nπi,m

(91)

and
∑

ni,m>0

ni,m log

�

1+
1

ni,m

�

=
∑

ni,m>0

ni,m

 

1

ni,m

+
1

2
(1+ηi,m)

−2
1

n2
i,m

!

(92)

where 0≤ ηi,m ≤ 1. By Lemma 8 and (87) of Lemma 9 we have

−Amα1 +O(m)≤
m
∑

i=1

ni,m log
(n+m)πi,m

ni,m+ 1
≤ O(m) a.s. (93)

uniformly in m ∈ [nγ1 , nγ2] as n→∞.

It can also be seen that

α2m log m+O(m)≤ −
m
∑

i=1

log

�

πi,m+
1

n

�

≤ α1m log m+O(m). (94)

From (75), (93), (88) of Lemma 9, and (94) it follows that

−Amα1 + (α2 −α1)m log m+O(m)≤ −L∗1(X
n; m) +

n
∑

j=1

log f (X j|q̃m)

≤ (α1 − 1)m log m+O(m) a.s. (95)

uniformly in m ∈ [nγ1 , nγ2] as n→∞. ⊳

Lemma 11. Under the conditions (i) to (iv) of Theorem 2 and f 6= 1, we have as m→∞

E f log
f

f (·|q̃m)
=

m
∑

i=1

1

24
r̃2

i,m

∫

Q̃i,m

ḟ 2

f
+ o(m−2α2). (96)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 73

Proof. By the definition of f (x |q̃m)

lim
m→∞( f (x)− f (x |q̃m)) = lim

m→∞
1

r̃i,m(x)

∫

Q̃i,m(x)

( f (x)− f (y))d y = 0 (97)

uniformly in x ∈ [s, t], where Q̃ i,m(x) is the subinterval containing x , and r̃i,m(x) is the

corresponding width. Now by Taylor expansion

E f log
f

f (·|q̃m)
=

m
∑

i=1

∫

Q̃i,m

f log

�

1+
f − f (·|q̃m)

f (·|q̃m)

�

=

m
∑

i=1

∫

Q̃i,m

f
f − f (·|q̃m)

f (·|q̃m)
− 1

2

m
∑

i=1

∫

Q̃i,m

f (1+ηi)
−2

�

f − f (·|q̃m)

f (·|q̃m)

�2

(98)

where |ηi(x)| ≤
�

�

�

f − f (·|q̃m)

f (·|q̃m)

�

�

� and by (97) supx |ηi(x)|= o(1). Hence

E f log
f

f (·|q̃m)
=

m
∑

i=1

∫

Q̃i,m

( f − f (·|q̃m))2

f (·|q̃m)

−1

2
(1+ o(1))

m
∑

i=1

∫

Q̃i,m

( f − f (·|q̃m))3

f (·|q̃m)2
− 1

2
(1+ o(1))

m
∑

i=1

∫

Q̃i,m

( f − f (·|q̃m))2

f (·|q̃m)

=
1

2
(1+ o(1))

m
∑

i=1

∫

Q̃i,m

( f − f (·|q̃m))2

f (·|q̃m)
(99)

Now we apply the technique used in Proposition 2.7 of [6] to prove that

m
∑

i=1

∫

Q̃i,m

( f − f (·|q̃m))2

f (·|q̃m)
=

1

12

m
∑

i=1

r̃2
i,m

∫

Q̃i,m

ḟ 2

f
+ o(m−2α2). (100)

The lemma would follow from (100) and (99).

By denoting z = x − f̃i−1,m we have

∫

Q̃i,m

( f (x)− f (x |q̃m))2

f (x |q̃m)
d x =

r̃i,m

πi,m

∫ r̃i,m

0

[ f (z + q̃i−1)− f (z + q̃i−1|q̃m)]2dz

=
r̃i,m

πi,m

∫ r̃i,m

0





∫ z

0

ḟ (y + q̃i−1,m)d y − 1

r̃i,m

∫ r̃i,m

0

(r̃i,m− y) ḟ (y + q̃i−1,m)d y





2

dz

=
r̃i,m

πi,m

∫ r̃i,m

0

�∫ z

0

ḟ (y + q̃i−1,m)d y

�2

dz − 1

πi,m





∫ r̃i,m

0

(r̃i,m− y) ḟ (y + q̃i−1,m)d y





2

=
r̃i,m

πi,m

∫ r̃i,m

0

∫ z

0

∫ z

0

ḟ (u+ q̃i−1,m) ḟ (v+ q̃i−1,m)dudvdz



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 74

− 1

πi,m

∫ r̃i,m

0

∫ r̃i,m

0

(r̃i,m− u)(r̃i,m− v) ḟ (u+ q̃i−1,m) ḟ (v+ q̃i−1,m)dudv

=
r̃i,m

πi,m

∫ r̃i,m

0

∫ r̃i,m

0

(r̃i,m− u∨ v) ḟ (u+ q̃i−1,m) ḟ (v+ q̃i−1,m)dudv

− 1

πi,m

∫ r̃i,m

0

∫ r̃i,m

0

(r̃i,m− u)(r̃i,m− v) ḟ (u+ q̃i−1,m) ḟ (v+ q̃i−1,m)dudv

=
r̃i,m

πi,m

∫ r̃i,m

0

∫ r̃i,m

0

(u∧ v− 1

r̃i,m

uv) ḟ (u+ q̃i−1,m) ḟ (v+ q̃i−1,m)dudv (101)

where u∨ v =max(u, v) and u∧ v =min(u, v). Direct computation shows that

∫ r̃i,m

0

∫ r̃i,m

0

(u∧ v − 1

r̃i,m

uv)dudv =
1

12
r̃3

i,m. (102)

Define
¯̇
fi,m =

1

r̃i,m

∫ r̃i,m

0
ḟ (u+ q̃i−1,m)du. By (101)

m
∑

i=1

∫

Q̃i,m

( f − f (·|q̃m))2

f (·|q̃m)

=

m
∑

i=1

r̃i,m

πi,m

∫ r̃i,m

0

∫ r̃i,m

0

(u∧ v− 1

r̃i,m

uv)[ ḟ (u+ q̃i−1,m) ḟ (v+ q̃i−1,m)− ¯̇f 2
i,m]dudv

+

m
∑

i=1

r̃3
i,m

12πi,m

∫ r̃i,m

0

[ ¯̇f 2
i,m− ḟ 2(u+ q̃i−1,m)]du

+

m
∑

i=1

r̃2
i,m

12

∫ r̃i,m

0

 

r̃i,m ḟ 2(u+ q̃i−1,m)

πi,m

− ḟ 2(u+ q̃i−1,m)

f (u+ q̃i−1,m)

!

du

+
1

12

m
∑

i=1

r̃2
i,m

∫

Q̃i,m

ḟ 2(x)

f (x)
d x . (103)

Note that |u∧ v− 1

r̃i,m
uv| ≤ r̃i,m and

| ḟ (u+ q̃i−1,m) ḟ (v + q̃i−1,m)− ¯̇
f 2
i,m| ≤

| ḟ (u+ q̃i−1,m)− ¯̇
fi,m|| ḟ (v + q̃i−1,m)|+ | ḟ (v + q̃i−1,m)− ¯̇

fi,m|| ¯̇fi,m|,
hence

�

�

�

�

�

m
∑

i=1

r̃i,m

πi,m

∫ r̃i,m

0

∫ r̃i,m

0

(u∧ v − 1

r̃i,m

uv)[ ḟ (u+ q̃i−1,m) ḟ (v + q̃i−1,m)− ¯̇f 2
i,m]dudv

�

�

�

�

�

≤ c−1
1

m
∑

i=1

r̃i,m

∫ r̃i,m

0

| ḟ (u+ q̃i−1,m)− ¯̇
fi,m|

∫ r̃i,m

0

| ḟ (v+ q̃i−1,m)|



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 75

+c−1
1

m
∑

i=1

r̃i,m

∫ r̃i,m

0

| ḟ (v + q̃i−1,m)− ¯̇
fi,m|

∫ r̃i,m

0

| ¯̇fi,m|

≤ 2c−1
1

m
∑

i=1

r̃i,m

∫

Q̃i,m

| ḟ − ¯̇
fi,m|

∫

Q̃i,m

| ¯̇f |. (104)

Using the Cauchy-Schwartz inequality

m
∑

i=1

r̃i,m

∫

Q̃i,m

| ḟ − ¯̇fi,m|
∫

Q̃i,m

| ¯̇f |

≤






m
∑

i=1

r̃i,m

 
∫

Q̃i,m

| ḟ − ¯̇fi,m|
!2






1

2






m
∑

i=1

r̃i,m

 
∫

Q̃i,m

| ¯̇f |
!2






1

2

≤




m
∑

i=1

r̃2
i,m

∫

Q̃i,m

| ḟ − ¯̇
fi,m|2





1

2




m
∑

i=1

r̃2
i,m

∫

Q̃i,m

| ¯̇f |2




1

2

≤ cm−2α2

 

∫

[s,t]

( ḟ − ¯̇
fi,m)

2

! 1

2

where c = (t − s)b2
2c3 is a constant. By (2.5) of [6]

∫

[s,t]

( ḟ − ¯̇fi,m)
2→ 0 as m→∞. (105)

Hence the first term of the righthand side of (103) is bounded by o(m−2α2). Using the Cauchy-

Schwartz inequality, (105) and the following result similar to (105)

∫

[s,t]

�

ḟ − πi,m

r̃i,m

�2

→ 0 as m→∞, (106)

one can similarly show that the second and third terms of the righthand side of (103) are both

bounded by o(m−2α2). Hence (100) and accordingly the lemma is true. ⊳

Lemma 12. Under the conditions (i) to (iv) of Theorem 2 we have

n
∑

j=1

log
f (X j)

f (X j|q̃m)
= nE f log

f

f (·|q̃m)
+ o(nm−2α+m log n) a.s. (107)

as n→∞ uniformly for m ∈ [nγ1 , nγ2], where α is a constant satisfying α2 ≤ α < α2 +
1

2
.

Proof. Denote Z j,m = log
f (X j)

f (X j |q̃m)
for each X j, then Z j,m’s are i.i.d. and

|Z j,m| ≤max
x

| f − f (·|q̃m)|
f (·|q̃m)

≤ c3

c1

max
1≤i≤m

r̃i,m. (108)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 76

Thus

|Z j,m− EZ j,m| ≤
2c3

c1

max
1≤i≤m

r̃i,m
def
= B, (109)

and
n
∑

j=1

Var(Z j,m)≤ 4n
c2
3

c2
1

max
1≤i≤m

r̃2
i,m

def
= V. (110)

By Bernstein’s inequality, for arbitrary ǫ > 0

P







�

�

�

�

�

�

n
∑

j=1

(Z j,m− EZ j,m)

�

�

�

�

�

�

> η





 ≤ 2 exp

(

− η2

2(V + 1

3
Bη)

)

, (111)

where η = n(m−2α+mn−1 log n)ǫ and α2 ≤ α < α2 +
1

2
. By the definition of B and V ,

V +
1

3
Bη = 4n

c2
3

c2
1

max
1≤i≤m

r̃2
i,m+

2c3

3c1

max
1≤i≤m

r̃i,mn(m−2α +mn−1 log n)ǫ

≤ c′nm−2α2 + c′′m1−α2 log n

where c′ and c′′ are constants not depending on n and m. Therefore,

η2

V + 1

3
Bη
≥ 1

2

n2(m−2α +mn−1 log n)2ǫ2

max{c′nm−2α2 , c′′m1−α2 log n}
=min{c′n(m−2α+α2 +m1+α2 n−1 log n)2,

c′′n2(log n)−1(m−2α− 1

2
+ 1

2
α2 +m

1

2
+ 1

2
α2 n−1 log n)2}

for any m ∈ [nγ1 , nγ2] and hence

η2

V + 1

3
Bη
≥ O

�

n
−2α+2α2+1

2α+1 (log n)
4α−2α2

2α+1

�

. (112)

By (112) and (111), it follows that

∞
∑

n=1

∑

m∈[nγ1 ,nγ2]

P







�

�

�

�

�

�

n
∑

j=1

(Z j,m− EZ j,m)

�

�

�

�

�

�

> η







≤ 2

∞
∑

n=1

∑

m∈[nγ1 ,nγ2]

exp

§

−O

�

n
−2α+2α2+1

2α+1 (log n)
4α−2α2

2α+1

�ª

<∞.

From the Borel-Cantelli Lemma, (107) follows. ⊳

Proof. [Proof of Theorem 2] The first part of the theorem, i.e. the equation (25) can be

obtained from (83), Lemma 10, Lemma 11 and Lemma 12. Then the second part is straight-

forward from Theorem 1. ⊳



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 77

Proof. [Proof of Theorem 3] Noting that

min
m∈[nγ1 ,nγ2]

{(α1 − 1)m log m+ C f nm−2α2} = M2n
1

1+2α2 (log n)
2α2

1+2α2 , (113)

min
m∈[nγ1 ,nγ2 ]

{−Amα1 + (α2 −α1)m log m} = −M1(n
α1γ2 + nγ2 log n), (114)

the first part of Theorem 3 is obvious from Theorem 2. The second part can be proved simi-

larly. ⊳

Proof. [Proof of Theorem 4] Regarding m as a real value and taking the derivative of
1

2
n log n

m
+ C ′

f
nm−2 with respect to m, we get

min
m∈[nγ1 ,nγ2 ]

�

1

2
n log

n

m
+ C ′f nm−2

�

= M5n
1

3 (log n)
2

3 (115)

and the minimization is achieved at m = M6(n/ log n)
1

3 . By this result and Theorem 2, (a),

(b), (c) and (d) are readily obtained. ⊳

Proof. [Proof of Theorem 5] As in Lemma 7, it can be shown that

L4(q̃
m1

1 , · · · , q̃mk

k
, m1, · · · , mk,δ) = o

 

k
∑

i=1

mi

!

. (116)

If either α1 6= 1 or α2 6= 1, then by Theorem 3

−M3

k
∑

i=1

(n
α1γ2

i
+ n

γ2

i
log ni)≤ C(X

n1

1 , · · · , X
nk

k
) +

k
∑

i=1

log f
ni

i
(X

ni

i
)

≤ M4

k
∑

i=1

n

1

1+2α2

i
(log ni)

2α2
1+2α2 a.s. (117)

and

−M3(n
α1γ2 + nγ2 log n)≤ C(X n) + log f n

mix(X
n)≤ M4n

1

1+2α2 (log n)
2α2

1+2α2 a.s. (118)

for some positive constants M3 and M4 depending on f1, · · · , fk.

If α1 = α2 = 1, then by Theorem 4 (b)

C(X
n1

1 , · · · , X
nk

k
) +

k
∑

i=1

log f
ni

i
(X

ni

i
) = O

 

k
∑

i=1

n
1

3

i
(log n)

2

3

!

a.s. (119)

and

C(X n) + log f n
mix(X

n) = O
�

n
1

3 (log n)
2

3

�

a.s.. (120)

It remains to prove that there exists a constant η < 0 such that

1

n

 

log f n
mix(X

n)−
k
∑

i=1

log f
ni

i
(X

ni

i
)

!

< η a.s. (121)



G. Qian / Eur. J. Pure Appl. Math, 3 (2010), 51-80 78

as n1 →∞, · · · , nk →∞ satisfying
n1

n
> ǫ1 > 0, · · · , nk

n
> ǫk > 0 for any prescribed constants

ǫ1, · · · ,ǫk, if at least two of f1, · · · , fk are not equal almost surely, and

1

n

 

log f n
mix(X

n)−
k
∑

i=1

log f
ni

i
(X

ni

i
)

!

→ 0 a.s. (122)

as n1→∞, · · · , nk→∞ if f1 = f2 = · · ·= fk a.s..

Because

k
∑

i=1

log f
ni

i
(X

ni

i
) =

k
∑

i=1

ni
∑

j=1

log fi(X i j),

log f n
mix(X

n) =

k
∑

i=1

ni
∑

j=1

log

 

k
∑

l=1

nl

n
fl(X i j)

!

and fi ’s are bounded density functions, by the strong law of large numbers for i.i.d. random

variables it follows that

1

n

k
∑

i=1

log f
ni

i
(X

ni

i
)−

k
∑

i=1

ni

n

∫

fi log fi → 0 a.s. (123)

and
1

n
log f n

mix(X
n)−

∫

fmix log fmix→ 0 a.s. (124)

as n1→∞, · · · , nk→∞. By the convexity of x log x ,

∫

fmix log fmix ≤
k
∑

i=1

ni

n

∫

fi log fi (125)

for any group of samples of sizes n1, · · · , nk satisfying
∑k

i=1 ni = n, where the equality holds

if and only if all the densities f1, · · · , fk are equal (except a set with measure zero). Therefore

(122) is established by using (123) and (124). Also for any ǫ1 > 0, · · · ,ǫk > 0, if
n1

n
>

ǫ1, · · · , nk

n
> ǫk and if at least two of f1, · · · , fk are not equal almost surely, there exists a

constant η < 0 depending on ǫ1, · · · ,ǫk such that

∫

fmix log fmix−
k
∑

i=1

ni

n

∫

fi log fi < η (126)

for any set of integers {ni} satisfying
∑k

i=1 ni = n. Hence (121) follows from (123) and (124).

Notice that α1γ2 < 1, γ2 < 1 and 1

1+2α2
< 1, (41) and (42) hold by (116) to (122). ⊳



REFERENCES 79

References

[1] Bozdogan, H. (2000). Akaike’s information criterion and recent developments in infor-

mation complexity. Journal of Mathematical Psychology, 44, 62-91.

[2] Dawid, A.P. (1992). Prequential analysis, stochastic complexity and Bayesian inference.

Bayesian Statistics 4 (J.M. Bernardo, J.O. Berger, A.P. Dawid and A.F.M. Smith eds),

Oxford University Press, 109-125 (with discussions).

[3] Dawid, A.P. (1991). Fisherian inference in likelihood and prequential frames of refer-

ence. J. Roy. Statist. Soc. B 53, 79-109 (with discussions).

[4] Dawid, A.P. (1984). Present position and potential developments: some personal views,

statistical theory, the prequential approach. J. Roy. Statist. Soc. A, 47, 278-292 (with

discussions).

[5] Elias, P. (1975). Universal codeword sets and representations of the integers. IEEE Trans.

Information Theory 21, 194-203.

[6] Freedman, D.A. and Diaconis, P. (1981). On the histogram as a density estimator: L2

theory. Z. Wahrscheinlichkeitstheor. Verw. Geb. 57, 453-475.

[7] Hall, P. and Hannan, E.J. (1988). On stochastic complexity and nonparametric density

estimation. Biometrika, 75, 705-714.

[8] Lehmann, E.L. and Casella, G. (1998). Theory of Point Estimation. Springer-Verlag, New

York.

[9] Qian, G. and Künsch, H.R. (1998). Some notes on Rissanen’s stochastic complexity. IEEE

Trans Information Theory 44, 782-786.

[10] Qian, G. Gabor, G. and Gupta, R.P. (1996). Test for homogeniety of several populations

by stochastic complexity. Journal of Statistical Planning and Inference. 53. 133-151

[11] Rissanen, J. (2007). Information and Complexity in Statistical Modeling. Springer, New

York.

[12] Rissanen, J. (1996). Fisher information and stochastic complexity. IEEE Trans. Informa-

tion Theory, 42, 40-47.

[13] Rissanen, J. (1989). Stochastic Complexity in Statistical Inquiry. World Scientific Publish-

ing Company, Teaneck, NJ.

[14] Rissanen, J., Speed, T.P. and Yu, B. (1992). Density estimation by stochastic complexity.

IEEE Trans. Information Theory 38, 315-323.

[15] Rissanen, J. (1986). Stochastic complexity and modeling. Ann. Statist., 14, 1080-1100.



REFERENCES 80

[16] Rosenblatt, M. (1975). A quadratic measure of deviation of two-dimensional density

estimates and a test of independence. Ann. Statist. 3, 1-14.

[17] Shiryayev, A.N. (1995).Probability (2nd Edition). Springer-Verlag, New York.

[18] Solomonoff, R.J. (1978). Complexity-based induction system: comparison and conver-

gence theorems. IEEE Trans. Information Theory 24, 422-432.

[19] Stone, C.J. (1985). An asymptotic optimal histogram selection rule. Proceedings of the

Berkeley Conference in Honor of Jerzy Neyman and Jack Kiefer (ed. by Le Cam, L.M. and

Ohshen, R.A.), Volume II, 513-520. Wadsworth, Belmont, CA.

[20] Yu, B. and Speed, T.P. (1992). Data compression and histograms. Probability Theory and

Related Fields 92, 195-229.