共查询到20条相似文献,搜索用时 31 毫秒
1.
A k-noncrossing RNA structure can be identified with a k-noncrossing diagram over [n], which in turn corresponds to a vacillating tableau having at most (k−1) rows. In this paper we derive the limit distribution of irreducible substructures via studying their corresponding vacillating tableaux. Our main result proves, that the limit distribution of the numbers of irreducible substructures in k-noncrossing, σ-canonical RNA structures is determined by the density function of a -distribution for some τk>1. 相似文献
2.
Consider a time homogeneous {0, 1}-valued m-dependent Markov chain . In this paper, we study the joint probability distribution of number of 0-runs of length and number of 1-runs of length in n trials. We study the joint distributions based on five popular counting schemes of runs. The main tool used to obtain the
probability generating function of the joint distribution is the conditional probability generating function method. Further
a compact method for the evaluation of exact joint distribution is developed. For higher-order two-state Markov chain, these
joint distributions are new in the literature of distributions of run statistics. We use these distributions to derive some
waiting time distributions. 相似文献
3.
In this paper, we prove that a non-negative rational number sequence (a
1,a
2, ...,a
k+1) isk-Hamilton-nice, if (1)a
k+12, and (2)
j
=1/h
(i
j
–1)k–1 implies
for arbitraryi
1,i
2,...i
h
{1,2,... ,k}. This result was conjectured by Guantao Chen and R.H. Schelp, and it generalizes several well-known sufficient conditions for graphs to be Hamiltonian.This project is supported by the National Natural Science Foundation of China. 相似文献
4.
Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k-degenerate graphs. For a given integer k1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k-dense forest F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k-dense tree. 1-dense trees are standard trees. We have |E|k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated. 相似文献
5.
Paul C. Shields 《Journal of Theoretical Probability》1993,6(3):499-519
Asymptotic properties of the waiting timeW
k
(x,y) until an initial segment of lengthk of a sample pathx of an ergodic finite-alphabet process is seen in an independently chosen sample pathy are discussed. Wyner and Ziv have shown that for irreducible Markov chains, (1/k) logW
k
(x,y) converges in probability to the entropyH of the process. In this paper, almost sure convergence toH is established for the somewhat larger class of functions of irreducible Markov chains and convergence in probability toH is established for weak Bernoulli processes. A stationary coding of an i.i.d. process is constructed for which there is a subsequencek(n) such that (1/k(n) logW
k(n
)(x,y), converges in probability to +. Positive and negative results for the case when only approximate matches are required are also obtained.Partially supported by NSF Grant DMS-9024240.From 9/1 to 12/1 earch year: Mathematies Institute, POB 127, 1364 Budapest, Hungary. 011-361-1-177-175. At other times: Department of Mathematics, University of Toledo, Toledo, Ohio 43606, (419) 537-2069. 相似文献
6.
Demetrios L. Antzoulakos Stathis Chadjiconstantinidis 《Annals of the Institute of Statistical Mathematics》2001,53(3):599-619
Let {Z
n
, n 1} be a time-homogeneous {0, 1}-valued Markov chain, and let N
n
be a random variable denoting the number of runs of "1" of length k in the first n trials. In this article we conduct a systematic study of N
n
by establishing formulae for the evaluation of its probability generating function, probability mass function and moments. This is done in three different enumeration schemes for counting runs of length k, the "non-overlapping", the "overlapping" and the "at least" scheme. In the special case of i.i.d. trials several new results are established. 相似文献
7.
Exact distributions of the numbers of failures, successes and successes with indices no less thanl (1lk–1) until the first consecutivek successes are obtained for some {0, 1}-valued random sequences such as a sequence of independent and identically distributed (iid) trials, a homogeneous Markov chain and a binary sequence of orderk. The number of failures until the first consecutivek successes follows the geometric distribution with an appropriate parameter for each of the above three cases. When the {0, 1}-sequence is an iid sequence or a Markov chain, the distribution of the number of successes with indices no less thanl is shown to be a shifted geometric distribution of orderk - l. When the {0, 1}-sequence is a binary sequence of orderk, the corresponding number follows a shifted version of an extended geometric distribution of orderk - l.This research was partially supported by the ISM Cooperative Research Program (92-ISM-CRP-16) of the Institute of Statistical Mathematics. 相似文献
8.
Let be the uniform triangulation generated by the usual three directional mesh of the plane and let H
1 be the regular hexagon formed by the six triangles of surrounding the origin. We study the space of piecewise polynomial functions in C
k
(R
2) with support H
1 having a sufficiently high degree n, which are invariant with respect to the group of symmetries of H
1 and whose sum of integer translates is constant. Such splines are called H
1-splines. We first compute the dimension of this space in function of n and k. Then we prove the existence of a unique H
1-spline of minimal degree for any fixed k0. Finally, we describe an algorithm computing the Bernstein–Bézier coefficients of this spline. 相似文献
9.
A new distribution called a generalized binomial distribution of order k is defined and some properties are investigated. A class of enumeration schemes for success-runs of a specified length including non-overlapping and overlapping enumeration schemes is rigorously studied. For each nonnegative integer less than the specified length of the runs, an enumeration scheme called -overlapping way of counting is defined. Let k and be positive integers satisfying < k. Based on independent Bernoulli trials, it is shown that the number of (– 1)-overlapping occurrences of success-run of length k until the n-th overlapping occurrence of success-run of length follows the generalized binomial distribution of order (k–). In particular, the number of non-overlapping occurrences of success-run of length k until the n-th success follows the generalized binomial distribution of order (k– 1). The distribution remains unchanged essentially even if the underlying sequence is changed from the sequence of independent Bernoulli trials to a dependent sequence such as higher order Markov dependent trials. A practical example of the generalized binomial distribution of order k is also given. 相似文献
10.
Let k and m are positive integers with k ≥ m. The probability generating function of the waiting time for the first occurrence of consecutive k successes in a sequence of m-th order Markov dependent trials is given as a function of the conditional probability generating functions of the waiting
time for the first occurrence of consecutive m successes. This provides an efficient algorithm for obtaining the probability generating function when k is large. In particular, in the case of independent trials a simple relationship between the geometric distribution of order
k and the geometric distribution of order k−1 is obtained.
This research was partially supported by the ISM Cooperative Research Program(2004-ISM-CRP-2006) and by a Grant-in-Aid for
Scientific Research (C) of the JSPI (Grant Number 16500183) 相似文献
11.
We explicitly solve the existence problem for 1-rotational k-cycle systems of the complete graph Kv with v1 or k (mod 2k). For v1 (mod 2k) we have existence if and only if k is an odd composite number. For any odd k and vk (mod 2k), (except k3 and v15, 21 (mod 24)) a 1-rotational k-cycle system of Kv exists.Final version received: June 18, 2003 相似文献
12.
A. Krajka 《Acta Appl Math》2007,96(1-3):327-338
Let
be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N
n
,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F
k
,k≥1} be a family of probability laws and let X be some random element defined on
and taking values in (S,ρ).
In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X
n,k
,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that
, and moreover
as n→∞. Furthermore, we consider the speed of convergence
to X as n→∞.
相似文献
13.
We study a W-algebra of central charge 2(k−1)/(k+2), k=2,3,…, contained in the commutant of a Heisenberg algebra in a simple affine vertex operator algebra L(k,0) of type with level k. We calculate the operator product expansions of the W-algebra. We also calculate some singular vectors in the case k6 and determine the irreducible modules and Zhu's algebra. Furthermore, the rationality and the C2-cofiniteness are verified for such k. 相似文献
14.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2003,53(3):627-629
One of numerical invariants concerning domination in graphs is the k-subdomination number
of a graph G. A conjecture concerning it was expressed by J.H. Hattingh, namely that for any connected graph G with n vertices and any k with
the inequality
holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and k = 5. 相似文献
15.
A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1}
n
for somen. A probability space isk-wise independent if, whenY
i
is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY
i
's is (mutually) independent, and it is said to be a probability spacefor p
1,p
2, ...,p
n
ifP[Y
i
=1]=p
i
.We study constructions ofk-wise independent 0–1 probability spaces in which thep
i
's are arbitrary. It was known that for anyp
1,p
2, ...,p
n
, ak-wise independent probability space of size
always exists. We prove that for somep
1,p
2, ...,p
n
[0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp
i
=k/n has size (n
k
). For a very large degree of independence —k=[n], for >1/2- and allp
i
=1/2, we prove a lower bound on the size of
. We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology. 相似文献
16.
Bang-Yen Chen 《Annals of Global Analysis and Geometry》1994,12(1):87-96
In the first part of this series, we prove that the tensor product immersionf
1
f
2k
of2k isometric spherical immersions of a Riemannian manifoldM in Euclidean space is of-type with k and classify tensor product immersionsf
1
f
2k
which are ofk-type. In this article we investigate the tensor product immersionsf
1
f
2k
which are of (k+1)-type. Several classification theorems are obtained. 相似文献
17.
Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center. 相似文献
18.
On-line k-Truck Problem and Its Competitive Algorithms 总被引:1,自引:0,他引:1
In this paper, based on the Position Maintaining Strategy (PMS for short), on-line scheduling of k-truck problem, which is a generalization of the famous k-server problem, is originally presented by our team. We proposed several competitive algorithms applicable under different conditions for solving the on-line k-truck problem. First, a competitive algorithm with competitive ratio 2k+1/ is given for any 1. Following that, if (c+1)/(c-1) holds, then there must exist a (2k-1)-competitive algorithm for k-truck problem, where c is the competitive ratio of the on-line algorithm about the relevant k-server problem. And then a greedy algorithm with competitive ratio 1+/, where lambda is a parameter related to the structure property of a given graph, is given. Finally, competitive algorithms with ratios 1+1/ are given for two special families of graphs. 相似文献
19.
We consider k-th power of upper bound graphs. According
to the characterization of upper bound graphs, we obtain a characterization of
k-th power of upper bound graphs. That is,
for a connected upper bound graph
G, Gk is an upper bound graph if
and only if for any pair of
Ak
-simplicial vertices s1,
s2 such that
, there exists a
Gk
-simplicial vertex s satisfying
the conditions:
and
. Furthermore we also get some properties on squares of upper bound graphs.AMS Subject Classification: 05C62. 相似文献
20.
Ekkehard Krätzel 《Monatshefte für Mathematik》1995,120(2):105-119
There are many results on the distribution of square-full and cube-full numbers. In this article the distribution of these numbers are studied in more detail. Suchk-full numbers (k=2,3) are considered which are at the same time 1-free (1k+2). At first an asymptotic result is given for the numberN
k,1(x) ofk-full and 1-free numbers not exceedingx. Then the distribution of these numbers in short intervals is investigated. We obtain different estimations of the differenceN
k,1(x+h)–Nk,1(x) in the casesk=2, 1=4,5,6,7,18 andk=3, 1=5,6,7, 18. 相似文献