The visibility parameter for words and permutations

We investigate the visibility parameter, i.e., the number of visible pairs, first for words over a finite alphabet, then for permutations of the finite set {1, 2, …, n}, and finally for words over an infinite alphabet whose letters occur with geometric probabilities. The results obtained for permutations correct the formula for the expectation obtained in a recent paper by Gutin et al. [Gutin G., Mansour T., Severini S., A characterization of horizontal visibility graphs and combinatorics on words, Phys. A, 2011, 390 (12), 2421–2428], and for words over a finite alphabet the formula obtained in the present paper for the expectation is more precise than that obtained in the cited paper. More importantly, we also compute the variance for each case.     

On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001     

Palindromic prefixes and episturmian words

Let w be an infinite word on an alphabet A. We denote by (ni)_i?1 the increasing sequence (assumed to be infinite) of all lengths of palindromic prefixes of w. In this text, we give an explicit construction of all words w such that ni+1?2ni+1 for all i, and study these words. Special examples include characteristic Sturmian words, and more generally standard episturmian words. As an application, we study the values taken by the quantity lim supni+1/ni, and prove that it is minimal (among all nonperiodic words) for the Fibonacci word.     

Enumeration of words by their number of mistakes

Consider all words in {1,…,n}. A fixed set of words is labeled as the set of “mistakes”. A generating function for the number of words with m₁1's,…,m_nn's and k mistakes is given. This generalizes a result of Gessel who considered the case where all the mistakes are two-lettered. A similar result has been independently obtained by Goulden and Jackson.     

On a functional equation generalizing the class of semistable distributions

With ?(p),p≥0 the Laplace-Stieltjes transform of some infinitely divisible probability distribution, we consider the solutions to the functional equation ?(p-e ^?pβΠ _i=1 ^m ?^γi (c _i p) for somem≥1,c _i>0, γ _i >0,i=1., …,m, β ε ®. We supply its complete solutions in terms of semistable distributions (the ones obtained whenm=1). We then show how to obtain these solutions as limit laws (r → ∞) of normalized Poisson sums of iid samples when the Poisson intensity λ(r) grows geometrically withr.     

Optimal maps for the multidimensional Monge-Kantorovich problem

Let μ₁,…, μ_N be Borel probability measures on ℝ^d. Denote by Γ(μ₁,…, μ_N) the set of all N-tuples T=(T₁,…, T_N) such that T_i:ℝ^d ↔ ℝ^d (i = 1,…, N) are Borel-measurable and satisfy μ₁ = μ_i[V] for all Borel V ⊂ ℝ^d. The multidimensional Monge-Kantorovich problem investigated in this paper consists of finding S=(S₁,…, S_N) ∈ Γ(μ₁,…, μ_N) minimizing over the set Γ(μ₁, ···, μ_N). We study the case where the μ_i's have finite second moments and vanish on (d - 1)-rectifiable sets. We prove existence and uniqueness of optimal maps S when we impose that S₁( x ) ≡ x and give an explicit form of the maps S_i. The result is obtained by variational methods and to the best of our knowledge is the first available in the literature in this generality. As a consequence, we obtain uniqueness and characterization of an optimal measure for the multidimensional Kantorovich problem. © 1998 John Wiley & Sons, Inc.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

The box parameter for words and permutations

The box parameter for words counts how often two letters w _j and w _k define a “box” such that all the letters w _j+1; ..., w _k?1 fall into that box. It is related to the visibility parameter and other parameters on words. Three models are considered: Words over a finite alphabet, permutations, and words with letters following a geometric distribution. A typical result is: The average box parameter for words over an M letter alphabet is asymptotically given by 2n ? 2 _n H _M /M, for fixed M and n → ∞.     

Δ-Monotone arrangements of real numbers

Given a set of M × N real numbers, can these always be labeled as x_i,j; i = 1,…, M; j = 1,…, N; such that x_i+1,j+1 ? x_i+1,j ? x_i,j+1 + x_ij ≥ 0, for every (i, j) where 1 ≤ i ≤ M ? 1, 1 ≤ j ≤ N ? 1? For M = N = 3, or smaller values of M, N it is shown that there is a “uniform” rule. However, for max(M, N) > 3 and min(M, N) ≥ 3, it is proved that no uniform rule can be given. For M = 3, N = 4 a way of labeling is demonstrated. For general M, N the problem is still open although, for a special case where all the numbers are 0's and 1's, a solution is given.     

A fundamental inequality for the sum of sets of m-tuples

For n a positive integer and A₁, A₂, …, A_k sets of nonnegative integers, sufficient conditions are found which imply that the sum of the cardinalities of the sets $\text{{1, 2, …, n} ? A}{}_{\mathrm{i}}\text{(i = 1, 2, …, k)}$ does not exceed the cardinality of the intersection of {1, 2, …, n} and the number theoretic sum of the k sets. Some of the results are generalized to sets of m-tuples of nonnegative integers.     

Trimmed estimates in simultaneous estimation of parameters in exponential families

Let X₁,…, X_p be p (≥ 3) independent random variables, where each X_i has a distribution belonging to the one-parameter exponential family of distributions. The problem is to estimate the unknown parameters simultaneously in the presence of extreme observations. C. Stein (Ann. Statist.9 (1981), 1135–1151) proposed a method of estimating the mean vector of a multinormal distribution, based on order statistics corresponding to the |X_i|'s, which permitted improvement over the usual maximum likelihood estimator, for long-tailed empirical distribution functions. In this paper, the ideas of Stein are extended to the general discrete and absolutely continuous exponential families of distributions. Adaptive versions of the estimators are also discussed.     

Asymptotic bias of some election methods

Consider an election where N seats are distributed among parties with proportions p ₁,…,p _m of the votes. We study, for the common divisor and quota methods, the asymptotic distribution, and in particular the mean, of the seat excess of a party, i.e. the difference between the number of seats given to the party and the (real) number Np _i that yields exact proportionality. Our approach is to keep p ₁,…,p _m fixed and let N→∞, with N random in a suitable way. In particular, we give formulas showing the bias favouring large or small parties for the different election methods.     

Multivariate distributions having Weibull properties

Random variables X₁ ,…, X_n are said to have a joint distribution with Weibull minimums after arbitrary scaling if min_i(a_iX_i) has a one dimensional Weibull distribution for arbitrary constants a_i > 0, i = 1,…, n. Some properties of this class are demonstrated, and some examples are given which show the existence of a number of distributions belonging to the class. One of the properties is found to be useful for computing component reliability importance. The class is seen to contain an absolutely continuous Weibull distribution which can be generated from independent uniform and gamma distributions.     

Avoiding abelian squares in partial words

Erd?s raised the question whether there exist infinite abelian square-free words over a given alphabet, that is, words in which no two adjacent subwords are permutations of each other. It can easily be checked that no such word exists over a three-letter alphabet. However, infinite abelian square-free words have been constructed over alphabets of sizes as small as four. In this paper, we investigate the problem of avoiding abelian squares in partial words, or sequences that may contain some holes. In particular, we give lower and upper bounds for the number of letters needed to construct infinite abelian square-free partial words with finitely or infinitely many holes. Several of our constructions are based on iterating morphisms. In the case of one hole, we prove that the minimal alphabet size is four, while in the case of more than one hole, we prove that it is five. We also investigate the number of partial words of length n with a fixed number of holes over a five-letter alphabet that avoid abelian squares and show that this number grows exponentially with n.     

The perimeter of words

We define $\left[k\right]=\{1,2,\dots ,k\}$ to be a (totally ordered) alphabet on $k$ letters. A word $w$ of length $n$ on the alphabet $\left[k\right]$ is an element of ${\left[k\right]}^n$. A word can be represented by a bargraph (i.e., by a column-convex polyomino whose lower edges lie on the $x$-axis) in which the height of the $i$th column equals the size of the $i$th part of the word. Thus these bargraphs have heights which are less than or equal to $k$. We consider the perimeter, which is the number of edges on the boundary of the bargraph. By way of Cramer’s method and the kernel method, we obtain the generating function that counts the perimeter of words. Using these generating functions we find the average perimeter of words of length $n$ over the alphabet $\left[k\right]$. We also show how the mean and variance can be obtained using a direct counting method.     

Navigation and control of the motion of a back wheel drive tricycle

This work deals with the guidance and control of the motion of a back wheel drive tricycle. Denote by O the center of mass of the tricycle. Given N points P_i, i = 0,…, N − 1 in the horizontal plane, a finite time interval [0, t_f], and a sequence of times τ₀ = 0 < τ₁ < … < τ_{N −1} = t_f. Based on a dynamical model of the tricycle, and by using the concept of path controllability, control laws are derived for the tricycle's pedalling moment and directional moment such that O will pass through p_j at the time τ_j, j = 0,…, N − 1, respectively.     

An estimator for the mean of an exponential distribution with random right-censoring

Let (Y₁, Z₁),…,(Y_N, Z_N) be i.i.d. pairs of independent random variables such that Y_i is exponentially distributed with unknown mean 1/λ and Z_i has an unknown distribution function F. Let X_i ≔ min(Y_i, Z_i). Under certain assumptions on F an estimator T_N(X₁,…,X_N) for 1/λ is constructed which is consistent and asymptotically normal.     

A cyclic production problem: an application of max-algebra

Given are m identical machines, each of which performs the same N operations O_i, 1⩽ i ⩽ N, cyclically and indefinitely, i.e. a production run on a machine looksO₁, O₂,…,O_N, O₁, O₂,…,O_N, O₁…. There are n_i⩽m to to perform operation O_i. The tools are transported between the machines by means of an infinitely fast transport device.Given a particular transport policy we prove the existence of stationary cyclic behaviour, determine the corresponding cycle time, and investigate the long run behaviour of the system starting from a given initial state.     

On highly palindromic words

We study some properties of palindromic (scattered) subwords of binary words. In view of the classical problem on subwords, we show that the set of palindromic subwords of a word characterizes the word up to reversal.Since each word trivially contains a palindromic subword of length at least half of its length-a power of the prevalent letter-we call a word that does not contain any palindromic subword longer than half of its length minimal palindromic. We show that every minimal palindromic word is abelian unbordered, that is, no proper suffix of the word can be obtained by permuting the letters of a proper prefix.We also propose to measure the degree of palindromicity of a word w by the ratio |rws|/|w|, where the word rws is minimal palindromic and rs is as short as possible. We prove that the ratio is always bounded by four, and construct a sequence of words that achieves this bound asymptotically.     

Towards the inverse of a word

Let w be a word, i.e., a permutation with repetitions. We present a construction for the inverse of w in the case where w has at most three distinct letters, and indicate steps towards the construction in the general case.