Huang, Liang. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 109-116). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Learning on graphs has been studied for decades with abundant models proposed, yet many of their behaviors and relations remain unclear. This thesis fills this gap by introducing a novel second-order Markov chain, called partially absorbing random walks (ParWalk). Different from ordinary random walk, ParWalk is absorbed at the current state $i$ with probability $p_i$, and follows a random edge out with probability $1-p_i$. The partial absorption results in absorption probability between any two vertices, which turns out to encompass various popular models including PageRank, hitting times, label propagation, and regularized Laplacian kernels. The unified treatment reveals the distinguishing characteristics of these models arising from different contexts, and allows comparing them and transferring findings from one paradigm to another. The key for learning on graphs is capitalizing on the cluster structure of the underlying graph. The absorption probabilities of ParWalk, turn out to be highly effective in capturing the cluster structure. Given a query vertex $q$ in a cluster $\mathcal{S}$, we show that when the absorbing capacity ($p_i$) of each vertex on the graph is small, the probabilities of ParWalk to be absorbed at $q$ have small variations in region of high conductance (within clusters), but have large gaps in region of low conductance (between clusters). And the less absorbent the vertices of $\mathcal{S}$ are, the better the absorption probabilities can represent the local cluster $\mathcal{S}$. Our theory induces principles for designing reliable similarity measures and provides justification to a number of popular ones such as hitting times and the pseudo-inverse of graph Laplacian. Furthermore, it reveals their new important properties. For example, we are the first to show that hitting times is better in retrieving sparse clusters, while the pseudo-inverse of graph Laplacian is better for dense ones. The theoretical insights instilled from ParWalk guide us in developing robust algorithms for various applications including local clustering, semi-supervised learning, and ranking. For local clustering, we propose a new method for salient object segmentation. By taking a noisy saliency map as the probability distribution of query vertices, we compute the absorption probabilities of ParWalk to the queries, producing a high-quality refined saliency map where the objects can be easily segmented. For semi-supervised learning, we propose a new algorithm for label propagation. The algorithm is justified by our theoretical analysis and guaranteed to be superior than many existing ones. For ranking, we design a new similarity measure using ParWalk, which combines the strengths of both hitting times and the pseudo-inverse of graph Laplacian. The hybrid similarity measure can well adapt to complex data of diverse density, thus performs superiorly overall. For all these learning tasks, our methods achieve substantial improvements over the state-of-the-art on extensive benchmark datasets.

The use of networks to model the spread of epidemics through structured populations is widespread. However, epidemics on networks lead to intractable exact systems with the need to coarse grain and focus on some average quantities. Often, the underlying stochastic processes are Markovian and so are the resulting mean-field models constructed as systems of ordinary differential equations (ODEs). However, the lack of memory (or memorylessness) does not accurately describe real disease dynamics. For instance, many epidemiological studies have shown that the true distribution of the infectious period is rather centred around its mean, whereas the memoryless assumption imposes an exponential distribution on the infectious period. Assumptions such as these greatly affect the predicted course of an epidemic and can lead to inaccurate predictions about disease spread. Such limitations of existing approaches to modelling epidemics on networks motivated my efforts to develop non-Markovian models which would be better suited to capture essential realistic features of disease dynamics. In the first part of my thesis I developed a pairwise, multi-stage SIR (susceptible-infected-recovered) model. Each infectious node goes through some K 2 N infectious stages, which for K > 1 means that the infectious period is gamma-distributed. Analysis of the model provided analytic expressions for the epidemic threshold and the expected final epidemic size. Using available epidemiological data on the infectious periods of various diseases, I demonstrated the importance of considering the shape of the infectious period distribution. The second part of the thesis expanded the framework of non-Markovian dynamics to networks with heterogeneous degree distributions with non-negligible levels of clustering. These properties are ubiquitous in many real-world networks and make model development and analysis much more challenging. To this end, I have derived and analysed a compact pairwise model with the number of equations being independent of the range of node degrees, and investigated the effects of clustering on epidemic dynamics. My thesis culminated with the third part where I explored the relationships between several different modelling methodologies, and derived an original non-Markovian Edge-Based Compartmental Model (EBCM) which allows both transmission and recovery to be arbitrary independent stochastic processes. The major result is a rigorous mathematical proof that the message passing (MP) model and the EBCM are equivalent, and thus, the EBCM is statistically exact on the ensemble of configuration model networks. From this consideration I derived a generalised pairwise-like model which I then used to build a model hierarchy, and to show that, given corresponding parameters and initial conditions, these models are identical to MP model or EBCM. In the final part of my thesis I considered the important problem of coupling epidemic dynamics with changes in network structure in response to the perceived risk of the epidemic. This was framed as a susceptible-infected-susceptible (SIS) model on an adaptive network, where susceptible nodes can disconnect from infected neighbours and, after some fixed time delay, connect to a random susceptible node that they are not yet connected to. This model assumes that nodes have perfect information on the state of all other nodes. Robust oscillations were found in a significant region of the parameter space, including an enclosed region known as an 'endemic bubble'. The major contribution of this work was to show that oscillations can occur in a wide region of the parameter space, this is in stark contrast with most previous research where oscillations were limited to a very narrow region of the parameter space. Any mathematical model is a simplification of reality where assumptions must be made. The models presented here show the importance of interrogating these assumptions to ensure that they are as realistic as possible while still being amenable to analysis.

by Ma Ka Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 50-52). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.7 / Chapter 2 --- Queueing Networks --- p.9 / Chapter 2.1 --- One-queue Networks --- p.9 / Chapter 2.2 --- Two-queue Free Networks --- p.12 / Chapter 2.3 --- Two-queue Overflow Networks --- p.13 / Chapter 2.4 --- Networks with Batch Arrivals --- p.14 / Chapter 3 --- ODE Solvers --- p.16 / Chapter 3.1 --- The Initial Value Methods --- p.16 / Chapter 3.1.1 --- The Linear System of Ordinary Differential Equations --- p.16 / Chapter 3.1.2 --- Euler's Method --- p.17 / Chapter 3.1.3 --- Runge-Kutta Methods --- p.17 / Chapter 3.1.4 --- The Stability of the IVMs --- p.19 / Chapter 3.1.5 --- Applications in Queueing Networks --- p.20 / Chapter 3.2 --- The Boundary Value Methods --- p.20 / Chapter 3.2.1 --- The Generalized Backward Differentiation For- mulae --- p.21 / Chapter 3.2.2 --- An example --- p.24 / Chapter 4 --- The Linear Equation Solver --- p.26 / Chapter 4.1 --- Iterative Methods --- p.26 / Chapter 4.1.1 --- The Jacobi method --- p.27 / Chapter 4.1.2 --- The Gauss-Seidel Method --- p.28 / Chapter 4.1.3 --- Other Iterative Methods --- p.29 / Chapter 4.1.4 --- Preconditioning --- p.29 / Chapter 4.2 --- The Multigrid Method --- p.30 / Chapter 4.2.1 --- Iterative Refinement --- p.30 / Chapter 4.2.2 --- Restriction and Prolongation --- p.30 / Chapter 4.2.3 --- The Geometric Multigrid Method --- p.33 / Chapter 4.2.4 --- The Algebraic Multigrid Method --- p.38 / Chapter 4.2.5 --- Higher Dimensional Cases --- p.38 / Chapter 4.2.6 --- Applications in Queueing Networks --- p.38 / Chapter 5 --- Numerical Experiments --- p.41 / Chapter 6 --- Concluding Remarks --- p.49 / Bibliography --- p.50

設T為一於二維環面T²上，特徵值為整數的線性自同態，而D為一T²的Markov分割。那麼每一個D上定義的符號空間有限型子轉移則對應一個T²的T -不變緊子集K。判斷K的 Hausdor和Minkowski維數何時相等是一有趣問題。Kenyon and Peres [15]說明了此問題與(K, T )的測度熵及拓撲熵關係密切。這篇論文將進一步說明兩種維數的相等與符號動力系統及矩陣乘積的漸近性態的密切關係。此外我們描述一種算法以判斷兩個譜半徑為1的本原矩陣的任意乘積的譜半徑何時維持1，以及此算法對於研究sofic自仿集K的應用。 / Let T be a linear endomorphism on the 2-torus T² with integer eigenvalues, and D be a natural Markov partition (c.f. Bowen [4]) of T² . Then a subshift of nite type over D corresponds to a T-invariant compact subset K of T². An interesting problem is to determine when the Hausdorff and Minkowski dimensions of K conincide. Kenyon and Peres [15] showed that this is closely related to the measure-theoretic and topological entropies of (K, T). In this thesis, we further show that the coincidence of dimensions has a deep connection to symbolic dynamics and the asymptotic behaviour of matrix products. Moreover, we develop an algorithm to determine when the spectral radii of arbitrary products of two primitive matrices, with spectral radius 1, are preserved, and apply this algorithm to some sofic self-affine sets considered above. / Detailed summary in vernacular field only. / Lo, Chiu Hong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 55-56). / Abstracts also in Chinese. / Chapter 1 --- Introduction and Main Results --- p.6 / Chapter 2 --- Preliminaries --- p.12 / Chapter 2.1 --- Basic symbolic dynamics --- p.12 / Chapter 2.2 --- The symbolic representations --- p.13 / Chapter 2.3 --- An adapted covering of the invariant set KT (A) --- p.17 / Chapter 2.4 --- Some basic lemmas and theorems --- p.18 / Chapter 3 --- Proofs of Proposition 1.2 and Theorem 1.3 --- p.22 / Chapter 3.1 --- Proof of Proposition 1.2 --- p.22 / Chapter 3.2 --- Proof of Theorem 1.3 --- p.24 / Chapter 4 --- Projection of measure of maximal entropy for sub-shifts of finite type --- p.26 / Chapter 4.1 --- Projection of the Parry measure via a general factor map --- p.26 / Chapter 4.2 --- Proof of Theorem 1.4 --- p.36 / Chapter 5 --- Spectral radii of products of primitive matrices --- p.38 / Chapter 5.1 --- The algorithm --- p.40 / Chapter 5.2 --- Some applications and examples --- p.51 / Bibliography --- p.55

Chang, Kwong Wa = 一般量子系統非馬可夫領域的主方程 / 張光華. / "October 2010." / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 89-92). / Abstracts in English and Chinese. / Chang, Kwong Wa = Yi ban liang zi xi tong fei Makefu ling yu de zhu fang cheng / Zhang Guanghua. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Born-Markov Master Equations --- p.4 / Chapter 2.1 --- Master Equations from von Neumann equation --- p.4 / Chapter 2.2 --- Born Approximation --- p.6 / Chapter 2.3 --- Markov Approximation --- p.8 / Chapter 2.4 --- Born-Markov Approximation --- p.10 / Chapter 2.5 --- Lindblad Equation --- p.12 / Chapter 2.6 --- The Limitations of the Born-Markov Approximation --- p.16 / Chapter 2.7 --- Beyond Born and Markov Approximations --- p.20 / Chapter 2.7.1 --- General projection operator approach --- p.20 / Chapter 2.7.2 --- Time-local form of the master equation --- p.21 / Chapter 3 --- TCL non-Markovian Master Equation for Linear Systems --- p.24 / Chapter 3.1 --- Model --- p.24 / Chapter 3.2 --- The General Structure of the TCL non-Markovian Master Equation for Initially Factorizable States --- p.27 / Chapter 3.3 --- Determination of Unknown Coefficients --- p.32 / Chapter 3.4 --- Weak-Coupling Approximation --- p.46 / Chapter 3.5 --- Steady State Solutions --- p.51 / Chapter 4 --- An Application: Coherence Protection by Parity Kicks --- p.54 / Chapter 4.1 --- Review on Parity Kicks --- p.54 / Chapter 4.2 --- Parity Kicks oil Damped Harmonic Oscillators --- p.58 / Chapter 4.3 --- Numerical Results for Soft Pulses --- p.61 / Chapter 5 --- Other Initial States --- p.67 / Chapter 5.1 --- Factorizable States --- p.67 / Chapter 5.2 --- Non-Factorizable States --- p.73 / Chapter 6 --- Non-Markovianity --- p.75 / Chapter 6.1 --- The Concept of non-Markovianity --- p.75 / Chapter 6.2 --- A Recent Measure --- p.76 / Chapter 6.3 --- A Prospective Measure --- p.79 / Chapter 7 --- Conclusion --- p.87 / Bibliography --- p.89 / Chapter A --- Evolution of Factorizable Coherent State for Linear Damped Harmonic Oscillator with RWA --- p.93 / Chapter B --- "Derivation of G, L and F" --- p.95 / Chapter C --- Comparison of Equations of Motion for Master Equation Coefficients --- p.98

The purpose of this PhD thesis is to study mesoscopic and macroscopic fluctuations in Interacting Particle Systems. The thesis is split into two main parts. In the first part, we consider a system of Ising spins interacting via Kac potential evolving with Glauber dynamics and study the macroscopic motion of an one-dimensional interface under forced displacement as the result of large scale fluctuations. In the second part, we consider a diffusive system modelled by a Simple Symmetric Exclusion Process (SSEP) which is driven out of equilibrium by the action of current reservoirs at the boundary and study the non-equilibrium fluctuations around the hydrodynamic limit for the SSEP with current reservoirs. We give a brief summary of the first part. In recent years, there has been significant effort to derive deterministic models describing two-phase materials and their dynamical properties. In this context, we investigate the law that governs the power needed to force a motion of a one dimensional macroscopic interface between two different phases of a given ferromagnetic sample with a prescribed speed V at low temperature. We show that given the mesoscopic deterministic non-local evolution equation for the magnetisation (a non local version of the Allen-Cahn equation), we consider a stochastic Ising spin system with Glauber dynamics and Kac interaction (the underlying microscopic stochastic process) whose mesoscopic scaling limit (intermediate scale between microscale and macroscale) is the given PDE, and we calculate the corresponding large deviations functional which would provide the action functional. We obtain that by deriving upper and lower bounds of the large deviation cost functional. Concepts from statistical mechanics such as contours, free energy, local equilibrium allow a better understanding of the structure of the cost functional. Then we characterise the limiting behaviour of the action functional under a parabolic rescaling, by proving that for small values of the ratio between the distance and the time, the interface moves with a constant speed, while for larger values the occurrence of nucleations is the preferred way to make the transition. This led to a production of two published papers [12] and [14] with my supervisor D. Tsagkarogiannis and N. Dirr. In the second part we study the non-equilibrium fluctuations of a system modelled by SSEP with current reservoirs around its hydrodynamic limit. In particular, we prove that, in the limit, the appropriately scaled fluctuation field is given by a Generalised Ornstein- Uhlenbeck process. For the characterisation of the limiting fluctuation field we implement the Holley-Stroock theory. This is not straightforward due to the boundary terms coming from the nature of the model. Hence, by following a martingale approach (martingale decomposition) and the derivation of the equation of the variance for this model combined with “good” enough correlation estimates (the so-called v-estimates), we reduce the problem to a form whose Holley-Stroock result in [45] is now applicable. This is work in progress jointly with my supervisor and P. Gonçalves, [13].

"July 12, 2002" / Bibliography: p. 130-137 / viii, 160 leaves ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / Thesis (Ph.D.)--University of Adelaide, Dept. of Applied Mathematics, 2002

A random variable that is defined as the absorption time of an evanescent finite-state continuous-time Markov chain is said to have a phase-type distribution. A phase-type distribution is said to have a representation (α,T ) where α is the initial state probability distribution and T is the infinitesimal generator of the Markov chain. The distribution function of a phase-type distribution can be expressed in terms of this representation. The wider class of matrix-exponential distributions have distribution functions of the same form as phase-type distributions, but their representations do not need to have a simple probabilistic interpretation. This class can be equivalently defined as the class of all distributions that have rational Laplace-Stieltjes transform. There exists a one-to-one correspondence between the Laplace-Stieltjes transform of a matrix- exponential distribution and a representation (β,S) for it where S is a companion matrix. In order to use matrix-exponential distributions to fit data or approximate probability distributions the following question needs to be answered: “Given a rational Laplace-Stieltjes transform, or a pair (β,S) where S is a companion matrix, when do they correspond to a matrix-exponential distribution?” In this thesis we address this problem and demonstrate how its solution can be applied to the abovementioned fitting or approximation problem. / Thesis (Ph.D.)--School of Applied Mathematics, 2003.

Thesis (M. Phil.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.