共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Rajeeva L. Karandikar Vidyadhar G. Kulkarni 《Stochastic Processes and their Applications》1985,19(2):225-235
Let \s{Xn, n ? 0\s} and \s{Yn, n ? 0\s} be two stochastic processes such that Yn depends on Xn in a stationary manner, i.e. P(Yn ? A\vbXn) does not depend on n. Sufficient conditions are derived for Yn to have a limiting distribution. If Xn is a Markov chain with stationary transition probabilities and Yn = f(Xn,..., Xn+k) then Yn depends on Xn is a stationary way. Two situations are considered: (i) \s{Xn, n ? 0\s} has a limiting distribution (ii) \s{Xn, n ? 0\s} does not have a limiting distribution and exits every finite set with probability 1. Several examples are considered including that of a non-homogeneous Poisson process with periodic rate function where we obtain the limiting distribution of the interevent times. 相似文献
3.
Yuanyuan Liu 《Operations Research Letters》2010,38(3):218-222
Let P be a positive recurrent infinite transition matrix with invariant distribution π and be a truncated and arbitrarily augmented stochastic matrix with invariant distribution (n)π. We investigate the convergence ‖(n)π−π‖→0, as n→∞, and derive a widely applicable sufficient criterion. Moreover, computable bounds on the error ‖(n)π−π‖ are obtained for polynomially and geometrically ergodic chains. The bounds become rather explicit when the chains are stochastically monotone. 相似文献
4.
《Stochastic Processes and their Applications》1986,22(1):17-26
[0, 1] is partitioned by randomly splitting the longest subinterval, of length L, into two intervals of lengths LV and L(1 − V). V is independent of the past with a fixed distribution on (0, 1) If there are n subintervals and Ln is the length of a randomly chosen subinterval, then P(nLn ∈ dy) ≅ y−1P(K exp(−T0) ∈ dy) where K = E(exp(T0)) and T0 is the first renewal in a stationary renewa process constructed from V. 相似文献
5.
Awi Federgruen 《Stochastic Processes and their Applications》1981,11(2):187-192
Recent papers have shown that Π∞k = 1P(k) = limm→∞ (P(m) ? P(1)) exists whenever the sequence of stochastic matrices {P(k)}∞k = 1 exhibits convergence to an aperiodic matrix P with a single subchain (closed, irreducible set of states). We show how the limit matrix depends upon P(1).In addition, we prove that limm→∞limn→∞ (P(n + m) ? P(m + 1)) exists and equals the invariant probability matrix associated with P. The convergence rate is determined by the rate of convergence of {P(k)}∞k = 1 towards P.Examples are given which show how these results break down in case the limiting matrix P has multiple subchains, with {P(k)}∞k = 1 approaching the latter at a less than geometric rate. 相似文献
6.
Alan B. Poritz 《Linear algebra and its applications》2011,434(6):1425-4165
When an n×n doubly stochastic matrix A acts on Rn on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γn denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γn is a subset of Bn×Σn where Bn is the Birkhoff polytope and Σn is the probability simplex.We characterize Γn and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γn if and only if AtAP=P. We show that for any n, Γn is a connected set, and is in fact piecewise-linearly contractible in Bn×Σn. We write Γn as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γn. Γ3 is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable. 相似文献
7.
Let A(Pn) be the adjacency matrix of the path on n vertices. Suppose that r(λ) is a polynomial of degree less than n, and consider the matrix M = r(A>/(Pn)). We determine all polynomials for which M is the adjacency matrix of a graph. 相似文献
8.
Kiyoshi Hosono 《Discrete Mathematics》2008,308(20):4696-4709
Let P be a finite point set in general position in the plane. We consider empty convex subsets of P such that the union of the subsets constitute a simple polygon S whose dual graph is a path, and every point in P is on the boundary of S. Denote the minimum number of the subsets in the simple polygons S's formed by P by fp(P), and define the maximum value of fp(P) by Fp(n) over all P with n points. We show that ⌈(4n-17)/15⌉?Fp(n)?⌊n/2⌋. 相似文献
9.
Ting-Chung Chang 《Linear algebra and its applications》2011,435(10):2451-2461
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then Hn,k, the graph obtained from the star K1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges. 相似文献
10.
11.
It has been conjectured that if A is a doubly stochastic n>× n matrix such that per A(i, j)≥perA for all i, j, then either A = Jn, then n × n matrix with each entry equal to , or, up to permutations of rows and columns, , where Pn is a full cycle permutation matrix. This conjecture is proved. 相似文献
12.
For an n by n matrix A, let K(A) be the associated matrix corresponding to a permutation group (of degree m) and one of its characters. Let Dr(A) be the coefficient of xm?r in K(A+xI). If A is reducible, then Dr(A) is reducible. If A is irreducible and the character is identically one, then D1(A) is irreducible. If A is row stochastic and the character is identically one, then Dr(A) is essentially row stochastic. Finally, the results motivate the definition of group induced diagraphs. 相似文献
13.
《Journal of Combinatorial Theory, Series A》1987,45(2):316-322
P(n) and Pm(n) denote the number of (unordered) partitions of n and the number of partitions of n into m parts, respectively. For P(n), there exists a recursion formula which is shown in Eq. (3) and a complicated formula indicated in J. L. Doob et al. (“Hans Rademacher: Topic Analytic Number Theory,” Springer-Verlag, Berlin/New York, 1973, p. 275, which is accompanied with the error term. For Pm(n), there is no general rule known covering all m (Doob et al., p. 222). In this article, P(n) and Pm(n) are represented by determinants. Note that the determinant of the former agrees with the above recursion formula and the finite product of binomials analogous to Euler identity, which is indicated in (5), leads to the representation of the latter. The computation of determinant is a little troublesome, but it is very important that the representations themselves of the number of partitions are simple, if we make use of the determinant. 相似文献
14.
Let G be a finite group. The prime graph of G is denoted by Γ(G). It is proved in [1] that if G is a finite group such that Γ(G) = Γ(B p (3)), where p > 3 is an odd prime, then G ? B p (3) or C p (3). In this paper we prove the main result that if G is a finite group such that Γ(G) = Γ(B n (3)), where n ≥ 6, then G has a unique nonabelian composition factor isomorphic to B n (3) or C n (3). Also if Γ(G) = Γ(B 4(3)), then G has a unique nonabelian composition factor isomorphic to B 4(3), C 4(3), or 2 D 4(3). It is proved in [2] that if p is an odd prime, then B p (3) is recognizable by element orders. We give a corollary of our result, generalize the result of [2], and prove that B 2k+1(3) is recognizable by the set of element orders. Also the quasirecognition of B 2k (3) by the set of element orders is obtained. 相似文献
15.
In 1930 Kuratowski proved that a graph does not embed in the real plane R2 if and only if it contains a subgraph homeomorphic to one of two graphs, K5 or K33. Let In(P) denote the minimal set of graphs whose vertices have miximal valency n such that any graph which does not embed in the real projective plane (or equivalently, does not embed in the Möbius band) contains a subgraph homeomorphic to a graph in In(P) for some positive integer n. Glover and Huneke and Milgram proved that there are only 6 graphs in I3(P). This note proves that for each n, In(P) is finite. 相似文献
16.
C.E. Langenhop 《Linear algebra and its applications》1977,16(3):267-284
An explicit representation is obtained for P(z)?1 when P(z) is a complex n×n matrix polynomial in z whose coefficient of the highest power of z is the identity matrix. The representation is a sum of terms involving negative powers of z?λ for each λ such that P(λ) is singular. The coefficients of these terms are generated by sequences uk, vk of 1×n and n×1 vectors, respectively, which satisfy u1≠0, v1≠0, ∑k?1h=0(1?h!)uk?hP(h)(λ)=0, ∑k?1h=0(1?h!)P(h)(λ)vk?h=0, and certain orthogonality relations. In more general cases, including that when P(z) is analytic at λ but not necessarily a polynomial, the terms in the representation involving negative powers of z?λ provide the principal part of the Laurent expansion for P(z)?1 in a punctured neighborhood of z=λ. 相似文献
17.
Hermann Thorisson 《Stochastic Processes and their Applications》1985,20(1):85-104
We consider stochastic processes Z = (Zt)[0,∞), on a general state space, having a certain periodic regeneration property: there is an increasing sequence of random times (Sn)∞0 such that the post-Sn process is conditionally independent of S0,…,Sn given (Sn mod 1) and the conditional distribution does not depend on n. Our basic condition is that the distributions , have a common component that is absolutely continuous w.r.t. Lebesgue measure. Then Z has the following time-homogeneous regeneration property: there exists a discrete aperiodic renewal process T = (Tn)∞0 such that the post-Tn process is independent of T0,…,Tn and its distribution does not depend on n; this yields weak ergodicity. Further, the Markov chain (Snmod 1)∞0 has an invariant distribution π[0,1) and it holds that Tn+1 ? Tn has finite first moment if and only if m = ∫ m(Ps)π[0,1)(ds) < ∞ where m(Ps) is the first moment of Ps; this yields periodic ergodicity. Also, some distributional properties of T0 and Tn+1 ? Tn are established leading to improved ergodic regults. Finally, a uniform key periodic renewal theorem is derived. 相似文献
18.
Nicholas J. Kuhn 《Advances in Mathematics》2006,201(2):318-378
Let K(n) be the nth Morava K-theory at a prime p, and let T(n) be the telescope of a vn-self map of a finite complex of type n. In this paper we study the K(n)*-homology of Ω∞X, the 0th space of a spectrum X, and many related matters.We give a sampling of our results.Let PX be the free commutative S-algebra generated by X: it is weakly equivalent to the wedge of all the extended powers of X. We construct a natural map
sn(X):LT(n)P(X)→LT(n)Σ∞(Ω∞X)+ 相似文献
19.
A unified approach to a variety of graph-theoretic problems is introduced. The k-closure Ck(G) of a simple graph G of order n is the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree-sum at least k. It is shown that, for many properties P, one can find a suitable value of k (depending on P and n) such that if Ck(G) has P, then so does G. For instance, if P is the hamiltonian property, one may take k = n. Thus if Cn(G) is hamiltonian, then so is G; in particular, if n ? 3 and Cn(G) is complete, then G is hamiltonian. This condition for a graph to be hamiltonian is shown to imply the well-known conditions of Chvátal and Las Vergnas. The same method, applied to other properties, yields many new theorems of a similar nature. 相似文献
20.
Frederick J Beutler 《Journal of Mathematical Analysis and Applications》1973,44(2):464-471
A random discrete-time system {xn}, n = 0, 1, 2, … is called stochastically stable if for every ? > 0 there exists a λ > 0 such that the probability P[(supn ∥ xn ∥) > ?] < ? whenever P[∥ x0 ∥ > λ] < λ. A system is shown stochastically stable if some local Lyapunov function V(·) satisfies the supermartingale definition on {V(xn)} in a neighborhood of the origin; earlier proofs of stochastic stability require additional restrictions. A criterion for xn → 0 almost surely is developed. It consists of a global inequality on {U(xn)} stronger than the supermartingale defining inequality, but applied to a U(·) that need not be a Lyapunov function. The existence of such a U(·) is exhibited for a stochastically unstable nontrivial stochastic system. This indicates that our criterion for xn → 0 is “tight,” and that the two stability concepts studied are substantially distinct. 相似文献