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.     

Limiting distributions of two random sequences

For fixed p (0 ≤ p ≤ 1), let {L₀, R₀} = {0, 1} and X₁ be a uniform random variable over {L₀, R₀}. With probability p let {L₁, R₁} = {L₀, X₁} or = {X₁, R₀} according as $\text{X}{}_1\text{≥}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}$; with probability 1 ? p let {L₁, R₁} = {X₁, R₀} or = {L₀, X₁} according as $\text{X}{}_1\text{≥}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}$, and let X₂ be a uniform random variable over {L₁, R₁}. For n ≥ 2, with probability p let {L_n, R_n} = {L_{n ? 1}, X_n} or = {X_n, R_{n ? 1}} according as $\text{X}{}_{\mathrm{n}}\text{≥}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}$, with probability 1 ? p let {L_n, R_n} = {X_n, R_{n ? 1}} or = {L_{n ? 1}, X_n} according as $\text{X}{}_{\mathrm{n}}\text{≥}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}$, and let X_{n + 1} be a uniform random variable over {L_n, R_n}. By this iterated procedure, a random sequence {X_n}_{n ≥ 1} is constructed, and it is easy to see that X_n converges to a random variable Y_p (say) almost surely as n → ∞. Then what is the distribution of Y_p? It is shown that the Beta, (2, 2) distribution is the distribution of Y₁; that is, the probability density function of Y₁ is g(y) = 6y(1 ? y) I_0,1(y). It is also shown that the distribution of Y₀ is not a known distribution but has some interesting properties (convexity and differentiability).     

On the fair coin tossing process

Let Ω = {1, 0} and for each integer n ≥ 1 let $\text{Ω}{}_{\mathrm{n}}\text{= Ω × Ω × … × Ω}$ (n-tuple) and $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}\text{= {(a}{}_1\text{, a}{}_2\text{, …, a}{}_{\mathrm{n}}\text{)|(a}{}_1\text{, a}{}_2\text{, … , a}{}_{\mathrm{n}}\text{) ? Ω}{}_{\mathrm{n}}\text{and}\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{a}{}_{\mathrm{i}}\text{= k}}$ for all k = 0,1,…,n. Let {Y_m}_m≥1 be a sequence of i.i.d. random variables such that $\text{P(Y}{}_1\text{= 0) = P(Y}{}_1\text{= 1) =}\text{1}\text{2}$. For each A in $\text{Ω}{}_{\mathrm{n}}$, let T_A be the first occurrence time of A with respect to the stochastic process {Y_m}_m≥1. R. Chen and A.Zame (1979, J. Multivariate Anal. 9, 150–157) prove that if n ≥ 3, then for each element A in $\text{Ω}{}_{\mathrm{n}}$, there is an element B in $\text{Ω}{}_{\mathrm{n}}$ such that the probability that T_B is less than T_A is greater than $\text{1}\text{2}$. This result is sharpened as follows: (I) for n ≥ 4 and 1 ≤ k ≤ n ? 1, each element A in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$, there is an element B also in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$ such that the probability that T_B is less than T_A is greater than $\text{1}\text{2}$; (II) for n ≥ 4 and 1 ≤ k ≤ n ? 1, each element A = (a₁, a₂,…,a_n) in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$, there is an element C also in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$ such that the probability that T_A is less than T_C is greater than $\text{1}\text{2}$ if n ≠ 2m or n = 2m but a_i = a_{i + 1} for some 1 ≤ i ≤ n?1. These new results provide us with a better and deeper understanding of the fair coin tossing process.     

Limit laws for record values

{X_n,n?1} are i.i.d. random variables with continuous d.f. F(x). X_j is a record value of this sequence if X_j>max{X₁,…,X_j?1}. Consider the sequence of such record values {X_Ln,n?1}. Set R(x)=-log(1?F(x)). There exist B_n > 0 such that . in probability (i.p.) iff i.p. iff $\text{{R(kx)?R(x)}}\text{R}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(kx)}$ → ∞ as x→∞ for all k>1. Similar criteria hold for the existence of constants A_n such that X_Ln?A_n → 0 i.p. Limiting record value distributions are of the form N(-log(-logG(x))) where G(·) is an extreme value distribution and N(·) is the standard normal distribution. Domain of attraction criteria for each of the three types of limit laws can be derived by appealing to a duality theorem relating the limiting record value distributions to the extreme value distributions. Repeated use is made of the following lemma: If $\text{P}\text{{X}{}_{\mathrm{n}}\text{?x}=1?e}{}^{\mathrm{-x}}\text{,x?0}$, then X_Ln=Y₀+…+Y_n where the Y_j's are i.i.d. and $\text{P}\text{{Y}{}_{\mathrm{j}}\text{?x}=1?e}{}^{\mathrm{-x}}$.     

Cogrowth and amenability of discrete groups

Let G be a group and g₁,…, g_t a set of generators. There are approximately (2t ? 1)ⁿ reduced words in g₁,…, g_t, of length ?n. Let $\text{}\text{?}\text{gg}{}_{\mathrm{n}}$ be the number of those which represent 1_G. We show that $\text{γ =}\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{(}\text{}\text{?}\text{gg}{}_{\mathrm{n}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ exists. Clearly 1 ? γ ? 2t ? 1. $\text{η =}\text{(}\text{log}\text{γ)}\text{(}\text{log}\text{(2t ? 1))}$ is the cogrowth. 0 ? η ? 1. In fact $\text{η ∈ {0} ∪ (}\text{1}\text{2}\text{, 1¦}$. The entropic dimension of G is shown to be 1 ? η. It is then proved that d(G) = 1 if and only if G is free on g₁,…, g_t and d(G) = 0 if and only if G is amenable.     

Duality between some linear preserver problems. II. Isometries with respect to c-special norms and matrices with fixed singular values

Let $\text{F}{}_{\mathrm{m\times n}}$ (m?n) denote the linear space of all m × n complex or real matrices according as $\text{F}$=$\text{C}$ or $\text{R}$. Let c=(c₁,…,c_m)≠0 be such that c₁???c_m?0. The c-spectral norm of a matrix A?$\text{F}$_m×n is the quantity

$\text{6A6}{}_{\mathrm{c}}\text{∑}\text{i=I}\text{m}\text{c}{}_{\mathrm{i}}\text{σ}{}_{\mathrm{i}}\text{(A)}$

. where σ₁(A)???σ_m(A) are the singular values of A. Let d=(d₁,…,d_m)≠0, where d₁???d_m?0. We consider the linear isometries between the normed spaces $\text{(}\text{F}{}_{\mathrm{m\times }}{}_{\mathrm{n}}\text{,∥·∥}{}_{\mathrm{<mtext>c</mtext>}}\text{)}$ and $\text{(}\text{F}{}_{\mathrm{m\times }}{}_{\mathrm{n}}\text{,∥·∥}{}_{\mathrm{d}}\text{)}$, and prove that they are dual transformations of the linear operators which map $\text{L}$(d) onto $\text{L}$(c), where

$\text{L}\text{(c)= {X?}\text{F}{}_{\mathrm{m\times n}}\text{:X}\text{has singular values}\text{c}{}_1\text{,…,c}{}_{\mathrm{m}}\text{}}$

.     

On graphs with equal edge connectivity and minimum degree

The note contains some conditions on a graph implying that the edge connectivity is equal to the minimum degree. One of these conditions is that if d₁?d₂???d_n is the degree sequence then ∑^l_l?1(d₁+d_n?1)>In?1 for $\text{1 ? l? min {}\text{n}\text{2?1}\text{, d}{}_{\mathrm{n}}\text{}}$.     

Sufficient conditions for ergodicity and recurrence of Markov chains on a general state space

Let {X_n} be a ?-irreducible Markov chain on an arbitrary space. Sufficient conditions are given under which the chain is ergodic or recurrent. These extend known results for chains on a countable state space. In particular, it is shown that if the space is a normed topological space, then under some continuity conditions on the transition probabilities of {X_n} the conditions for ergodicity will be met if there is a compact set K and an ? > 0 such that $\text{E}\text{{6X}{}_{\mathrm{n+1}}\text{6 — 6X}{}_{\mathrm{n}}\text{6 ∣ X}{}_{\mathrm{n}}\text{= x} ? ??}$ whenever x lies outside K and $\text{E}\text{{6X}{}_{\mathrm{n+1}}\text{6 ∣ X}{}_{\mathrm{n}}\text{=x}}$ is bounded, x ∈ K; whilst the conditions for recurrence will be met if there exists a compact K with $\text{E}\text{{6X}{}_{\mathrm{n+1}}\text{6 ? 6X}{}_{\mathrm{n}}\text{6 ∣ X}{}_{\mathrm{n}}\text{= x} ? 0}$ for all x outside K. An application to queueing theory is given.     

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}$.     

The Fréchet distance between multivariate normal distributions

The Fréchet distance between two multivariate normal distributions having means μ_X, μ_Y and covariance matrices Σ_X, Σ_Y is shown to be given by $\text{d}{}^2\text{= |μ}{}_{\mathrm{X}}\text{? μ}{}_{\mathrm{Y}}\text{|}{}^2\text{+}\text{tr}\text{(Σ}{}_{\mathrm{X}}\text{+ Σ}{}_{\mathrm{Y}}\text{? 2(Σ}{}_{\mathrm{X}}\text{Σ}{}_{\mathrm{Y}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$. The quantity d₀ given by $\text{d}{}_0{}^2\text{=}\text{tr}\text{(Σ}{}_{\mathrm{X}}\text{+ Σ}{}_{\mathrm{Y}}\text{? 2(Σ}{}_{\mathrm{X}}\text{Σ}{}_{\mathrm{Y}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ is a natural metric on the space of real covariance matrices of given order.     

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).     

The Dirichlet problem for the Kohn Laplacian on the Heisenberg group,I

For (x,y,t)∈$\text{R}$ⁿ × $\text{R}$ⁿ × $\text{R}$, denote $\text{X}{}_{\mathrm{j}}\text{=}\text{?}\text{?x}{}_{\mathrm{j}}\text{+ 2y}{}_{\mathrm{j}}\text{?}\text{?t}\text{, y}{}_{\mathrm{j}}\text{=}\text{?}\text{?y}{}_{\mathrm{j}}\text{? 2x}{}_{\mathrm{j}}\text{?}\text{?t}$ and $\text{L}{}_{\mathrm{\alpha }}\text{=?}\text{1}\text{4}\text{∑}\text{j=1}\text{n}\text{X}{}_{\mathrm{j}}{}^2\text{+ Y}{}_{\mathrm{j}}{}^2\text{+}\text{?}\text{?t}$. When α = n ? 2q, $\text{L}$_a represents the action of the Kohn Laplacian □_b on q-forms on the Heisenberg group. For ?n < α < n, we construct a parametrix for the Dirichlet problem in smooth domains D near non-characteristic points of ?D. A point w of ?D is non-characteristic if one of X₁,…, X_n, Y₁,…, Y_n is transverse to ?D at w. This yields sharp local estimates in the Dirichlet problem in the appropriate non-isotropic Lipschitz classes. The main new tool is a “convolution calculus” of pseudo-differential operators that can be applied to the relevant layer potentials, for which the usual asymptotic composition formula is false. Characteristic points are treated in Part II.     

On differences and sums of integers,I

A set {b₁,b₂,…,b_i} ? {1,2,…,N} is said to be a difference intersector set if {a₁,a₂,…,a_s} ? {1,2,…,N}, j > ?N imply the solvability of the equation a_x ? a_y = b′; the notion of sum intersector set is defined similarly. The authors prove two general theorems saying that if a set {b₁,b₂,…,b_i} is well distributed simultaneously among and within all residue classes of small moduli then it must be both difference and sum intersector set. They apply these theorems to investigate the solvability of the equations ($\text{a}{}_{\mathrm{x}}\text{?}\text{a}{}_{\mathrm{y}}\text{p}\text{= + 1}$, $\text{(a}{}_{\mathrm{u}}\text{?}\text{a}{}_{\mathrm{v}}\text{p}\text{) = ? 1}$, $\text{(a}{}_{\mathrm{r}}\text{+}\text{a}{}_{\mathrm{s}}\text{p}\text{) = + 1}$, $\text{(a}{}_{\mathrm{t}}\text{+}\text{a}{}_{\mathrm{z}}\text{p}\text{) = ? 1}$ (where ($\text{a}\text{p}$) denotes the Legendre symbol) and to show that “almost all” sets form both difference and sum intersector sets.     

A new normal form of Boolean functions

A new normal form of Boolean functions based on the sum (mod 2), product and negation is presented. Let n = {1, 2,…, n}, let A_s be the family of s-element subsets of a set A and let π_a?φx_a = 1. Then every Boolean function ?(x₁,x₂,…,x_n) has a normal form

$\text{?(x}{}_1\text{,x}{}_2\text{,…,x}{}_{\mathrm{n}}\text{=}\text{∑}\text{s=0}\text{n}\text{⊕}\text{Π}\text{A∈n}{}_{\mathrm{s}}\text{1⊕d}{}_{\mathrm{A}}\text{Π}\text{a∈A}\text{x}{}_{\mathrm{a}}$

with unique coefficients d_A? {0, 1}. A transformation of Galois normal form into the present normal form is also shown.     

A complete set of invariants for finite groups and other results

For a finite group G and a set I ? {1, 2,…, n} let

${}_{\mathrm{G}}\text{(n,I) = ∑}{}_{\mathrm{g\; \in \; G}}\text{ε}{}_1\text{(g)?ε}{}_2\text{(g)???ε}{}_{\mathrm{n}}\text{(g)}$

,where

$\text{ε}{}_{\mathrm{i}}\text{(g)=g}\text{if}\text{i=∈ I,}$

$\text{ε}{}_{\mathrm{l}}\text{(g)=l}\text{if}\text{i=∈ I.}$

We prove, among other results, that the positive integers

$\text{tr}\text{(e}{}_{\mathrm{G}}\text{(n,I}{}_1\text{)+?+e}{}_{\mathrm{G}}\text{(n,I}{}_{\mathrm{r}}\text{))}{}^{\mathrm{k}}\text{:n,r,k,?1, I}{}_{\mathrm{j}}\text{?{1,…,n}, 1?|i}{}_{\mathrm{j}}\text{|?3}$

for 1 ? j ? r, I_j1 ∩ I_j2 ∩ I_j3 ∩ I_j4 = Ø for any 1 ? j₁ <j₂ <j₃ <j₄ ? r, determine G up to isomorphism. We also show that under certain assumptions finite groups are determined up to isomorphism by the number of their subgroups.     

An extremal problem among subsets of a set

We determine the maximum size of a family of subsets in {1, 2,…, n} with the property that if A₁, A₂, A₃,… are any members of the family with $\text{∩A}{}_{\mathrm{i}}\text{= ?}$, then ∪A_i = {1, 2,…, n}.     

A note on the cross-correlation function between two binary maximal length linear sequences

Let {a_j}and {a_dj} be two binary maximal length linear sequences of period 2ⁿ?1. The cross-correlation function is defined as for t = 0, 1,…, 2ⁿ ? 2. We find the values and the number of occurrences of each value of C_d(t) when $\text{d =}\text{2}{}^{\mathrm{<mtext>n</mtext><mtext>2</mtext>}}\text{?}\text{2}{}^{\mathrm{<mtext>n</mtext><mtext>4</mtext>}}\text{+}\text{1}\text{, n ≡}\text{0}$ (mod 8).     

Isomorphisms between Lp-function spaces when p < 1

We prove a number of results concerning isomorphisms between spaces of the type L_p(X), where X is a separable p-Banach space and 0 < p < 1. Our results imply that the quotient of L_p([0, 1] × [0, 1]) by the subspace of functions depending only on the first variable is not isomorphic to L_p, answering a question of N. T. Peck. More generally if $\text{B}$₀ is a sub-σ-algebra of the Borel sets of [0, 1], then $\text{L}{}_{\mathrm{p}}\text{([0, 1])}\text{L}{}_{\mathrm{p}}\text{([0, 1]}$, $\text{B}$₀) is isomorphic to L_p if and only if L_p([0, 1], B₀) is complemented. We also show that L_p has, up to isomorphism, at most one complemented subspace non-isomorphic to L_p and classify completely those spaces X for which $\text{L}{}_{\mathrm{p}}\text{(X) ? L}{}_{\mathrm{p}}$. In particular if $\text{L(L}{}_{\mathrm{p}}\text{, X) = {0}}\text{and}\text{L}{}_{\mathrm{p}}\text{(X) ? L}{}_{\mathrm{p}}$ then $\text{X ? l}{}_{\mathrm{p}}$ or is finite-dimensional. If X has trivial dual and $\text{L}{}_{\mathrm{p}}\text{(X) ? L}{}_{\mathrm{p}}\text{then}\text{X ? L}{}_{\mathrm{p}}$.     

A note on the functional law of iterated logarithm for maxima of Gaussian sequences

Let {X_n, n ≥ 1} be a real-valued stationary Gaussian sequence with mean zero and variance one. Let M_n = max{X_t, i ≤ n} and H_n(t) = (M_[nt] ? b_n)a_n^?1 be the maximum resp. the properly normalised maximum process, where $\text{c}{}_{\mathrm{n}}\text{= (2}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, $\text{a}{}_{\mathrm{n}}\text{=}\text{(}\text{log log}\text{n)}\text{c}{}_{\mathrm{n}}$ and $\text{b}{}_{\mathrm{n}}\text{= c}{}_{\mathrm{n}}\text{?}\text{1}\text{2}\text{(}\text{log}\text{(4π}\text{log}\text{n))}\text{c}{}_{\mathrm{n}}$. We characterize the almost sure limit functions of (H_n)_n≥3 in the set of non-negative, non-decreasing, right-continuous, real-valued functions on (0, ∞), if r(n) (log n)^3?Δ = O(1) for all Δ > 0 or if r(n) (log n)^2?Δ = O(1) for all Δ > 0 and r(n) convex and fulfills another regularity condition, where r(n) is the correlation function of the Gaussian sequence.     

On some bidimensional denumerable chains of infinite order

We study homogeneous chains of infinite order (ξ_t)_{t∈$\text{Z}$} with the set of states taken to be $\text{X=(}\text{N}\text{{0,1})x{-1,1}}$. Our approach is to interpret the half-infinite sequence ..., ξ_?n,..., ξ_?1, ξ₀, where $\text{ξ}{}_{\mathrm{t}}\text{=(i}{}_{\mathrm{t}}\text{, ε}{}_{\mathrm{t}}\text{) ∈ X, t ∈}\text{Z}$ as the continued fraction to the nearer integer expansion (read inversely) of a y ? [?$\text{1}\text{2}$,$\text{1}\text{2}$]. Thus, we are led to study certain Y-valued Markov chains, where Y = [?$\text{1}\text{2}$, $\text{1}\text{2}$] and then by making use of their properties we establish the existence of denumerable chains of infinite order under conditions different from those given in Theorem 2.3.8 of Iosifescu-Theodorescu (1969). A (weak) variant of mixing is proved as well.