A note on the construction of optimal linear codes

Let us denote by (n,k,d)-code, a binary linear code with code length nk information symbols and the minimum distance d. It is well known that the problem of obtaining a binary linear code whose code length n is minimum among (n,k,d)-codes for given integers k and d, is equivalent to solve a linear programming whose solutions correspond to a minimum redundancy error-correcting code. In this paper it will be shown that for some given integers d, there exists no solution of the linear programming except a solution which is obtained using a flat in a finite projective geometry.     

A characterization of the geometric distribution

We show that for a simple random sample from a discrete distribution on the positive integers, the regression ofX _(2∶n) onX _(1∶n) is linear with unit slope if and only if the distribution is geometric.     

Minimizing the expected sample range

Let X_i be i.i.d. random variables with finite expectations, and θ_i arbitrary constants, i=1,…,n. Y_i=X_i+θ_i. The expected range of the Y's is R_n(θ₁,…,θ_n)=E(maxY_i-minY_i. It is shown that the expected range is minimized if and only if θ₁=?=θ_n. In the case where the X_i are independently and symmetrically distributed around the same constant, but not identically distributed, it is shown that θ₁=?=θ_n are not necessarily the only (θ₁,...,θ_n) minimizing R_n. Some lemmas which are applicable to more general problems of minimizing R_n are also given.     

Poisson approximations in selected metrics by coupling and semigroup methods with applications

Let S_n = X₁ + … + X_n, where X₁,…, X_n are independent Bernoulli random variables. In this paper, we evaluate probability metrics of the Wasserstein type between the distribution of S_n and a Poisson distribution. Our results show that, if E(S_n) = O(1) and if the individual probabilities of success of the X_i's tend uniformly to zero, then the general rate of convergence of the above mentioned metrics to zero is O(∑ⁿ_i = ₁P²_i). We also show that this rate is sharp and discuss applications of these results.     

Weight hierarchies of linear codes of dimension 3

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,…,d_k), where d_r is the smallest support of an r-dimensional subcode of C. The weight hierarchies of [n,3;q] codes are studied. In particular, for q⩽5 the possible weight hierarchies of [n,3;q] codes are determined.     

The intersection problem for K4 - e designs

A G-design of order n is a pair (P,B) where P is the vertex set of the complete graph K_n and B is an edge-disjoint decomposition of K_n into copies of the simple graph G. Following design terminology, we call these copies “blocks”. Here K₄ - e denotes the complete graph K₄ with one edge removed. It is well-known that a K₄ - e design of order n exists if and only if n ≡ 0 or 1 (mod 5), n ⩾ 6. The intersection problem here asks for which k is it possible to find two K₄ - e designs (P,B₁) and (P,B₂) of order n, with |B₁ ∩ B₂| = k, that is, with precisely k common blocks. Here we completely solve this intersection problem for K₄ - e designs.     

Circular success and failure runs in a sequence of exchangeable binary trials

Let X₁,…,X_n be an exchangeable sequence of binary trials arranged on a circle with possible values “1” (success) or “0” (failure). In an exchangeable sequence, the joint distribution of X₁,X₂,…,X_n is invariant under the permutation of its arguments. For the circular sequence, general expressions for the joint distributions of run statistics based on the joint distribution of success and failure run lengths are obtained. As a special case, we present our results for Bernoulli trials. The results presented consist of combinatorial terms and therefore provide easier calculations. For illustration purposes, some numerical examples are given and the reliability of the circular combined k-out-of-n:G and consecutive k_c-out-of-n:G system under stress–strength setup is evaluated.     

On the Markov property of order statistics

The order statistics from a sample of size n≥3 from a discrete distribution form a Markov chain if and only if the parent distribution is supported by one or two points. More generally, a necessary and sufficient condition for the order statistics to form a Markov chain for (n≥3) is that there does not exist any atom x₀ of the parent distribution F satisfying F(x₀-)>0 and F(x₀)<1. To derive this result a formula for the joint distribution of order statistics is proved, which is of an interest on its own. Many exponential characterizations implicitly assume the Markov property. The corresponding putative geometric characterizations cannot then be reasonably expected to obtain. Some illustrative geometric characterizations are discussed.     

On tail parameter estimation in certain point process models

Let μ(ds, dx) denote Poisson random measure with intensity dsG(dx) on (0, ∞) × (0, ∞), for a measure G(dx) with tails varying regularly at ∞. We deal with estimation of index of regular variation α and weight parameter ξ if the point process is observed in certain windows K_n = [0, T_n] × [Y_n, ∞), where Y_n → ∞ as n → ∞. In particular, we look at asymptotic behaviour of the Hill estimator for α. In certain submodels, better estimators are available; they converge at higher speed and have a strong optimality property. This is deduced from the parametric case G(dx) = ξαx^−α−1 dx via a neighbourhood argument in terms of Hellinger distances.     

On the equivalence of certain constant weight codes and combinatorial designs

Stinson and van Rees (Combinatorica (1984), 357–362) proved that the existence of an equidistant code E: (n = 4s + 1,d = 2s, N) with N = n implies the existence of a certain symmetrical BIB design. This result is extended here for the constant weight codes with the same n and d. A theorem on the equivalence of a Hadamard matrix and a certain constant weight code is also proved.     

A stochastic Newton-Raphson method

A stochastic approximation procedure of the Robbins-Monro type is considered. The original idea behind the Newton-Raphson method is used as follows. Given n approximations X₁,…, X_n with observations Y₁,…, Y_n, a least squares line is fitted to the points (X_m, Y_m),…, (X_n, Y_n) where m<n may depend on n. The (n+1)st approximation is taken to be the intersection of the least squares line with y=0. A variation of the resulting process is studied. It is shown that this process yields a strongly consistent sequence of estimates which is asymptotically normal with minimal asymptotic variance.     

Existence of frame SOLS of type anb1 for odd n

It has been proved that (i) FSOLS(2ⁿb¹) exist if and only if n⩾4 and n⩾1+b and (ii) FSOLS(3ⁿb¹) exist if and only if n⩾4 and n⩾1+2b/3 with 17 possible exceptions. In this article, we show that for b⩾2 and odd n, FSOLS(aⁿb¹) exists if and only if n⩾4 and n⩾1+2b/a.     

Revealing the dependence structure between X(1) and X(n)

In this paper we address the dependence structure of the minimum and maximum of n iid random variables X₁,…,X_n by determining their copula. It is then easy to give an alternative proof for their asymptotic independence and to calculate Kendall's τ and Spearman's ρ for (X₍₁₎,X_(n)). This will show that the dependence between the variables is already small for small sample sizes. Finally, it can be shown that 3τ_n⩾ρ_n⩾τ_n>0. Although closed-form expressions are available for τ_n and ρ_n, we cannot compare them directly but have to use the concept of positive likelihood ratio dependence to establish this result.     

Deletions in random binary search trees: A story of errors

The usual assumptions for the average case analysis of binary search trees (BSTs) are random insertions and random deletions. If a BST is built by n random insertions the expected number of key comparisons necessary to access a node is 2 ln n+O(1). This well-known result is already contained in the first papers on such ‘random’ BSTs. However, if random insertions are intermixed with random deletions the analysis of the resulting BST seems to become more intricate. At least this is the impression one gets from the related publications since 1962, and it is quite appropriate to speak of a story of errors in this context, as will be seen in the present survey paper, giving an overview on this story.     

Density estimation for samples satisfying a certain absolute regularity condition

Let {ξ_i} be an absolutely regular sequence of identically distributed random variables having common density function f(x). Let H_k(x,y) (k=1, 2,…) be a sequence of Borel-measurable functions and f_n(x)=n^?1(H_n(x,ξ₁)+…+H_n(x,ξ_n)) the empirical density function. In this paper, the asymptotic property of the probability P(sup_x|f_n(x)?f(x)|>ε) (n→∞) is studied.     

On some joint distributions in fluctuation theory

For non-negative integral valued interchangeable random variables v₁, v₂,…,v_n, Takács (1967, 70) has derived the distributions of the statistics ?_n' ?¹_n' ?^(c)_n and ?^(-c)_n concerning the partial sums N_r = v₁ + v₂ + ··· + v_rr = 1,…,n. This paper deals with the joint distributions of some other statistics viz., (α^(c)_n, δ^(c)_n, Z_n), (β^(c)_n, Z_n) and (β^(-c)_n, Z_n) concerning the partial sums N_r = ε₁ + ··· + ε_rr = 1,2,…,n, of geometric random variables ε₁, ε₂,…,ε_n.