Search results for "probabilistic"
showing 10 items of 380 documents
Running time to recognize nonregular languages by 2-way probabilistic automata
1991
R. Freivalds proved that the language {0m1m} can be recognized by 2-way probabilistic finite automata (2pfa) with arbitrarily high probability 1-ɛ. A.G.Greenberg and A.Weiss proved that no 2pfa can recognize this language in expected time \(T(n) = c^\circ{(n)}\). For arbitrary languages C.Dwork and L.Stockmeyer showed somewhat less: if a language L is recognized by a 2pfa in expected time \(T(n) = c^{n^\circ{(1)} }\), then L is regular. First, we improve this theorem replacing the expected time by the time with probability 1-ɛ. On the other hand, time bound by C.Dwork and L.Stockmeyer cannot be improved: for arbitrary k≥2 we exhibit a specific nonregular language that can be recognized by 2…
Iterated Conditionals and Characterization of P-Entailment
2021
In this paper we deepen, in the setting of coherence, some results obtained in recent papers on the notion of p-entailment of Adams and its relationship with conjoined and iterated conditionals. We recall that conjoined and iterated conditionals are suitably defined in the framework of conditional random quantities. Given a family \(\mathcal {F}\) of n conditional events \(\{E_{1}|H_{1},\ldots , E_{n}|H_{n}\}\) we denote by \(\mathcal {C}(\mathcal {F})=(E_{1}|H_{1})\wedge \cdots \wedge (E_{n}|H_{n})\) the conjunction of the conditional events in \(\mathcal F\). We introduce the iterated conditional \(\mathcal {C}(\mathcal {F}_{2})|\mathcal {C}(\mathcal {F}_{1})\), where \(\mathcal {F}_{1}\)…
Values of games with probabilistic graphs
1999
Abstract In this paper we consider games with probabilistic graphs. The model we develop is an extension of the model of games with communication restrictions by Myerson (1977) . In the Myerson model each pair of players is joined by a link in the graph if and only if these two players can communicate directly. The current paper considers a more general setting in which each pair of players has some probability of direct communication. The value is defined and characterized in this context. It is a natural extension of the Myerson value and it turns out to be the Shapley value of a modified game.
REPEATED GAMES WITH PROBABILISTIC HORIZON
2005
Repeated games with probabilistic horizon are defined as those games where players have a common probability structure over the length of the game's repetition, T. In particular, for each t, they assign a probability pt to the event that "the game ends in period t". In this framework we analyze Generalized Prisoners' Dilemma games in both finite stage and differentiable stage games. Our construction shows that it is possible to reach cooperative equilibria under some conditions on the distribution of the discrete random variable T even if the expected length of the game is finite. More precisely, we completely characterize the existence of sub-game perfect cooperative equilibria in finite s…
Memory limited inductive inference machines
1992
The traditional model of learning in the limit is restricted so as to allow the learning machines only a fixed, finite amount of memory to store input and other data. A class of recursive functions is presented that cannot be learned deterministically by any such machine, but can be learned by a memory limited probabilistic leaning machine with probability 1.
Seismic evaluation of ordinary RC buildings retrofitted with externally bonded FRPs using a reliability-based approach
2020
International audience; Despite the extensive literature on reinforced concrete (RC) members retrofitted with fiberreinforced polymer (FRP) composites, few studies have employed a reliability-based approach to evaluate the seismic performance of RC buildings in terms of their collapse capacity and ductility. In this study, the performance of a poorly-confined RC building structure is investigated for different FRP retrofitting schemes using different configurations and combinations of wrapping and flange-bonded FRPs, as two well-established techniques. A nonlinear pushover analysis is then implemented with a computational reliability analysis based on Latin Hypercube Sampling (LHS) to deter…
Iteratively Learning a Liver Segmentation Using Probabilistic Atlases: Preliminary Results
2016
This works deals with the concept of liver segmentation by using a priori information based on probabilistic atlases and segmentation learning based of previous steps. A probabilistic atlas is here understood as a probability or membership map that tells how likely is that a point belongs to a shape drawn from the shape distribution at hand. We devise a procedure to segment Perfusion Magnetic Resonance liver images that combines both: a probabilistic atlas of the liver and a segmentation algorithm based on global information of previous simpler segmentation steps, local information from close segmented slices and finally a mathematical morphology procedure, namely viscous reconstruction, to…
Improving Lossless Image Compression with Contextual Memory
2019
With the increased use of image acquisition devices, including cameras and medical imaging instruments, the amount of information ready for long term storage is also growing. In this paper we give a detailed description of the state-of-the-art lossless compression software PAQ8PX applied to grayscale image compression. We propose a new online learning algorithm for predicting the probability of bits from a stream. We then proceed to integrate the algorithm into PAQ8PX&rsquo
Probabilistic Self-Localization and Mapping - An Asynchronous Multirate Approach
2008
[EN] In this paper, we present a set of robust and efficient algorithms with O(N) cost for the solution of the Simultaneous Localization And Mapping (SLAM) problem of a mobile robot. First, we introduce a novel object detection method, which is mainly based on multiple line fitting method for landmark detection with regular constrained angles. Second, a line-based pose estimation method is proposed, based on LeastSquares (LS). This method performs the matching of lines, providing the global pose estimation under assumption of known Data-Association. Finally, we extend the FastSLAM (FActored Solution To SLAM) algorithm for mobile robot self-localisation and mapping by considering the asynchr…
Probabilistic characterization of flood hazard using bivariate analysis based on copulas
2014
This study presents an innovative approach to obtain flood hazard maps where hydrological input (synthetic flood design event) to a 2D hydraulic model has been defined by generating flood peak discharges and volumes from a bivariate statistical analysis, through the use of copulas. Synthetic hydrographs were generated by means two different approaches: an indirect one, where rainfall were generated by a stochastic bivariate rainfall generator to be entered a distributed conceptual rainfall-runoff model that consisted of a soil moisture routine and a flow routing routine; and a direct one, where stochastic generation of flood peaks and flow volumes have been obtained via copulas, which descr…