Asymptotic expansions for the conditional sojourn time distribution in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1-PS queue

We consider the M/M/1 queue with processor sharing. We study the conditional sojourn time distribution, conditioned on the customer’s service requirement, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. The asymptotic formulas relate to, and extend, some results of Morrison (SIAM J. Appl. Math. 45:152–167, [1985]) and Flatto (Ann. Appl. Probab. 7:382–409, [1997]). This work was partly supported by NSF grant DMS 05-03745.     

NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach

In this paper we investigate the problem of testing the coherence of an assessment of conditional probability following a purely logical setting. In particular we will prove that the coherence of an assessment of conditional probability χ can be characterized by means of the logical consistency of a suitable theory T _χ defined on the modal-fuzzy logic FP _k (RŁ_Δ) built up over the many-valued logic RŁ_Δ. Such modal-fuzzy logic was previously introduced in Flaminio (Lecture Notes in Computer Science, vol. 3571, 2005) in order to treat conditional probability by means of a list of simple probabilities following the well known (smart) ideas exposed by Halpern (Proceedings of the eighth conference on theoretical aspects of rationality and knowledge, pp 17–30, 2001) and by Coletti and Scozzafava (Trends Logic 15, 2002). Roughly speaking, such logic is obtained by adding to the language of RŁ_Δ a list of k modalities for “probably” and axioms reflecting the properties of simple probability measures. Moreover we prove that the satisfiability problem for modal formulas of FP _k (RŁ_Δ) is NP-complete. Finally, as main result of this paper, we prove FP _k (RŁ_Δ) in order to prove that the problem of establishing the coherence of rational assessments of conditional probability is NP-complete.      

A Conditional 0–1 Law for the Symmetric <Emphasis Type="Italic">σ</Emphasis>-field

Let (Ω,ℬ,P) be a probability space, a sub-σ-field, and μ a regular conditional distribution for P given . For various, classically interesting, choices of (including tail and symmetric), we prove the following 0–1 law: There is a set such that P(A ₀)=1 and μ(ω)(A)∈{0,1} for all and ω∈A ₀. If ℬ is countably generated (and certain regular conditional distributions exist), the result applies whatever P is.      

Modal operators on bounded commutative residuated <Emphasis Type="Italic">ℓ</Emphasis>-monoids

Bounded commutative residuated lattice ordered monoids (Rℓ-monoids) are a common generalization of, e.g., Heyting algebras and BL-algebras, i.e., algebras of intuitionistic logic and basic fuzzy logic, respectively. Modal operators (special cases of closure operators) on Heyting algebras were studied in [MacNAB, D. S.: Modal operators on Heyting algebras, Algebra Universalis 12 (1981), 5–29] and on MV-algebras in [HARLENDEROVá,M.—RACHŮNEK, J.: Modal operators on MV-algebras, Math. Bohem. 131 (2006), 39–48]. In the paper we generalize the notion of a modal operator for general bounded commutative Rℓ-monoids and investigate their properties also for certain derived algebras. The first author was supported by the Council of Czech Government, MSM 6198959214.     

A Lower Bound of <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> Norms in the CLT for Strongly Mixing Random Variables

We derive a lower bound of L _p norms, 1 ⩽ p ⩽ ∞, in the central limit theorem for strongly mixing random variables X ₁,..., X _n with under the boundedness condition ℙ{|X _i | ⩽ M} = 1 with a nonrandom constantM > 0 and condition ∑ _r⩾1 r ²α(r) < ∞, where α(r) are the Rosenblatt strong mixing coefficients. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 4, pp. 587–602, October–December, 2005.     

Age-dependent branching processes in random environments

We consider an age-dependent branching process in random environments. The environments are represented by a stationary and ergodic sequence ξ = (ξ0,ξ1,...) of random variables. Given an environment ξ, the process is a non-homogenous Galton-Watson process, whose particles in n-th generation have a life length distribution G(ξn) on R , and reproduce independently new particles according to a probability law p(ξn) on N. Let Z(t) be the number of particles alive at time t. We first find a characterization of the conditional probability generating function of Z(t) (given the environment ξ) via a functional equation, and obtain a criterion for almost certain extinction of the process by comparing it with an embedded Galton-Watson process. We then get expressions of the conditional mean EξZ(t) and the global mean EZ(t), and show their exponential growth rates by studying a renewal equation in random environments.     

Concavity of the conditional mean sojourn time in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 processor-sharing queue with batch arrivals

Avrachenkov et al. (Queueing Syst. 50:459–480, [2005]) conjectured that in an M/G/1 processor-sharing queue with batch arrivals, the conditional mean sojourn time is concave. In this paper, we show that this conjecture is generally not true. This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-312-C00470).     

Unilateral <Emphasis Type="Italic">o</Emphasis>-Groups

For a big number of varieties of groups close to Engelian, it is proved that a variety of lattice-ordered groups generated by all linearly ordered groups in the class does not coincide with the variety of all o-approximable lattice-ordered groups. Supported by FP “Universities of Russia” grant No. UR.04.01.001. __________ Translated from Algebra i Logika, Vol. 45, No. 1, pp. 20–27, January–February, 2006.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/∞ system revisited: finiteness,summability, long range dependence,and reverse engineering

We explore M/G/∞ systems ‘fed’ by Poissonian inflows with infinite arrival rates. Three processes – corresponding to the system's state, workload, and queue-size – are studied and analyzed. Closed form formulae characterizing the system's stationary structure and correlation structure are derived. And, the issues of queue finiteness, workload summability, and Long Range Dependence are investigated. We then turn to devise a ‘reverse engineering’ scheme for the design of the system's correlation structure. Namely: how to construct an M/G/∞ system with a pre-desired ‘target’ workload/queue auto-covariance function. The ‘reverse engineering’ scheme is applied to various examples, including ones with infinite queues and non-summable workloads. AMS Subject Classifications Primary: 60K25; Secondary: 60G55, 60G10     

Improved lower bounds on sizes of single-error correcting codes

A construction of codes of length n = q + 1 and minimum Hamming distance 3 over is given. Substitution of the derived codes into a concatenation construction yields nonlinear binary single-error correcting codes with better than known parameters. In particular, new binary single-error correcting codes having more codewords than the best previously known in the range n ≤ 512 are obtained for the lengths 64–66, 128–133, 256–262, and 512.     

<Emphasis Type="Italic">I</Emphasis>-projection onto isotonic cones and its applications to maximum likelihood estimation for log-linear models

A frequently occurring problem is to find a probability vector,p∈D, which minimizes theI-divergence between it and a given probability vector π. This is referred to as theI-projection of π ontoD. Darroch and Ratcliff (1972,Ann. Math. Statist.,43, 1470–1480) gave an algorithm whenD is defined by some linear equalities and in this paper, for simplicity of exposition, we propose an iterative procedure whenD is defined by some linear inequalities. We also discuss the relationship betweenI-projection and the maximum likelihood estimation for multinomial distribution. All of the results can be applied to isotonic cone.     

Stability and Instance Optimality for Gaussian Measurements in Compressed Sensing

In compressed sensing, we seek to gain information about a vector x∈ℝ ^N from d ≪ N nonadaptive linear measurements. Candes, Donoho, Tao et al. (see, e.g., Candes, Proc. Intl. Congress Math., Madrid, 2006; Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006; Donoho, IEEE Trans. Inf. Theory 52:1289–1306, 2006) proposed to seek a good approximation to x via ℓ ₁ minimization. In this paper, we show that in the case of Gaussian measurements, ℓ ₁ minimization recovers the signal well from inaccurate measurements, thus improving the result from Candes et al. (Commun. Pure Appl. Math. 59:1207–1223, 2006). We also show that this numerically friendly algorithm (see Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006) with overwhelming probability recovers the signal with accuracy, comparable to the accuracy of the best k-term approximation in the Euclidean norm when k∼d/ln N.     

Probabilistic Choice in Games: Properties of Rosenthal’s t-Solutions

The t-solutions introduced in R. W. Rosenthal (1989, Int J Game Theory 18:273–292) are quantal response equilibria based on the linear probability model. Choice probabilities in t-solutions are related to the determination of leveling taxes in taxation problems. The set of t-solutions coincides with the set of Nash equilibria of a game with quadratic control costs. Evaluating the set of t-solutions for increasing values of t yields that players become increasingly capable of iteratively eliminating never-best replies and eventually only play rationalizable actions with positive probability. These features are not shared by logit quantal response equilibria. Moreover, there exists a path of t-solutions linking uniform randomization to Nash equilibrium     

On fractional moments of Dirichlet <Emphasis Type="Italic">L</Emphasis>-functions,II

We obtain upper and lower bounds for fractional moments of Dirichlet L-functions. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 4, pp. 606–621, October–December, 2006.     

On the Waiting Time for the First Success Run

Let k and m are positive integers with k ≥ m. The probability generating function of the waiting time for the first occurrence of consecutive k successes in a sequence of m-th order Markov dependent trials is given as a function of the conditional probability generating functions of the waiting time for the first occurrence of consecutive m successes. This provides an efficient algorithm for obtaining the probability generating function when k is large. In particular, in the case of independent trials a simple relationship between the geometric distribution of order k and the geometric distribution of order k−1 is obtained. This research was partially supported by the ISM Cooperative Research Program(2004-ISM-CRP-2006) and by a Grant-in-Aid for Scientific Research (C) of the JSPI (Grant Number 16500183)     

Many-Place Sequent Calculi for Finitely-Valued Logics

In this paper, we study multiplicative extensions of propositional many-place sequent calculi for finitely-valued logics arising from those introduced in Sect. 5 of Pynko (J Multiple-Valued Logic Soft Comput 10:339–362, 2004) through their translation by means of singularity determinants for logics and restriction of the original many-place sequent language. Our generalized approach, first of all, covers, on a uniform formal basis, both the one developed in Sect. 5 of Pynko (J Multiple-Valued Logic Soft Comput 10:339–362, 2004) for singular finitely-valued logics (when singularity determinants consist of a variable alone) and conventional Gentzen-style (i.e., two-place sequent) calculi suggested in Pynko (Bull Sect Logic 33(1):23–32, 2004) for finitely-valued logics with equality determinant. In addition, it provides a universal method of constructing Tait-style (i.e., one-place sequent) calculi for finitely-valued logics with singularity determinant (in particular, for Łukasiewicz finitely-valued logics) that fits the well-known Tait calculus (Lecture Notes in Mathematics, Springer, Berlin, 1968) for the classical logic. We properly extend main results of Pynko (J Multiple-Valued Logic Soft Comput 10:339–362, 2004) and explore calculi under consideration within the framework of Sect. 7 of Pynko (Arch Math Logic 45:267–305, 2006), generalizing the results obtained in Sect. 7.5 of Pynko (Arch Math Logic 45:267–305 2006) for two-place sequent calculi associated with finitely-valued logics with equality determinant according to Pynko (Bull Sect Logic 33(1):23–32, 2004). We also exemplify our universal elaboration by applying it to some denumerable families of well-known finitely-valued logics.     

Generalized Waiting Time Problems Associated with Pattern in Polya's Urn Scheme

Let X ₁, X ₂, ... be a sequence obtained by Polya's urn scheme. We consider a waiting time problem for the first occurrence of a pattern in the sequence X ₁, X ₂, ... , which is generalized by a notion score. The main part of our results is derived by the method of generalized probability generating functions. In Polya's urn scheme, the system of equations is composed of the infinite conditional probability generating functions, which can not be solved. Then, we present a new methodology to obtain the truncated probability generating function in a series up to an arbitrary order from the system of infinite equations. Numerical examples are also given in order to illustrate the feasibility of our results. Our results in this paper are not only new but also a first attempt to treat the system of infinite equations.     

<Emphasis Type="Italic">m</Emphasis>-Dissipativity of Some Gradient Systems with Measurable Potential

We consider the operator in L ²(B, ν) and in L ¹(B, ν) with Neumann boundary condition, where U is an unbounded function belonging to for some q ∈(1, ∞), B is the possibly unbounded convex open set in where U is finite and ν(dx) = C exp (−2U (x))dx is a probability measure, infinitesimally invariant for N ₀. We prove that the closure of N ₀ is a m-dissipative operator both in L ²(B, ν) and in L ¹(B, ν). Moreover we study the properties of ergodicity and strong mixing of the measure ν in the L ² case.      

The Width-Volume Inequality

We prove that a bounded open set U in has k-width less than C(n) Volume(U) ^k/n . Using this estimate, we give lower bounds for the k-dilation of degree 1 maps between certain domains in . In particular, we estimate the smallest (n – 1)-dilation of any degree 1 map between two n-dimensional rectangles. For any pair of rectangles, our estimate is accurate up to a dimensional constant C(n). We give examples in which the (n – 1)-dilation of the linear map is bigger than the optimal value by an arbitrarily large factor. Received: January 2006, Revision: May 2006, Accepted: June 2006