Waiting for the pattern 123123 … 123 in independent trinomial observations

The method for geometric transforms (probability generating functions) is used to study the expected number of observations until the pattern 123123 … 123 is obtained. These results provide a first generalization of similar problems considered by other authors.     

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.     

Strings of consecutive successes

A sequence of independent Bernoulli trials is conducted. Let Nbe the number of trials required before observing a string of m successes. Using only elementary methods of probability theory, the expected value, variance and probability generating function of N are determined as functions of m and p, the probability of success on any given trial.     

An Iterative Approach to Determining the Length of the Longest Common Subsequence of Two Strings

This paper concerns the longest common subsequence (LCS) shared by two sequences (or strings) of length N, whose elements are chosen at random from a finite alphabet. The exact distribution and the expected value of the length of the LCS, k say, between two random sequences is still an open problem in applied probability. While the expected value E(N) of the length of the LCS of two random strings is known to lie within certain limits, the exact value of E(N) and the exact distribution are unknown. In this paper, we calculate the length of the LCS for all possible pairs of binary sequences from N=1 to 14. The length of the LCS and the Hamming distance are represented in color on two all-against-all arrays. An iterative approach is then introduced in which we determine the pairs of sequences whose LCS lengths increased by one upon the addition of one letter to each sequence. The pairs whose score did increase are shown in black and white on an array, which has an interesting fractal-like structure. As the sequence length increases, R(N) (the proportion of sequences whose score increased) approaches the Chvátal–Sankoff constant a _c (the proportionality constant for the linear growth of the expected length of the LCS with sequence length). We show that R(N) is converging more rapidly to a _c than E(N)/N.     

Generating Birth and Death Processes

Associated with an ordered sequence of an even number 2N of positive real numbers is a birth and death process (BDP) on {0, 1, 2,…, N} having these real numbers as its birth and death rates. We generate another birth and death process from this BDP on {0, 1, 2,…, 2N}. This can be further iterated. We illustrate with an example from tan(kz). In BDP, the decay parameter, viz., the largest non-zero eigenvalue is important in the study of convergence to stationarity. In this article, the smallest eigenvalue is found to be useful.     

An application of prophet regions to optimal stopping with a random number of observations

Let X ₁,X ₂ ,?…?be any sequence of nonnegative integrable random variables, and let N∈{1,2 , …} be a random variable with known distribution, independent of X ₁,X ₂ , …. The optimal stopping value sup _t E(X_t I(N≥ t)) is considered for two players: one who has advance knowledge of the value of N, and another who does not. Sharp ratio and difference inequalities relating the two players' optimal values are given in a number of settings. The key to the proofs is an application of a prophet region for arbitrarily dependent random variables by Hill and Kertz [T.P. Hill and R.P. Kertz (1983). Stop rule inequalities for uniformly bounded sequences of random variables. Trans. Amer. Math. Soc., 278, 197–207].     

Coalescing times for IID random variables with applications to population biology

We consider a coalescing particle model where particles move in discrete time. At each time period, each remaining ball is independently put in one of n bins according to a probability distribution p = (p₁, …, p_n), and all balls put into the same bin merge into a single ball. Starting with k balls, we are interested in the properties of E[N( p , k)], the expected time until all balls merge into one. We derive both upper and lower bounds for E[N( p , k)], some asymptotic results, and show that P{N( p , k) > t}, and thus E[N( p , k)], is a Schur concave function of p . Applications to population biology are noted. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 155–166, 2003     

An optimal sequence in multicharacteristics inspection

Given a component withN critical characteristics, each characteristici has a cost of inspectionC _i>0 and a probability of rejectionR _i, 0R _i<1. an=" optimal=" sequence=" for=" ordering=" these=" critical=" characteristics=" for=" inspection=" is=" found.=" this=" sequence=" minimizes=" the=" total=" expected=" cost=" of=" inspection.=" the=" implications=" and=" the=" applications=" of=" this=" sequence=" are=">Communicated by M. D. Intriligator     

Mixing Properties and Central Limit Theorem for a Class of Non-Identical Piecewise Monotonic C2 — Transformations

For a sequence T⁽¹⁾, T⁽²⁾,…of piecewise monotonic C² - transformations of the unit interval I onto itself, we prove exponential ψ- mixing, an almost Markov property and other higher-order mixing properties. Furthermore, we obtain optimal rates of convergence in the central limit Theorem and large deviation relations for the sequence f_k oT(k?1)o…oT⁽¹⁾, k=1, 2, …, provided that the real-valued functions f₁, f₂,…on I are of bounded variation and the corresponding probability measure on I possesses a positive, Lipschitz-continuous Lebesgue density.     

Critical Pairs of Sequences of a Mixed Frame Potential

The classical frame potential in a finite-dimensional Hilbert space has been introduced by Benedetto and Fickus, who showed that all finite unit-norm tight frames can be characterized as the minimizers of this energy functional. This was the starting point of a series of new results in frame theory, related to finding tight frames with determined lengths. The frame potential has been studied in the traditional setting as well as in the finite-dimensional fusion frame context. In this work we introduce the concept of mixed frame potential, which generalizes the notion of the Benedetto-Fickus frame potential. We study properties of this new potential, and give the structure of its critical pairs of sequences on a suitable restricted domain. For a given sequence {α _m } _{m=1,…, N} in K, where K is ? or ?, we obtain necessary and sufficient conditions in order to have a dual pair of frames {f _m } _{m=1,…, N} , {g _m } _{m=1,…, N} such that ? f _m , g _m  ? = α _m for all m = 1,…, N.     

Non–parametric probability density function estimation on a bounded support: Applications to shape classification and speech coding

In statistics, it is usually difficult to estimate the probability density function from N independent samples X₁,X₂, …?, X_N identically distributed. A lot of work has been done in the statistical literature on the problem of probability density estimation (e.g. Cencov, 1962; Devroye and Gyorfi, 1981; Hall, 1980 and 1982; Hominal, 1979; Izenman, 1991; Kronmal and Tarter, 1968; Parzen, 1962; Rosenblatt, 1956). In this paper, we consider random variables on bounded support. Orthogonal series estimators, studied in detail by Kronmal and Tarter (1968), by Hall (1982) and by Cencov (1962), show that there is a disadvantage related to the Gibbs phenomenon on the bias of these estimators. We suggest a new method for the non–parametric probability density function estimation based on the kernel method using an appropriately chosen regular change of variable. The new method can be used for several problems of signal processing applications (scalar or vector quantization, speech or image processing, pattern recognition, etc.). Applications to shape classification and speech coding are given.     

The generalized Banach match-box problem: Application in disc storage management

A computer system manages disc storage of finite capacity c blocks. This storage must be divided among N files in such a way that the expected number of disc accesses accomplished until the necessary reorganization is maximized. Each access to the disc appends a record of a fixed length to the ith file with probability p _i (i=1,h., N). The reorganization is needed when the chosen file has run out of space. It is shown that the above problem is a generalization of Banach's match-box problem known from the probability theory. A detailed separate analysis for the N=2 case and for the multivariate case is performed and some approximate results for large c are given.     

A nonsymmetric matrix with integer eigenvalues

A nonsymmetric N?×?N matrix with elements as certain simple functions of N distinct real or complex numbers r ₁, r ₂, …, r_N is presented. The matrix is special due to its eigenvalues???the consecutive integers 0,1,2, …, N?1. Theorems are given establishing explicit expressions of the right and left eigenvectors and formulas for recursive calculation of the right eigenvectors. A special case of the matrix has appeared in sampling theory where its right eigenvectors, if properly normalized, give the inclusion probabilities of the conditional Poisson sampling design.     

Large Closed Queueing Networks in Semi-Markov Environment and Their Application

The paper studies closed queueing networks containing a server station and k client stations. The server station is an infinite server queueing system, and client stations are single-server queueing systems with autonomous service, i.e. every client station serves customers (units) only at random instants generated by a strictly stationary and ergodic sequence of random variables. The total number of units in the network is N. The expected times between departures in client stations are (N μ _j )⁻¹. After a service completion in the server station, a unit is transmitted to the jth client station with probability p _j (j=1,2,…,k), and being processed in the jth client station, the unit returns to the server station. The network is assumed to be in a semi-Markov environment. A semi-Markov environment is defined by a finite or countable infinite Markov chain and by sequences of independent and identically distributed random variables. Then the routing probabilities p _j (j=1,2,…,k) and transmission rates (which are expressed via parameters of the network) depend on a Markov state of the environment. The paper studies the queue-length processes in client stations of this network and is aimed to the analysis of performance measures associated with this network. The questions risen in this paper have immediate relation to quality control of complex telecommunication networks, and the obtained results are expected to lead to the solutions to many practical problems of this area of research.      

Structure of sequential tests minimizing an expected sample size

Summary The testing problem is to decide on the basis of repeated independent observations which of the probability densitiesf andg is true. Given upper bounds on the probabilities of error, the object is to minimize the expected sample size if the densityp is true (allowed to differ fromf andg). A characterization of the structure of optimal tests is obtained which is particularly informative in the case wheref,g, andp belong to a Koopman-Darmois family. Ifp=f org, then the optimal tests are sequential probability ratio tests (SPRT's) and a new proof of the well-known optimality property of these tests is obtained as a corollary.Research supported by National Science Foundation grant MCS 76-08489     

Learning finite binary sequences from half‐space data

The problem of inferring a finite binary sequence w *∈{−1, 1}ⁿ is considered. It is supposed that at epochs t=1, 2,…, the learner is provided with random half‐space data in the form of finite binary sequences u ^(t)∈{−1, 1}ⁿ which have positive inner‐product with w *. The goal of the learner is to determine the underlying sequence w * in an efficient, on‐line fashion from the data { u ^(t), t≥1}. In this context, it is shown that the randomized, on‐line directed drift algorithm produces a sequence of hypotheses {w^(t)∈{−1, 1}ⁿ, t≥1} which converges to w * in finite time with probability 1. It is shown that while the algorithm has a minimal space complexity of 2n bits of scratch memory, it has exponential time complexity with an expected mistake bound of order Ω(e^0.139n). Batch incarnations of the algorithm are introduced which allow for massive improvements in running time with a relatively small cost in space (batch size). In particular, using a batch of 𝒪(n log n) examples at each update epoch reduces the expected mistake bound of the (batch) algorithm to 𝒪(n) (in an asynchronous bit update mode) and 𝒪(1) (in a synchronous bit update mode). The problem considered here is related to binary integer programming and to learning in a mathematical model of a neuron. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 345–381 (1999)     

The full-information best choice problem with a random number of observations

The full-information best choice problem with a random number of observations is considered. N i.i.d. random variables with a known continuous distribution are observed sequentially with the object of selecting the largest. Neither recall nor uncertainty of selection is allowed and one choice must be made. In this paper the number N of observations is random with a known distribution. The structure of the stopping set is investigated. A class of distributions of N (which contains in particular the uniform, negative-binomial and Poisson distributions) is determined, for which the so-called “monotone case” occurs. The theoretical solution for the monotone case is considered. In the case where N is geometric the optimal solution is presented and the probability of winning worked out. Finally, the case where N is uniform is examined. A simple asymptotically optimal stopping rule is found and the asymptotic probability of winning is obtained.     

Simulating events of unknown probabilities via reverse time martingales

Let s∈(0,1) be uniquely determined but only its approximations can be obtained with a finite computational effort. Assume one aims to simulate an event of probability s. Such settings are often encountered in statistical simulations. We consider two specific examples. First, the exact simulation of non‐linear diffusions ([ 3 ]). Second, the celebrated Bernoulli factory problem ([ 10 , 13 ]) of generating an f(p)‐coin given a sequence X₁,X₂,… of independent tosses of a p‐coin (with known f and unknown p). We describe a general framework and provide algorithms where this kind of problems can be fitted and solved. The algorithms are straightforward to implement and thus allow for effective simulation of desired events of probability s. Our methodology links the simulation problem to existence and construction of unbiased estimators. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 441–452, 2011     

Sooner and Later Waiting Time Problems Based on a Dependent Sequence

This paper introduces a new concept: a binary sequence of order (k,r), which is an extension of a binary sequence of order k and a Markov dependent sequence. The probability functions of the sooner and later waiting time random variables are derived in the binary sequence of order (k,r). The probability generating functions of the sooner and later waiting time distributions are also obtained. Extensions of these results to binary sequence of order (g,h) are also presented.