This paper studies the asymptotic performance of a modified version of Page's sequential change detection algorithm based on universal compression. Such a class of change detection algorithms was first introduced by Jacob and Bansal in [1] where the authors studied the performance of the modified test under Lorden's minimax framework. This paper is motivated by the monograph [2] of Lai, which introduced a host of criteria for gauging the performance of change detection tests. We consider the performance of the modified test under one such criteria namely a constraint on the probability of false alarm within a window and establish that asymptotically the modified test is equivalent to Page's Cumulative Sum Test (CUSUM).

In this work, we establish the pointwise optimality of side information version of SWLZ algorithm for stationary ergodic sources. We also obtain a pointwise upper bound on the redundancy rate of this side information version of SWLZ algorithm for a subclass of φ-mixing sources, which includes Markov sources as a special case. This upper bound obtained differs only by a constant factor from the best bound that has been obtained on redundancy rate for the original SWLZ algorithm itself.

Summary Energy‐efficient scheduling is a step towards meeting green computing requirements. The work in this direction mainly aims at reducing dynamic energy consumption that includes clock gating, cache subbanking, and dynamic voltage and frequency scaling of underlying processors. However, the emergence of fast and compact transistor sizes has exponentially added onto the processor static power consumption, which has not been paid much attention. This article proposes a duplication‐controlled static energy‐efficient scheduling (C‐SEED) algorithm for scheduling precedence constrained applications on parallel computing systems. The C‐SEED algorithm couples adaptive threshold‐based duplication with system level dynamic power management technique to achieve its objectives. Dynamic power management works by selectively putting the energy‐consuming resources to efficient low‐power states for idle times to reduce energy consumption. Efficacy of the proposed algorithm is analyzed and compared against other relevant works on the basis of makespan and total energy (dynamic + static + communication) consumption. The extensive simulation results carried over large set of random and regular task graphs show that the proposed C‐SEED algorithm has potential to reduce energy consumption as well as makespan.

In this paper we analyse the redundancy rate of a variant of sliding window Lempel-Ziv (SWLZ) proposed by Bender and Wolf, which encodes phrase lengths differently from the original algorithm. We examine upper bound on the contribution of phrase length bits for this variant to get an overall upper bound of O(1/log nw) on the redundancy rate for Markov sources which is better than the lower bound of O(log log nw/log nw), established by the Lastras-Montano for SWLZ algorithm. Here nwdenotes the window size.

We use the machinery developed by Wyner [1], for the sources satisfying Markov condition, to obtain an upper bound on the contribution of pointer bits to the compression ratio for fixed database Lempel-Ziv (FDLZ) algorithm to be H + O(1/ log2n) which is an improvement from the previous bound of H + H(1 + o(1))log2log2n/ log2n . We use the definition of compression ratio as in Yang and Kieffer [2]. Here H is the entropy rate of the source and n is the size of the database. Then using the same definition of compression ratio we obtain an upper bound on the contribution of phrase length bits for the variant of FDLZ suggested in [3] to be O(1/ log2n), which gives an upper bound of O(1/ log2n) on the redundancy rate itself for this version of FDLZ.

In this paper, we bound the number of phrases of the sliding window Lempel-Ziv (SWLZ) algorithm using an upper bound on the expected number of phrases in the fixed database Lempel-Ziv (FDLZ) algorithm for a class of φ-mixing sources which includes Markov sources, unifilar sources and finite state sources as special cases, as developed by Yang and Kieffer [1]. We use this bound to obtain a point-wise upper bound on the redundancy rate of SWLZ algorithm to be 2H(log2log2nw/log2nw) + O(log2log2log2nw/log2nw). Here H is the entropy rate of the source and nwis the window size.

In this work, we first relate rate of convergence of waiting times Wn(D), until a D-close version of the first n symbols of a realization of a process appears in the realization of another independent process, with rate of convergence in generalized AEP. We then identify the conditions under which exponential rates of convergence holds in generalized AEP and for waiting times.

The sliding window Lempel-Ziv (SWLZ) algorithm that makes use of recurrence times and match lengths has been studied from various perspectives in information theory literature. In this paper, we undertake a finer study of these quantities under two different scenarios: 1) zero entropy sources that are characterized by strong long-term memory and 2) the processes with weak memory as described through various mixing conditions. For zero entropy sources, a general statement on match length is obtained. It is used in the proof of almost sure optimality of fixed shift variant of Lempel-Ziv (FSLZ) and SWLZ algorithms given in literature. Through an example of stationary and ergodic processes generated by an irrational rotation, we establish that for a window of size nw, a compression ratio given by O(log nw/nwa), where a depends on nwand approaches 1 as nw→ ∞, is obtained under the application of FSLZ and SWLZ algorithms. In addition, we give a general expression for the compression ratio for a class of stationary and ergodic processes with zero entropy. Next, we extend the study of Ornstein and Weiss on the asymptotic behavior of the normalized version of recurrence times and establish the large deviation property for a class of mixing processes. In addition, an estimator of entropy based on recurrence times is proposed for which large deviation principle is proved for sources satisfying similar mixing conditions.

In this work, we study the asymptotic properties of the waiting time until the opening string in the realization of a process first appears in an independent realization of the same or a different process. We first establish that the normalized waiting time between two independent realizations of a single source obeys the large deviation property for a class of mixing processes. Using the method of Markov types, we extend the result to when both the sequences are realizations of two distinct irreducible and aperiodic Markov sources.

We extend the study by Ornstein and Weiss on the asymptotic behavior of the normalized version of recurrence times and establish the large deviation property for a certain class of mixing processes. Further, an estimator for entropy based on recurrence times is proposed for which large deviation behavior is proved for stationary and ergodic sources satisfying similar mixing conditions.

The Sliding Window Lempel-Ziv (SWLZ) algorithm has been studied from various perspectives in information theory literature. In this paper, we provide a general law which defines the asymptotics of match length for stationary and ergodic zero entropy processes. Moreover, we use this law to choose the match length Loin the almost sure optimality proof of Fixed Shift Variant of Lempel-Ziv (FSLZ) and SWLZ algorithms given in literature. First, through an example of stationary and ergodic processes generated by irrational rotation we establish that for a window size of nwa compression ratio given by O(log nw/nwa) where a is arbitrarily close to 1 and 0 <; a <; 1, is obtained under the application of FSLZ and SWLZ algorithms. Further, we give a general expression for the compression ratio for a class of stationary and totally ergodic processes with zero entropy.

The sliding window Lempel–Ziv (SWLZ) algorithm has been studied extensively in the information theory literature and has been used in several commercial compression packages. The asymptotic behavior of this algorithm has been studied by Wyner and Ziv and by Shields using different approaches. Shields' results proving asymptotic optimality for all individual sequences with respect to the class of all finite state encoders is known to imply the almost sure asymptotic optimality for the class of stationary and ergodic sources. We establish the almost sure asymptotic optimality (without any mixing conditions) by extending the ideas of Wyner and Ziv using results on recurrence times from ergodic theory. A nonuniversal fixed shift version of the algorithm is introduced to gain more insight into its behavior. Pointwise optimality results are also obtained for several variants based on match-length functions introduced by Gavish and Lempel. We also propose variants of the algorithm for sources with countable alphabet and demonstrate their pointwise optimality.

The application of universal source coding algorithms to the problem of classification was initiated by Ziv and has been extended to other problems in statistics such as order estimation. In spite of the large literature, these studies have been limited to problems with fixed number of samples. In this paper we study the application of universal source coding to the problem of sequential hypothesis testing and sequential change detection. Algorithms are proposed which are inspired by Waldpsilas Sequential Probability Ratio Test (SPRT) and Pagepsilas Cumulative Sum Test (CUSUM) for these problems respectively. Performance of the proposed algorithms are studied in the asymptotic regime to demonstrate their effectiveness.

Outlier-resistant algorithms that detect a change from a given nominal stationary process to another such process are given. The nominal processes are assumed to be mutually independent and to satisfy some general regularity conditions. The outlier sequences are assumed to be independently and identically distributed and independent of the nominal processes. The proposed algorithms are sequential and consist of uniformly bounded steps. The asymptotic performance of the algorithms is analyzed, both in the absence and the presence of outliers. Breakdown points and influence functions are defined and analyzed. The algorithms are studied in more detail for Gaussian autoregressive nominal processes.>

The problem of detecting a change from one given stationary and ergodic stochastic process to another such process is considered. It is assumed that both stochastic processes are processes with memory and that they are mutually independent. A sequential test is proposed and analyzed. It is proved that the proposed test is asymptotically optimal in a mathematically precise sense.