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}\).     

On the outcome of false images of linear <Emphasis Type="Italic">k</Emphasis>-valued functions for composite numbers <Emphasis Type="Italic">k</Emphasis> when the number of variables increases

The problem of constructing discrete functions such that parts of their value sets determine (generate) arbitrary linear functions is considered. A case in which k is a prime number was considered earlier by the author. It is proved that the existence of such partial functions wshen the number of independent variables is no less then two implies they exists for any arbitrary greater number of independent variables. Upper estimates linear with respect to the number of independent variables are proved for the size of the domain of universal functions. The existence of two-variable universal functions is proved for sufficiently large k.     

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.     

Order statistics of uncertain random variables with application to <Emphasis Type="Italic">k</Emphasis>-out-of-<Emphasis Type="Italic">n</Emphasis> system

Uncertain random variables are tools to deal with a mixture of uncertainty and randomness. A new concept of order statistics associated with uncertain random variables is proposed, and is applied to analyze k-out-of-n systems with uncertain random lifetimes. The chance distributions of order statistics of uncertain random variables are derived from the operational law of uncertain random variables. Finally, the reliability of k-out-of-n systems with uncertain random lifetimes is discussed.     

An active set feasible method for large-scale minimization problems with bound constraints

We are concerned with the solution of the bound constrained minimization problem {minf(x), l??x??u}. For the solution of this problem we propose an active set method that combines ideas from projected and nonmonotone Newton-type methods. It is based on an iteration of the form x ^k+1=[x ^k +?? ^k d ^k ]^?, where ?? ^k is the steplength, d ^k is the search direction and [?]^? is the projection operator on the set [l,u]. At each iteration a new formula to estimate the active set is first employed. Then the components $d_{N}^{k}$ of d ^k corresponding to the free variables are determined by a truncated Newton method, and the components $d_{A}^{k}$ of d ^k corresponding to the active variables are computed by a Barzilai-Borwein gradient method. The steplength ?? ^k is computed by an adaptation of the nonmonotone stabilization technique proposed in Grippo et?al. (Numer. Math. 59:779?C805, 1991). The method is a feasible one, since it maintains feasibility of the iterates x ^k , and is well suited for large-scale problems, since it uses matrix-vector products only in the truncated Newton method for computing $d_{N}^{k}$ . We prove the convergence of the method, with superlinear rate under usual additional assumptions. An extensive numerical experimentation performed on an algorithmic implementation shows that the algorithm compares favorably with other widely used codes for bound constrained problems.     

Stability and convergence of a fully discrete local discontinuous Galerkin method for multi-term time fractional diffusion equations

In this paper, a fully discrete local discontinuous Galerkin method for a class of multi-term time fractional diffusion equations is proposed and analyzed. Using local discontinuous Galerkin method in spatial direction and classical L1 approximation in temporal direction, a fully discrete scheme is established. By choosing the numerical flux carefully, we prove that the method is unconditionally stable and convergent with order O(h ^k+1 + (Δt)^2?α ), where k, h, and Δt are the degree of piecewise polynomial, the space, and time step sizes, respectively. Numerical examples are carried out to illustrate the effectiveness of the numerical scheme.     

Mesonic Differential Forms

When M is a differentiable manifold, the exterior differential k -forms on M are the alternate k -linear forms on the tangent bundle T(M) . The mesonic differential k -forms are the k -linear forms on T(M) that are alternate with respect to the variables of odd rank, and also alternate with respect to the variables of even rank. After a reminder about meson algebras, and after the presentation of elementary properties of mesonic forms, this article introduces the mesonic differentiation of mesonic forms, which can be partially compared to the exterior differentiation of exterior forms. Some applications to riemannian manifolds and flat manifolds follow.     

DICE: exploiting <Emphasis Type="Italic">all</Emphasis> bivariate dependencies in binary and multary search spaces

Although some of the earliest Estimation of Distribution Algorithms (EDAs) utilized bivariate marginal distribution models, up to now, all discrete bivariate EDAs had one serious limitation: they were constrained to exploiting only a limited O(d) subset out of all possible \(O(d^{2})\) bivariate dependencies. As a first we present a family of discrete bivariate EDAs that can learn and exploit all \(O(d^{2})\) dependencies between variables, and yet have the same run-time complexity as their more limited counterparts. This family of algorithms, which we label DICE (DIscrete Correlated Estimation of distribution algorithms), is rigorously based on sound statistical principles, and particularly on a modelling technique from statistical physics: dichotomised multivariate Gaussian distributions. Initially (Lane et al. in European Conference on the Applications of Evolutionary Computation, Springer, 1999), DICE was trialled on a suite of combinatorial optimization problems over binary search spaces. Our proposed dichotomised Gaussian (DG) model in DICE significantly outperformed existing discrete bivariate EDAs; crucially, the performance gap increasingly widened as dimensionality of the problems increased. In this comprehensive treatment, we generalise DICE by successfully extending it to multary search spaces that also allow for categorical variables. Because correlation is not wholly meaningful for categorical variables, interactions between such variables cannot be fully modelled by correlation-based approaches such as in the original formulation of DICE. Therefore, here we extend our original DG model to deal with such situations. We test DICE on a challenging test suite of combinatorial optimization problems, which are defined mostly on multary search spaces. While the two versions of DICE outperform each other on different problem instances, they both outperform all the state-of-the-art bivariate EDAs on almost all of the problem instances. This further illustrates that these innovative DICE methods constitute a significant step change in the domain of discrete bivariate EDAs.     

Membership of distributions of polynomials in the Nikolskii–Besov class

The main result of this paper asserts that the distribution density of any non-constant polynomial f(ξ₁,ξ₂,...) of degree d in independent standard Gaussian random variables ξ₁ (possibly, in infinitely many variables) always belongs to the Nikol’skii–Besov space B^1/d (R¹) of fractional order 1/d (see the definition below) depending only on the degree of the polynomial. A natural analog of this assertion is obtained for the density of the joint distribution of k polynomials of degree d, also with a fractional order that is independent of the number of variables, but depends only on the degree d and the number of polynomials. We also give a new simple sufficient condition for a measure on R^k to possess a density in the Nikol’skii–Besov class B^α(R)^k. This result is applied for obtaining an upper bound on the total variation distance between two probability measures on R^k via the Kantorovich distance between them and a certain Nikol’skii–Besov norm of their difference. Applications are given to estimates of distributions of polynomials in Gaussian random variables.     

Identities for partial Bell polynomials derived from identities for weighted integer compositions

We discuss closed-form formulas for the (n, k)th partial Bell polynomials derived in Cvijovi? (Appl Math Lett 24:1544–1547, 2011). We show that partial Bell polynomials are special cases of weighted integer compositions, and demonstrate how the identities for partial Bell polynomials easily follow from more general identities for weighted integer compositions. We also provide short and elegant probabilistic proofs of the latter, in terms of sums of discrete integer-valued random variables. Finally, we outline further identities for the partial Bell polynomials.     

Unweighted linear congruences with distinct coordinates and the Varshamov–Tenengolts codes

In this paper, we first give explicit formulas for the number of solutions of unweighted linear congruences with distinct coordinates. Our main tools are properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions. Then, as an application, we derive an explicit formula for the number of codewords in the Varshamov–Tenengolts code \(VT_b(n)\) with Hamming weight k, that is, with exactly k 1’s. The Varshamov–Tenengolts codes are an important class of codes that are capable of correcting asymmetric errors on a Z-channel. As another application, we derive Ginzburg’s formula for the number of codewords in \(VT_b(n)\), that is, \(|VT_b(n)|\). We even go further and discuss connections to several other combinatorial problems, some of which have appeared in seemingly unrelated contexts. This provides a general framework and gives new insight into all these problems which might lead to further work.     

On teaching sets for 2-threshold functions of two variables

We consider k-threshold functions of n variables, i.e. the functions representable as the conjunction of k threshold functions. For n = 2, k = 2, we give upper bounds for the cardinality of the minimal teaching set depending on the various properties of the function.     

Some results on the regularization of LSQR for large-scale discrete ill-posed problems

LSQR, a Lanczos bidiagonalization based Krylov subspace iterative method, and its mathematically equivalent conjugate gradient for least squares problems (CGLS) applied to normal equations system, are commonly used for large-scale discrete ill-posed problems. It is well known that LSQR and CGLS have regularizing effects, where the number of iterations plays the role of the regularization parameter. However, it has long been unknown whether the regularizing effects are good enough to find best possible regularized solutions. Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method. We establish bounds for the distance between the k-dimensional Krylov subspace and the k-dimensional dominant right singular space. They show that the Krylov subspace captures the dominant right singular space better for severely and moderately ill-posed problems than for mildly ill-posed problems. Our general conclusions are that LSQR has better regularizing effects for the first two kinds of problems than for the third kind, and a hybrid LSQR with additional regularization is generally needed for mildly ill-posed problems. Exploiting the established bounds, we derive an estimate for the accuracy of the rank k approximation generated by Lanczos bidiagonalization. Numerical experiments illustrate that the regularizing effects of LSQR are good enough to compute best possible regularized solutions for severely and moderately ill-posed problems, stronger than our theory predicts, but they are not for mildly ill-posed problems and additional regularization is needed.     

Three-Webs Defined by Symmetric Functions

We study local differential-geometrical properties of curvilinear k-webs defined by symmetric functions (webs SW(k)). This class of k-webs contains in particular algebraic rectilinear k-webs defined by algebraic curves of genus 0. On a web SW(3), there are three three-parameter families of closed Thomsen configurations. We find equations of a rectilinear web SW(k) in terms of adapted coordinates and prove that the curvature of a symmetric three-web is a skew-symmetric function with respect to adapted coordinates. In conclusion, we formulate some open problems.     

Bose–Einstein condensation in satisfiability problems

This paper is concerned with the complex behavior arising in satisfiability problems. We present a new statistical physics-based characterization of the satisfiability problem. Specifically, we design an algorithm that is able to produce graphs starting from a k-SAT instance, in order to analyze them and show whether a Bose–Einstein condensation occurs. We observe that, analogously to complex networks, the networks of k-SAT instances follow Bose statistics and can undergo Bose–Einstein condensation. In particular, k-SAT instances move from a fit-get-rich network to a winner-takes-all network as the ratio of clauses to variables decreases, and the phase transition of k-SAT approximates the critical temperature for the Bose–Einstein condensation. Finally, we employ the fitness-based classification to enhance SAT solvers (e.g., ChainSAT) and obtain the consistently highest performing SAT solver for CNF formulas, and therefore a new class of efficient hardware and software verification tools.     

Tail Behavior of Sums and Maxima of Sums of Dependent Subexponential Random Variables

In this paper, we consider dependent random variables X _k , k=1,2,?? with supports on [?b _k ,??), respectively, where the b _k ??0 are some finite constants. We derive asymptotic results on the tail probabilities of the quantities $S_{n}=\sum_{k=1}^{n} X_{k}$ , X _(n)=max?_1??k??n X _k and S _(n)=max?_1??k??n S _k , n??1 in the case where the random variables are dependent with heavy-tailed (subexponential) distributions, which substantially generalize the results of Ko and Tang (J. Appl. Probab. 45, 85?C94, 2008).     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

Monotonic optimization based decoding for linear codes

New efficient methods are developed for the optimal maximum-likelihood (ML) decoding of an arbitrary binary linear code based on data received from any discrete Gaussian channel. The decoding algorithm is based on monotonic optimization that is minimizing a difference of monotonic (d.m.) objective functions subject to the 0–1 constraints of bit variables. The iterative process converges to the global optimal ML solution after finitely many steps. The proposed algorithm’s computational complexity depends on input sequence length k which is much less than the codeword length n, especially for a codes with small code rate. The viability of the developed is verified through simulations on different coding schemes.     

A criterion for positive completeness in ternary logic

The operator of positive closure is considered on the set P _k of functions of k-valued logic. Some positive complete systems of functions are defined. It is proved that every positive complete class of functions from P _k is positive generated by the set of all functions depending on at most k variables. For each k ? 3, the three families of positive precomplete classes are defined. It is shown that, for k = 3, the 10 classes of these families constitute a criterion system.     

Coloring Geometric Range Spaces

We study several coloring problems for geometric range-spaces. In addition to their theoretical interest, some of these problems arise in sensor networks. Given a set of points in ?² or ?³, we want to color them so that every region of a certain family (e.g., every disk containing at least a certain number of points) contains points of many (say, k) different colors. In this paper, we think of the number of colors and the number of points as functions of k. Obviously, for a fixed k using k colors, it is not always possible to ensure that every region containing k points has all colors present. Thus, we introduce two types of relaxations: either we allow the number of colors used to increase to c(k), or we require that the number of points in each region increases to p(k).Symmetrically, given a finite set of regions in ?² or ?³, we want to color them so that every point covered by a sufficiently large number of regions is contained in regions of k different colors. This requires the number of covering regions or the number of allowed colors to be greater than k.The goal of this paper is to bound these two functions for several types of region families, such as halfplanes, halfspaces, disks, and pseudo-disks. This is related to previous results of Pach, Tardos, and Tóth on decompositions of coverings.