Directed Dominating Set Problem Studied by Cavity Method: Warning Propagation and Population Dynamics

The minimal dominating set for a digraph (directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erdös-Rényi graphs to find the ground state energy. In this paper we continue to develope the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following. (i) The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one. (ii) We determine the ground state energy and the transition point of the Erdös-Rényi random graph. (iii) The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm.     

A Two-Moment Inequality with Applications to Rényi Entropy and Mutual Information

This paper explores some applications of a two-moment inequality for the integral of the rth power of a function, where 0<r<1. The first contribution is an upper bound on the Rényi entropy of a random vector in terms of the two different moments. When one of the moments is the zeroth moment, these bounds recover previous results based on maximum entropy distributions under a single moment constraint. More generally, evaluation of the bound with two carefully chosen nonzero moments can lead to significant improvements with a modest increase in complexity. The second contribution is a method for upper bounding mutual information in terms of certain integrals with respect to the variance of the conditional density. The bounds have a number of useful properties arising from the connection with variance decompositions.     

The Length of the Longest Head-Run in a Model with Long Range Dependence

In this paper, we construct stationary sequences of random variables { _i : i0} taking values ±1 with probability 1/2 and we prove an Erdös–Rényi law of large numbers for the length of the longest run of consecutive +1's in the sample {₀,..., _n }. Our model, which is called random walk in random scenery, exhibits long-range, positive dependence.     

From Rényi Entropy Power to Information Scan of Quantum States

In this paper, we generalize the notion of Shannon’s entropy power to the Rényi-entropy setting. With this, we propose generalizations of the de Bruijn identity, isoperimetric inequality, or Stam inequality. This framework not only allows for finding new estimation inequalities, but it also provides a convenient technical framework for the derivation of a one-parameter family of Rényi-entropy-power-based quantum-mechanical uncertainty relations. To illustrate the usefulness of the Rényi entropy power obtained, we show how the information probability distribution associated with a quantum state can be reconstructed in a process that is akin to quantum-state tomography. We illustrate the inner workings of this with the so-called “cat states”, which are of fundamental interest and practical use in schemes such as quantum metrology. Salient issues, including the extension of the notion of entropy power to Tsallis entropy and ensuing implications in estimation theory, are also briefly discussed.     

On Rényi Permutation Entropy

Among various modifications of the permutation entropy defined as the Shannon entropy of the ordinal pattern distribution underlying a system, a variant based on Rényi entropies was considered in a few papers. This paper discusses the relatively new concept of Rényi permutation entropies in dependence of non-negative real number q parameterizing the family of Rényi entropies and providing the Shannon entropy for q=1. Its relationship to Kolmogorov–Sinai entropy and, for q=2, to the recently introduced symbolic correlation integral are touched.     

Rényi Entropy and Free Energy

The Rényi entropy is a generalization of the usual concept of entropy which depends on a parameter q. In fact, Rényi entropy is closely related to free energy. Suppose we start with a system in thermal equilibrium and then suddenly divide the temperature by q. Then the maximum amount of work the system can perform as it moves to equilibrium at the new temperature divided by the change in temperature equals the system’s Rényi entropy in its original state. This result applies to both classical and quantum systems. Mathematically, we can express this result as follows: the Rényi entropy of a system in thermal equilibrium is without the ‘q−1-derivative’ of its free energy with respect to the temperature. This shows that Rényi entropy is a q-deformation of the usual concept of entropy.     

Acoustic classification of Australian anurans based on hybrid spectral-entropy approach

A new hybrid method for automated frog sound identification, using spectral centroid, Shannon entropy and Rényi entropy is proposed. The advantage of using entropy based information theoretic approach for analyzing complexity of bioacoustics signals in animal vocalization is discussed. Sound samples from nine species of Microhylidae frogs are first segmented into syllables. Fourier spectral centroid, Shannon entropy and Rényi entropy of the syllables are then determined. Finally, nonparametric k-th nearest neighbour (k-NN) classifier is used to recognize the frog species based on these three extracted features. Result shows that the k-NN classifier based on these selected features is capable to identify the species of the frogs with an average accuracy of 98%. It is found that the accuracy reduces significantly only when the noise levels higher than −20 dB.     

High Dimensional Atomic States of Hydrogenic Type: Heisenberg-like and Entropic Uncertainty Measures

High dimensional atomic states play a relevant role in a broad range of quantum fields, ranging from atomic and molecular physics to quantum technologies. The D-dimensional hydrogenic system (i.e., a negatively-charged particle moving around a positively charged core under a Coulomb-like potential) is the main prototype of the physics of multidimensional quantum systems. In this work, we review the leading terms of the Heisenberg-like (radial expectation values) and entropy-like (Rényi, Shannon) uncertainty measures of this system at the limit of high D. They are given in a simple compact way in terms of the space dimensionality, the Coulomb strength and the state’s hyperquantum numbers. The associated multidimensional position–momentum uncertainty relations are also revised and compared with those of other relevant systems.     

Relativistic effects on information measures for hydrogen-like atoms

Position and momentum information measures are evaluated for the ground state of the relativistic hydrogen-like atoms. Consequences of the fact that the radial momentum operator is not self-adjoint are explicitly studied, exhibiting fundamental shortcomings of the conventional uncertainty measures in terms of the radial position and momentum variances. The Shannon and Rényi entropies, the Fisher information measure, as well as several related information measures, are considered as viable alternatives. Detailed results on the onset of relativistic effects for low nuclear charges, and on the extreme relativistic limit, are presented. The relativistic position density decays exponentially at large r, but is singular at the origin. Correspondingly, the momentum density decays as an inverse power of p. Both features yield divergent Rényi entropies away from a finite vicinity of the Shannon entropy. While the position space information measures can be evaluated analytically for both the nonrelativistic and the relativistic hydrogen atom, this is not the case for the relativistic momentum space. Some of the results allow interesting insight into the significance of recently evaluated Dirac-Fock vs. Hartree-Fock complexity measures for many-electron neutral atoms.     

Statistical Estimation of Generalized Dimensions

A statistical estimate for generalized dimensions of a set based on the computation of average distances to the closest points in a sample of elements of A is given. For smooth manifolds with Lebesgue measures and for self-similar fractals with self-similar measures, the estimate is proved to be consistent.