Alfréd Rényi Institute of Mathematics

Distance correlation is a new class of multivariate dependence coefficients applicable to random vectors of arbitrary and not necessarily equal dimension. Distance covariance and distance correlation are analogous to product-moment covariance and correlation, but generalize and extend these classical bivariate measures of dependence. Distance correlation characterizes independence: it is zero if and only if the random vectors are independent. The notion of covariance with respect to a stochastic process is introduced, and it is shown that population distance covariance coincides with the covariance with respect to Brownian motion; thus, both can be called Brownian distance covariance. In the bivariate case, Brownian covariance is the natural extension of product-moment covariance, as we obtain Pearson product-moment covariance by replacing the Brownian motion in the definition with identity. The corresponding statistic has an elegantly simple computing formula. Advantages of applying Brownian covariance and correlation vs the classical Pearson covariance and correlation are discussed and illustrated.

Abstract Recently, Barabási and Albert [2] suggested modeling complex real‐world networks such as the worldwide web as follows: consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number of earlier vertices, selected with probabilities proportional to their degrees. In [2] and, with Jeong, in [3], Barabási and Albert suggested that after many steps the proportion P ( d ) of vertices with degree d should obey a power law P ( d )α d −γ . They obtained γ=2.9±0.1 by experiment and gave a simple heuristic argument suggesting that γ=3. Here we obtain P ( d ) asymptotically for all d ≤ n 1/15 , where n is the number of vertices, proving as a consequence that γ=3. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 279–290, 2001

We derive single-letter characterizations of (strong) secrecy capacities for models with an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unrestricted and interactive public communication permitted between the terminals. A subset of these terminals can serve as helpers for the remaining terminals in generating secrecy. According to the extent of an eavesdropper's knowledge, three kinds of secrecy capacity are considered: secret key (SK), private key (PK), and wiretap secret key (WSK) capacity. The characterizations of the SK and PK capacities highlight the innate connections between secrecy generation and multiterminal source coding without secrecy requirements. A general upper bound for WSK capacity is derived which is tight in the case when the eavesdropper can wiretap noisy versions of the components of the underlying multiple source, provided randomization is permitted at the terminals. These secrecy capacities are seen to be achievable with noninteractive communication between the terminals. The achievability results are also shown to be universal.

This book is the first comprehensive, modern introduction to the theory of central simple algebras over arbitrary fields. Starting from the basics, it reaches such advanced results as the Merkurjev-Suslin theorem. This theorem is both the culmination of work initiated by Brauer, Noether, Hasse and Albert and the starting point of current research in motivic cohomology theory by Voevodsky, Suslin, Rost and others. Assuming only a solid background in algebra, but no homological algebra, the book covers the basic theory of central simple algebras, methods of Galois descent and Galois cohomology, Severi-Brauer varieties, residue maps and, finally, Milnor K-theory and K-cohomology. The last chapter rounds off the theory by presenting the results in positive characteristic, including the theorem of Bloch-Gabber-Kato. The book is suitable as a textbook for graduate students and as a reference for researchers working in algebra, algebraic geometry or K-theory.

This tutorial is concerned with applications of information theory concepts in statistics, in the finite alphabet setting. The information measure known as information divergence or Kullback-Leibler distance or relative entropy plays a key role, often with a geometric flavor as an analogue of squared Euclidean distance, as in the concepts of I-projection, I-radius and I-centroid. The topics covered include large deviations, hypothesis testing, maximum likelihood estimation in exponential families, analysis of contingency tables, and iterative algorithms with an “information geometry” background. Also, an introduction is provided to the theory of universal coding, and to statistical inference via the minimum description length principle motivated by that theory.

In analogy with the classical Minkowski problem, necessary and sufficient conditions are given to assure that a given measure on the unit sphere is the cone-volume measure of the unit ball of a finite-dimensional Banach space.

In this paper we show that for any fixed Pearson correlation coefficient strictly between −1 and 1, the distance correlation coefficient can take any value in the open unit interval (0,1).

We consider the generation of common randomness (CR), secret or not secret, by two user terminals with aid from a "helper" terminal. Each terminal observes a different component of a discrete memoryless multiple source. The helper aids the users by transmitting information to them over a noiseless public channel subject to a rate constraint. Furthermore, one of the users is allowed to transmit to the other user over a public channel under a similar rate constraint. We study the maximum rate of CR which can be thus generated, including under additional secrecy conditions when it must be concealed from a wiretapper. Lower bounds for the corresponding capacities are provided, and single-letter capacity formulas are obtained for several special cases of interest.

We consider sequences of graphs (Gn) and define various notions of convergence related to these sequences including "left-convergence," defined in terms of the densities of homomorphisms from small graphs into Gn, and "right-convergence," defined in terms of the densities of homomorphisms from Gn into small graphs.

A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs (i.e. all but $o(2^{( \begin{subarray}{l} n \\ 2 \end{subarray} )} )$) of the $2^{( \begin{subarray}{l} n \\ 2 \end{subarray} )} $ graphs on n vertices). Hence, for almost all graphs X, any graph Y can be easily tested for isomorphism to X by an extremely naive linear time algorithm. This result is based on the following: In almost all graphs on n vertices, the largest $n^{0.15} $ degrees are distinct. In fact, they are pairwise at least $n^{0.03} $ apart.

We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, or the monochromatic path theorem of Sands et al. In this framework, we formulate a matroid-generalization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope.

Given a high dimensional convex body K⊆ℝn by a separation oracle, we can approximate its volume with relative error ε, using O*(n5) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding” followed by a multiphase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing; and a stepwise interlacing of rounding and sampling. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11, 1–50, 1997

Axiomatic characterizations of Shannon entropy, Kullback I-divergence, and some generalized information measures are surveyed. Three directions are treated: (A) Characterization of functions of probability distributions suitable as information measures. (B) Characterization of set functions on the subsets of {1; : : : ;N} representable by joint entropies of components of an N-dimensional random vector. (C) Axiomatic characterization of MaxEnt and related inference rules. The paper concludes with a brief discussion of the relevance of the axiomatic approach for information theory.

Ongoing fluctuations of neuronal activity have long been considered intrinsic noise that introduces unavoidable and unwanted variability into neuronal processing, which the brain eliminates by averaging across population activity (Georgopoulos et al., 1986; Lee et al., 1988; Shadlen and Newsome, 1994; Maynard et al., 1999). It is now understood, that the seemingly random fluctuations of cortical activity form highly structured patterns, including oscillations at various frequencies, that modulate evoked neuronal responses (Arieli et al., 1996; Poulet and Petersen, 2008; He, 2013) and affect sensory perception (Linkenkaer-Hansen et al., 2004; Boly et al., 2007; Sadaghiani et al., 2009; Vinnik et al., 2012; Palva et al., 2013). Ongoing cortical activity is driven by proprioceptive and interoceptive inputs. In addition, it is partially intrinsically generated in which case it may be related to mental processes (Fox and Raichle, 2007; Deco et al., 2011). Here we argue that respiration, via multiple sensory pathways, contributes a rhythmic component to the ongoing cortical activity. We suggest that this rhythmic activity modulates the temporal organization of cortical neurodynamics, thereby linking higher cortical functions to the process of breathing.

Genome structure variation has profound impacts on phenotype in organisms ranging from microbes to humans, yet little is known about how natural selection acts on genome arrangement. Pathogenic bacteria such as Yersinia pestis, which causes bubonic and pneumonic plague, often exhibit a high degree of genomic rearrangement. The recent availability of several Yersinia genomes offers an unprecedented opportunity to study the evolution of genome structure and arrangement. We introduce a set of statistical methods to study patterns of rearrangement in circular chromosomes and apply them to the Yersinia. We constructed a multiple alignment of eight Yersinia genomes using Mauve software to identify 78 conserved segments that are internally free from genome rearrangement. Based on the alignment, we applied Bayesian statistical methods to infer the phylogenetic inversion history of Yersinia. The sampling of genome arrangement reconstructions contains seven parsimonious tree topologies, each having different histories of 79 inversions. Topologies with a greater number of inversions also exist, but were sampled less frequently. The inversion phylogenies agree with results suggested by SNP patterns. We then analyzed reconstructed inversion histories to identify patterns of rearrangement. We confirm an over-representation of "symmetric inversions"-inversions with endpoints that are equally distant from the origin of chromosomal replication. Ancestral genome arrangements demonstrate moderate preference for replichore balance in Yersinia. We found that all inversions are shorter than expected under a neutral model, whereas inversions acting within a single replichore are much shorter than expected. We also found evidence for a canonical configuration of the origin and terminus of replication. Finally, breakpoint reuse analysis reveals that inversions with endpoints proximal to the origin of DNA replication are nearly three times more frequent. Our findings represent the first characterization of genome arrangement evolution in a bacterial population evolving outside laboratory conditions. Insight into the process of genomic rearrangement may further the understanding of pathogen population dynamics and selection on the architecture of circular bacterial chromosomes.

Journal Article SUFFICIENCY OF CHANNELS OVER VON NEUMANN ALGEBRAS Get access DÉNES PETZ DÉNES PETZ Mathematical Institut of HASReáltanoda u. 13–15 H-1364 Budapest, PF. 127 Hungary Search for other works by this author on: Oxford Academic Google Scholar The Quarterly Journal of Mathematics, Volume 39, Issue 1, March 1988, Pages 97–108, https://doi.org/10.1093/qmath/39.1.97 Published: 01 March 1988 Article history Received: 17 July 1986 Published: 01 March 1988

We exhibit a subset of a finite Abelian group, which tiles the group by translation, and such that its tiling complements do not have a common spectrum (orthogonal basis for their L2 space consisting of group characters). This disproves the Universal Spectrum Conjecture of Lagarias and Wang [Lagarias J. C. and Wang Y.: Spectral sets and factorizations of finite Abelian groups.J. Func. Anal. 145 (1997), 73–98]. Further, we construct a set in some finite Abelian group, which tiles the group but has no spectrum. We extend this last example to the groups ℤd and ℝd (for d ≥5 ) thus disproving one direction of the Spectral Set Conjecture of Fuglede [Fuglede B.: Commuting self-adjoint partial differential operators and a group theoretic problem. J. Funct. Anal. 16 (1974), 101–121]. The other direction was recently disproved by Tao [Tao T.: Fuglede's conjecture is false in 5 and higher dimensions. Math. Res. Letters 11 (2004), 251–258].

This book collects the material delivered in the 2008 edition of the DocCourse in Combinatorics and Geometry which was devoted to the topic of Additive Combinatorics.

Energy distance is a metric that measures the distance between the distributions of random vectors. Energy distance is zero if and only if the distributions are identical, thus it characterizes equality of distributions and provides a theoretical foundation for statistical inference and analysis. Energy statistics are functions of distances between observations in metric spaces. As a statistic, energy distance can be applied to measure the difference between a sample and a hypothesized distribution or the difference between two or more samples in arbitrary, not necessarily equal dimensions. The name energy is inspired by the close analogy with Newton's gravitational potential energy. Applications include testing independence by distance covariance, goodness‐of‐fit, nonparametric tests for equality of distributions and extension of analysis of variance, generalizations of clustering algorithms, change point analysis, feature selection, and more. WIREs Comput Stat 2016, 8:27–38. doi: 10.1002/wics.1375 This article is categorized under: Statistical and Graphical Methods of Data Analysis > Multivariate Analysis Statistical and Graphical Methods of Data Analysis > Nonparametric Methods

We construct binary codes for fingerprinting. Our codes for n users that are ε-secure against c pirates have length O(c2 log(n/ε)). This improves the codes proposed by Boneh and Shaw [3] whose length is approximately the square of this length. Our codes are probabilistic. By proving matching lower bounds we establish that the length of these codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert, Shelat, and Smith [10] that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet, and also the equal strength of two distinct models for fingerprinting.