共查询到20条相似文献,搜索用时 31 毫秒
1.
Let us fix a function f(n)=o(nlnn) and real numbers 0≤α<β≤1. We present a polynomial time algorithm which, given a directed graph G with n vertices, decides either that one can add at most βn new edges to G so that G acquires a Hamiltonian circuit or that one cannot add αn or fewer new edges to G so that G acquires at least e−f(n)n! Hamiltonian circuits, or both. 相似文献
2.
Tertuliano Franco Patrícia Gonçalves Adriana Neumann 《Stochastic Processes and their Applications》2013
We analyze the equilibrium fluctuations of density, current and tagged particle in symmetric exclusion with a slow bond. The system evolves in the one-dimensional lattice and the jump rate is everywhere equal to one except at the slow bond where it is αn−β, with α>0, β∈[0,+∞] and n is the scaling parameter. Depending on the regime of β, we find three different behaviors for the limiting fluctuations whose covariances are explicitly computed. In particular, for the critical value β=1, starting a tagged particle near the slow bond, we obtain a family of Gaussian processes indexed in α, interpolating a fractional Brownian motion of Hurst exponent 1/4 and the degenerate process equal to zero. 相似文献
3.
It is known that in the critical case the conditional least squares estimator (CLSE) of the offspring mean of a discrete time branching process with immigration is not asymptotically normal. If the offspring variance tends to zero, it is normal with normalization factor n2/3. We study a situation of its asymptotic normality in the case of non-degenerate offspring distribution for the process with time-dependent immigration, whose mean and variance vary regularly with non-negative exponents α and β, respectively. We prove that if β<1+2α, the CLSE is asymptotically normal with two different normalization factors and if β>1+2α, its limit distribution is not normal but can be expressed in terms of the distribution of certain functionals of the time-changed Wiener process. When β=1+2α the limit distribution depends on the behavior of the slowly varying parts of the mean and variance. 相似文献
4.
5.
We consider a multidimensional diffusion X with drift coefficient b(α,Xt) and diffusion coefficient ?σ(β,Xt). The diffusion sample path is discretely observed at times tk=kΔ for k=1…n on a fixed interval [0,T]. We study minimum contrast estimators derived from the Gaussian process approximating X for small ?. We obtain consistent and asymptotically normal estimators of α for fixed Δ and ?→0 and of (α,β) for Δ→0 and ?→0 without any condition linking ? and Δ. We compare the estimators obtained with various methods and for various magnitudes of Δ and ? based on simulation studies. Finally, we investigate the interest of using such methods in an epidemiological framework. 相似文献
6.
We prove that if for a continuous map f on a compact metric space X, the chain recurrent set, R(f) has more than one chain component, then f does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f on a compact metric space X has the asymptotic average shadowing property and if A is an attractor for f, then A is the single attractor for f and we have A=R(f). We also study diffeomorphisms with asymptotic average shadowing property and prove that if M is a compact manifold which is not finite with dimM=2, then the C1 interior of the set of all C1 diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω-stable diffeomorphisms. 相似文献
7.
For α∈R, let pR(t,x,x) denote the diagonal of the transition density of the α-Bessel process in (0,1], killed at 0 and reflected at 1. As a function of x, if either α≥3 or α=1, then for t>0, the diagonal is nondecreasing. This monotonicity property fails if 1≠α<3. 相似文献
8.
The ball hull mapping β associates with each closed bounded convex set K in a Banach space its ball hull β(K), defined as the intersection of all closed balls containing K. We are concerned in this paper with continuity and Lipschitz continuity (with respect to the Hausdorff metric) of the ball hull mapping. It is proved that β is a Lipschitz map in finite dimensional polyhedral spaces. Both properties, finite dimension and polyhedral norm, are necessary for this result. Characterizing the ball hull mapping by means ofH-convexity we show, with the help of a remarkable example from combinatorial geometry, that there exist norms with noncontinuous β map, even in finite dimensional spaces. Using this surprising result, we then show that there are infinite dimensional polyhedral spaces (in the usual sense of Klee) for which the map β is not continuous. A property known as ball stability implies that β has Lipschitz constant one. We prove that every Banach space of dimension greater than two can be renormed so that there is an intersection of closed balls for which none of its parallel bodies is an intersection of closed balls, thus lacking ball stability. 相似文献
9.
In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s-dimensional sequence m, whose elements are vectors obtained by concatenating d-dimensional vectors from a low-discrepancy sequence q with (s−d)-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0 the difference of the star discrepancies of the first N points of m and q is bounded by ε with probability at least 1−2exp(−ε2N/2) for N sufficiently large. The authors did not study how large N actually has to be and if and how this actually depends on the parameters s and ε. In this note we derive a lower bound for N, which significantly depends on s and ε. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N points of m and q, which holds without any restrictions on N. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N. We compare this bound to other known bounds. 相似文献
10.
We extend the notion of shape-Wilf-equivalence to vincular patterns (also known as “generalized patterns” or “dashed patterns”). First we introduce a stronger equivalence on patterns which we call filling-shape-Wilf-equivalence. When vincular patterns α and β are filling-shape-Wilf-equivalent, we prove that α⊕σ and β⊕σ must also be filling-shape-Wilf-equivalent. We also discover two new pairs of patterns which are filling-shape-Wilf-equivalent: when α, β, and σ are nonempty consecutive patterns which are Wilf-equivalent, α⊕σ is filling-shape-Wilf-equivalent to β⊕σ; and for any consecutive pattern α , 1⊕α is filling-shape-Wilf-equivalent to 1?α. These new equivalences imply many new Wilf-equivalences for vincular patterns. 相似文献
11.
Let R be a commutative ring with identity. We will say that an R-module M satisfies the weak Nakayama property, if IM=M, where I is an ideal of R, implies that for any x∈M there exists a∈I such that (a−1)x=0. In this paper, we will study modules satisfying the weak Nakayama property. It is proved that if R is a local ring, then R is a Max ring if and only if J(R), the Jacobson radical of R, is T-nilpotent if and only if every R-module satisfies the weak Nakayama property. 相似文献
12.
We consider a multidimensional diffusion X with drift coefficient b(Xt,α) and diffusion coefficient εa(Xt,β) where α and β are two unknown parameters, while ε is known. For a high frequency sample of observations of the diffusion at the time points k/n, k=1,…,n, we propose a class of contrast functions and thus obtain estimators of (α,β). The estimators are shown to be consistent and asymptotically normal when n→∞ and ε→0 in such a way that ε−1n−ρ remains bounded for some ρ>0. The main focus is on the construction of explicit contrast functions, but it is noted that the theory covers quadratic martingale estimating functions as a special case. In a simulation study we consider the finite sample behaviour and the applicability to a financial model of an estimator obtained from a simple explicit contrast function. 相似文献
13.
Let G=(V,E) be a graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. A dominating set D is called a total dominating set if every vertex in D is adjacent to a vertex in D. The domination (resp. total domination) number of G is the smallest cardinality of a dominating (resp. total dominating) set of G. The bondage (resp. total bondage) number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with larger domination (resp. total domination) number of G. The reinforcement (resp. total reinforcement) number of G is the smallest number of edges whose addition to G results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard. 相似文献
14.
Jean-Stéphane Dhersin Fabian Freund Arno Siri-Jégousse Linglong Yuan 《Stochastic Processes and their Applications》2013
In this paper, we consider Beta(2−α,α) (with 1<α<2) and related Λ-coalescents. If T(n) denotes the length of a randomly chosen external branch of the n-coalescent, we prove the convergence of nα−1T(n) when n tends to ∞, and give the limit. To this aim, we give asymptotics for the number σ(n) of collisions which occur in the n-coalescent until the end of the chosen external branch, and for the block counting process associated with the n-coalescent. 相似文献
15.
We study boundary value problems of the form -Δu=f on Ω and Bu=g on the boundary ∂Ω, with either Dirichlet or Neumann boundary conditions, where Ω is a smooth bounded domain in Rn and the data f,g are distributions . This problem has to be first properly reformulated and, for practical applications, it is of crucial importance to obtain the continuity of the solution u in terms of f and g . For f=0, taking advantage of the fact that u is harmonic on Ω, we provide four formulations of this boundary value problem (one using nontangential limits of harmonic functions, one using Green functions, one using the Dirichlet-to-Neumann map, and a variational one); we show that these four formulations are equivalent. We provide a similar analysis for f≠0 and discuss the roles of f and g, which turn to be somewhat interchangeable in the low regularity case. The weak formulation is more convenient for numerical approximation, whereas the nontangential limits definition is closer to the intuition and easier to check in concrete situations. We extend the weak formulation to polygonal domains using weighted Sobolev spaces. We also point out some new phenomena for the “concentrated loads” at the vertices in the polygonal case. 相似文献
16.
This paper considers the short- and long-memory linear processes with GARCH (1,1) noises. The functional limit distributions of the partial sum and the sample autocovariances are derived when the tail index α is in (0,2), equal to 2, and in (2,∞), respectively. The partial sum weakly converges to a functional of α-stable process when α<2 and converges to a functional of Brownian motion when α≥2. When the process is of short-memory and α<4, the autocovariances converge to functionals of α/2-stable processes; and if α≥4, they converge to functionals of Brownian motions. In contrast, when the process is of long-memory, depending on α and β (the parameter that characterizes the long-memory), the autocovariances converge to either (i) functionals of α/2-stable processes; (ii) Rosenblatt processes (indexed by β, 1/2<β<3/4); or (iii) functionals of Brownian motions. The rates of convergence in these limits depend on both the tail index α and whether or not the linear process is short- or long-memory. Our weak convergence is established on the space of càdlàg functions on [0,1] with either (i) the J1 or the M1 topology (Skorokhod, 1956); or (ii) the weaker form S topology (Jakubowski, 1997). Some statistical applications are also discussed. 相似文献
17.
Two modifications of Newton’s method to accelerate the convergence of the nth root computation of a strictly positive real number are revisited. Both modifications lead to methods with prefixed order of convergence p∈N,p≥2. We consider affine combinations of the two modified pth-order methods which lead to a family of methods of order p with arbitrarily small asymptotic constants. Moreover the methods are of order p+1 for some specific values of a parameter. Then we consider affine combinations of the three methods of order p+1 to get methods of order p+1 again with arbitrarily small asymptotic constants. The methods can be of order p+2 with arbitrarily small asymptotic constants, and also of order p+3 for some specific values of the parameters of the affine combination. It is shown that infinitely many pth-order methods exist for the nth root computation of a strictly positive real number for any p≥3. 相似文献
18.
19.
We consider the motion of a Brownian particle in R, moving between a particle fixed at the origin and another moving deterministically away at slow speed ε>0. The middle particle interacts with its neighbours via a potential of finite range b>0, with a unique minimum at a>0, where b<2a. We say that the chain of particles breaks on the left- or right-hand side when the middle particle is at a distance greater than b from its left or right neighbour, respectively. We study the asymptotic location of the first break of the chain in the limit of small noise, in the case where ε=ε(σ) and σ>0 is the noise intensity. 相似文献
20.
The second neighborhood conjecture of Seymour says that every antisymmetric digraph has a vertex whose second neighborhood is not smaller than the first one. The Caccetta–Häggkvist conjecture says that every digraph with n vertices and minimum out-degree r contains a cycle of length at most ⌈n/r⌉. We give a proof of the former conjecture for digraphs with out-degree r and connectivity r−1, and of the second one for digraphs with connectivity r−1 and r≥n/3. The main tool is the isoperimetric method of Hamidoune. 相似文献