Search results for "combinatoric"

Cotas inferiores para el QAP-Arbol

1985

The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.

Large deviations results for subexponential tails, with applications to insurance risk

1996

AbstractConsider a random walk or Lévy process {St} and let τ(u) = inf {t⩾0 : St > u}, P(u)(·) = P(· | τ(u) < ∞). Assuming that the upwards jumps are heavy-tailed, say subexponential (e.g. Pareto, Weibull or lognormal), the asymptotic form of the P(u)-distribution of the process {St} up to time τ(u) is described as u → ∞. Essentially, the results confirm the folklore that level crossing occurs as result of one big jump. Particular sharp conclusions are obtained for downwards skip-free processes like the classical compound Poisson insurance risk process where the formulation is in terms of total variation convergence. The ideas of the proof involve excursions and path decompositions for Mark…

Can the Adaptive Metropolis Algorithm Collapse Without the Covariance Lower Bound?

2011

The Adaptive Metropolis (AM) algorithm is based on the symmetric random-walk Metropolis algorithm. The proposal distribution has the following time-dependent covariance matrix at step $n+1$ \[ S_n = Cov(X_1,...,X_n) + \epsilon I, \] that is, the sample covariance matrix of the history of the chain plus a (small) constant $\epsilon>0$ multiple of the identity matrix $I$. The lower bound on the eigenvalues of $S_n$ induced by the factor $\epsilon I$ is theoretically convenient, but practically cumbersome, as a good value for the parameter $\epsilon$ may not always be easy to choose. This article considers variants of the AM algorithm that do not explicitly bound the eigenvalues of $S_n$ away …

2021

Abstract We prove the existence of a smoothing for a toroidal crossing space under mild assumptions. By linking log structures with infinitesimal deformations, the result receives a very compact form for normal crossing spaces. The main approach is to study log structures that are incoherent on a subspace of codimension 2 and prove a Hodge–de Rham degeneration theorem for such log spaces that also settles a conjecture by Danilov. We show that the homotopy equivalence between Maurer–Cartan solutions and deformations combined with Batalin–Vilkovisky theory can be used to obtain smoothings. The construction of new Calabi–Yau and Fano manifolds as well as Frobenius manifold structures on moduli…

Explicit, identical maximum likelihood estimates for some cyclic Gaussian and cyclic Ising models

2017

Cyclic models are a subclass of graphical Markov models with simple, undirected probability graphs that are chordless cycles. In general, all currently known distributions require iterative procedures to obtain maximum likelihood estimates in such cyclic models. For exponential families, the relevant conditional independence constraint for a variable pair is given all remaining variables, and it is captured by vanishing canonical parameters involving this pair. For Gaussian models, the canonical parameter is a concentration, that is, an off-diagonal element in the inverse covariance matrix, while for Ising models, it is a conditional log-linear, two-factor interaction. We give conditions un…

PROBABILISTIC QUANTIFICATION OF HAZARDS: A METHODOLOGY USING SMALL ENSEMBLES OF PHYSICS-BASED SIMULATIONS AND STATISTICAL SURROGATES

2015

This paper presents a novel approach to assessing the hazard threat to a locale due to a large volcanic avalanche. The methodology combines: (i) mathematical modeling of volcanic mass flows; (ii) field data of avalanche frequency, volume, and runout; (iii) large-scale numerical simulations of flow events; (iv) use of statistical methods to minimize computational costs, and to capture unlikely events; (v) calculation of the probability of a catastrophic flow event over the next T years at a location of interest; and (vi) innovative computational methodology to implement these methods. This unified presentation collects elements that have been separately developed, and incorporates new contri…

The smallest singular value of a shifted $d$-regular random square matrix

2017

We derive a lower bound on the smallest singular value of a random d-regular matrix, that is, the adjacency matrix of a random d-regular directed graph. Specifically, let $$C_1<d< c n/\log ^2 n$$ and let $$\mathcal {M}_{n,d}$$ be the set of all $$n\times n$$ square matrices with 0 / 1 entries, such that each row and each column of every matrix in $$\mathcal {M}_{n,d}$$ has exactly d ones. Let M be a random matrix uniformly distributed on $$\mathcal {M}_{n,d}$$ . Then the smallest singular value $$s_{n} (M)$$ of M is greater than $$n^{-6}$$ with probability at least $$1-C_2\log ^2 d/\sqrt{d}$$ , where c, $$C_1$$ , and $$C_2$$ are absolute positive constants independent of any other parameter…

Hitting straight lines by compound Poisson process paths

1990

In a recent article Mallows and Nair (1989,Ann. Inst. Statist. Math.,41, 1–8) determined the probability of intersectionP{X(t)=αt for somet≥0} between a compound Poisson process {X(t), t≥0} and a straight line through the origin. Using four different approaches (direct probabilistic, via differential equations and via Laplace transforms) we extend their results to obtain the probability of intersection between {X(t), t≥0} and arbitrary lines. Also, we display a relationship with the theory of Galton-Watson processes. Additional results concern the intersections with two (or more) parallel lines.

Decomposable multiphase entropic descriptor

2013

To quantify degree of spatial inhomogeneity for multiphase materials we adapt the entropic descriptor (ED) of a pillar model developed to greyscale images. To uncover the contribution of each phase we introduce the suitable 'phase splitting' of the adapted descriptor. As a result, each of the phase descriptors (PDs) describes the spatial inhomogeneity attributed to each phase-component. Obviously, their sum equals to the value of the overall spatial inhomogeneity. We apply this approach to three-phase synthetic patterns. The black and grey components are aggregated or clustered while the white phase is the background one. The examples show how the valuable microstuctural information related…

Multitype spatial point patterns with hierarchical interactions.

2001

Multitype spatial point patterns with hierarchical interactions are considered. Here hierarchical interaction means directionality: points on a higher level of hierarchy affect the locations of points on the lower levels, but not vice versa. Such relations are common, for example, in ecological communities. Interacting point patterns are often modeled by Gibbs processes with pairwise interactions. However, these models are inherently symmetric, and the hierarchy can be acknowledged only when interpreting the results. We suggest the following in allowing the inclusion of the hierarchical structure in the model. Instead of regarding the pattern as a realization of a stationary multivariate po…