Search results for "probability"

Stochastic Learning for SAT- Encoded Graph Coloring Problems

2010

The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.

Graphical representation of some duality relations in stochastic population models

2007

We derive a unified stochastic picture for the duality of a resampling-selection model with a branching-coalescing particle process (cf. http://www.ams.org/mathscinet-getitem?mr=MR2123250) and for the self-duality of Feller's branching diffusion with logistic growth (cf. math/0509612). The two dual processes are approximated by particle processes which are forward and backward processes in a graphical representation. We identify duality relations between the basic building blocks of the particle processes which lead to the two dualities mentioned above.

Functional Data Analysis with R and Matlab by RAMSAY, J. O., HOOKER, G., and GRAVES, S.

2010

Searching for a strong double tracing in a graph

1998

Given a connected graph G, we present a polynomial algorithm which either finds a tour traversing each edge of G exactly two non-consecutive times, one in each direction, or decides that no such tour exists. The main idea of this algorithm is based on the modification of a proof given by Thomassen related to a problem proposed by Ore in 1951.

(φ, ψ)-weak contractions in intuitionistic fuzzy metric spaces

2014

The purpose of this paper is to extend the notion of (phi,psi)-weak contraction to intuitionistic fuzzy metric spaces, by using an altering distance function. We obtain common fixed point results in intuitionistic fuzzy metric spaces, which generalize several known results from the literature.

Inference based on the affine invariant multivariate Mann–Whitney–Wilcoxon statistic

2003

A new affine invariant multivariate analogue of the two-sample Mann–Whitney–Wilcoxon test based on the Oja criterion function is introduced. The associated affine equivariant estimate of shift, the multivariate Hodges-Lehmann estimate, is also considered. Asymptotic theory is developed to provide approximations for null distribution as well as for a sequence of contiguous alternatives to consider limiting efficiencies of the test and estimate. The theory is illustrated by an example. Hettmansperger et al. [9] considered alternative slightly different affine invariant extensions also based on the Oja criterion. The methods proposed in this paper are computationally more intensive, but surpri…

Erratum: Partition function of the trigonometric SOS model with reflecting end

2010

Applications de type Lasota–Yorke à trou : mesure de probabilité conditionellement invariante et mesure de probabilité invariante sur l'ensemble des …

2003

Abstract Let T :I→I be a Lasota–Yorke map on the interval I, let Y be a nontrivial sub-interval of I and g 0 :I→ R + , be a strictly positive potential which belongs to BV and admits a conformal measure m. We give constructive conditions on Y ensuring the existence of absolutely continuous (w.r.t. m) conditionally invariant probability measures to nonabsorption in Y. These conditions imply also existence of an invariant probability measure on the set X∞ of points which never fall into Y. Our conditions allow rather “large” holes.

Stochastic order characterization of uniform integrability and tightness

2013

We show that a family of random variables is uniformly integrable if and only if it is stochastically bounded in the increasing convex order by an integrable random variable. This result is complemented by proving analogous statements for the strong stochastic order and for power-integrable dominating random variables. Especially, we show that whenever a family of random variables is stochastically bounded by a p-integrable random variable for some p>1, there is no distinction between the strong order and the increasing convex order. These results also yield new characterizations of relative compactness in Wasserstein and Prohorov metrics.

Sign test of independence between two random vectors

2003

A new affine invariant extension of the quadrant test statistic Blomqvist (Ann. Math. Statist. 21 (1950) 593) based on spatial signs is proposed for testing the hypothesis of independence. In the elliptic case, the new test statistic is asymptotically equivalent to the interdirection test by Gieser and Randles (J. Amer. Statist. Assoc. 92 (1997) 561) but is easier to compute in practice. Limiting Pitman efficiencies and simulations are used to compare the test to the classical Wilks’ test. peerReviewed