Successes,runs and longest runs

The probability distribution of the number of success runs of length k (⩾1) in n (⩾1) Bernoulli trials is obtained. It is noted that this distribution is a binomial distribution of order k, and several open problems pertaining to it are stated. Let S_n and L_n, respectively, denote the number of successes and the length of the longest success run in the n Bernoulli trials. A formula is derived for the probability P(L_n ⩽ k | S_n = r) (0 ⩽ k ⩽ r ⩽ n), which is alternative to those given by Burr and Cane (1961) and Gibbons (1971). Finally, the probability distribution of X_{n, Ln}^(k) is established, where X_{n, Ln}^(k) denotes the number of times in the n Bernoulli trials that the length of the longest success run is equal to k.     

Successes,runs and longest runs

The probability distribution of the numbeer of success runs of length k ( >/ 1) in n ( ⩾ 1) Bernoulli trials is obtained. It is noted that this distribution is a binomial distribution of order k, and several open problems pertaining to it are stated. Let S_n and L_n, respectively, denote the number of successes and the length of the longest success run in the n Bernoulli trials. A formula is derived for the probability P(L_n ⩽ k | S_n = r) (0 ⩽ k ⩽ r ⩽ n), which is alternative to those given by Burr and Cane (1961) and Gibbons (1971). Finally, the probability distribution of X_{n, Ln}^(k) is established, where X_{n, Ln}^(k) denotes the number of times in the n Bernoulli trials that the length of the longest success run is equal to k.     

The Littlewood-Offord problem and invertibility of random matrices

We prove two basic conjectures on the distribution of the smallest singular value of random n×n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n−1/2, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables Xk and real numbers ak, determine the probability p that the sum k_∑akXk lies near some number v. For arbitrary coefficients ak of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.     

On the internal structure of random recursive circuits

We study the joint probability distribution of the number of nodes of fan-out k in random recursive circuits. For suitable norming we obtain a limiting multivariate normal distribution for the numbers of node of fan-out at most k, where we compute explicitly the limiting covariance matrix by solving a recurrence satisfied among its entries.     

Generalized symmetric elements generated by a prime sequence

Let be a prime sequence in a local Noether lattice L. For denotes the set of finite joins in L of power products of the generalized symmetric elements of order k (majorization elements) in together with 0 and I. We have previously showed that for is a Noetherian distributive -domain. For and for any is again such a sub--domain of . For and is not closed under the meet of . However with its induced meet is again a Noetherian distributive -domain. Each finite set of majorization elements asymptotically forms a distributive sublattice of for k sufficiently large. Received March 2, 1998; accepted in final form June 11, 1998.     

Compound Geometric Distribution of Order <Emphasis Type="Italic">k</Emphasis>

The distribution of the number of trials until the first k consecutive successes in a sequence of Bernoulli trials with success probability p is known as geometric distribution of order k. Let T _k be a random variable that follows a geometric distribution of order k, and Y ₁,Y ₂,… a sequence of independent and identically distributed discrete random variables which are independent of T _k . In the present article we develop some results on the distribution of the compound random variable \(S_{k} =\sum_{t=1}^{T_{k}}Y_{t}\).     

Majorization in de Branges spaces I. Representability of subspaces

In this series of papers we study subspaces of de Branges spaces of entire functions which are generated by majorization on subsets D of the closed upper half-plane. The present, first, part is addressed to the question which subspaces of a given de Branges space can be represented by means of majorization. Results depend on the set D where majorization is permitted. Significantly different situations are encountered when D is close to the real axis or accumulates to i∞.     

On the mean number of trials until the last trials satisfy a given condition

Random variables are collected one at a time until the last k variables satisfy a given condition. The mean waiting time until this happens is studied and a general lemma is given. If the condition is satisfied by many possible stopping sequences the probability distribution of the k last variables is discussed. A fairly general treatment is given for the case when k = 2. Two other special cases are mentioned, viz. the case when the condition is defined by order relations between the last variables, and the case when the variables are discrete.     

Faces of Poisson�CVoronoi mosaics

For a stationary Poisson?CVoronoi tessellation in Euclidean d-space and for ${k\in \{1,\dots,d\}}$ , we consider the typical k-dimensional face with respect to a natural centre function. We express the distribution of this typical k-face in terms of a certain Poisson process of closed halfspaces in a k-dimensional space. Then we show that, under the condition of large inradius, the relative boundary of the typical k-face lies, with high probability, in a narrow spherical annulus.     

A geometric approach to a class of optimization problems concerning exchangeable binary variables

In [Zaigraev, A., Kaniovski, S., 2010. Exact bounds on the probability of at least k successes in n exchangeable Bernoulli trials as a function of correlation coefficients. Statist. Probab. Lett. 80, 1079-1084] the authors present sharp bounds for the probability R_k,n of having k successes out of n exchangeable Bernoulli trials, as a function of the marginal probability of success. The result is obtained by linear programming arguments. In this paper we develop further the result utilizing a geometrical approach to the problem, and find sharp bounds for R_k,n given the marginal probability of success and the correlation among the exchangeable variables.     

Sparse solutions to random standard quadratic optimization problems

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.     

Analysis of a queueing system with a general service scheduling function,with applications to telecommunication network traffic control

In this paper we analyze a queueing system with a general service scheduling function. There are two types of customer with different service requirements. The service order for customers of each type is determined by the service scheduling function α_k(i, j) where α_k(i, j) is the probability for type-k customer to be selected when there are i type-1 and j type-2 customers. This model is motivated by traffic control to support traffic streams with different traffic characteristics in telecommunication networks (in particular, ATM networks). By using the embedded Markov chain and supplementary variable methods, we obtain the queue-length distribution as well as the loss probability and the mean waiting time for each type of customer. We also apply our model to traffic control to support diverse traffics in telecommunication networks. Finally, the performance measures of the existing diverse scheduling policies are compared. We expect to help the system designers select appropriate scheduling policy for their systems.     

Majorization and some operator monotone functions

Let h(t) be a non-decreasing function on I and k(t) an increasing function on J. Then h is said to be majorized by k if k(A)≦k(B) implies h(A)≦h(B). f(t) is operator monotone, by definition, if f(t) is majorized by t. By making use of this majorization we will show that is operator monotone on [0,∞) for 0≦a,b<∞ and for 0≦r≦1; the special case of a=b=1 is the theorem due to Petz-Hasegawa.     

Functions, Measures, and Equipartitioning Convex k-Fans

A k-fan in the plane is a point x∈?² and k halflines starting from x. There are k angular sectors σ ₁,…,σ _k between consecutive halflines. The k-fan is convex if every sector is convex. A (nice) probability measure μ is equipartitioned by the k-fan if μ(σ _i )=1/k for every sector. One of our results: Given a nice probability measure μ and a continuous function f defined on sectors, there is a convex 5-fan equipartitioning μ with f(σ ₁)=f(σ ₂)=f(σ ₃).     

Markov decision processes with noise-corrupted and delayed state observations

We consider the partially observed Markov decision process with observations delayed by k time periods. We show that at stage t, a sufficient statistic is the probability distribution of the underlying system state at stage t - k and all actions taken from stage t - k through stage t - 1. We show that improved observation quality and/or reduced data delay will not decrease the optimal expected total discounted reward, and we explore the optimality conditions for three important special cases. We present a measure of the marginal value of receiving state observations delayed by (k - 1) stages rather than delayed by k stages. We show that in the limit as k →∞ the problem is equivalent to the completely unobserved case. We present numerical examples which illustrate the value of receiving state information delayed by k stages.     

Information spreading in Delay Tolerant Networks based on nodes’ behaviors

Information spreading in DTNs (Delay Tolerant Networks) adopts a store–carry–forward method, and nodes receive the message from others directly. However, it is hard to judge whether the information is safe in this communication mode. In this case, a node may observe other nodes’ behaviors. At present, there is no theoretical model to describe the varying rule of the nodes’ trusting level. In addition, due to the uncertainty of the connectivity in DTN, a node is hard to get the global state of the network. Therefore, a rational model about the node’s trusting level should be a function of the node’s own observing result. For example, if a node finds k nodes carrying a message, it may trust the information with probability p(k). This paper does not explore the real distribution of p(k), but instead presents a unifying theoretical framework to evaluate the performance of the information spreading in above case. This framework is an extension of the traditional SI (susceptible-infected) model, and is useful when p(k) conforms to any distribution. Simulations based on both synthetic and real motion traces show the accuracy of the framework. Finally, we explore the impact of the nodes’ behaviors based on certain special distributions through numerical results.     

Degree distribution in random planar graphs

We prove that for each k?0, the probability that a root vertex in a random planar graph has degree k tends to a computable constant dk, so that the expected number of vertices of degree k is asymptotically dkn, and moreover that k_∑dk=1. The proof uses the tools developed by Giménez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of the generating functions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function p(w)=k_∑dkwk. From this we can compute the dk to any degree of accuracy, and derive the asymptotic estimate dk∼c⋅k−1/2qk for large values of k, where q≈0.67 is a constant defined analytically.     

On the first birth and the last death in a generation in a multi-type Markov branching process

In a multi-type continuous time Markov branching process the asymptotic distribution of the first birth in and the last death (extinction) of the kth generation can be determined from the asymptotic behavior of the probability generating function of the vector Z(^k)(t), the size of the kth generation at time t, as t tends to zero or as t tends to infinity, respectively. Apart from an appropriate transformation of the time scale, for a large initial population the generations emerge according to an independent sum of compound multi-dimensional Poisson processes and become extinct like a vector of independent reversed Poisson processes. In the first birth case the results also hold for a multi-type Bellman-Harris process if the life span distributions are differentiable at zero.     

Optimal Linear Bernoulli Factories for Small Mean Problems

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = C p for constant C. Presented here is a new algorithm that for small values of C p, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of C p, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability p _k of heads, and the goal is to simulate a coin flip with probability C ₁ p ₁+? + C _k p _k of heads.