Circular law theorem for random Markov matrices

Let (X _jk ) _jk≥1 be i.i.d. nonnegative random variables with bounded density, mean m, and finite positive variance σ ². Let M be the n?× n random Markov matrix with i.i.d. rows defined by ${M_{jk}=X_{jk}/(X_{j1}+\cdots+X_{jn})}$ . In particular, when X ₁₁ follows an exponential law, the random matrix M belongs to the Dirichlet Markov Ensemble of random stochastic matrices. Let λ₁, . . . , λ _n be the eigenvalues of ${\sqrt{n}M}$ i.e. the roots in ${\mathbb{C}}$ of its characteristic polynomial. Our main result states that with probability one, the counting probability measure ${\frac{1}{n}\delta_{\lambda_1}+\cdots+\frac{1}{n}\delta_{\lambda_n}}$ converges weakly as n→∞ to the uniform law on the disk ${\{z\in\mathbb{C}:|z|\leq m^{-1}\sigma\}}$ . The bounded density assumption is purely technical and comes from the way we control the operator norm of the resolvent.     

Norms and Essential Norms of the Singular Integral Operator with Cauchy Kernel on Weighted Lebesgue Spaces

Let ?? and ?? be bounded measurable functions on the unit circle ${\mathbb{T}}$ , and let L ²(W) be a weighted L ² space on ${\mathbb{T}}$ . The singular integral operator S _??,?? is defined by ${S_{\alpha, \beta}f = \alpha Pf + \beta Qf~ (f \in L^2(W))}$ where P is an analytic projection and Q = I ? P is a co-analytic projection. In the previous paper, the essential norm of S _??,?? are calculated in the case when W is a constant function. In this paper, the essential norm of S _??,?? are estimated in the case when W is an A ₂-weight.     

Composition Operators on Spaces of Fractional Cauchy Transforms

For ?? > 0, the Banach space ${\mathcal{F}_{\alpha}}$ is defined as the collection of functions f which can be represented as integral transforms of an appropriate kernel against a Borel measure defined on the unit circle T. Let ?? be an analytic self-map of the unit disc D. The map ?? induces a composition operator on ${\mathcal{F}_{\alpha}}$ if ${C_{\Phi}(f) = f \circ \Phi \in \mathcal{F}_{\alpha}}$ for any function ${f \in \mathcal{F}_{\alpha}}$ . Various conditions on ?? are given, sufficient to imply that C _?? is bounded on ${\mathcal{F}_{\alpha}}$ , in the case 0 < ?? < 1. Several of the conditions involve ???? and the theory of multipliers of the space ${\mathcal{F}_{\alpha}}$ . Relations are found between the behavior of C _?? and the membership of ?? in the Dirichlet spaces. Conditions given in terms of the generalized Nevanlinna counting function are shown to imply that ?? induces a bounded composition operator on ${\mathcal{F}_{\alpha}}$ , in the case 1/2 ?? ?? < 1. For such ??, examples are constructed such that ${\| \Phi \|_{\infty} = 1}$ and ${C_{\Phi}: \mathcal{F}_{\alpha} \rightarrow \mathcal{F}_{\alpha}}$ is bounded.     

On the correlation functions of the characteristic polynomials of the hermitian sample covariance matrices

We consider asymptotic behavior of the correlation functions of the characteristic polynomials of the hermitian sample covariance matrices ${H_n=n^{-1}A_{m,n}^* A_{m,n}}$ , where A _m,n is a m × n complex random matrix with independent and identically distributed entries ${\mathfrak{R}a_{\alpha j}}$ and ${\mathfrak{I}a_{\alpha j}}$ . We show that for the correlation function of any even order the asymptotic behavior in the bulk and at the edge of the spectrum coincides with those for the Gaussian Unitary Ensemble up to a factor, depending only on the fourth moment of the common probability law of entries ${\mathfrak{R}a_{\alpha j}}$ , ${\mathfrak{I}a_{\alpha j}}$ , i.e., the higher moments do not contribute to the above limit.     

Topological transitivity for a class of monotonic mod one transformations

Suppose that f : [0, 1] ?? [0, 2] is a continuous strictly increasing piecewise differentiable function, and define T _f x :=?f(x) (mod 1). Let ${\beta \geq \sqrt[3]{2}}$ . It is proved that T _f is topologically transitive if inf f???????? and ${f(0)\geq\frac{1}{\beta+1}}$ . Counterexamples are provided if the assumptions are not satisfied. For ${\sqrt[3]{2}\leq\beta < \sqrt{2}}$ and 0????????? 2 ? ?? it is shown that ??x?+??? (mod 1) is topologically transitive if and only if ${\alpha < \frac{1}{\beta^2+\beta}}$ or ${\alpha >2 -\beta-\frac{1}{\beta^2+\beta}}$ .     

Mass Transport and Uniform Rectifiability

In this paper we characterize the so called uniformly rectifiable sets of David and Semmes in terms of the Wasserstein distance W ₂ from optimal mass transport. To obtain this result, we first prove a localization theorem for the distance W ₂ which asserts that if??? and ?? are probability measures in ${{\mathbb{R}^n}}$ , ${{\varphi}}$ is a radial bump function smooth enough so that ${{\int \varphi d \mu \gtrsim 1}}$ , and??? has a density bounded from above and from below on supp( ${{\varphi}}$ ), then ${{W_2(\varphi \mu, a\varphi \nu) \leq cW_2(\mu, \nu)}}$ , where ${{a = \int \varphi d\mu/ \int \varphi d\nu}}$ .     

Heavy tail phenomenon and convergence to stable laws for iterated Lipschitz maps

We consider the Markov chain ${\{X_n^x\}_{n=0}^\infty}$ on ${\mathbb{R}^d}$ defined by the stochastic recursion ${X_{n}^{x}= \psi_{\theta_{n}} (X_{n-1}^{x})}$ , starting at ${x\in\mathbb{R}^d}$ , where ?? ₁, ?? ₂, . . . are i.i.d. random variables taking their values in a metric space ${(\Theta, \mathfrak{r})}$ , and ${\psi_{\theta_{n}} :\mathbb{R}^d\mapsto\mathbb{R}^d}$ are Lipschitz maps. Assume that the Markov chain has a unique stationary measure ??. Under appropriate assumptions on ${\psi_{\theta_n}}$ , we will show that the measure ?? has a heavy tail with the exponent ???>?0 i.e. ${\nu(\{x\in\mathbb{R}^d: |x| > t\})\asymp t^{-\alpha}}$ . Using this result we show that properly normalized Birkhoff sums ${S_n^x=\sum_{k=1}^n X_k^x}$ , converge in law to an ??-stable law for ${\alpha\in(0, 2]}$ .     

Degree complexity of birational maps related to matrix inversion: symmetric case

For q?≥ 3, we let ${\mathcal{S}_q}$ denote the projectivization of the set of symmetric q × q matrices with coefficients in ${\mathbb{C}}$ . We let ${I(x)=(x_{i,j})^{-1}}$ denote the matrix inverse, and we let ${J(x)=(x_{i,j}^{-1})}$ be the matrix whose entries are the reciprocals of the entries of x. We let ${K|\mathcal{S}_q=I\circ J:~\mathcal{S}_q\rightarrow \mathcal{S}_q}$ denote the restriction of the composition I ? J to ${\mathcal{S}_q}$ . This is a birational map whose properties have attracted some attention in statistical mechanics. In this paper we compute the degree complexity of ${K|\mathcal{S}_q}$ , thus confirming a conjecture of Angles d’Auriac et?al. (J Phys A Math Gen 39:3641–3654, 2006).     

The Eigenfunctions of the Hilbert Matrix

For each noninteger complex number ??, the Hilbert matrix $$H_\lambda= \biggl( \frac{1}{n+m+\lambda} \biggr)_{n,m\geq0}$$ defines a bounded linear operator on the Hardy spaces $\mathcal{H}^{p}$ , 1<p<??, and on the Korenblum spaces $\mathcal{A}^{-\tau}$ , ??>0. In this work, we determine the point spectrum with multiplicities of the Hilbert matrix acting on these spaces. This extends to complex ?? results by Hill and Rosenblum for real ??. We also provide a closed formula for the eigenfunctions. They are in fact closely related to the associated Legendre functions of the first kind. The results will be achieved through the analysis of certain differential operators in the commutator of the Hilbert matrix.     

On a problem concerning the Banach algebra generated by the maps n\mapsto\lambda^{\binom{n}{k}}

In Jabbari and Namioka (Milan J. Math. 78:503?C522, 2010), the authors characterized the spectrum M(W) of the Weyl algebra W, i.e. the norm closure of the algebra generated by the family of functions $\{n\mapsto x^{n^{k}}; x\in\mathbb{T}, k\in\mathbb{N}\}$ , ( $\mathbb{T}$ the unit circle), with a closed subgroup of $E(\mathbb{T})^{\mathbb{N}}$ where $E(\mathbb{T})$ denotes the family of the endomorphisms of the multiplicative group $\mathbb{T}$ . But the size of M(W) in $E(\mathbb{T})^{\mathbb{N}}$ as well as the induced group operation were left as a problem. In this paper, we will give a solution to this problem.     

Lyapunov exponents of Green��s functions for random potentials tending to zero

We consider quenched and annealed Lyapunov exponents for the Green??s function of ????+? ??V, where the potentials ${V(x),\ x\in\mathbb {Z}^d}$ , are i.i.d.? nonnegative random variables and ?? > 0 is a scalar. We present a probabilistic proof that both Lyapunov exponents scale like ${c\sqrt{\gamma}}$ as ?? tends to 0. Here the constant c is the same for the quenched as for the annealed exponent and is computed explicitly. This improves results obtained previously by Wang. We also consider other ways to send the potential to zero than multiplying it by a small number.     

Parametric nonlinear discrete optimization over well-described sets and matroid intersections

We address optimization of parametric nonlinear functions of the form f(Wx), where ${f : \mathbb {R}^d \rightarrow \mathbb {R}}$ is a nonlinear function, W is a d × n matrix, and feasible x are in some large finite set ${\mathcal {F}}$ of integer points in ${\mathbb {R}^n}$ . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f, W and ${\mathcal {F}}$ . One of our main motivations is multi-objective discrete optimization, where f trades off the linear functions given by the rows of W. Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures. We assume that ${\mathcal {F}}$ is well described (i.e., we can efficiently optimize a linear objective function on ${\mathcal {F}}$ ; equivalently, we have an efficient separation oracle for the convex hull of ${\mathcal {F}}$ ). For example, the sets of characteristic vectors of (i) matchings of a graph, and (ii) common bases of a pair of matroids on a common ground set satisfy this property. In this setting, the problem is already known to be intractable (even for a single matroid), for general f (given by a comparison oracle), for (i) d = 1 and binary-encoded W, and for (ii) d = n and W = I. Our main results (a few technicalities and some generality suppressed):

1. When ${\mathcal {F}}$ is well described, f is convex (or even quasi-convex), and W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic algorithm for maximization.

1. When ${\mathcal {F}}$ is well described, f is a norm, and W is binary-encoded, we give an efficient deterministic constant-approximation algorithm for maximization (Note that the approximation factor depends on the norm, and hence implicitly on the number of rows of W, while the running time increases only linearly in the number of rows of W).

1. When non-negative ${\mathcal {F}}$ is well described, f is “ray concave” and non-decreasing, and non-negative W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic constant-approximation algorithm for minimization.

1. When ${\mathcal {F}}$ is the set of characteristic vectors of common independent sets or bases of a pair of rational vectorial matroids on a common ground set, f is arbitrary, and W has a fixed number of rows and is unary encoded, we give an efficient randomized algorithm for optimization.

     

On fixed points of a generalized multidimensional affine recursion

Let G be a multiplicative subsemigroup of the general linear group Gl ${(\mathbb{R}^d)}$ which consists of matrices with positive entries such that every column and every row contains a strictly positive element. Given a G-valued random matrix A, we consider the following generalized multidimensional affine equation $$R\stackrel{\mathcal{D}}{=} \sum_{i=1}^N A_iR_i+B,$$ where N ≥ 2 is a fixed natural number, A ₁, . . . , A _N are independent copies of ${A, B \in \mathbb{R}^d}$ is a random vector with positive entries, and R ₁, . . . , R _N are independent copies of ${R \in \mathbb{R}^d}$ , which have also positive entries. Moreover, all of them are mutually independent and ${\stackrel{\mathcal{D}}{=}}$ stands for the equality in distribution. We will show with the aid of spectral theory developed by Guivarc’h and Le Page (Simplicité de spectres de Lyapounov et propriété d’isolation spectrale pour une famille d’opérateurs de transfert sur l’espace projectif. Random Walks and Geometry, Walter de Gruyter GmbH & Co. KG, Berlin, 2004; On matricial renewal theorems and tails of stationary measures for affine stochastic recursions, Preprint, 2011) and Kesten’s renewal theorem (Kesten in Ann Probab 2:355–386, 1974), that under appropriate conditions, there exists χ >  0 such that ${{\mathbb{P}(\{\langle R, u \rangle > t\})\asymp t^{-\chi}}}$ , as t → ∞, for every unit vector ${u \in \mathbb{S}^{d-1}}$ with positive entries.     

Lengths of periods of continued fractions of square roots of integers

Empirical study of the period’s length T of the continued fractions of $\sqrt{Q}$ (for growing integers Q) shows several strange asymptotical results, for instance, $T\leq C\sqrt{Q}\ln{Q}$ . These results show important differences between the statistics of the elements of the continued fractions of random real numbers and of square roots of random integers.     

On Minimum Saturated Matrices

Motivated both by the work of Anstee, Griggs, and Sali on forbidden submatrices and also by the extremal sat-function for graphs, we introduce sat-type problems for matrices. Let ${\mathcal{F}}$ be a family of k-row matrices. A matrix M is called ${\mathcal{F}}$ -admissible if M contains no submatrix ${F \in \mathcal{F}}$ (as a row and column permutation of F). A matrix M without repeated columns is ${\mathcal{F}}$ -saturated if M is ${\mathcal{F}}$ -admissible but the addition of any column not present in M violates this property. In this paper we consider the function sat( ${n, \mathcal{F}}$ ) which is the minimal number of columns of an ${\mathcal{F}}$ -saturated matrix with n rows. We establish the estimate sat ${(n, \mathcal{F})=O(n^{k-1})}$ for any family ${\mathcal{F}}$ of k-row matrices and also compute the sat-function for a few small forbidden matrices.     

Donsker-type theorems for nonparametric maximum likelihood estimators

Let ${\mathcal{P}}$ be a nonparametric probability model consisting of smooth probability densities and let ${\hat{p}_{n}}$ be the corresponding maximum likelihood estimator based on n independent observations each distributed according to the law ${\mathbb{P}}$ . With $\hat{\mathbb{P}}_{n}$ denoting the measure induced by the density ${\hat{p}_{n}}$ , define the stochastic process ${\hat{\nu}}_{n}: f\longmapsto \sqrt{n} \int fd({\hat{\mathbb{P}}}_{n} -\mathbb{P})$ where f ranges over some function class ${\mathcal{F}}$ . We give a general condition for Donsker classes ${\mathcal{F}}$ implying that the stochastic process $\hat{\nu}_{n}$ is asymptotically equivalent to the empirical process in the space ${\ell ^{\infty }(\mathcal{F})}$ of bounded functions on ${ \mathcal{F}}$ . This implies in particular that $\hat{\nu}_{n}$ converges in law in ${\ell ^{\infty }(\mathcal{F})}$ to a mean zero Gaussian process. We verify the general condition for a large family of Donsker classes ${\mathcal{ F}}$ . We give a number of applications: convergence of the probability measure ${\hat{\mathbb{P}}_{n}}$ to ${\mathbb{P}}$ at rate ${\sqrt{n}}$ in certain metrics metrizing the topology of weak(-star) convergence; a unified treatment of convergence rates of the MLE in a continuous scale of Sobolev-norms; ${\sqrt{n}}$ -efficient estimation of nonlinear functionals defined on ${\mathcal{P}}$ ; limit theorems at rate ${\sqrt{n}}$ for the maximum likelihood estimator of the convolution product ${\mathbb{P\ast P}}$ .     

Random repeated quantum interactions and random invariant states

We consider a generalized model of repeated quantum interactions, where a system ${\mathcal{H}}$ is interacting in a random way with a sequence of independent quantum systems ${\mathcal{K}_n, n \geq 1}$ . Two types of randomness are studied in detail. One is provided by considering Haar-distributed unitaries to describe each interaction between ${\mathcal{H}}$ and ${\mathcal{K}_n}$ . The other involves random quantum states describing each copy ${\mathcal{K}_n}$ . In the limit of a large number of interactions, we present convergence results for the asymptotic state of ${\mathcal{H}}$ . This is achieved by studying spectral properties of (random) quantum channels which guarantee the existence of unique invariant states. Finally this allows to introduce a new physically motivated ensemble of random density matrices called the asymptotic induced ensemble.     

On definability in some lattices of semigroup varieties

An identity of the form x ₁?x _n ??x _1?? x _2?? ?x _n?? where ?? is a non-trivial permutation on the set {1,??,n} is called a permutation identity. If u??v is a permutation identity, then ?(u??v) [respectively r(u??v)] is the maximal length of the common prefix [suffix] of the words u and v. A variety that satisfies a permutation identity is called permutative. If $\mathcal{V}$ is a permutative variety, then $\ell=\ell(\mathcal{V})$ [respectively $r=r(\mathcal{V})$ ] is the least ? [respectively r] such that $\mathcal{V}$ satisfies a permutation identity ?? with ?(??)=? [respectively r(??)=r]. A?variety that consists of nil-semigroups is called a nil-variety. If ?? is a set of identities, then $\operatorname {var}\varSigma$ denotes the variety of semigroups defined by ??. If $\mathcal{V}$ is a variety, then $L (\mathcal{V})$ denotes the lattice of all subvarieties of $\mathcal{V}$ . For ?,r??0 and n>1 let $\mathfrak{B}_{\ell,r,n}$ denote the set that consists of n! identities of the form $$t_1\cdots t_\ell x_1x_2 \cdots x_n z_{1}\cdots z_{r}\approx t_1\cdots t_\ell x_{1\pi}x_{2\pi} \cdots x_{n\pi}z_{1}\cdots z_{r}, $$ where ?? is a permutation on the set {1,??,n}. We prove that for each permutative nil-variety $\mathcal{V}$ and each $\ell\ge\ell(\mathcal{V})$ and $r\ge r(\mathcal{V})$ there exists n>1 such that $\mathcal{V}$ is definable by a first-order formula in $L(\operatorname{var}{\mathfrak{B}}_{l,r,n})$ if ???r or $\mathcal{V}$ is definable up to duality in $L(\operatorname{var}{\mathfrak{B}}_{\ell,r,n})$ if ?=r.     

The Essential Norm of a Generalized Composition Operator Between Bloch-Type Spaces and Q K Type Spaces

Let ?? be an analytic self-map of the unit disk ${\rm \mathbb{D},H(\rm \mathbb{D})}$ the space of analytic functions on ${{\rm \mathbb{D}}}$ and ${g \in H(\rm \mathbb{D})}$ . We define a linear operator as follows $$C_\varphi^gf(z)=\int\limits_0^zf'(\varphi(w))g(w)\, {\rm d}w, $$ on ${ H(\rm \mathbb{D})}$ . In this paper, estimates for the essential norm of the generalized composition operator between Bloch-type spaces and Q _K type spaces are obtained.     

On Bipartite Distance-Regular Graphs with Intersection Numbers c i = (q i ? 1)/(q ? 1)

Let q denote an integer at least two. Let ?? denote a bipartite distance-regular graph with diameter D ?? 3 and intersection numbers c _i = (q ⁱ ? 1)/(q ? 1), 1 ?? i ?? D. Let X denote the vertex set of ?? and let ${V = \mathbb{C}^X}$ denote the vector space over ${\mathbb{C}}$ consisting of column vectors whose coordinates are indexed by X and whose entries are in ${\mathbb{C}}$ . For ${z \in X}$ , let ${{\hat z}}$ denote the vector in V with a 1 in the z-coordinate and 0 in all other coordinates. Fix ${x, y \in X}$ such that ?(x, y) = 2, where ? denotes the path-length distance function. For 0 ?? i, j ?? D define ${w_{ij} = \sum {\hat z}}$ , where the sum is over all ${z \in X}$ such that ?(x, z) = i and ?(y, z) = j. We define W?=?span{w _ij | 0 ?? i, j ?? D}. In this paper we consider the space ${MW={\rm span} \{mw \mid m \in M, w \in W\}}$ , where M is the Bose?CMesner algebra of ??. We observe that MW is the minimal A-invariant subspace of V which contains W, where A is the adjacency matrix of ??. We give a basis for MW that is orthogonal with respect to the Hermitean dot product. We compute the square-norm of each basis vector. We compute the action of A on the basis. For the case in which ?? is the dual polar graph D _D (q) we show that the basis consists of the characteristic vectors of the orbits of the stabilizer of x and y in the automorphism group of ??.