On fair coin-tossing games

Let Ω be a finite set with k elements and for each integer $\text{n ≧ 1}$ let $\text{Ω}{}_{\mathrm{n}}\text{= Ω × Ω × … × Ω}$ (n-tuple) and $\text{Ω}{}_{\mathrm{n}}\text{= {(a}{}_1\text{, a}{}_2\text{,…, a}{}_{\mathrm{n}}\text{) | (a}{}_1\text{, a}{}_2\text{,…, a}{}_{\mathrm{n}}\text{) ∈ Ω}{}_{\mathrm{n}}$ and a_j ≠ a_j+1 for some 1 ≦ j ≦ n ? 1}. Let {Y_m} be a sequence of independent and identically distributed random variables such that P(Y₁ = a) = k^?1 for all a in Ω. In this paper, we obtain some very surprising and interesting results about the first occurrence of elements in $\text{Ω}{}_{\mathrm{n}}$ and in Ω?_n with respect to the stochastic process {Y_m}. The results here provide us with a better and deeper understanding of the fair coin-tossing (k-sided) process.     

Coding theory in white Gaussian channel with feedback

The message m = {m(t)} is a Gaussian process that is to be transmitted through the white Gaussian channel with feedback: $\text{Y(t) = ∫}{}_0{}^{\mathrm{t}}\text{F(s, Y}{}_0{}^{\mathrm{s}}\text{, m)ds + W(t)}$. Under the average power constraint, $\text{E[F}{}^2\text{(s, Y}{}_0{}^{\mathrm{s}}\text{, m)] ≤ P}{}_0$, we construct causally the optimal coding, in the sense that the mutual information I_t(m, Y) between the message m and the channel output Y (up to t) is maximized. The optimal coding is presented by $\text{Y(t) = ∫}{}_0{}^{\mathrm{t}}\text{A(s)[m(s) ?}\text{m}\text{?}\text{(s)] ds + W(t)}$, where $\text{m}\text{?}\text{(s) = E[m(s) ¦ Y(u), 0 ≤ u ≤ s]}$ and A(s) is a positive function such that $\text{A}{}^2\text{(s) E |m(s) ?}\text{m}\text{?}\text{(s)|}{}^2\text{= P}{}_0$.     

Factorization of fredholm operators on analytic functions

Let Ω be a simply connected domain in the complex plane, and $\text{A(Ω}{}^{\mathrm{n}}\text{)}$, the space of functions which are defined and analytic on $\text{Ω}{}^{\mathrm{n}}$, if K is the operator on elements $\text{u(t, a}{}_1\text{, …, a}{}_{\mathrm{n}}\text{)}\text{of}\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of the kernels k_i(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by is the identity operator on $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$, then the operator I ? K may be factored in the form (I ? K)(M ? W) = (I ? ΠK)(M ? ΠW). Here, W is an operator on $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of a kernel w(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by Wu = ∝_an^tw(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠW is the operator; ΠWu = ∝_{an ? 1}w(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠK is the operator; ΠKu = ∑_{i = 1}^{n ? 1} ∝_ai^tk_i(t, s, a₁, …, a_n) ds + ∝_{an ? 1}^tk_n(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. The operator M is of the form m(t, a₁, …, a_n)I, where $\text{m ? A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ and maps elements of $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ into itself by multiplication. The function m is uniquely derived from K in the following manner. The operator K defines an operator $\text{K}{}^1$ on functions u in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$, by . A determinant $\text{δ(I ? K}{}^1\text{)}$ of the operator $\text{I ? K}{}^1$ is defined as an element $\text{m}{}^1\text{(t, a}{}_1\text{, …, a}{}_{\mathrm{n\; +\; 1}}\text{)}$ of $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$. This is mapped into $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ by setting a_{n + 1} = t to give m(t, a₁, …, a_n). The operator I ? ΠK may be factored in similar fashion, giving rise to a chain factorization of I ? K. In some cases all the matrix kernels k_i defining K are separable in the sense that k_i(t, s, a₁, …, a_n) = P_i(t, a₁, …, a_n) Q_i(s, a₁, …, a_n), where P_i is a 1 × p_i matrix and Q_i is a p_i × 1 matrix, each with elements in $\text{A(Ω}{}_{\mathrm{n\; +\; 1}}\text{)}$, explicit formulas are given for the kernels of the factors W. The various results are stated in a form allowing immediate extension to the vector-matrix case.     

The probability that k positive integers are relatively r-prime

If r, k are positive integers, then $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ denotes the number of k-tuples of positive integers (x₁, x₂, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r = 1. An explicit formula for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}$ is derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(n)}\text{n}{}^{\mathrm{k}}\text{=}\text{1}\text{ζ(rk)}$.If S = {p₁, p₂, …, p_a} is a finite set of primes, then 〈S〉 = {p₁^a₁p₂^a₂…p_s^a_s; p_i ∈ S and a_i ≥ 0 for all i} and $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ denotes the number of k-tuples (x₁, x₃, …, x_k) with 1 ≤ x_i ≤ n and (x₁, x₂, …, x_k)_r ∈ 〈S〉. Asymptotic formulas for $\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}$ are derived and it is shown that $\text{lim}{}_{\mathrm{n\to \infty }}\text{T}{}_{\mathrm{k}}{}^{\mathrm{r}}\text{(S, n)}\text{n}{}^{\mathrm{k}}\text{=}\text{(p}{}_1\text{… p}{}_{\mathrm{a}}\text{)}{}^{\mathrm{rk}}\text{ζ(rk)(p}{}_1{}^{\mathrm{rk}}\text{? 1) … (p}{}_{\mathrm{s}}{}^{\mathrm{rk}}\text{? 1)}$.     

Strong law for the bootstrap

Let X₁, X₂, X₃, … be i.i.d. r.v. with E|X₁| < ∞, E X₁ = μ. Given a realization X = (X₁,X₂,…) and integers n and m, construct Y_n,i, i = 1, 2, …, m as i.i.d. r.v. with conditional distribution $\text{P}{}^1\text{(Y}{}_{\mathrm{n,i}}\text{= X}{}_{\mathrm{j}}\text{) =}\text{1}\text{n}$ for 1 ? j ? n. ($\text{P}{}^1$ denotes conditional distribution given X). Conditions relating the growth rate of m with n and the moments of X₁ are given to ensure the almost sure convergence of $\text{(}\text{1}\text{m}\text{)Σ}{}^{\mathrm{m}}{}_{\mathrm{i=1}}\text{Y}{}_{\mathrm{n,i}}$ toμ. This equation is of some relevance in the theory of Bootstrap as developed by Efron (1979) and Bickel and Freedman (1981).     

Extension de quelques theoremes sur les densites de series d'elements de n a des series de sous-ensembles finis de n

For a sequence A = {A_k} of finite subsets of N we introduce: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{n}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$, where A(m) is the number of subsets A_k ? {1, 2, …, m}.The collection of all subsets of {1, …, n} together with the operation $\text{a ∪ b, (a ∩ b), (a 1 b = a ∪ b ? a ∩ b)}$ constitutes a finite semi-group N^∪ (semi-group N^∩) (group $\text{N}{}^1$). For N^∪, N^∩ we prove analogues of the Erdös-Landau theorem: δ(A+B) ? δ(A)(1+(2λ)^?1(1?δ(A>))), where B is a base of N of the average order λ. We prove for $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ analogues of Schnirelmann's theorem (that δ(A) + δ(B) > 1 implies δ(A + B) = 1) and the inequalities λ ? 2h, where h is the order of the base.We introduce the concept of divisibility of subsets: a|b if b is a continuation of a. We prove an analog of the Davenport-Erdös theorem: if d(A) > 0, then there exists an infinite sequence {A_kr}, where A_kr | A_kr+1 for r = 1, 2, …. In Section 6 we consider for $\text{N∪, N∩, N1}$ analogues of Rohrbach inequality: $\text{2n}\text{? g(n) ? 2}\text{n}$, where g(n) = min k over the subsets {a₁ < … < a_k} ? {0, 1, 2, …, n}, such that every m? {0, 1, 2, …, n} can be expressed as m = a_i + a_j.Pour une série A = {A_k} de sous-ensembles finis de N on introduit les densités: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{m}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$ où A(m) est le nombre d'ensembles A_k ? {1, 2, …, m}. L'ensemble de toutes les parties de {1, 2, …, n} devient, pour les opérations $\text{a ∪ b, a ∩ b, a 1 b = a ∪ b ? a ∩ b}$, un semi-groupe fini N^∪, N^∩ ou un groupe N¹ respectivement. Pour N^∪, N^∩ on démontre l'analogue du théorème de Erdös-Landau: δ(A + B) ? δ(A)(1 + (2λ)^?1(1?δ(A))), où B est une base de N d'ordre moyen λ. On démontre pour $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ l'analogue du théorème de Schnirelmann (si δ(A) + δ(B) > 1, alors δ(A + B) = 1) et les inégalités λ ? 2h, où h est l'ordre de base. On introduit le rapport de divisibilité des enembles: a|b, si b est une continuation de a. On démontre l'analogue du théorème de Davenport-Erdös: si d(A) > 0, alors il existe une sous-série infinie {A_kr}, où A_kr|A_kr+1, pour r = 1, 2, … . Dans le Paragraphe 6 on envisage pour N^∪, $\text{N}{}^{\mathrm{\cap }}\text{, N}{}^1$ les analogues de l'inégalité de Rohrbach: $\text{2n}\text{? g(n) ? 2}\text{n}$, où g(n) = min k pour les ensembles {a₁ < … < a_k} ? {0, 1, 2, …, n} tels que pour tout m? {0, 1, 2, …, n} on a m = a_i + a_j.     

How small are the increments of a Wiener process?

Let $\text{γ}{}_{\mathrm{т}}\text{=(8(}\text{logTa}{}^{-1}{}_{\mathrm{T}}\text{+log log T)}\text{π}{}^2\text{a}{}_{\mathrm{T}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, 0<a_T?T<∞, and {W(t);0?t<∞} be a standard Wiener process. This exposition studies the almost sure behaviour of

, under varying conditions on a_T and T/a_T. The following analogue of Lévy's modulus of continuity of a Wiener Process is also given:

$\text{lim}{}_{\mathrm{h\to 0}}\text{inf}{}_{\mathrm{0?t?1}}\text{sup}{}_{\mathrm{0?s?h}}\text{(}\text{8 log h}{}^{-1}\text{π}{}^2\text{h}\text{)}\text{1}\text{2}\text{|W(t+s)?W(t)| =}{}^{\mathrm{a.s.}}\text{1.}$

and this may be viewed as the exact “modulus of non-differentiability” of a Wiener Process.     

On majorization and Schur products

Suppose A, D₁,…,D_m are n × n matrices where A is self-adjoint, and let $\text{X = Σ}{}^{\mathrm{m}}{}_{\mathrm{k\; =\; 1}}\text{D}{}_{\mathrm{k}}\text{AD}{}^1{}_{\mathrm{k}}$. It is shown that if $\text{ΣD}{}_{\mathrm{k}}\text{D}{}^1{}_{\mathrm{k}}\text{= ΣD}{}^1{}_{\mathrm{k}}\text{D}{}_{\mathrm{k}}\text{= I}$, then the spectrum of X is majorized by the spectrum of A. In general, without assuming any condition on D₁,…,D_m, a result is obtained in terms of weak majorization. If each D_k is a diagonal matrix, then X is equal to the Schur (entrywise) product of A with a positive semidefinite matrix. Thus the results are applicable to spectra of Schur products of positive semidefinite matrices. If A, B are self-adjoint with B positive semidefinite and if b_ii = 1 for each i, it follows that the spectrum of the Schur product of A and B is majorized by that of A. A stronger version of a conjecture due to Marshall and Olkin is also proved.     

Duality in hypercomplex function theory

Let $\text{A}$ be the Clifford algebra constructed over a quadratic n-dimensional real vector space with orthogonal basis {e₁,…, e_n}, and e₀ be the identity of $\text{A}$. Furthermore, let M_k(Ω;$\text{A}$) be the set of $\text{A}$-valued functions defined in an open subset Ω of R^m+1 (1 ? m ? n) which satisfy D^kf = 0 in Ω, where D is the generalized Cauchy-Riemann operator $\text{D = ∑}{}_{\mathrm{i\; =\; 0}}{}^{\mathrm{m}}\text{e}{}_{\mathrm{i}}\text{(}\text{?}\text{?x}{}_{\mathrm{i}}\text{)}$ and k? N. The aim of this paper is to characterize the dual and bidual of M_k(Ω;$\text{A}$). It is proved that, if M_k(Ω;$\text{A}$) is provided with the topology of uniform compact convergence, then its strong dual is topologically isomorphic to an inductive limit space of Fréchet modules, which in its turn admits M_k(Ω;$\text{A}$) as its dual. In this way, classical results about the spaces of holomorphic functions and analytic functionals are generalized.     

On a conjecture by D. Ž. D̄okovic

It is shown that if $\text{A?Ω}{}_{\mathrm{n}}\text{?{J}{}_{\mathrm{n}}\text{}}$ satisfies

$\text{nkσ}{}_{\mathrm{k}}\text{(A)?(n?k+1)}{}^2\text{σ}{}_{\mathrm{k?1}}\text{(A)}$

$\text{(k=1,2,…,n)}$

, where σ_k(A) denotes the sum of all kth order subpermanent of A, then Per[λJ_n+(1?λ)A] is strictly decreasing in the interval 0<λ<1.     

On the closability of some positive definite symmetric differential forms on c0∞(ω)

Let $\text{S}$ be a Dirichlet form in $\text{L}{}^2\text{(Ω; m)}$, where Ω is an open subset of $\text{R}$ⁿ, n ? 2, and m a Radon measure on Ω; for each integer k with 1 ? k < n, let $\text{S}$_k be a Dirichlet form on some k-dimensional submanifold $\text{Ω}{}_{\mathrm{k}}$ of Ω. The paper is devoted to the study of the closability of the forms E with domain $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ and defined by: $\text{(?,g)=}$$\text{E}$$\text{(?, g)+}\text{∑}\text{i}\text{p}\text{=1}$$\text{E}$k_i where 1 ? k_p < ? < n, and where , g^k_i denote restrictions of ?, g in $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ to . Conditions are given for E to be closable if, for each i = 1,…, p, one has k_i = n ? i. Other conditions are given for E to be nonclosable if, for some i, k_i < n ? i.     

Enumeration of pairs of permutations

Let π = (a₁, a₂, …, a_n), ? = (b₁, b₂, …, b_n) be two permutations of $\text{Z}{}_{\mathrm{n}}\text{= {1, 2, …, n}}$. A rise of π is pair a_i, a_i+1 with a_i < a_i+1; a fall is a pair a_i, a_i+1 with a_i > a_i+1. Thus, for i = 1, 2, …, n ? 1, the two pairs a_i, a_i+1; b_i, b_i+1 are either both rises, both falls, the first a rise and the second a fall or the first a fall and the second a rise. These possibilities are denoted by RR, FF, RF, FR. The paper is concerned with the enumeration of pairs π, p with a given number of RR, FF, RF, FR. In particular if ω_n denotes the number of pairs with RR forbidden, it is proved that $\text{∑}{}^{\mathrm{\infty }}{}_0\text{ω}{}_{\mathrm{n}}\text{z}{}^{\mathrm{n}}\text{n!n!}\text{=}\text{1}\text{?(z)}$, $\text{?(z) = ∑}{}^{\mathrm{\infty }}{}_0\text{(-1)}{}^{\mathrm{n}}\text{z}{}^{\mathrm{n}}\text{n!n!}$. More precisely if ω(n, k) denotes the number of pairs π, p with exactly k occurences of RR(or FF, RF, FR) then $\text{1 + ∑}{}^{\mathrm{\infty }}{}_{\mathrm{n=1}}\text{z}{}^{\mathrm{n}}\text{n!n!}$$\text{∑}{}^{\mathrm{n?1}}{}_{\mathrm{k=0}}\text{ω(n, k)x}{}^{\mathrm{k}}\text{=}\text{(1 ? x)}\text{(?(z(1 ? x)) ? x)}$.     

The minimal generating space of a polynomial

Given a polynomial $\text{P(X}{}_1\text{,…,X}{}_{\mathrm{N}}\text{)∈}\text{R}\text{[}\text{X}\text{]}$, we calculate a subspace G_p of the linear space 〈X〉 generated by the indeterminates which is minimal with respect to the property $\text{P∈}\text{R}\text{[}\text{G}{}_{\mathrm{p}}\text{]}$ (the algebra generated by G_p, and prove its uniqueness. Furthermore, we use this result to characterize the pairs (P,Q) of polynomials P(X₁,…,X_n) and Q(X₁,…,X_n) for which there exists an isomorphism T:〈X〉 →〈X〉 that “separates P from Q,” i.e., such that for some k(1<k<n) we can write P and Q as $\text{P}{}^1\text{(Y}{}_1\text{,…,Y}{}_{\mathrm{k}}\text{)}$ and $\text{Q}{}^1\text{(Y}{}_{\mathrm{<mtext>k+</mtext><mtext>1</mtext>}}\text{,…,Y}{}_{\mathrm{n}}\text{)}$ respectively, where $\text{Y}\text{=T}\text{X}$.     

Inverse Hölder inequalities in one and several dimensions

We study certain functionals and obtain an inverse Hölder inequality for n functions f₁^a1,…,f_n^an (f_k concave, 1 dimension).We also prove a multidimensional inverse Hölder inequality for n functions f₁,…,f_n, where $\text{?}{}^2\text{f}{}_{\mathrm{k}}\text{?x}{}_{\mathrm{i}}{}^2\text{? 0, i = 1,…, d, k = 1,…, n}$.Finally we give an inverse Minkowski inequality for concave functions.     

The asymptotic eigenvalue-distribution for a certain class of random matrices

For an n × n Hermitean matrix A with eigenvalues λ₁, …, λ_n the eigenvalue-distribution is defined by $\text{G(x, A) :=}\text{1}\text{n}$ · number {λ_i: λ_i ? x} for all real x. Let A_n for n = 1, 2, … be an n × n matrix, whose entries a_ik are for i, k = 1, …, n independent complex random variables on a probability space (Ω, $\text{R}$, p) with the same distribution F_a. Suppose that all moments $\text{E}$ | a | ^k, k = 1, 2, … are finite, $\text{E}$a=0 and $\text{E}$ | a | ². Let

$\text{M(A)=}\text{∑}\text{σ=1}\text{s}\text{θ}{}_{\mathrm{\sigma }}\text{P}{}_{\mathrm{\sigma }}\text{(A,A}{}^1\text{)}$

with complex numbers θ_σ and finite products P_σ of factors A and $\text{A}{}^1$ (= Hermitean conjugate) be a function which assigns to each matrix A an Hermitean matrix M(A). The following limit theorem is proved: There exists a distribution function G₀(x) = G₁x) + G₂(x), where G₁ is a step function and G₂ is absolutely continuous, such that with probability $\text{1 G(x, M(}\text{A}{}_{\mathrm{n}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{))}$ converges to G₀(x) as n → ∞ for all continuity points x of G₀. The density g of G₂ vanishes outside a finite interval. There are only finitely many jumps of G₁. Both, G₁ and G₂, can explicitly be expressed by means of a certain algebraic function f, which is determined by equations, which can easily be derived from the special form of M(A). This result is analogous to Wigner's semicircle theorem for symmetric random matrices (E. P. Wigner, Random matrices in physics, SIAM Review9 (1967), 1–23). The examples $\text{A}{}_{\mathrm{r}}\text{A}{}^{\mathrm{1r}}$, $\text{A}{}^{\mathrm{r}}\text{+ A}{}^{\mathrm{1r}}$, $\text{A}{}^{\mathrm{r}}\text{A}{}^{\mathrm{1r}}\text{± A}{}^{\mathrm{1r}}\text{A}{}^{\mathrm{r}}$, r = 1, 2, …, are discussed in more detail. Some inequalities for random matrices are derived. It turns out that with probability 1 the sharpened form

$\text{lim sup}\text{n→∞}\text{∑}\text{i=1}{}^{\mathrm{n}}\text{|γ}{}_{\mathrm{i}}{}^{\mathrm{(n)}}\text{|}{}^2\text{?6A}{}_{\mathrm{n}}\text{6}{}^2\text{? 0.8228…}$

of Schur's inequality for the eigenvalues λ_i⁽ⁿ⁾ of A_n holds. Consequently random matrices do not tend to be normal matrices for large n.     

On exponential bases for the Sobolev spaces over an interval

We suppose that K is a countable index set and that $\text{Λ = {λ}{}_{\mathrm{k}}\text{¦ k ? K}}$ is a sequence of distinct complex numbers such that forms a Riesz (strong) basis for L²[a, b], a < b. Let Σ = {σ₁, σ₂,…, σ_m} consist of m complex numbers not in Λ. Then, with p(λ) = Π_{k = 1}^m (λ ? σ_k), forms a Riesz (strong) bas Sobolev space H^m[a, b]. If we take σ₁, σ₂,…, σ_m to be complex numbers already in Λ, then, defining p(λ) as before, forms a Riesz (strong) basis for the space H^?m[a, b]. We also discuss the extension of these results to “generalized exponentials” tⁿe^λ_kt.