SampleSearch: Importance sampling in presence of determinism

The paper focuses on developing effective importance sampling algorithms for mixed probabilistic and deterministic graphical models. The use of importance sampling in such graphical models is problematic because it generates many useless zero weight samples which are rejected yielding an inefficient sampling process. To address this rejection problem, we propose the SampleSearch scheme that augments sampling with systematic constraint-based backtracking search. We characterize the bias introduced by the combination of search with sampling, and derive a weighting scheme which yields an unbiased estimate of the desired statistics (e.g., probability of evidence). When computing the weights exactly is too complex, we propose an approximation which has a weaker guarantee of asymptotic unbiasedness. We present results of an extensive empirical evaluation demonstrating that SampleSearch outperforms other schemes in presence of significant amount of determinism.     

On Probabilistic Networks for Selection, Merging, and Sorting

We study comparator networks for selection, merging, and sorting that output the correct result with high probability, given a random input permutation. We prove tight bounds, up to constant factors, on the size and depth of probabilistic (n,k)-selection networks. In the case of (n, n/2)-selection, our result gives a somewhat surprising bound of on the size of networks of success probability in , where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size . We also prove tight bounds, up to lower-order terms, on the size and depth of probabilistic merging networks of success probability in , where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least and nearly logarithmic depth. Received January 22, 1996, and in final form February 14, 1997.     

Model checking for a probabilistic branching time logic with fairness

We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL [4, 14] to obtain procedures for PBTL under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized distributed systems. Received: June 1997 / Accepted: May 1998     

Probabilistic Logic over Paths

We introduce a probabilistic modal logic PPL extending the work of [Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Information and Computation, 87(1,2):78–128, 1990; Ronald Fagin and Joseph Y. Halpern. Reasoning about knowledge and probability. Journal of the ACM, 41(2):340–367, 1994] by allowing arbitrary nesting of a path probabilistic operator and we prove its completeness. We prove that our logic is strictly more expressive than other logics such as the logics cited above. By considering a probabilistic extension of CTL we show that this additional expressive power is really needed in some applications.     

On Approximate Majority and Probabilistic Time

We prove new results on the circuit complexity of approximate majority, which is the problem of computing the majority of a given bit string whose fraction of 1’s is bounded away from 1/2 (by a constant). We then apply these results to obtain new relationships between probabilistic time, BPTime (t), and alternating time, ∑_O(1)Time (t). Our main results are the following:

Testing axioms for quantum theory on probabilistic toy-theories

In D’Ariano in Philosophy of Quantum Information and Entanglement, Cambridge University Press, Cambridge, UK (2010), one of the authors proposed a set of operational postulates to be considered for axiomatizing Quantum Theory. The underlying idea is to derive Quantum Theory as the mathematical representation of a fair operational framework, i.e. a set of rules which allows the experimenter to make predictions on future events on the basis of suitable tests, e.g. without interference from uncontrollable sources and having local control and low experimental complexity. In addition to causality, two main postulates have been considered: PFAITH (existence of a pure preparationally faithful state), and FAITHE (existence of a faithful effect). These postulates have exhibited an unexpected theoretical power, excluding all known nonquantum probabilistic theories. In the same paper also postulate PURIFY-1 (purifiability of all states) has been introduced, which later has been reconsidered in the stronger version PURIFY-2 (purifiability of all states unique up to reversible channels on the purifying system) in Chiribella et al. (Reversible realization of physical processes in probabilistic theories, arXiv:0908.1583). There, it has been shown that Postulate PURIFY-2, along with causality and local discriminability, narrow the probabilistic theory to something very close to the quantum one. In the present paper we test the above postulates on some nonquantum probabilistic models. The first model—the two-box world—is an extension of the Popescu–Rohrlich model (Found Phys, 24:379, 1994), which achieves the greatest violation of the CHSH inequality compatible with the no-signaling principle. The second model—the two-clock world— is actually a full class of models, all having a disk as convex set of states for the local system. One of them corresponds to—the two-rebit world— namely qubits with real Hilbert space. The third model—the spin-factor—is a sort of n-dimensional generalization of the clock. Finally the last model is the classical probabilistic theory. We see how each model violates some of the proposed postulates, when and how teleportation can be achieved, and we analyze other interesting connections between these postulate violations, along with deep relations between the local and the non-local structures of the probabilistic theory.     

Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source

For a Markovian source, we analyze the Lempel—Ziv parsing scheme that partitions sequences into phrases such that a new phrase is the shortest phrase not seen in the past. We consider three models: In the Markov Independent model, several sequences are generated independently by Markovian sources, and the ith phrase is the shortest prefix of the ith sequence that was not seen before as a phrase (i.e., a prefix of previous (i-1) sequences). In the other two models, only a single sequence is generated by a Markovian source. In the second model, called the Gilbert—Kadota model, a fixed number of phrases is generated according to the Lempel—Ziv algorithm, thus producing a sequence of a variable (random) length. In the last model, known also as the Lempel—Ziv model, a string of fixed length is partitioned into a variable (random) number of phrases. These three models can be efficiently represented and analyzed by digital search trees that are of interest to other algorithms such as sorting, searching, and pattern matching. In this paper we concentrate on analyzing the average profile (i.e., the average number of phrases of a given length), the typical phrase length, and the length of the last phrase. We obtain asymptotic expansions for the mean and the variance of the phrase length, and we prove that appropriately normalized phrase length in all three models tends to the standard normal distribution, which leads to bounds on the average redundancy of the Lempel—Ziv code. For the Markov Independent model, this finding is established by analytic methods (i.e., generating functions, Mellin transform, and depoissonization), while for the other two models we use a combination of analytic and probabilistic analyses. Received June 6, 2000; revised January 14, 2001.     

Space Hierarchy Results for Randomized and other Semantic Models

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice where a machine is only required to behave appropriately when given the correct advice sequence. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems deal with space-bounded randomized machines that always halt. Let s(n) be any space-constructible monotone function that is Ω(log n) and let s′(n) be any function such that s′(n) = ω(s(n + as(n))) for all constants a.

Lower bounds for the majority communication complexity of various graph accessibility problems

We investigate the probabilistic communication complexity (more exactly, the majority communication complexity), of the graph accessibility problem (GAP) and its counting versions MOD _k -GAP,k ≥ 2. Due to arguments concerning matrix variation ranks and certain projection reductions, we prove that, for any partition of the input variables, GAP and MOD _m -GAP have majority communication complexity Ω,(n), wheren denotes the number of nodes of the graph under consideration.     

Probabilistic π-Calculus and Event Structures

This paper proposes two semantics of a probabilistic variant of the π-calculus: an interleaving semantics in terms of Segala automata and a true concurrent semantics, in terms of probabilistic event structures. The key technical point is a use of types to identify a good class of non-deterministic probabilistic behaviours which can preserve a compositionality of the parallel operator in the event structures and the calculus. We show an operational correspondence between the two semantics. This allows us to prove a “probabilistic confluence” result, which generalises the confluence of the linearly typed π-calculus.     

Fast computation of the Smith form of a sparse integer matrix

We present a new probabilistic algorithm to compute the Smith normal form of a sparse integer matrix . The algorithm treats A as a “black box”—A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about black box evaluations for word-sized primes p and , plus additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no “fill-in” or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about bit operations, where O(MM(m)) operations are sufficient to multiply two matrices over a field. Both algorithms are probabilistic of the Monte Carlo type — on any input they return the correct answer with a controllable, exponentially small probability of error. Received: March 9, 2000.     

Complexity of identification of linear systems with rational transfer functions

We study the complexity of worst-case time-domain identification of linear time-invariant systems using model sets consisting of degree-n rational models with poles in a fixed region of the complex plane. For specific noise level δ and tolerance levels τ, the number of required output samples and the total sampling time should be as small as possible. In discrete time, using known fractional covers for certain polynomial spaces (with the same norm), we show that the complexity isO(n ²) for theH ^∞ norm,O(n) for the ℓ² norm, and exponential inn for the ℓ¹ norm, for each δ and τ. We also show that these bounds are tight. For the continuous-time case we prove analogous results, and show that the input signals may be compactly supported step functions with equally spaced nodes. We show, however, that the internodal spacing must approach 0 asn increases.     

Approximation of functions by means of a new generalized Bernstein operator

In this paper we first use a probabilistic method to construct a linear positive polynomial operatorL _{m, r} ^α,β Bernstein type, depending on a non-negative integer parameterr and on two real parameters α and β, such that 0≤α≤β. Then we investigate the approximation properties of this operator mapping into itself the Banach spaceC[0,1] of real-valued continuous functions on [0,1]. A special attention is accorded to the case of the operatorL _m,r=L _m,r ^0,0 . We prove that the remainder of the approximation formula of a functionfεC[0,1] byL _m,r f can be represented either by means of divided differences, or in an integral form, obtained by using a classical theorem of Peano. We give also an asymptotic estimate for this remainder. The operatorL _m,r enjoys the variation diminishing property—in the sense of I. J. Schoenberg [15]. By extending the known inequalities of T. Popoviciu [12] and G. G. Lorentz [7], we evaluate the orders of approximation in terms of the modulus of continuity of the functionf or of its derivative. In the last section of this paper we determine the point spectrum of the operatorL _m,r and , finally, we present a quadrature formula which can be constructed by means of this operator. Dedicated to Professor Aldo Ghizzetti on his 75th birthday     

PMaude: Rewrite-based Specification Language for Probabilistic Object Systems

We introduce a rewrite-based specification language for modelling probabilistic concurrent and distributed systems. The language, based on PMaude, has both a rigorous formal basis and the characteristics of a high-level rule-based programming language. Furthermore, we provide tool support for performing discrete-event simulations of models written in PMaude, and for statistically analyzing various quantitative aspects of such models based on the samples that are generated through discrete-event simulation. Because distributed and concurrent communication protocols can be modelled using actors (concurrent objects with asynchronous message passing), we provide an actor PMaude module. The module aids writing specifications in a probabilistic actor formalism. This allows us to easily write specifications that are purely probabilistic – and not just non-deterministic. The absence of such (un-quantified) non-determinism in a probabilistic system is necessary for a form of statistical analysis that we also discuss. Specifically, we introduce a query language called Quantitative Temporal Expressions (or QuaTEx in short), to query various quantitative aspects of a probabilistic model. We also describe a statistical technique to evaluate QuaTEx expressions for a probabilistic model.     

General <Emphasis Type="Italic">E</Emphasis>-unification with Eager Variable Elimination and a Nice Cycle Rule

We present a goal-directed E-unification procedure with eager Variable Elimination and a new rule, Cycle, for the case of collapsing equations – that is, equations of the type x ≈ v where x ∈Var(v). Cycle replaces Variable Decomposition (or the so-called Root Imitation) and thus removes possibility of some obviously unnecessary infinite paths of inferences in the E-unification procedure. We prove that, as in other approaches, such inferences into variable positions in our goal-directed procedure are not needed. Our system is independent of selection rule and complete for any E-unification problem.     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

Probabilistic logic under coherence: complexity and algorithms

In previous work [V. Biazzo, A. Gilio, T. Lukasiewicz and G. Sanfilippo, Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in System P, Journal of Applied Non-Classical Logics 12(2) (2002) 189–213.], we have explored the relationship between probabilistic reasoning under coherence and model-theoretic probabilistic reasoning. In particular, we have shown that the notions of g-coherence and of g-coherent entailment in probabilistic reasoning under coherence can be expressed by combining notions in model-theoretic probabilistic reasoning with concepts from default reasoning. In this paper, we continue this line of research. Based on the above semantic results, we draw a precise picture of the computational complexity of probabilistic reasoning under coherence. Moreover, we introduce transformations for probabilistic reasoning under coherence, which reduce an instance of deciding g-coherence or of computing tight intervals under g-coherent entailment to a smaller problem instance, and which can be done very efficiently. Furthermore, we present new algorithms for deciding g-coherence and for computing tight intervals under g-coherent entailment, which reformulate previous algorithms using terminology from default reasoning. They are based on reductions to standard problems in model-theoretic probabilistic reasoning, which in turn can be reduced to linear optimization problems. Hence, efficient techniques for model-theoretic probabilistic reasoning can immediately be applied for probabilistic reasoning under coherence (for example, column generation techniques). We describe several such techniques, which transform problem instances in model-theoretic probabilistic reasoning into smaller problem instances. We also describe a technique for obtaining a reduced set of variables for the associated linear optimization problems in the conjunctive case, and give new characterizations of this reduced set as a set of non-decomposable variables, and using the concept of random gain. This paper is a substantially extended and revised version of a preliminary paper that appeared in: Proceedings of the Second International Symposium on Imprecise Probabilities and Their Applications (ISIPTA '01), pp. 51–61, 2001.