树上马氏链场的若干极限性质

该文引进广义Ｂｅｔｈｅ树和广义Ｃａｙｌｅｙ树的概念,并研究其上马氏链场关于状态和状态序偶出现频率的强极限定理,作为主要结果的推论,得到Ｂｅｔｈｅ树和Ｃａｙｌｅｙ树上马氏链场的ＳｈａｎｎｏｎＭｃＭｉｌｌａｎ定理．证明中采用了研究概率论强极限定理的一种新的方法．     

Cayley树上随机场的马尔可夫逼近与一类小偏差定理

通过引进样本相对熵率作为Cayley树上任意随机场与马尔可夫链场之间的偏差的一种度量, 建立了关于状态序偶频率的一类小偏差定理. 证明中应用了研究马尔可夫链强极限定理的一种新的分析方法.     

Distributions of Runs and Consecutive Systems on Directed Trees

In this paper we study exact distributions of runs on directed trees. On the assumption that the collection of random variables indexed by the vertices of a directed tree has a directed Markov distribution, the exact distribution theory of runs is extended from based on random sequences to based on directed trees. The distribution of the number of success runs of a specified length on a directed tree along the direction is derived. A consecutive-k-out-of-n:F system on a directed tree is introduced and investigated. By assuming that the lifetimes of the components are independent and identically distributed, we give the exact distribution of the lifetime of the consecutive system. The results are not only theoretical but also suitable for computation.     

Almost Sure Central Limit Theorem for Partial Sums of Markov Chain

The authors prove an almost sure central limit theorem for partial sums based on an irreducible and positive recurrent Markov chain using logarithmic means,which realizes the extension of the almost sure central limit theorem for partial sums from an i.i.d.sequence of random variables to a Markov chain.     

Brouwer and Euclid

We explore the relationship between Brouwer’s intuitionistic mathematics and Euclidean geometry. Brouwer wrote a paper in 1949 called The contradictority of elementary geometry. In that paper, he showed that a certain classical consequence of the parallel postulate implies Markov’s principle, which he found intuitionistically unacceptable. But Euclid’s geometry, having served as a beacon of clear and correct reasoning for two millennia, is not so easily discarded.Brouwer started from a “theorem” that is not in Euclid, and requires Markov’s principle for its proof. That means that Brouwer’s paper did not address the question whether Euclid’s Elements really requires Markov’s principle. In this paper we show that there is a coherent theory of “non-Markovian Euclidean geometry”. We show in some detail that our theory is an adequate formal rendering of (at least) Euclid’s Book I, and suffices to define geometric arithmetic, thus refining the author’s previous investigations (which include Markov’s principle as an axiom).Philosophically, Brouwer’s proof that his version of the parallel postulate implies Markov’s principle could be read just as well as geometric evidence for the truth of Markov’s principle, if one thinks the geometrical “intersection theorem” with which Brouwer started is geometrically evident.     

多元随机序列泛函的强偏差定理

利用熵密度和样本偏差率的概念,建立了多元随机序列泛函关于条件期望的用不等式表示的强极限性质(称之为强偏差定理),在推论部分得到了非齐次马氏链的强偏差定理和随机条件概率的调和平均值的极限性质等相关结论.证明中给出了将条件矩母函数应用于研究多元随机序列泛函的强极限性质的一种途径.     

Existence of solution to a model for gas transportation networks on non-flat topography

In this paper we prove the existence of solution to a mathematical model for gas transportation networks on non-flat topography. Firstly, the network topology is represented by a directed graph and then a nonlinear system of numerical equations is introduced whose unknowns are the pressures at the nodes and the mass flow rates at the edges of the graph. This system is written in a compact vector form in terms of the vector of the square pressures at the nodes and then an existence result is proved under some simplifying assumptions. The proof is done in two steps: the first one uses convex analysis tools and the second one the Brouwer fixed-point theorem.     

STRONG LAW OF LARGE NUMBERS AND SHANNON-MCMILLAN THEOREM FOR MARKOV CHAINS FIELD ON CAYLEY TREE

1 lntroductionA tr(t(t is a grapl1 G = {T, E) wllicl1 is co1l11ected a11d colltai1ls no cir(.uits. Give11 a11y twov(irtic'is 't / P E T, let crP bc tl1e ullique patl1 col111ecti11g,v aIld /]. Defille tl1e graph distal1cc(l(rr, p) to hc the Ilu1llber of edges co11tained in the path crP.We discuss ulainly tl1e rooted Cayley tree TC,2(i.e.,binary tree. See Fig.1). In tlle Cayleytree Tc,2,tl1e root (denoted by 0) llas OIlly two 11(tiglll)(irs al1d all otller vertices have threeneighbors. A…     

Local Limit Theorems for Sequences of Simple Random Walks on Graphs

In this article, local limit theorems for sequences of simple random walks on graphs are established. The results formulated are motivated by a variety of random graph models, and explanations are provided as to how they apply to supercritical percolation clusters, graph trees converging to the continuum random tree and the homogenisation problem for nested fractals. A subsequential local limit theorem for the simple random walks on generalised Sierpinski carpet graphs is also presented.      

Directed cut transversal packing for source-sink connected graphs

Concerning the conjecture that in every directed graph, a maximum packing of directed cut transversals is equal in cardinality to a minimum directed cut, a proof is given for the side coboundaries of a graph. This case includes, and is essentially equivalent to, all source-sink connected graphs, for which Schrijver has given a proof. The method used here first reduces the assertion to a packing theorem for bi-transversals. A packing of bi-transversals of the required size is constructed one edge at a time, by maintaining a Hall-like feasibility condition as each edge is added.     

Stein's method and Plancherel measure of the symmetric group

We initiate a Stein's method approach to the study of the Plancherel measure of the symmetric group. A new proof of Kerov's central limit theorem for character ratios of random representations of the symmetric group on transpositions is obtained; the proof gives an error term. The construction of an exchangeable pair needed for applying Stein's method arises from the theory of harmonic functions on Bratelli diagrams. We also find the spectrum of the Markov chain on partitions underlying the construction of the exchangeable pair. This yields an intriguing method for studying the asymptotic decomposition of tensor powers of some representations of the symmetric group.

     

一个随机偏差定理

设{Xn,n≥0}是可列非齐次马尔可夫链,Sn(i0,i1,…,im-1,ω)表示m元状态序组(i0,i1,…,im-1)在序列(X0,X1,…,Xm-1),(X1,X2,…,Xm),…,(Xn-1,Xn,…,Xn+m-2)中出现的次数.本文给出了关于Sn(i0,i1,…,im-1,ω)的一个对任意可列非齐次马尔可夫链普遍成立的随机偏差定理,即用不等式表示的一个强极限定理.     

Markov random fields,Markov cocycles and the 3-colored chessboard

The well-known Hammersley–Clifford Theorem states (under certain conditions) that any Markov random field is a Gibbs state for a nearest neighbor interaction. In this paper we study Markov random fields for which the proof of the Hammersley–Clifford Theorem does not apply. Following Petersen and Schmidt we utilize the formalism of cocycles for the homoclinic equivalence relation and introduce “Markov cocycles”, reparametrizations of Markov specifications. The main part of this paper exploits this to deduce the conclusion of the Hammersley–Clifford Theorem for a family of Markov random fields which are outside the theorem’s purview where the underlying graph is Z_d. This family includes all Markov random fields whose support is the d-dimensional “3-colored chessboard”. On the other extreme, we construct a family of shift-invariant Markov random fields which are not given by any finite range shift-invariant interaction.     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

Bethe树和Cayley树上奇偶马尔可夫链场的强极限定理

本文介绍了N元Bethe树TB,N(N元Cayley树TC,N)上的奇偶马尔可夫链场的定义,并通过构造两个非负鞅证得了随机变量序列的强极限定理,应用此强极限定理获得了奇偶马尔可夫链场上的一个强极限定理,作为它的推论得到了状态和状态序偶出现频率的一类强极限定理及其估计,从而推广了关于N元Bethe树上马氏链场和二进树上奇偶马氏链场的部分强极限定理.     

一个随机偏差定理

设{Xn，n≥0}是可列非齐次马尔可夫链，Sn（i0，i1，…，im-1，ω）表示m元状态序组（i0，i1，…，im-1）在序列（X0，X1，…，Xm-1），（X1，X2，…，Xm），…，（Xn-1，Xn，…，Xn＋m-2）中出现的次数.本文给出了关于Sn（i0，i1，…，im-1，ω）的一个对任意可列非齐次马尔可夫链普遍成立的随机偏差定理，即用不等式表示的一个强极限定理.     

Graph homomorphisms through random walks

In this paper we introduce some general necessary conditions for the existence of graph homomorphisms, which hold in both directed and undirected cases. Our method is a combination of Diaconis and Saloff–Coste comparison technique for Markov chains and a generalization of Haemers interlacing theorem. As some applications, we obtain a necessary condition for the spanning subgraph problem, which also provides a generalization of a theorem of Mohar (1992) as a necessary condition for Hamiltonicity. In particular, in the case that the range is a Cayley graph or an edge‐transitive graph, we obtain theorems with a corollary about the existence of homomorphisms to cycles. This, specially, provides a proof of the fact that the Coxeter graph is a core. Also, we obtain some information about the cores of vertex‐transitive graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 15–38, 2003     

m阶马氏链关于广义随机选择系统的极限定理

主要研究广义随机选择系统中的m阶非齐次马氏链随机转移概率调和平均的a.s.收敛的强极限定理.在证明中采用了一种把网微分法与条件矩母函数相结合应用于马氏链强极限定理研究的新途径.作为推论,得到m阶非齐次马氏链随机条件概率一个公平比的强极限定理,并将已有的结果加以推广.     

Renewal theory for extremal Markov sequences of Kendall type

The paper deals with renewal theory for a class of extremal Markov sequences connected with the Kendall convolution. We consider here some particular cases of the Wold processes associated with generalized convolutions. We prove an analogue of the Fredholm theorem for all regular generalized convolutions algebras. Using regularly varying functions we prove a Blackwell theorem and a limit theorem for renewal processes defined by Kendall random walks.Our results set new research hypotheses for other generalized convolution algebras to investigate renewal processes constructed by Markov processes with respect to generalized convolutions.     

The Passage Time Distribution for a Birth-and-Death Chain: Strong Stationary Duality Gives a First Stochastic Proof

A well-known theorem usually attributed to Keilson states that, for an irreducible continuous-time birth-and-death chain on the nonnegative integers and any d, the passage time from state 0 to state d is distributed as a sum of d independent exponential random variables. Until now, no probabilistic proof of the theorem has been known. In this paper we use the theory of strong stationary duality to give a stochastic proof of a similar result for discrete-time birth-and-death chains and geometric random variables, and the continuous-time result (which can also be given a direct stochastic proof) then follows immediately. In both cases we link the parameters of the distributions to eigenvalue information about the chain. We also discuss how the continuous-time result leads to a proof of the Ray–Knight theorem. Intimately related to the passage-time theorem is a theorem of Fill that any fastest strong stationary time T for an ergodic birth-and-death chain on {0,…,d} in continuous time with generator G, started in state 0, is distributed as a sum of d independent exponential random variables whose rate parameters are the nonzero eigenvalues of −G. Our approach yields the first (sample-path) construction of such a T for which individual such exponentials summing to T can be explicitly identified. Research of J.A. Fill was supported by NSF grant DMS–0406104 and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics.