The Maximal Variation of Martingales of Probabilities and Repeated Games with Incomplete Information

The variation of a martingale $p_{0}^{k}=p_{0},\ldots,p_{k}$ of probabilities on a finite (or countable) set X is denoted $V(p_{0}^{k})$ and defined by $$ V\bigl(p_0^k\bigr)=E\Biggl(\sum_{t=1}^k\|p_t-p_{t-1}\|_1\Biggr). $$ It is shown that $V(p_{0}^{k})\leq\sqrt{2kH(p_{0})}$ , where H(p) is the entropy function H(p)=?∑ _x p(x)logp(x), and log stands for the natural logarithm. Therefore, if d is the number of elements of X, then $V(p_{0}^{k})\leq\sqrt{2k\log d}$ . It is shown that the order of magnitude of the bound $\sqrt{2k\log d}$ is tight for d≤2 ^k : there is C>0 such that for all k and d≤2 ^k , there is a martingale $p_{0}^{k}=p_{0},\ldots,p_{k}$ of probabilities on a set X with d elements, and with variation $V(p_{0}^{k})\geq C\sqrt{2k\log d}$ . An application of the first result to game theory is that the difference between v _k and lim _j v _j , where v _k is the value of the k-stage repeated game with incomplete information on one side with d states, is bounded by $\|G\|\sqrt{2k^{-1}\log d}$ (where ∥G∥ is the maximal absolute value of a stage payoff). Furthermore, it is shown that the order of magnitude of this game theory bound is tight.     

On the growth order of the rectangular partial sums of multiple non-orthogonal series

Пустьd-натуральное ч исло,Z ^d — множество на боров k=(k ₁, ...,k _d ), состоящих из неотрицательных цел ыхk _j ,Z ₊ ^d =k∈Z ^d :k≧1. Предположи м, что системаf _k (x):k∈Z ₊ ^d ? ?L₂(X,A, μ) и последовател ьностьa _k :k∈Z ₊ ^d . таковы, чт о для всех b∈Z^d и m∈Z ₊ ^d выполн ены неравенства (2) $$\left\| {\sum\limits_{b + 1 \leqq k \leqq b + m} {a_k f_k (x)} } \right\|_2^2 \leqq w^2 (m)\sum\limits_{b + 1 \leqq k \leqq b + m} {a_k^2 } $$ где последовательно сть {w(m): m∈Z ₊ ^d положительн а и не убывает. Например, есл иf _k (х) — квазистационарная система, то для соотве тствующей последовательности {ω(m) (2) имeeт Меcтo ДЛЯ ЛЮбОЙ ПОС ЛеДОВатеЛЬНОСТИ {a_k}. В работе получены оце нки порядка роста пря моугольных частных суммS _m (x)= =∑ a_kf_k(x) при maxmj→∞ как в случ ае {a_k}∈l₂, таки для {a_k}l₂. Эти оценки явля1≦k≦m 1≦j≦d ются новыми даже для о ртогональных кратны х рядов. Показано, что упомяну тые оценки в общем слу чае являются точными.     

A Congruence Connecting Latin Rectangles and Partial Orthomorphisms

A partial orthomorphism of ${\mathbb{Z}_{n}}$ is an injective map ${\sigma : S \rightarrow \mathbb{Z}_{n}}$ such that ${S \subseteq \mathbb{Z}_{n}}$ and ??(i)?Ci ? ??(j)? j (mod n) for distinct ${i, j \in S}$ . We say ?? has deficit d if ${|S| = n - d}$ . Let ??(n, d) be the number of partial orthomorphisms of ${\mathbb{Z}_{n}}$ of deficit d. Let ??(n, d) be the number of partial orthomorphisms ?? of ${\mathbb{Z}_n}$ of deficit d such that ??(i) ? {0, i} for all ${i \in S}$ . Then ??(n, d) =???(n, d)n ²/d ² when ${1\,\leqslant\,d < n}$ . Let R _{k, n} be the number of reduced k ×?n Latin rectangles. We show that $$R_{k, n} \equiv \chi (p, n - p)\frac{(n - p)!(n - p - 1)!^{2}}{(n - k)!}R_{k-p,\,n-p}\,\,\,\,(\rm {mod}\,p)$$ when p is a prime and ${n\,\geqslant\,k\,\geqslant\,p + 1}$ . In particular, this enables us to calculate some previously unknown congruences for R _{n, n} . We also develop techniques for computing ??(n, d) exactly. We show that for each a there exists??? _a such that, on each congruence class modulo??? _a , ??(n, n-a) is determined by a polynomial of degree 2a in n. We give these polynomials for ${1\,\leqslant\,a\,\leqslant 6}$ , and find an asymptotic formula for ??(n, n-a) as n ?? ??, for arbitrary fixed a.     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.     

Signed total (k, k)-domatic number of digraphs

Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → {?1, 1} be a two-valued function. If k ≥?1 is an integer and ${\sum_{x \in N^-(v)}f(x) \ge k}$ for each ${v \in V(G)}$ , where N ^?(v) consists of all vertices of D from which arcs go into v, then f is a signed total k-dominating function on D. A set {f ₁, f ₂, . . . , f _d } of signed total k-dominating functions on D with the property that ${\sum_{i=1}^df_i(x)\le k}$ for each ${x \in V(D)}$ , is called a signed total (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed total (k, k)-dominating family on D is the signed total (k, k)-domatic number on D, denoted by ${d_{st}^{k}(D)}$ . In this paper we initiate the study of the signed total (k, k)-domatic number of digraphs, and we present different bounds on ${d_{st}^{k}(D)}$ . Some of our results are extensions of known properties of the signed total domatic number ${d_{st}(D)=d_{st}^{1}(D)}$ of digraphs D as well as the signed total domatic number d _st (G) of graphs G, given by Henning (Ars Combin. 79:277–288, 2006).     

Balanced Metrics and Chow Stability of Projective Bundles over Kähler Manifolds II

In the previous article (Seyyedali, Duke Math. J. 153(3):573–605, 2010), we proved that slope stability of a holomorphic vector bundle E over a polarized manifold (X,L) implies Chow stability of $(\mathbb{P}E^{*},\mathcal{O}_{\mathbb{P}E^{*}}(1)\otimes\pi^{*} L^{k})$ for k?0 if the base manifold has no nontrivial holomorphic vector field and admits a constant scalar curvature metric in the class of 2πc ₁(L). In this article, using asymptotic expansions of the Bergman kernel on Sym ^d E, we generalize the main theorem of Seyyedali (Duke Math. J. 153(3):573–605, 2010) to polarizations $(\mathbb{P}E^{*},\mathcal {O}_{\mathbb{P}E^{*}}(d)\otimes\pi^{*} L^{k})$ for k?0, where d is a positive integer.     

Structural and geometric characteristics of sets of convergence and divergence of multiple Fourier series with J k -lacunary sequence of rectangular partial sums

We study multiple trigonometric Fourier series of functions f in the classes $L_p \left( {\mathbb{T}^N } \right)$ , p > 1, which equal zero on some set $\mathfrak{A}, \mathfrak{A} \subset \mathbb{T}^N , \mu \mathfrak{A} > 0$ (µ is the Lebesgue measure), $\mathbb{T}^N = \left[ { - \pi ,\pi } \right]^N$ , N ≥ 3. We consider the case when rectangular partial sums of the indicated Fourier series S _n (x; f) have index n = (n ₁, ..., n _N ) ∈ ? ^N , in which k (k ≥ 1) components on the places {j ₁, ..., j _k } = J _k ? {1, ..., N} are elements of (single) lacunary sequences (i.e., we consider multiple Fourier series with J _k -lacunary sequence of partial sums). A correlation is found of the number k and location (the “sample” J _k ) of lacunary sequences in the index n with the structural and geometric characteristics of the set $\mathfrak{A}$ , which determines possibility of convergence almost everywhere of the considered series on some subset of positive measure $\mathfrak{A}_1$ of the set $\mathfrak{A}$ .     

Certain additive maps on m-power closed Lie ideals

Let R be a prime ring with extended centroid C and m a fixed positive integer >?1. A Lie ideal L of R is called m-power closed if ${u^m \in L}$ for all ${u \in L}$ . We prove that if char R = 0 or a prime p?>?m, then every non-central, m-power closed Lie ideal L of R contains a nonzero ideal of R except when dim _C RC?=?4, m is odd, and ${u^{m-1} \in C}$ for all ${u \in L}$ . Moreover, the additive maps d : L ?? R satisfying d(u ^m )?=?mu ^m-1 d(u) (resp. d(u ^m )?=?u ^m-1 d(u)) for all ${u \in L}$ are completely characterized if char R = 0 or a prime p?>?2(m ? 1).     

On the distribution of integer random variables related by a certain linear inequality: III

We consider tuples {N _jk }, j = 1, 2, ..., k = 1, ..., q _j , of nonnegative integers such that $$ \sum\limits_{j = 1}^\infty {\sum\limits_{k = 1}^{q_j } {jN_{jk} } } \leqslant M. $$ Assuming that q _j ～ j ^d?1, 1 < d < 2, we study how the probabilities of deviations of the sums $ \sum\nolimits_{j = j_1 }^{j_2 } {\sum\nolimits_{k = 1}^{q_j } {N_{jk} } } $ N _jk from the corresponding integrals of the Bose-Einstein distribution depend on the choice of the interval [j ₁,j ₂].     

On the Schröder equation and iterative sequences of C r diffeomorphisms in {\mathbb{R}^{N}} space

Let ${U \subset \mathbb{R}^{N}}$ be a neighbourhood of the origin and a function ${F:U\rightarrow U}$ be of class C ^r , r ≥ 2, F(0) = 0. Denote by F ⁿ the n-th iterate of F and let ${0<|s_1|\leq \cdots \leq|s_N| <1 }$ , where ${s_1, \ldots , s_N}$ are the eigenvalues of dF(0). Assume that the Schröder equation ${\varphi(F(x))=S\varphi(x)}$ , where S: = dF(0) has a C ² solution φ such that dφ(0) = id. If ${\frac{log|s_1|}{log|s_N|} <2 }$ then the sequence {S ^?n F ⁿ (x)} converges for every point x from the basin of attraction of F to a C ² solution φ of (1). If ${2\leq\frac{log|s_1|}{log|s_N|} }$ then this sequence can be diverging. In this case we give some sufficient conditions for the convergence and divergence of the sequence {S ^?n F ⁿ (x)}. Moreover, we show that if F is of class C ^r and ${r>\big[\frac{log|s_1|}{log|s_N|} \big ]:=p \geq 2}$ then every C ^r solution of the Schröder equation such that dφ(0) = id is given by the formula $$\begin{array}{ll}\varphi (x)={\lim\limits_{n \rightarrow \infty}} (S^{-n}F^n(x) + {\sum\limits _{k=2}^{p}} S^{-n}L_k (F^n(x))),\end{array}$$ where ${L_k:\mathbb{R}^{N} \rightarrow \mathbb{R}^{N}}$ are some homogeneous polynomials of degree k, which are determined by the differentials d ^(j) F(0) for 1 < j ≤  p.     

The {k}-domatic number of a graph

For a positive integer k, a {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0, 1, 2, . . . , k} such that for any vertex ${v\in V(G)}$ , the condition ${\sum_{u\in N[v]}f(u)\ge k}$ is fulfilled, where N[v] is the closed neighborhood of v. A {1}-dominating function is the same as ordinary domination. A set {f ₁, f ₂, . . . , f _d } of {k}-dominating functions on G with the property that ${\sum_{i=1}^df_i(v)\le k}$ for each ${v\in V(G)}$ , is called a {k}-dominating family (of functions) on G. The maximum number of functions in a {k}-dominating family on G is the {k}-domatic number of G, denoted by d _{k}(G). Note that d _{1}(G) is the classical domatic number d(G). In this paper we initiate the study of the {k}-domatic number in graphs and we present some bounds for d _{k}(G). Many of the known bounds of d(G) are immediate consequences of our results.     

On the second eigenvalue and random walks in randomd-regular graphs

The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, λ₂, of (the adjacency matrix of) a randomd-regular graph,G. In order to do so, we study the probability that a random walk on a random graph returns to its originating vertex at thek-th step, for various values ofk. Our main theorem about eigenvalues is that $$E|\lambda _2 (G)|^m \leqslant \left( {2\sqrt {2d - 1} \left( {1 + \frac{{\log d}}{{\sqrt {2d} }} + 0\left( {\frac{1}{{\sqrt d }}} \right)} \right) + 0\left( {\frac{{d^{3/2} \log \log n}}{{\log n}}} \right)} \right)^m $$ for any \(m \leqslant 2\left\lfloor {log n\left\lfloor {\sqrt {2d - } 1/2} \right\rfloor /\log d} \right\rfloor \) , where E denotes the expected value over a certain probability space of 2d-regular graphs. It follows, for example, that for fixedd the second eigenvalue's magnitude is no more than \(2\sqrt {2d - 1} + 2\log d + C'\) with probability 1?n ^?C for constantsC andC′ for sufficiently largen.     

Generalized monotone approximation inL p Space

Letf(x) ∈L _p[0,1], 1?p? ∞. We shall say that functionf(x)∈Δ^k (integerk?1) if for anyh ∈ [0, 1/k] andx ∈ [0,1?kh], we have Δ _h ^k f(x)?0. Denote by ∏ _n the space of algebraic polynomials of degree not exceedingn and define $$E_{n,k} (f)_p : = \mathop {\inf }\limits_{\mathop {P_n \in \prod _n }\limits_{P_n^{(\lambda )} \geqslant 0} } \parallel f(x) - P_n (x)\parallel _{L_p [0,1]} .$$ We prove that for any positive integerk, iff(x) ∈ Δ ^k ∩ L _p[0, 1], 1?p?∞, then we have $$E_{n,k} (f)_p \leqslant C\omega _2 \left( {f,\frac{1}{n}} \right)_p ,$$ whereC is a constant only depending onk.     

An extremal problem for algebraic polynomials in the symmetric discrete Gegenbauer-Sobolev space

We study discrete Sobolev spaces with symmetric inner product $$\left\langle {f,g} \right\rangle _\alpha = \int_{ - 1}^1 {f g d\mu _\alpha } + M[f(1)g(1) + f( - 1)g( - 1)] + K[f'(1)g'(1) + f'( - 1)g'( - 1)]$$ , where M ≥ 0, k ≥ 0, and $$d\mu _\alpha (x) = \frac{{\Gamma (2\alpha + 2)}}{{2^{2\alpha + 1} \Gamma ^2 (\alpha + 1)}}(1 - x^2 )^\alpha dx, \alpha > - 1$$ , is the Gegenbauer probability measure. We obtain the solution of the following extremal problem: Calculate $$\mathop {\inf }\limits_{a_0 ,a_1 ,...,a_{N - r} } \left\{ {\langle P_N^{(r)} ,P_N^{(r)} \rangle _\alpha ,1 \leqslant r \leqslant N - 1, P_N^{(r)} (x) = \sum\limits_{j = N - r + 1}^N {a_j^0 x^j } + \sum\limits_{j = 0}^{N - r} {a_j x^j } } \right\}$$ , where the a _j ⁰ , j = N ? r + 1, N ? r + 2, ..., N ? 1, N, a _N ⁰ > 0, are fixed numbers, and find the extremal polynomial.     

Deviation of best discrete and uniform polynomial approximants

ПустьC _2π — пространств о 2π-периодических вещественных непрер ывных функций, W{_rLip α={f∈C _2π ^r : ω(f ^(r), δ)≦δ^α}, Y?[?π,π] — некоторое дискр етное множество точе к на периоде, плотность ко торого задается соот ношением ?(Y)= max min ¦x-у¦. Дляf∈C_2π x∈[?π,π] y∈Y обозначим через p_k(f) p_k(f)_y т ригонометрические полиномы степени не в ышеk наилучшего чебышевского прибли жения функцииf на все м периоде и на дискретном множес тве Y соответственно. Тогда величина $$\Omega _{k,r + \alpha } (d) = \mathop {\sup }\limits_{f \in W_r Lip\alpha } \mathop {\sup }\limits_{\mathop {Y \subset [ - \pi ,\pi ]}\limits_{\rho (Y) \leqq d} } \left\| {p_k (f) - p_k (f)_Y } \right\| (d > 0)$$ xарактеризует отклон ение наилучших равно мерных и дискретных чебышевс ких приближений равномерно на классе функций W_rLip а. В работе да ются точные оценки для ?_k,r+α(d) пр и всехk, r и 0-?1.     

On Riemann sums and Lebesgue integrals

Call a sequence of positive integers(m _k ) _k=1 ^∞ a chain ifm _k devidesm _k+1 and that it has dimensiond if it is a subset of the set of least common multiples ofd chains. In this paper we give a new and elementary proof that iff∈L(logL)^d?1([0, 1)) and(m _k ) _k=1 ^∞ is of dimensiond then $$\mathop {\lim }\limits_{N \to \infty } \frac{1}{N}\sum\limits_{n = 1}^N {f\left( {\left\{ {x + \frac{n}{{m_N }}} \right\}} \right)} = \int_X {fd\mu , a.e.,} $$ with respect to Lebesgue measure. This result was first proved byL. Dubins andJ. Pitman [2] using martingale theory.     

Empty Monochromatic Simplices

Let S be a k-colored (finite) set of n points in $\mathbb{R}^{d}$ , d≥3, in general position, that is, no (d+1) points of S lie in a common (d?1)-dimensional hyperplane. We count the number of empty monochromatic d-simplices determined by S, that is, simplices which have only points from one color class of S as vertices and no points of S in their interior. For 3≤k≤d we provide a lower bound of $\varOmega(n^{d-k+1+2^{-d}})$ and strengthen this to Ω(n ^d?2/3) for k=2. On the way we provide various results on triangulations of point sets in  $\mathbb{R}^{d}$ . In particular, for any constant dimension d≥3, we prove that every set of n points (n sufficiently large), in general position in $\mathbb{R}^{d}$ , admits a triangulation with at least dn+Ω(logn) simplices.     

Mixing via the extended family

In this paper,the relationship between the extended family and several mixing properties in measuretheoretical dynamical systems is investigated.The extended family eF related to a given family F can be regarded as the collection of all sets obtained as"piecewise shifted"members of F.For a measure preserving transformation T on a Lebesgue space(X,B,μ),the sets of"accurate intersections of order k"defined below are studied,Nε(A0,A1,...,Ak)=n∈Z+:μk i=0T inAiμ(A0)μ(A1)μ(Ak)ε,for k∈N,A0,A1,...,Ak∈B and ε0.It is shown that if T is weakly mixing(mildly mixing)then for any k∈N,all the sets Nε(A0,A1,...,Ak)have Banach density 1(are in(eFip),i.e.,the dual of the extended family related to IP-sets).     

Limiting Spectral Distribution of Random k-Circulants

Consider random k-circulants A _k,n with n????,k=k(n) and whose input sequence {a _l } _l??0 is independent with mean zero and variance one and $\sup_{n}n^{-1}\sum_{l=1}^{n}\mathbb{E}|a_{l}|^{2+\delta}<\infty$ for some ??>0. Under suitable restrictions on the sequence {k(n)} _n??1, we show that the limiting spectral distribution (LSD) of the empirical distribution of suitably scaled eigenvalues exists, and we identify the limits. In particular, we prove the following: Suppose g??1 is fixed and p ₁ is the smallest prime divisor of g. Suppose $P_{g}=\prod_{j=1}^{g}E_{j}$ where {E _j }_1??j??g are i.i.d. exponential random variables with mean one. (i) If k ^g =?1+sn where s=1 if g=1 and $s=o(n^{p_{1}-1})$ if g>1, then the empirical spectral distribution of n ^?1/2 A _k,n converges weakly in probability to $U_{1}P_{g}^{1/(2g)}$ where U ₁ is uniformly distributed over the (2g)th roots of unity, independent of P _g . (ii) If g??2 and k ^g =1+sn with $s=o(n^{p_{1}-1})$ , then the empirical spectral distribution of n ^?1/2 A _k,n converges weakly in probability to $U_{2}P_{g}^{1/(2g)}$ where U ₂ is uniformly distributed over the unit circle in ?², independent of P _g . On the other hand, if k??2, k=n ^o(1) with gcd?(n,k)=1, and the input is i.i.d. standard normal variables, then $F_{n^{-1/2}A_{k,n}}$ converges weakly in probability to the uniform distribution over the circle with center at (0,0) and radius $r=\exp(\mathbb{E}[\log\sqrt{E}_{1}])$ .     

Binomial coefficients, Catalan numbers and Lucas quotients

Let p be an odd prime and let a,m ∈ Z with a 0 and p ︱ m.In this paper we determinep ∑k=0 pa-1(2k k=d)/mk mod p2 for d=0,1;for example,where(-) is the Jacobi symbol and {un}n≥0 is the Lucas sequence given by u0 = 0,u1 = 1 and un+1 =(m-2)un-un-1(n = 1,2,3,...).As an application,we determine ∑0kpa,k≡r(mod p-1) Ck modulo p2 for any integer r,where Ck denotes the Catalan number 2kk /(k + 1).We also pose some related conjectures.