Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory

We analyze continuous-time quantum and classical random walk on spidernet lattices. In the framework of Stieltjes transform, we obtain density of states, which is an efficiency measure for the performance of classical and quantum mechanical transport processes on graphs, and calculate the spacetime transition probabilities between two vertices of the lattice. Then we analytically show that there are two power law decays ∼ t ⁻³ and ∼ t ^−1.5 at the beginning of the transport for transition probability in the continuous-time quantum and classical random walk, respectively. This results illustrate the decay of quantum mechanical transport processes is quicker than that of the classical one. Due to the result, the characteristic time t _c , which is the time when the first maximum of the probabilities occur on an infinite graph, for the quantum walk is shorter than that of the classical walk. Therefore, we can interpret that the quantum transport speed on spidernet is faster than that of the classical one. In the end, we investigate the results by numerical analysis for two examples.     

A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars

We provide a strongly polynomial algorithm for determining whether a given multi-type branching process is subcritical, critical, or supercritical. The same algorithm also decides consistency of stochastic context-free grammars.     

On closed-form approximations for the free energy ofd-dimensional Ising model,II

It has been shown that it is possible to construct families of closed-form approximations lnZ* _d to lnZ _d for the anisotropic Ising model on ad-dimensional hypercubical lattice whose high- and low-temperature series expansions coincide with the corresponding exact expansions up to some order. For the isotropic case the density of zeros ofZ* _d near the critical pointK _c is found under the assumption that they behave like sinh2K=±(sinh2K _c +y±iy). It is shown that there exists a family of closed-form approximations such that ford3 the only possible densities of zeros arem(y)=|y|³ for=0 andm(y)=|y| for 0<||1, i.e., it contains the exact case ford5 corresponding to ||=1.     

A dedicated algorithm for calculating ground states for the triangular random bond Ising model

In the presented article we present an algorithm for the computation of ground state spin configurations for the 2d random bond Ising model on planar triangular lattice graphs. Therefore, it is explained how the respective ground state problem can be mapped to an auxiliary minimum-weight perfect matching problem, solvable in polynomial time. Consequently, the ground state properties as well as minimum-energy domain wall (MEDW) excitations for very large 2d systems, e.g. lattice graphs with up to N=384×384 spins, can be analyzed very fast.Here, we investigate the critical behavior of the corresponding T=0 ferromagnet to spin-glass transition, signaled by a breakdown of the magnetization, using finite-size scaling analyses of the magnetization and MEDW excitation energy and we contrast our numerical results with previous simulations and presumably exact results.     

Note on the Structure of Kruskal’s Algorithm

We study the merging process when Kruskal’s algorithm is run with random graphs as inputs. Our aim is to analyze this process when the underlying graph is the complete graph on n vertices lying in [0,1] ^d , and edge set weighted with the Euclidean distance. The height of the binary tree explaining the merging process is proved to be Θ(n) on average. On the way to the proof, we obtain similar results for the complete graph and the d-dimensional square lattice with i.i.d. edge weights.     

Equivalence of Julesz Ensembles and FRAME Models

In the past thirty years, research on textures has been pursued along two different lines. The first line of research, pioneered by Julesz (1962, IRE Transactions of Information Theory, IT-8:84–92), seeks essential ingredients in terms of features and statistics in human texture perception. This leads us to a mathematical definition of textures in terms of Julesz ensembles (Zhu et al., IEEE Trans. on PAMI, Vol. 22, No. 6, 2000). A Julesz ensemble is a set of images that share the same value of some basic feature statistics. Images in the Julesz ensemble are defined on a large image lattice (a mathematical idealization being Z ²) so that exact constraint on feature statistics makes sense. The second line of research studies Markov random field (MRF) models that characterize texture patterns on finite (or small) image lattice in a statistical way. This leads us to a general class of MRF models called FRAME (Filter, Random field, And Maximum Entropy) (Zhu et al., Neural Computation, 9:1627–1660). In this article, we bridge the two lines of research by the fundamental principle of equivalence of ensembles in statistical mechanics (Gibbs, 1902, Elementary Principles of Statistical Mechanics. Yale University Press). We show that 1). As the size of the image lattice goes to infinity, a FRAME model concentrates its probability mass uniformly on a corresponding Julesz ensemble. Therefore, the Julesz ensemble characterizes the global statistical property of the FRAME model; 2). For a large image randomly sampled from a Julesz ensemble, any local patch of the image given its environment follows the conditional distribution specified by a corresponding FRAME model. Therefore, the FRAME model describes the local statistical property of the Julesz ensemble, and is an inevitable texture model on finite (or small) lattice if texture perception is decided by feature statistics. The key to derive these results is the large deviation estimate of the volume of (or the number of images in) the Julesz ensemble, which we call the entropy function. Studying the equivalence of ensembles provides deep insights into questions such as the origin of MRF models, typical images of statistical models, and error rates in various texture related vision tasks (Yuille and Coughlan, IEEE Trans. on PAMI, Vol. 2, No. 2, 2000). The second thrust of this paper is to study texture distance based on the texture models of both small and large lattice systems. We attempt to explain the asymmetry phenomenon observed in texture pop-out experiments by the asymmetry of Kullback-Leibler divergence. Our results generalize the traditional signal detection theory (Green and Swets, 1988, Signal Detection Theory and Psychophysics, Peninsula Publishing) for distance measures from iid cases to random fields. Our theories are verified by two groups of computer simulation experiments.     

Random 2 XORSAT Phase Transition

We consider the 2-XOR satisfiability problem, in which each instance is a formula that is a conjunction of Boolean equations of the form x ⊕ y=0 or x ⊕ y=1. Formula of size m on n Boolean variables are chosen uniformly at random from among all ((n(n-1)) || (m)){n(n-1)\choose m} possible choices. When c<1/2 and as n tends to infinity, the probability p(n,m=cn) that a random 2-XOR formula is satisfiable, tends to the threshold function exp (c/2)⋅(1−2c)^1/4. This gives the asymptotic behavior of random 2-XOR formula in the SAT/UNSAT subcritical phase transition. In this paper, we first prove that the error term in this subcritical region is O(n ⁻¹). Then, in the critical region c=1/2, we prove that p(n,n/2)=Θ(n ^−1/12). Our study relies on the symbolic method and analytical tools coming from generating function theory which also enable us to describe the evolution of n^1/12 p(n,\fracn2(1+mn^-1/3))n^{1/12}\ p(n,\frac{n}{2}(1+\mu n^{-1/3})) as a function of μ. Thus, we propose a complete picture of the finite size scaling associated to the subcritical and critical regions of 2-XORSAT transition.     

On the number of control sets on projective spaces

The purpose of this paper is to provide an upper bound for the number of control sets for linear semigroups acting on a projective space . These semigroups and control sets were studied by Colonius and Kliemann (1993) who proved that there are at most d control sets. Here we apply the results of San Martin and Tonelli (1995) about control sets for semigroups in semisimple Lie groups and make a case by case analysis according to the transitive groups on P^d−1 which were classified by Boothby and Wilson (1975, 1979) in order to improve that upper bound. It turns out that in some cases there are at most d/2 or d/4 control sets.     

Optimal Routing in a Small-World Network

Substantial research has been devoted to the modelling of the small-world phenomenon that arises in nature as well as human society. Earlier work has focused on the static properties of various small-world models. To examine the routing aspects, Kleinberg proposes a model based on a d-dimensional toroidal lattice with long-range links chosen at random according to the d-harmonic distribution. Kleinberg shows that, by using only local information, the greedy routing algorithm performs in O（lg^2 n） expected number of hops. We extend Kleinberg＇s small-world model by allowing each node x to have two more random links to nodes chosen uniformly and randomly within （lg n）2/d Manhattan distance from x. Based on this extended model, we then propose an oblivious algorithm that can route messages between any two nodes in O（lg n） expected number of hops. Our routing algorithm keeps only O（（lgn）β＋1） bits of information on each node, where 1 〈 β 〈 2, thus being scalable w.r.t, the network size. To our knowledge, our result is the first to achieve the optimal routing complexity while still keeping a poly-logarithmic number of bits of information stored on each node in the small-world networks.     

The Combinatorics of Effective Resistances and Resistive Inverses

Let matrix (σ_ij) denote the edge conductances of an electrical network, so that there is a resistor ofr_ij=1/σ_ijohms between nodesiandj. This uniquely determines the matrix (R_ij) ofeffective resistances, defined such that if a potential of 1 V is applied across nodesiandj, a current of 1/R_ijwill flow. We call (σ_ij) theresistive inverseof (R_ij). One source of interest in the resistive inverse, arising in the design of on-line algorithms, is that it produces an efficient random walk if the walk must pay a cost ofr_ijfor traversing edge (i, j). Coppersmithet al.(1993,J. Assoc. Comput. Mach.40(3), 421–453) showed that the random walk that makes transitions according to (σ_ij) is more efficient—more “competitive”—than the random walk that makes transitions according to (R_ij). Coppersmithet al.gave a simple but obscure four-step algorithm for computing the resistive inverse. We give a complete self-contained combinatorial explanation of this algorithm, including the classical theorems of Kirchhoff and Foster.     

Predicting torsion angles in amino acid protein sequences based on a bayesian classification procedure on markov chains

Torsion angles formed by C ^α atoms of four neighboring residues are predicted using a Bayesian classification procedure on nonstationary Markov chains. The predicted sequence of torsion angles is used to construct a three-dimensional protein structure on Z ³ lattice.     

Compressing Two-Dimensional Routing Tables

We consider an algorithmic problem that arises in the context of routing tables used by Internet routers. The Internet addressing scheme is hierarchical, where a group of hosts are identified by a prefix that is common to all the hosts in that group. Each host machine has a unique 32-bit address. Thus, all traffic between a source group s and a destination group d can be routed along a particular route c by maintaining a routing entry (s, d, c) at all intermediate routers, where s and d are binary bit strings. Many different routing tables can achieve the same routing behavior. In this paper we show how to compute the most compact routing table. In particular, we consider the following optimization problem: given a routing table D with N entries of the form (s, d, c) , determine a conflict-free routing table with fewest entries that has the same routing behavior as D. If the source and destination fields have up to w bits, and there are at most K different route values, then our algorithm runs in worst-case time O( NK w ² ) .     

Performance Analysis for Dynamic Tree Embedding ink-Partite Networks by a Random Walk

We study the problem of dynamic tree embedding ink-partite networksG^kand analyze the performance on interpartition load distribution of the embedding. We show that, for ring-connectedG^k, if the embedding proceeds by taking a unidirectional random walk at a length randomly chosen from [0, Δ − 1], where Δ is a multiple ofk, the best-case performance is achievable at probability e^−k, which is much higher than the asymptotically zero probability at which the worst-case performance may appear. We also show that the same probabilities hold for fully connectedG^kif the embedding proceeds by taking a random walk at a length randomly chosen from [2, ∞). Whenk= 2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have a 50% chance to achieve the best-case performance. We also analyze the performances for embedding in these networks in the expected case and observe the interesting fact that they match the performances in the best case when the network isk-partitionable into partitions of equal size.     

Correlation structure of training data and the fitting ability of back propagation networks: Some experimental results

White [6–8] has theoretically shown that learning procedures used in network training are inherently statistical in nature. This paper takes a small but pioneering experimental step towards learning about this statistical behaviour by showing that the results obtained are completely in line with White's theory. We show that, given two random vectorsX (input) andY (target), which follow a two-dimensional standard normal distribution, and fixed network complexity, the network's fitting ability definitely improves with increasing correlation coefficient r_XY (0r_XY1) betweenX andY. We also provide numerical examples which support that both increasing the network complexity and training for much longer do improve the network's performance. However, as we clearly demonstrate, these improvements are far from dramatic, except in the case r_XY=+ 1. This is mainly due to the existence of a theoretical lower bound to the inherent conditional variance, as we both analytically and numerically show. Finally, the fitting ability of the network for a test set is illustrated with an example.Nomenclature X Generalr-dimensional random vector. In this work it is a one-dimensional normal vector and represents the input vector - Y Generalp-dimensional random vector. In this work it is a one-dimensional normal vector and represents the target vector - Z Generalr+p dimensional random vector. In this work it is a two-dimensional normal vector - E Expectation operator (Lebesgue integral) - g(X)=E(Y¦X) Conditional expectation - Experimental random error (defined by Eq. (2.1)) - y Realized target value - o Output value - f Network's output function. It is formally expressed asf: R ^r×WR ^p, whereW is the appropriate weight space - Average (or expected) performance function. It is defined by Eq. (2.2) as (w)=E[(Yf(X,w)],w W - Network's performance - w ^* Weight vector for optimal solution. That is, the objective of network is such that (w ^*) is minimum - C ₁ Component one - C ₂ Component two - Z Matrix of realised values of the random vectorZ overn observations - Z _t Transformed matrix version ofZ in such a way thatX andY have values in [0,1] - X _t ,Y _t Transformed versions ofX andY and both are standard one-dimensional normal vectors - n _h Number of hidden nodes (neurons) - r _XY Correlation coefficient between eitherX andY orX _t andY _t - _s and _k in Eq. (3.1) and afterwards _s is average value of 100 differentZ _t matrices. _k is the error function ofkthZ _t , matrix. In Eq. (3.1), the summation is fromk=1 to 100, and in Eq. (3.2) fromi=1 ton. In Eq. (3.2)o _ki andy _ki are the output and target values for the kthZ _t matrix and ith observation, respectively - ^1/2(w ^*) and _k (w_n) k(w_n) is the sample analogue of ^1/2(w ^*) - _Y ² In Eq. (4.1) and afterwards, _Y ² is the variance ofY - _Y ² variance ofY _t . In Sect. 4.3 the transformation isY _t=a Y+b - Y _max,Y _min the maximum and minimum values ofY - R Correlation matrix ofX andY - Covariance matrix ofX andY - Membership symbol in set theory     

Singular shift registers over residue class rings

The study of shift registers over the ringZ _p ^r (p a prime,r 1), in particular the singular case, is carried out, giving necessary and sufficient conditions to make a shift register singular. Its state graph is characterized as a tree, whose form depends on the characteristic polynomial of the shift register. The relationships with singular shift register overZ _p are explored and a proof of their equivalence is presented.Research sponsored by the National Science Foundation, Grant GK-1065x, and the Joint Services Electronics Program, Grant AFOSR-68-1488.Part of this work was done while the author was at Electronics Research Laboratory, University of California at Berkeley.     

Optimal numerical differentiation usingN function evaluations

An optimal choice ofu for approximating thed ^th derivative,d=1,2, of a real valued function of a real variable by a difference quotient of the formh ^−d ∑ _i=1 ⁿ w _i f(x+u _i h) is given. Ifd=1 andn is odd, or ifd=2 andn is even, this choiceu turns out to be surprisingly asymmetric.     

A test for multidimensional clustering tendency

This paper examines a d-dimensional extension of the Cox-Lewis statistic and investigates its power as a function of dimensionality in discriminating among random, aggregated and regular arrangements of points in d-dimensions. It was motivated by the Clustering Tendency problem which attempts to prevent the inappropriate application of clustering algorithms and other exploratory procedures. After reviewing the literature, the d-dimensional Cox-Lewis statistic is defined and its distribution under a randomness hypothesis of a Poisson spatial point process is given. Analytical expressions for the densities of the Cox-Lewis statistic under lattice regularity and under extreme clustering are also provided. The powers of Neyman-Pearson tests of hypotheses based on the Cox-Lewis statistic are derived and compared. Power is a unimodal function of dimensionality in the test of lattice regularity, with the minimum occurring at 12 dimensions.The power of the Cox-Lewis statistic is also examined under hard-core regularity and under Neyman-Scott clustering with Monte Carlo simulations. The Cox-Lewis statistic leads to one-sided tests for regularity having reasonable power and provides a sharper discrimination between random and clustered data than other statistics. The choice of sampling window is a critical factor. The Cox-Lewis statistic shows great promise for assessing the gross structure of data.     

惰性随机游走视觉显著性检测算法

目的 鉴于随机游走过程对人类视觉注意力的良好描述能力,提出一种基于惰性随机游走的视觉显著性检测算法。方法 首先通过对背景超像素赋予较大的惰性因子,即以背景超像素作为惰性种子节点,在由图像超像素组成的无向图上演化惰性随机游走过程,获得初始显著性图;然后利用空间位置先验及颜色对比度先验信息对初始显著图进行修正;最终通过基于前景的惰性随机游走产生鲁棒的视觉显著性检测结果。结果 为验证算法有效性,在MSRA-1000数据库上进行了仿真实验,并与主流相关算法进行了定性与定量比较。本文算法的Receiver ROC（operating characteristic）曲线及F值均高于其他相关算法。结论 与传统基于随机过程的显著性检测算法相比,普通随机游走过程无法保证收敛到稳定状态,本文算法从理论上有效克服了该问题,提高了算法的适用性;其次,本文算法通过利用视觉转移的往返时间来刻画显著性差异,在生物视觉的模拟上更加合理贴切,与普通随机游走过程采用的单向转移时间相比,效果更加鲁棒。     

Eclecticism shrinks even small worlds

We consider small world graphs as defined by Kleinberg (2000), i.e., graphs obtained from a d-dimensional mesh by adding links chosen at random according to the d-harmonic distribution. In these graphs, greedy routing performs in O(log ² n) expected number of steps. We introduce indirect-greedy routing. We show that giving O(log ² n) bits of topological awareness per node enables indirect-greedy routing to perform in O(log ^1+1/d n) expected number of steps in d-dimensional augmented meshes. We also show that, independently of the amount of topological awareness given to the nodes, indirect-greedy routing performs in Ω(log ^1+1/d n) expected number of steps. In particular, augmenting the topological awareness above this optimum of O(log ² n) bits would drastically decrease the performance of indirect-greedy routing. Our model demonstrates that the efficiency of indirect-greedy routing is sensitive to the “world’s dimension,” in the sense that high dimensional worlds enjoy faster greedy routing than low dimensional ones. This could not be observed in Kleinberg’s routing. In addition to bringing new light to Milgram’s experiment, our protocol presents several desirable properties. In particular, it is totally oblivious, i.e., there is no header modification along the path from the source to the target, and the routing decision depends only on the target, and on information stored locally at each node. A preliminary version of this paper appeared in the proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), St. Johns, Newfoundland, Canada, July 25–28, 2004.     

随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d＜1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.