Probabilistic Inductive Classes of Graphs

A unifying framework—probabilistic inductive classes of graphs (PICGs)—is defined by imposing a probability space on the rules and their left elements from the standard notion of inductive class of graphs. The rules can model the processes creating real-world social networks, such as spread of knowledge, dynamics of acquaintanceships or sexual contacts, and emergence of clusters. We demonstrate the characteristics of PICGs by casting some well-known models of growing networks in this framework. Results regarding expected size and order are derived. For PICG models of connected and 2-connected graphs order, size and asymptotic degree distribution are presented. The approaches used represent analytic alternative to computer simulation, which is mostly used to obtain the properties of evolving graphs.     

星图的条件容错哈密尔顿性

证明了在任意n（≥5）维星图中去掉2n-9条边且使得去边后的图的每个点关联至少两条边,得到的图是边-哈密尔顿的.     

一些条件连通图的关系

在这篇文章中，我们主要研究一些条件连通图之间的关系，如上连通，上边连通，超连通和上混合连通．     

Nonparametric Gaussian inference for stable processes

Statistical Inference for Stochastic Processes - Jump processes driven by $$\alpha $$ -stable Lévy processes impose inferential difficulties as their increments are heavy-tailed and the...     

Gaussian Conditional and Quotient Distributions on Conic Subsets

We introduce the property of concentration for conic measurasble partitions of Gaussian probability spaces. Simple examples are considered. Bibliography: 2 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 298, 2003, pp. 186–190.     

Probabilistic Methods for Decomposition Dimension of Graphs

In a graph G, the distance from an edge e to a set FE(G) is the vertex distance from e to F in the line graph L(G). For a decomposition of E(G) into k sets, the distance vector of e is the k-tuple of distances from e to these sets. The decomposition dimension dec(G) of G is the smallest k such that G has a decomposition into k sets so that the distance vectors of the edges are distinct. For the complete graph K _n and the k-dimensional hypercube Q _k , we prove that (2–o(1))lgndec(K _n )(3.2+o(1))lgn and k/lgk dec(Q _k ) (3.17+o(1))k/lgk. The upper bounds use probabilistic methods directly or indirectly. We also prove that random graphs with edge probability p such that p n ^1– for some positive constant have decomposition dimension (lnn) with high probability. Acknowledgments.The authors thank Noga Alon for clarifying and strengthening the results in Sections 3 and 4. Thanks also go to a referee for repeated careful readings and suggestions.AMS classifications: 05C12, 05C35, 05D05, 05D40     

Conditional Iterative Proportional Fitting for Gaussian Distributions

A Gaussian version of the iterative proportional fitting procedure (IFP-P) was applied by Speed and Kiiveri to solve the likelihood equations in graphical Gaussian models. The calculation of the maximum likelihood estimates can be seen as the problem to find a Gaussian distribution with prescribed Gaussian marginals. We extend the Gaussian version of the IPF-P so that additionally given conditionals of Gaussian type are taken into account. The convergence of both proposed procedures, called conditional iterative proportional fitting procedures (CIPF-P), is proved.     

Probabilistic inference with noisy-threshold models based on a CP tensor decomposition

The specification of conditional probability tables (CPTs) is a difficult task in the construction of probabilistic graphical models. Several types of canonical models have been proposed to ease that difficulty. Noisy-threshold models generalize the two most popular canonical models: the noisy-or and the noisy-and. When using the standard inference techniques the inference complexity is exponential with respect to the number of parents of a variable. More efficient inference techniques can be employed for CPTs that take a special form. CPTs can be viewed as tensors. Tensors can be decomposed into linear combinations of rank-one tensors, where a rank-one tensor is an outer product of vectors. Such decomposition is referred to as Canonical Polyadic (CP) or CANDECOMP-PARAFAC (CP) decomposition. The tensor decomposition offers a compact representation of CPTs which can be efficiently utilized in probabilistic inference. In this paper we propose a CP decomposition of tensors corresponding to CPTs of threshold functions, exactly ℓ-out-of-k functions, and their noisy counterparts. We prove results about the symmetric rank of these tensors in the real and complex domains. The proofs are constructive and provide methods for CP decomposition of these tensors. An analytical and experimental comparison with the parent-divorcing method (which also has a polynomial complexity) shows superiority of the CP decomposition-based method. The experiments were performed on subnetworks of the well-known QMRT-DT network generalized by replacing noisy-or by noisy-threshold models.     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

Conditional quantiles of Gaussian measures in Hilbert space

In this paper, we present the conditional quantiles of the Gaussian measure as affine measurable functionals whose values on the Hilbert space are uniquely determined by their explicitly calculated restrictions onto the kernel of the measure. Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow, Russia, 1996, Part I.     

Data driven time scale in Gaussian quasi-likelihood inference

We study parametric estimation of ergodic diffusions observed at high frequency. Different from the previous studies, we suppose that sampling stepsize is unknown, thereby making the conventional Gaussian quasi-likelihood not directly applicable. In this situation, we construct estimators of both model parameters and sampling stepsize in a fully explicit way, and prove that they are jointly asymptotically normally distributed. High order uniform integrability of the obtained estimator is also derived. Further, we propose the Schwarz (BIC) type statistics for model selection and show its model-selection consistency. We conducted some numerical experiments and found that the observed finite-sample performance well supports our theoretical findings.

     

Conditional information for an inverse Gaussian distribution with known coefficient of variation

Conditional inference about a mean of an inverse Gaussian distribution with known coefficient of variation is discussed. For a random sample from the distribution, sufficient statistics with respect to the mean parameter include an ancillary statistic. The effects of conditioning on the ancillary statistic are investigated. It is shown that the model provides a good illustration of R. A. Fisher's recommendation concerning use of the observed second derivative of the log likelihood function in normal approximations.This work was started while Ksei Iwase was visiting the Institute of Statistical Mathematics in Spring, 1987, and was partly supported by the ISM Cooperative Research Program (88-ISM·CRP-7), and by Scientific Research Fund No. 62540173 from the Ministry of Education, Science and Culture of Japan.     

An Approximate Probabilistic Model for Structured Gaussian Elimination

Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. Structured Gaussian elimination has been proposed as a first step in solving such sparse systems. It is a method for selecting pivots in an attempt to preserve the sparseness of the coefficient matrix. Eventually it terminates with a (smaller) residual linear system which must be solved by some other method. In many cases, the original column density is roughly proportional to the reciprocal of the of the column index. We discuss the asymptotic behavior of structured Gaussian elimination for this situation. One result is the observation that, for the column density just mentioned, the size of the residual system grows linearly with the size of the problem. This makes it possible to extrapolate the results of Monte Carlo simulation to much larger problems.     

Probabilistic Modelling of Monitoring and Maintenance of Multistate Monotone Systems with Dependent Components

In Gåsemyr and Natvig (2001) partial monitoring of components with applications to preventive system maintenance was considered for a binary monotone system of binary components. The purpose of the present paper is to extend this to a multistate monotone system of multistate components, where the states more realistically represent successive levels of performance ranging from the perfect functioning level down to the complete failure level. We start out close to the spirit of Arjas (1989) by using a marked point process with complete monitoring of all components, and hence of the system, as the basic reference framework. We then consider a marked point process linked to partial monitoring of some components, for instance in certain time intervals. Incorporation of information from the observed system history process is then treated. Mainly, we assume that the inspection strategy is determined by the observed component history process only, with a possible exception of a full or partial autopsy after an observed change of state of , the system. Furthermore, we consider how to arrive at the posterior distribution for the relevant parameter vector by a standard simulation procedure, the data augmentation method. The idea is to extend the observed data to the complete component history process. The theory is applied to an electrical power generation system for two nearby oilrigs with some standby components, as considered in Natvig et al. (1986).AMS 2000 Subject Classification: Primary 96B25; Secondary, 62N05, 60K10     

Conditional laplace transforms for bayesian nonparametric inference in reliabity theory

In order to apply nonparametric meyhods to reliability problems, it is desibrable to have available priors over a broad class of survival distributions.In the paper, this is achieved by taking the failure rate function to be the sum oof a nonnegative stochastic process with increasing sample patjhs and a process with decreasing sample paths. This approach produces a prior which chooses an absolutely survival distribution that can have an IFR, DFR, or U-shapped failure rate. Posterior Laplace transforms of the failure rate are obtained based on survival data allows censoring. Bayes estimates of the failure rate as well as the lifetime distribution are then calculated from these posterior Laplace transforms. This approach is also applied to a competing risks model and the proportional hazards model of Cox.     

Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure

We present sharp bounds on the Kolmogorov probabilistic (N,δ)-width and p-average N-width of multivariate Sobolev space with mixed derivative

Full-size image (1K)

, equipped with a Gaussian measure μ in , that is where 1<q<∞,0<p<∞, and ρ>1 is depending only on the eigenvalues of the correlation operator of the measure μ (see (4)).