text:
A Graph-Algorithmic Approachfor the Study of Metastability in Markov Chains

# A Graph-Algorithmic Approach for the Study of Metastability in Markov Chains

Tingyue Gan tgan@math.umd.edu Department of Mathematics, University of Maryland, College Park, MD 20742 Maria Cameron cameron@math.umd.edu Department of Mathematics, University of Maryland, College Park, MD 20742
July 5, 2019
###### Abstract

Large continuous-time Markov chains with exponentially small transition rates arise in modeling complex systems in physics, chemistry and biology. We propose a constructive graph-algorithmic approach to determine the sequence of critical timescales at which the qualitative behavior of a given Markov chain changes, and give an effective description of the dynamics on each of them. This approach is valid for both time-reversible and time-irreversible Markov processes, with or without symmetry. Central to this approach are two graph algorithms, Algorithm 1 and Algorithm 2, for obtaining the sequences of the critical timescales and the hierarchies of Typical Transition Graphs or T-graphs indicating the most likely transitions in the system without and with symmetry respectively. The sequence of critical timescales includes the subsequence of the reciprocals of the real parts of eigenvalues. Under a certain assumption, we prove sharp asymptotic estimates for eigenvalues (including prefactors) and show how one can extract them from the output of Algorithm 1. We discuss the relationship between Algorithms 1 and 2, and explain how one needs to interpret the output of Algorithm 1 if it is applied in the case with symmetry instead of Algorithm 2. Finally, we analyze an example motivated by R. D. Astumian’s model of the dynamics of kinesin, a molecular motor, by means of Algorithm 2.

## 1 Introduction

Phase transitions in non-equilibrium systems, conformational changes in molecules or atomic clusters, financial crises, global climate changes, and genetic mutations exemplify the phenomenon where a seemingly stable behavior of a system in hand, persisting for a long time, undergoes a sudden qualitative change. Such systems are often referred to as metastable. A popular choice of mathematical model for investigating such systems is a Markov jump process with a finite number of states and exponentially distributed holding times. The dynamics of the process is described by the generator matrix . Each off-diagonal entry of is the transition rate from state to state . Often, it takes the form [25, 18]

 Lij=κijexp(−Uij/ε), (1)

where is the pre-factor, the number is the exponential factor or order, and is a small parameter. In many cases, the pre-factors are not available, and the rates are determined only up to the exponential order:

 Lij≍exp(−Uij/ε),\leavevmode\nobreak \leavevmode\nobreak i.e.\leavevmode\nobreak \leavevmode\nobreak limε→0εlogLij(ε)=−Uij. (2)

The reciprocal is the expected waiting time for a jump from state to state . The diagonal entries are defined so that the row sums of are zeros, i.e., . Hence, is the escape rate from state .

A Markov chain with pairwise rates of the form (1) or (2) can be associated with a weighted directed graph where the set of vertices is the set of states, the set of arcs includes only such arcs that , and is the set of arc weights. An arc has weight if . We set if , i.e., if there is no arc in the graph.

In this work, we will consider continuous-time Markov chains with finite numbers of states and pairwise transition rates of the form (1) or (2). Under this framework, the timescales on which various transition processes take place in the system are well-separated as tends to zero. Our goal is to find a constructive way to calculate the sequence of critical timescales at which the behavior of such a Markov chain undergoes qualitative changes, and give effective descriptions of its behavior on the whole range of timescales from zero to infinity. Imagine that the time evolution of a given Markov chain is observed for some not very large fixed number of time units. We want to be able to predict what transitions the observer will see depending on the initial state and the size of the time unit. Such a prediction is easy if the time unit tends to zero. Then it is extremely unlikely to observe any transitions. If the time unit tends to infinity, then an equilibrium probability distribution will be observed. However, even in this case, the determination of arcs along which the transitions will be most likely observed remains a nontrivial problem. On timescales between those two extremes, the problem of giving an effective description of the observable transitions is difficult. Prior to presenting our solution to it, we give an account of works that provided us with necessary background and/or inspiration.

### 1.1 Background

Long-time behavior of stochastic systems with rare transitions has been attracting attention of mathematicians for the last fifty years. Freidlin and Wentzell developed the Large Deviation Theory [18] in 1970s. They showed that the long-time behavior of a system evolving according to the SDE

 dXt=b(Xt)dt+√εdWt

can be modeled by means of continuous-time Markov chains. The states of the Markov chain correspond to attractors of the corresponding ODE . The pairwise rates are logarithmically equivalent to , where is the quasi-potential, the quantity characterizing the difficulty of the passage from attractor to attractor . Recently, Buchet and Reygner [5] calculated the pre-factor in the case where state represents a stable equilibrium point separated from the attractor corresponding to state by a Morse index one saddle.

In early 1970s, Freidlin proposed to describe the long-time behavior of the system via a hierarchy of cycles (we refer to them as Freidlin’s cycles) [15, 16, 18] in the case where each cycle has a unique main state, a unique exit arc, and the exit rates for all cycles are distinct. This hierarchy can be mapped onto a tree. In the time-reversible case, this tree is a complete binary tree [10]. Later, in 2014, Freidlin extended this approach to the case with symmetry [17] replacing the hierarchy of cycles with the hierarchy of Markov chains. Each cycle/Markov chain in Freidlin’s hierarchy is born at a specific critical timescale, which is the reciprocal of its rotation rate. The corresponding hierarchy of timescales has only partial but not complete order: cycles/Markov chains of the same order typically have different timescales. The birth timescales of Freidlin’s cycles/Markov chains constitute an important subset of critical timescales of the system.

The other important subset of critical timescales is given by the reciprocals of the absolute values of the real parts of nonzero eigenvalues of the generator matrix . Using the classic potential theory as a tool, Bovier and collaborators [6, 7, 8, 9] derived sharp estimates for low lying spectra of time-reversible Markov chains (all their eigenvalues are real) with pairwise rates not necessarily of the form (1), defined a hierarchy of metastable sets, and identified the link between eigenvalues and expected exit times. A more general study, utilizing almost degenerate perturbation theory, was conducted by Gaveau and Schulman [19], in which a spectral definition of metastability was given for a broad class of Markov chains. The Transition Path Theory proposed by E and Vanden-Eijnden and extended to Markov chains by Metzner et al [23], can be viewed as an extension of the potential-theoretic approach exercised by Bovier et al in the time-irreversible case. It is focused on the study of transition pathways between any particular pair of metastable sets.

Asymptotic estimates of the exponential orders of the real parts of eigenvalues of the generator matrix of any Markov chain with pairwise rates of the form (2) were developed by Wentzell in early 1970s [30]. These estimates are given in terms of the optimal W-graphs, i.e., solutions of certain combinatoric optimization problems on so-called W-graphs. Assuming the more concrete form (1) of the pairwise transition rates, we have derived asymptotic estimates for eigenvalues including pre-factors for the case where all optimal W-graphs are unique. Greedy graph algorithms to solve these optimization problems in case where all optimal W-graphs are unique were introduced in [11] and [12]. The one in [11] assumes time-reversibility and finds the sequence of asymptotic estimates for eigenvalues starting from the smallest ones. The greedy/dynamical programing “single-sweep algorithm” in [12] does not require time-reversibility and computes the sequence of asymptotic estimates for eigenvalues starting from the largest ones. Sharp estimates for eigenvalues for the time-reversible case with symmetry were obtained by Berglund and Dutercq using tools from the group representation theory [4].

### 1.2 Summary of main results

The starting point of this work is the single-sweep algorithm. In [12], we introduced it in the form convenient for programming and used it only for the purpose of finding asymptotic estimates for eigenvalues and eigenvectors of the large time-reversible Markov chain with 169523 states representing the energy landscape of the Lennard-Jones-75 cluster.

In this work, we extend the single-sweep algorithm [12] for finding the whole sequence of critical timescales corresponding to both, births of Freidlin’s cycles and reciprocals of the absolute values of the real parts of eigenvalues. Besides the set of critical timescales, the output will include the hierarchy of Typical Transition Graphs (T-graphs) introduced in this work, that mark the transitions most likely to observe up to certain timescales. Wentzell’s optimal W-graphs are readily extracted from the T-graphs. We will refer to this extension of the single-sweep algorithm as Algorithm 1. The presentation of Algorithm 1 is significantly different from the one in [12]. Each step of Algorithm 1 is motivated by the consideration of the dynamics of the system at an appropriate timescale.

Algorithm 1 offers a constructive way to simultaneously solve both Freidlin’s problem of building the hierarchy of cycles and Wentzell’s problem of finding asymptotic estimates for eigenvalues. Contrary to [15, 16, 18], Freidlin’s cycles are found in the decreasing order of their rotation rates. Asymptotic estimates for eigenvalues, containing pre-factors (if so do the input data), are found during the run of Algorithm 1. Our proof for sharp asymptotic estimates of eigenvalues of the generator matrix for time-irreversible Markov chains for which all optimal W-graphs are unique is provided.

From the programming point of view, Algorithm 1 and the single-sweep algorithm in [12] differ in their stopping criteria. Algorithm 1 stops as it computes all Freidlin’s cycles. The costs of the single-sweep algorithm and Algorithm 1 and the difference between them depend on the structure of the graph. For a graph with vertices and maximal vertex degree , the cost of both algorithms are at worst .

Algorithm 1 is designed for the case with no symmetry, i.e., where all critical timescales are distinct and all Freidlin’s cycles have unique exit arcs. Markov chains arising in modeling complex physical systems might or might not be symmetric. For example, the networks representing energy landscapes of biomolecules and clusters of particles interacting according to a long-range potential [26, 27, 28, 29] are mostly non-symmetric, while the networks representing the dynamics of particles interacting according to a short-range potential [2, 22, 3, 21] are highly symmetric.

To handle the case with symmetry, we have developed a modification of Algorithm 1 and called it Algorithm 2. Algorithm 2 computes the sequence of distinct values of critical timescales and the hierarchy of T-graphs.

The presence of symmetry is not necessarily apparent in a Markov chain. Algorithm 1 can run in the case with symmetry and produce an output that does not reflect its presence. However, the output will be inaccurate in some aspects. The relationship between the outputs of Algorithms 1 and 2 and a recipe for the interpretation of the output of Algorithm 1 used in a symmetric case is summarized in a theorem proven in this work.

Algorithms 1 and 2 constitute a graph-algorithmic approach to the study of metastability in continuous-time Markov chains with exponentially small transition rates.

Algorithms 1 and 2 are illustrated on examples. The case with symmetry is not as graphic as the one without it, however, it is important, as symmetry often occurs in Markov chains modeling natural systems. One such example, motivated by Astumian’s model [1] of the directed motion of kinesin protein, a molecular motor, is analyzed by means of Algorithm 2. The stochastic switch between two chemical states, breaking the detailed balance in this system, enables the directed motion (walking). The rate of the chemical switch is treated as a parameter. The most likely walking style is indicated for each rate value.

The rest of the paper is organized as follows. Some necessary background on continuous-time Markov chains and optimal W-graphs is provided in Section 2. The T-graphs are introduced in Section 3. Algorithm 1 is presented and discussed in Section 4. In Section 5, we address the case with symmetry and introduce Algorithm 2. The interpretation of the output of Algorithm 1 applied in the case with symmetry is given in Section 6. The molecular motor example is investigated in Section 7. We summarize our work in Section 8. Appendices A and B contain proofs of theorems.

## 2 Significance and nested property of optimal W-graphs

In this Section, we provide some necessary background and discuss some of our recent results that are essential for the presentation of our new developments.

### 2.1 Continuous-time Markov chains

Let be a weighted directed graph associated with a given continuous-time Markov chain with pairwise transition rates of the form (1) or (2). Throughout the rest of the paper we adopt the following assumptions.

###### Assumption 1.

The set of states is finite and .

###### Assumption 2.

The graph has a unique closed communicating class.

We remind (see e.g. [24]) that a subset of vertices is called a communicating class, if there is a directed path leading from any vertex to any vertex . A communicating class is called closed if for any vertex the following condition holds: if there is a directed path from to , then . A trivial example of a closed communicating class is an absorbing state, i.e., a state with no outgoing arcs. All states of an irreducible Markov chain belong to the same closed communicating class.

In a weighted directed graph with a single closed communicating class , all states in are recurrent, while the rest of the states are transient. Assumption 2 guarantees that the invariant distribution satisfying , , , and , is unique and supported only on the recurrent states. Note that is the left eigenvector of corresponding to the zero eigenvalue . Due to the zero row sum property of , the corresponding right eigenvector is .

Due to the weak diagonal dominance of and non-positivity of its diagonal entries, all its eigenvalues have non-positive real parts. This can be shown, e.g., by applying Gershgorin’s circle theorem [20]. Let , , be nonzero eigenvalues of , ordered so that , and column vectors and row vectors be the corresponding right and left eigenvectors. If is diagonalizable, one can write the probability distribution , governed by the Fokker-Planck equation , in the following form:

 p(t)=p(0)etL=π+n−1∑m=1e−λmteiμmt(p(0)ϕm)ψm. (3)

Considering the time as a function of , one can infer from Eq. (3) that the th eigen-component of is significant only for time of an exponential order not greater than the one of .

### 2.2 Optimal W-graphs

The W-graphs were introduced by Wentzell [30] in order to obtain asymptotic estimates for exponential factors of real parts of eigenvalues of the generator matrices of Markov chains with pairwise rates of the form (2). The W-graphs generalize the -graphs introduced by Freidlin [15, 16] for building the hierarchy of cycles describing the long-term behavior of such Markov chains.

###### Definition 2.1.

(W-graph) Let be a weighted directed graph satisfying Assumptions 1 and 2. A W-graph with sinks is a subgraph of with the same set of vertices such that

1. vertices have exactly one outgoing arc in , while the other vertices, called sinks, have no outgoing arcs in ;

2. contains no cycles.

Assumptions 1 and 2 guarantee the existence of a W-graph with any sinks. If , there is the unique W-graph, and it has no arcs. A W-graph with sinks is a forest consisting of connected components. Each connected component is a directed in-tree, i.e., a rooted tree with arcs pointing towards its root (sink). The collection of all possible W-graphs with sinks will be denoted by .

Asymptotic estimates for eigenvalues are defined by a collection of W-graphs with minimal possible sums of weights of their arcs [30]. We call such graphs optimal W-graphs and denote by . Precisely,

###### Definition 2.2.

(Optimal W-graph) is an optimal W-graph with sinks if and only if

 g∗m=argming∈G(m)V(g),\leavevmode\nobreak \leavevmode\nobreak where\leavevmode\nobreak \leavevmode\nobreak V(g):=∑(i→j)∈gUij. (4)

For brevity, we write meaning , where is the set of arcs of . We emphasize that, in the optimal W-graph, the sum of weights needs to be minimized simultaneously with respect to the choices of sinks and arcs.

### 2.3 Asymptotic estimates for eigenvalues

Wentzell established the following asymptotic estimates for eigenvalues in terms of the optimal W-graphs [30]:

###### Theorem 2.3.

(Wentzell, 1972)111No proof of Theorem 1 was provided in [30]. We are not aware of any published proof of this result. Let be the eigenvalues of the generator matrix with off-diagonal entries of the order of , ordered so that . Then as ,

 λm≍exp(−Δm/ε),whereΔm:=V(g∗m)−V(g∗m+1),m=1,2,⋯,n−1. (5)

Theorem 1 implies [30] that

 Δ1≥Δ2≥⋯≥Δn−1>0. (6)

Assumption 3 below allows us to derive a number of important facts.

###### Assumption 3.

For all , the optimal W-graphs are unique.

It is, in essence, a genericness assumption, because if the weights are random real numbers in an interval , then it holds with probability one.

Under Assumption 3, the strict inequalities take place in Eq. (6). Hence, if is sufficiently small, all eigenvalues are real and distinct [30]. In this case, for a generator matrix with off-diagonal entries of the form (1), the estimates given by Theorem 1 can be made more precise.

###### Theorem 2.4.

Suppose a Markov chain with pairwise rates of the form satisfies Assumptions 1, 2, and 3. Let be eigenvalues of the corresponding matrix . Then as , for we have

 λm =αmexp(−Δm/ε)(1+o(1)),where (7) Δm :=V(g∗m)−V(g∗m+1),αm:=∏(i→j)∈g∗mκij∏(i→j)∈g∗m+1κij.

Originally, we formulated Theorem 2.4 in [12] but did not provide a detailed proof in order to stay focused on practical matters. Here, we provide a proof of Theorem 2.4 in Appendix A as promised in [12]. The key point in this proof is the relationship between the coefficients of the characteristic polynomial of and the W-graphs with the corresponding numbers of sinks.

### 2.4 Weak nested property of optimal W-graphs

In [12], under Assumption 3, we proved a weak nested property of optimal W-graphs, a pivotal property that serves as a stepping stone in the design of the single sweep algorithm [12] and Algorithm 1, and facilitates a deeper understanding of the metastable behavior of continuous-time Markov chains. The weak nested property can be compared to a stronger nested property of optimal W-graphs taking place if the underlying Markov chain is time-reversible [11].

A connected component of a W-graph will be identified with its set of vertices. will denote the set of arcs of with tails in .

###### Theorem 2.5.

(The weak nested property of optimal W-graphs [12]) Suppose that Assumptions 1, 2, and 3 hold. Then the following statements are true.

1. There exists a unique connected component of , whose sink is not a sink of .

2. , i.e. the arcs in with tails in coincide with those in . However, and do not necessarily coincide.

3. There exists a single arc with tail in and head in another connected component with sink of .

Theorem 2.5 is illustrated in Fig. 1. The optimal W-graph is obtained from by adding an arc with tail and head lying in different connected components of , denoted by and respectively, and possibly rearranging some arcs with tails and heads in . We say that is absorbed by to form . All arcs of with tails not in are inherited by .

## 3 Freidlin’s hierarchies, the critical timescales, and the T-graphs

In this Section, we introduce the Typical Transition Graphs or T-graphs for continuous-time Markov chains with pairwise rates of the form of Eq. (1) or (2). Originally, the T-graphs arose as a byproduct of the single-sweep algorithms [12]. In this work, we connect the T-graphs to Freidlin’s construction of the hierarchy of cycles/Markov chains [15, 16, 18, 17].

A timescale is a function of defined up to the exponential order: we say that is logarithmically equivalent to and write

 t(ε)≍eθ/ε\leavevmode\nobreak \leavevmode\nobreak \leavevmode\nobreak if\leavevmode\nobreak \leavevmode\nobreak \leavevmode\nobreak limε→0εlog(t(ε))=θ.

For brevity, we write

 t>eθ1/ε\leavevmode\nobreak \leavevmode\nobreak \leavevmode\nobreak  implying that \leavevmode\nobreak \leavevmode\nobreak \leavevmode\nobreak limε→0εlog(t(ε))>θ1,

and adopt analogous meanings for all other inequality signs for comparing timescales.

For every vertex , let . The outgoing arcs from of the minimal weight will be called min-arcs from , and the set of all min-arcs from will be denoted by . If a Markov jump process starts at state , then the probability of the first jump along an arc is given by

 Pi(i→j)=Lij∑l≠iLil=κije−Uij/ε∑l≠iκile−Uil/ε=[κij∑(i→l)∈Amin(i)κil]e−(Uij−Umin(i))/ε(1+o(1)). (8)

Eq. (8) shows that remains positive as if an only if the arc is a min-arc from . The expected exit time from is logarithmically equivalent to .

For simplicity of the presentation below, we adopt

###### Assumption 4.

The Markov chain associated with the graph is irreducible.

Freidlin’s construction of the hierarchy of cycles/Markov chains [15, 16, 17] can be outlined as follows (with minor terminological modifications). We begin with the graph with the set of states and no arcs. All vertices are called the zeroth order Markov chains. Then all min-arcs from all vertices are added to resulting in the graph

 G1(S,A1,U1),\leavevmode\nobreak \leavevmode\nobreak where\leavevmode\nobreak \leavevmode\nobreak A1:=⋃i∈SAmin(i),U1={Uij\leavevmode\nobreak |\leavevmode\nobreak (i→j)∈A1}.

All nontrivial closed communicating classes in (i.e., consisting of more than one state), are called the first order cycles/Markov chains. The birth timescale of each first order cycle/Markov chain (the reciprocal of its rotations rate) is the maximal expected holding time among its vertices. If there is only one first order cycle/Markov chain, and it contains the whole set of states , the construction is fulfilled. Otherwise, each first order cycle/Markov chain is treated as a macro-state. For each macro-state, the exit rate and the set of exit arcs along which the process escapes from it with probability that remains positive as are found. These exit arcs are the min-arcs from the macro-states. Their weights are modified to set them equal to the exponential factors of their exit rates. Contracting the macro-states into single super-vertices, one obtains the graph which is a directed forest. The graph is obtained from by adding all min-arcs from the macro-states with their modified weights. Then one checks for nontrivial closed communicating classes in . If there is a unique closed communicating class comprising the whole set of states , the process terminates. Otherwise, it is continued in the same manner as it was done for the graph . This recursive procedure will terminate in a finite number of steps with a graph . It produces the hierarchy of Freidlin’s cycles/Markov chains of orders . The one of order comprises the whole set of states . Recursively restoring all contracted closed communicating classes while keeping the modified arc weights, one obtains the graph . We will call the transitions corresponding to arcs of the graph typical transitions and associate them with the corresponding associated timescales .

We remark that the birth timescales and exit timescales of the cycles/Markov chains are only partially ordered in the sense that if is a closed communicating class in some containing a super-vertex comprising a closed communicating class that the birth timescale of is greater than the one of , and the holding time in is greater than the one in . However, if and are closed communicating classes in and respectively, where , it is possible that the birth and exit timescales of are greater than those of . Furthermore, the order in which arcs are added to to form eventually is, in general, neither increasing nor decreasing order of their modified or original weights.

In this work, we propose an alternative construction that builds the graph from by adding arcs to it in the increasing order of their modified weights. In our construction, the procedure of finding the exit rates from the closed communicating classes is simpler than that in Freidlin’s one due to the order in which the arcs are added.

###### Definition 3.1.

(Critical exponents and T-graphs) Let be the graph obtained as a result of the construction of the hierarchy of Freidlin’s cycles/Markov chains as described above. The ordered subset of defined by

 γ1≤…≤γK:=Q−1⋃q=0{U(q)min(i)\leavevmode\nobreak |\leavevmode\nobreak i∈S(q)} (9)

and is the set of critical exponents. The corresponding timescales , …, are the critical timescales.

Let be the ordered set of distinct numbers in . The Typical Transition Graph or T-graph is the subgraph of containing all arcs of weights up to , i.e., where

 A(Tp)={i→j∈A∗\leavevmode\nobreak |\leavevmode\nobreak U∗ij≤θp},U(Tp)={U∗ij∈U∗\leavevmode\nobreak |\leavevmode\nobreak U∗ij≤θp},p=0,1,…,P. (10)

The T-graph is associated with the range of timescales for . The T-graphs and are associated with the ranges of timescales and .

Algorithm 1 in Section 4 builds the hierarchy of the critical exponents and the T-graphs in the case where all critical exponents , , are distinct and the min-arcs from each vertex and each closed communicating class are unique. In this case, and , , and all closed communicating classes in all graphs , , are simple directed cycles. Each of these cycles has the unique main state, where the system is found with probability close to one for small enough provided that it is in the cycle, and the unique exit arc, via which the system escapes from the cycle with probability close to one for small enough . Furthermore, the exit rates from the all cycles of all orders are distinct. We refer to such a case as a case with no symmetry. In this case, one can subdivide the set of the critical exponents , , into two subsets associated with the set of nonzero eigenvalues and the births of cycles respectively. Besides, if the pairwise rates are of the form , one can obtain the sharp estimates for the eigenvalues from the output of Algorithm 1. Finally, the unique hierarchy of the optimal W-graphs can be easily extracted from the found T-graphs.

Algorithm 2 presented in Section 5.2 is designed to handle the case with symmetry, i.e., the one where at least two critical exponents coincide or at least one vertex or a closed communicating class has a non-unique min-arc. It computes the set of numbers , , and the hierarchy of the T-graphs .

Algorithm 1 is design to handle the case with no symmetry. However, it might be impossible to determine the presence of symmetry by the input data and output of Algorithm 1. This can happen if one of the closed communicating classes has more that one min-arc. Hence the symmetry test should be made at each step of the while-cycle in the code. Suppose the code implementing Algorithm 1 detects some symmetry while running, but continues running and terminates normally. In this case, its output will contain a correct set of distinct values of the critical exponents, while the set of graphs will not be the correct set of the T-graphs. Nevertheless, one can still extract some important facts about the true T-graphs from its output. Section 6 contains a discussion and a theorem on this subject.

## 4 Algorithm 1 for the study of the metastable behavior

In this Section, we design Algorithm 1 that (a) finds the set of critical exponents and (b) builds the hierarchy of T-graphs. Throughout this Section, we adopt Assumption 1-4 and

###### Assumption 5.

All min-arcs are unique at every stage of Algorithm 1 presented below, and all critical exponents are distinct.

The while-loop in Algorithm 1 is essentially the same as the one in the “single-sweep algorithm” introduced in [12] for finding asymptotic estimates for eigenvalues and the hierarchy of optimal W-graphs. However, Algorithm 1 has a different stopping criterion and used for a broader, more ambitious purpose. More output data are extracted. Furthermore, the presentations of these algorithms are very different. Here, the description of Algorithm 1 serves the purpose of understanding the metastable behavior of the Markov process. Its recursive structure and Contract and Expand operators reflect the processes taking place on various timescales. On the contrary, the single-sweep algorithm was presented in [12] as a recipe for programming, where the key procedures were manipulations with various sets of outgoing arcs. It was not recursive and involved no Contract and Expand operators.

### 4.1 The recursive structure of the algorithm

Assumption 5 implies that a Markov process starting at a vertex leaves via the unique min-arc from denoted by with probability approaching one as . For every vertex , we select the unique min-arc , sort the set of min-arcs according to their weights in the increasing order, and call the sorted set the bucket .

We start with the bucket containing arcs and a graph containing all vertices of and no arcs. At each step of the main cycle of Algorithm 1, the minimum weight arc in the bucket is transferred to the graph .

At step one, the arc of the minimum weight in the whole graph is transferred to . Set and . The graph coincides with the optimal W-graph with sinks. Theorem 2.4 implies that the eigenvalue is approximated by Hence, and .

At step two, we transfer the next arc from the bucket to the graph . Set and . If contains no cycles, the optimal W-graph with sinks coincides with , the eigenvalue , and , .

We continue transferring arcs from to in this manner until the addition of a new arc creates a cycle in the graph . This will happen sooner or later because, if all arcs in are transferred to the graph with vertices, a cycle must appear in (see Lemma B.2 in Section 6).

Suppose a cycle is formed after the arc of weight was added to the graph . Abusing notations, we treat as a graph or its set of vertices depending on the context. We need to identify the exit arc from , i.e., the arc with and such that the probability to exit via tends to one as . We discard all arcs with tails and heads both in and modify the weights and pre-factors of all remaining outgoing arcs from according to the following rule:

 Unewij=Uij+γlast−Uμ(i),κnewij=κijκμlastκμ(i). (11)

Note that none of the arcs with modified weight is in the bucket at this moment, and all min-arcs with tails in have been already removed from and added to the graph . The update rule is of crucial importance for Algorithm 1. It is consistent with the one in [16]. A simple explanation for it is provided in Section 4.3 below. The number shows what would be the total weight of the graph obtained from the last found optimal W-graph by replacing the arc with and adding the arc (see [12] for more details). Then we contract the cycle to a single vertex (a super-vertex) . Finally, among the arcs with tails in , we find an arc with minimal modified weight, denote it by , and add it to the bucket . By Assumption 5, such an arc is unique. The idea of such a contraction is borrowed from the Chu-Liu/Edmonds algorithm [13, 14] for finding the optimal branching when the root is given a priori.

We continue adding arcs and contacting cycles in this manner. Note that the indices of the numbers are equal to the number of steps or, equivalently, to the arcs removed from the bucket and added to the graph T-graph where is the current recursion level, i.e., the number of cycles contracted into super-vertices. All arc additions not leading to cycles are associated with eigenvalues. The indices of the numbers and at step are .

The main cycle terminates as the bucket becomes empty. This stopping criterion allows us to obtain the whole collection of the critical timescales and the whole hierarchy of T-graphs. Suppose the main cycle terminates at the recursion level . Then Algorithm 1 returns to the previous recursion level and expands super-vertex back into the cycle . Then, if , Algorithm 1 returns to the recursion level and expands super-vertex back into the cycle . And so on, until recursion level zero is reached. After that, one can extract the optimal W-graphs out of the appropriate T-graphs..

Below, Algorithm 1 is given in the form of a pseudocode. The operators Contract and Expand are described in Section 4.2 below.

Algorithm 1
Initialization: Set step counter , cycle or recursion depth counter , and eigenvalue index . Prepare the bucket , i.e., for every state , find the min-arc , and then sort the set according to the arc weights in the increasing order:

 Uμ1

The graph is original graph .
Set the graph . Set .

The main body of the Algorithm: Call the function FindTgraphs with arguments , , , , and .
Function FindTgraphs
while is not empty and has no cycles
(1) Increase the step counter: ;
(2) Transfer the minimum weight arc from the bucket to the graph ;
(3) Set ;
(4) Set ;
(5) Check whether has a cycle; if so, denote the cycle by ;
if contains no cycle
(6) Decrease the eigenvalue index and set ; ;
(7) Set and denote by the sink of

the connected component of containing the tail of ;

end if
end while
if a cycle was detected at step (5)
(8) Save the index at which the cycle arose: set ;
(9) Remove the arcs with both tails and heads in (if any);
if the set of arcs of with tails in and heads not in is not empty
(10) Modify weights and pre-factors of all arcs

with tails in and heads not in according to Eq. (11);

(11) Contract into a super-vertex :

= Contract; = Contract;

(12) Denote the min-arc from by and add it to ;
(13) Call the function FindTgraphs;
(14) Expand the super-vertex back into the cycle :

for = Expand; end for

end if
end if
end

The flow chart of Algorithm 1 is shown in Fig. 2. At each recursion level, the T-graphs obtained in the while-cycle are placed into the green boxes, while the ones obtained by the Expand operator are placed into the yellow boxes. The number is the index of the last step of Algorithm 1. At , cycle is detected in . Hence steps (8) and (9) are performed. However, since it is the last step, the set of arcs in with tails in and heads not in is empty. Therefore, steps (10) - (14) are not executed. Instead, the algorithm returns to the previous recursion level and lands at step (14) where the function Expand is called.

The output of Algorithm 1 consists of several datasets.

• The set of critical exponents defining the critical timescales .

• The hierarchy of T-graphs , indicating the most likely transitions to observe up to timescales , where , , …, respectively.

• The set of exponents and pre-factors determining sharp estimates of eigenvalues according to . Note that .

• The set of sinks and . The optimal W-graph has the sinks where the sink is defined as the sink . The sinks are the sinks of those connected components of the optimal W-graphs that absorb the connected components with sinks as the graphs are created. The sets of vertices in connected components of the optimal W-graph coincides with those of the T-graph . An explanation how one can extract the optimal W-graphs from the graphs is given in Section 4.4.

• The set of step numbers at which the cycles are created.

###### Remark 4.1.

The number of arcs in the bucket is reduced by one after each step when no cycle is created, and remains that same otherwise. Let be the smallest step index such that the number of arcs in the bucket at the end of step reaches one. The eigenvalue index switches to during step . A new cycle will be obtained at every step such that . For all , the T-graphs are connected, while for all , are not connected.

###### Remark 4.2.

The total number of steps and the total number of cycles satisfy the relationship

 K−Nc=n−1. (12)

The maximal recursion level . Hence .

###### Remark 4.3.

In the case of a time-reversible Markov chain, the total number of Freidlin’s cycles of nonzero orders is [10]. Therefore, the total number of steps made by Algorithm 1 in this case will be . In the general case, the total number of cycles satisfies

 1≤Nc≤n−1. (13)

Indeed, let us construct a directed rooted tree of cycles, whose leaves are the vertices, the root is the cycle , the other nodes correspond to the cycles , , and whose arcs are directed toward the root. Each node of this tree except for the root has exactly one outgoing arc. Hence, the total number of arcs is . On the other hand, the nodes corresponding to the cycles , have at least two incoming arcs. Therefore, the number of arcs must satisfy

 Na=n+Nc−1≥2Nc.

This inequality implies that . Besides, Assumption 4, implies that there must be at least one cycle. This proves Eq. (13). Hence, the maximal possible recursion depth is achieved if and only if the Markov chain is time-reversible.

###### Remark 4.4.

The stopping criterion of Algorithm 1 can be modified depending on the goal. If one would like to use Algorithm 1 only for finding estimates for eigenvalues and optimal W-graphs, it suffices to stop the while-cycle as soon as . If one would like to find all T-graphs for the timescales , one needs to stop the while-cycle as soon as .

###### Remark 4.5.

For programming purposes, if a cycle is encountered, it is more convenient to merge the sets of outgoing arcs from the vertices in instead of contracting into a single super-vertex as it is done in the single-sweep algorithm in [12].

### 4.2 The functions Contract and Expand

The function = Contract maps the graph onto the graph as follows. All vertices of belonging to the cycle are mapped onto a single vertex of . More formally, let and . Let be the subset of vertices lying in the cycle , and be the subset of arcs of defined by

 Ac:={(i→j)\leavevmode\nobreak |\leavevmode\nobreak i,j∈Sc}.

Then , , if and , and , if and .

The function = Expand is the inverse function of = Contract. If , , then , , if and , and , if and .

### 4.3 An explanation of the update rules for arc weights and pre-factors

In this Section, we explain the update rules for arc weights and pre-factors given by Eq. (11) (also see [15, 16, 18]). A cycle

 c={i1→i2→…→iq→i1}

appears in Algorithm 1 if and only if the min-arcs from the vertices , are , and the min-arc from is . Let us restrict the dynamics of the Markov chain to the cycle and for each state neglect the transition rates of smaller exponential orders than which is for sufficiently small . Then we obtain the following generator matrix approximately describing the dynamics within the cycle :

 Lc=⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣−Lcμ(i1)Lcμ(i1)−Lcμ(i2)Lcμ(i2)⋱⋱−Lcμ(iq−1)Lcμ(iq−1)Lcμ(iq)−Lcμ(iq)⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦,where\leavevmode\nobreak \leavevmode\nobreak Lcμ(il)=κμ(il)e−Uμ(il)/ε. (14)

Solving , , we find the approximation to the invariant distribution in :

 πc(il)≈1κμ(il)eUμ(il)/ε∑qj=11κμ(ij)eUμ(ij)/ε,l=1,…,q. (15)

Without the loss of generality we assume that the last added arc to the cycle is . Then for . Multiplying the enumerator and the denominator in Eq. (15) by and neglecting small summands in the denominator we obtain

 πc≈[κμ(iq)κμ(i1)e−(Uμ(iq)−Uμ(i1))/ε,…,κμ(iq)κμ(iq−1)e−(Uμ(iq)−Uμ(iq−1))/ε,1]. (16)

The quasi-invariant distribution (i.e., the approximation to the invariant distribution for dynamics restricted to the subset of states ) allows us to obtain sharp estimates for the exit rates from the cycle via arcs with tails in . For any arc where and , the exit rate from through the arc is approximated by

 πc(il)Lilj=κμ(iq)κiljκμ(il)e−(Uilj+Uμ(iq)−Uμ(il))/ε. (17)

If one treats the cycle as a macro-state, i.e., contracts it into a single vertex, then the effective exit rate from it is given by Eq. (17). Recalling that is the last added arc, one readily reads off the update rule for the arc weights and the pre-factors given by Eq. (11).

### 4.4 Extraction of optimal W-graphs

Let us imagine that we have abolished the Contract and Expand operators in Algorithm 1 and manipulate the arc sets instead as it is done in the single-sweep algorithm [12], i.e., as it is suggested in Remark 4.5 in Section 4.1. I.e., instead of contracting a cycle into a super-vertex, we discard all arcs with both tails and heads in that are not in the current graph , modify the weights and the pre-factors of all outgoing arcs with tails in and heads not in according to Eq. (11) and denote the set of such arcs by , and find the arc of minimal weight in and add it to the bucket ; this arc becomes the min-arc for all vertices in . The weight of any arc modified according to the update rule Eq. (11) is equal to the increment of the total weight of the graph obtained from the current optimal W-graph by replacing the arc with and adding the arc that led to the current cycle. This fact and the weak nested property of the optimal W-graphs (Theorem 2.5) guarantee that the whole hierarchy of the optimal W-graphs , …, can be extracted from the T-graphs , …, built by Algorithm 1.

Recall that is the step number at which the eigenvalue counter switches to : , where is the recursion depth at step in Algorithm 1. For convenience, we denote the unique absorbing state of the T-graph by , i.e., . The optimal W-graphs can be extracted from the corresponding T-graphs for . We emphasize that is fully expanded graph, i.e., its set of vertices is . The set of sinks of is


text:
# semi-direct factor and quotient group

###### Theorem.

If the group $G$ is a semi-direct product of its subgroups $H$ and $Q$, then the semi-direct $Q$ is isomorphic to the quotient group $G/H$.

Proof. Every element $g$ of $G$ has the unique representation $g=hq$ with $h\in H$ and $q\in Q$. We therefore can define the mapping

 $g\mapsto q$

from $G$ to $Q$. The mapping is surjective since any element $y$ of $Q$ is the image of $ey$. The mapping is also a homomorphism since if $g_{1}=h_{1}q_{1}$ and $g_{2}=h_{2}q_{2}$, then we obtain

 $f(g_{1}g_{2})=f(h_{1}q_{1}h_{2}q_{2})=f(h_{1}h_{2}q_{1}q_{2})=q_{1}q_{2}=f(g_{% 1})f(g_{2}).$

Then we see that $\ker{f}=H$ because all elements $h=he$ of $H$ are mapped to the identity element $e$ of $Q$. Consequently we get, according to the first isomorphism theorem, the result

 $G/H\cong Q.$

Example. The multiplicative group $\mathbb{R}^{\times}$ of reals is the semi-direct product of the subgroups $\{1,\,-1\}=\{\pm 1\}$ and $\mathbb{R}_{+}$. The quotient group $\mathbb{R}^{\times}/\{\pm 1\}$ consists of all cosets

 $x\{\pm 1\}=\{x,\,-x\}$

where $x\neq 0$, and is obviously isomorphic with $\mathbb{R}_{+}=\{x\mid x>0\}$.

Title semi-direct factor and quotient group SemidirectFactorAndQuotientGroup 2013-03-22 15:10:22 2013-03-22 15:10:22 yark (2760) yark (2760) 8 yark (2760) Theorem msc 20E22

format: plain


text:
Problem #1203

 1203 In $\triangle ABC$, we have $AC = BC = 7$ and $AB = 2$. Suppose that $D$ is a point on line $AB$ such that $B$ lies between $A$ and $D$ and $CD = 8$. What is $BD$? $\mathrm{(A)} 3 \qquad \mathrm{(B)} 2\sqrt{3} \qquad \mathrm{(C)} 4 \qquad \mathrm{(D)} 5 \qquad \mathrm{(E)} 4\sqrt{2}$ This problem is copyrighted by the American Mathematics Competitions.
Note: you aren't logged in. If you log in, we'll keep a record of which problems you've solved.


text:
Publication
Title
Observation of top quark pairs produced in association with a vector boson in pp collisions at $\sqrt{s}$=8 TeV
Author
Abstract
 Measurements of the cross sections for top quark pairs produced in association with a W or Z boson are presented, using 8 TeV pp collision data corresponding to an integrated luminosity of 19.5 fb(-1), collected by the CMS experiment at the LHC. Final states are selected in which the associated W boson decays to a charged lepton and a neutrino or the Z boson decays to two charged leptons. Signal events are identified by matching reconstructed objects in the detector to specific final state particles from t (t) over barW or t (t) over barZ decays. The t (t) over barW cross section is measured to be 382(-102)(+117) fb with a significance of 4.8 standard deviations from the background-only hypothesis. The t (t) over barZ cross section is measured to be 242(-55)(+65) fb with a significance of 6.4 standard deviations from the background-only hypothesis. These measurements are used to set bounds on five anomalous dimension-six operators that would affect the t (t) over barW and t (t) over barZ cross sections.
Language
English
Source (journal)
Journal of high energy physics. - Bristol
Publication
Bristol : 2016
ISSN
1126-6708
1029-8479 [online]
Volume/pages
1(2016), 55 p.
Article Reference
096
ISI
000370438700001
Medium
E-only publicatie
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
 Faculty/Department Research group Publication type Subject Affiliation Publications with a UAntwerp address


text:
# Making a better programming language

Today, I write about making my dream programming language. Again.

Writer’s Note: I recommend reading my first post Making a programming language before reading this one! This post contains complex jargon which is explained in that previous one.

Towards the end of summer last year, I created a programming language which I called “my dream programming language”. It was a purely functional programming language with dynamic types that included the core features of set data structures, pattern matching and guards. At the time, I had some basic knowledge of JavaCC and created an interpreter for the language using a SECD machine. However, it had a number of pitfalls:

• Brackets are ignored, so the order of operations are not handled
• There are no if statements, which makes the language difficult to use for new users
• Despite being called a ‘pure’ programming language, it was not actually pure

So, this time I decided to create a better language, its successor so to speak, which resolves these issues and takes advantage of the new knowledge that I’ve gained by taking my university’s compiler design module.

## A new language design

So, what does my new dream language consist of? What features does it definitely require for me to call it my dream language? After being exposed to the functional programming language Elm and after writing a purely functional programming language called the Untitled Lambda Calculus for my third year project (a smart package manager), I now have a much better idea of what my dream language consists of:

• Pure. A pure programming language is one where its functions have no side effects (no mutation, or I/O) and its return value is the same for the same input arguments. My previous language was initially pure, but the introduction of trying to handle I/O caused it to be impure. Pure languages also have the perk of being easy to read and reason about, which can help developers write functions (and prove they work) easily.

• Java interoperability. In the current world of programming languages, having a programming language that doesn’t have some form of interoperability with another language is pretty much useless. For example, take Kotlin. Kotlin can be used on the JVM, allowing it to call Java classes (and vice versa), but it can also compile down to JavaScript or native code via LLVM. Since I primarily program in Java and often want to code in a functional manner, having a method to call functional code is ideal without having to use additional libraries or frameworks.

• Lazy evaluation. I love lazy evaluation. The idea of being able to only call what you actually need when you need it seems very smart and since my original programming language failed to have lazy evaluation, implementing lazy evaluation will instantly make this language better than my previous one.

• A compiled language. My first programming language was interpreted using an SECD machine, however I found that I didn’t like that very much. My third year project’s Untitled Lambda Calculus was interpreted by reducing a given expression until it could not be reduced further. The downside of both of these methods is that they are currently interpreted. In order to have some form of Java-based interoperability, I would either have to write an interpreter for the language, or have it compile down to Java bytecode, in which Java can directly call functions from the language. Since Java bytecode is something that I’ve wanted to learn for some time, I want to try my hand at generating bytecode.

• Less bloat. The biggest problem that I have with other programming languages that run on the JVM, such as Scala, Kotlin or Groovy is that they’re incredibly bloaty. If you have to ship an additional entire standard library (such as the Kotlin runtime) that consists of a tonnes of everything that’s pretty much already existent in Java (I’m looking at you kotlin.collections), then I don’t believe it’s a proper solution. It’s on the same level of converting a web application to a desktop application by shipping it with chromium (Who thought this was a good idea?!). My dream language must have as minimal bloat as possible.

• Static types. My first language had dynamic types, but I found that with static types, it’s easier to create much more complex data structures. In addition, my third year project pretty much depends on static types and I thought that having a (decent) language that could interact with my third year project would be cool sub-project to undertake.

So that’s pretty much what I want in this programming language, so let’s make it!

## Making the language

After completing my third year project, I decide to take the advice of my supervisor so I don’t make the same mistakes that I did when I created my first programming language and start small, then expand from there. I start with my trusty JavaCC project template to get a simple project structure with JavaCC. From there, I begin to plan out what the syntax would look like.

### A new syntax

Since this programming language is pure, I decide to make it such that you can only call functions from some other programming language that runs on the JVM. This basically means that the language can’t “start” by itself - it has no main method. In other words, it’s a language used for creating libraries.

I decide to go with the Elm-like style for “exposing” functions, where functions and types to expose are declared at the top of the file. Since I want my language to be Java-like, I decide to use the keyword export (since it’s just the opposite of import).

For the syntax of function declarations, I want to keep the essence of Java’s syntax, but modify it to be some sort of functional/Java-like hybrid. I decide to use the < and > symbols which are used for generics in Java to refer to types in general, where nested types just consist of nested < and > symbols. In general, I don’t want to use : or :: to state types (used by Elm and Haskell respectively) since that’s a very ‘non-Java-like’ syntax.

Library MyLibrary {
export identity;
} {
identity input<Int> -> <Int> = input;
}

Now, I know it’s not the most beautiful syntax at this point, but hey, it’s subject to change if and when I feel necessary. While I am at it, I decide to to draft up syntax for guards, pattern matching, type declarations and enum definitions. With the syntax somewhat thought up, I decide to work on the parser. I’m much more confident with changing the grammar of the language as I was last summer, so I’m okay with having a non-concrete syntax for now.

### Creating the language from the syntax

Initially, I try writing a parser to parse all of the constructs of the language - numbers, strings, lists, sets, function calls, type declarations, guards, pattern matching… you name it. After taking a break from development, I decide to start from scratch and implement each feature one at a time through to the end. By that I mean that each feature will be added in the following cycle:

• Write the JavaCC code to parse it
• Create the AST node to store the code structure
• Write the code generation function for the code structure
• Test it by calling it in a Java program

Since I’ve parsed many languages in the past, creating the parser for the basic constructs is simple. Similarly, creating the AST nodes is trivial. The difficulty lies in writing code to generate bytecode - I’ve never done it before!

## Introducing ASM

For well over 3 years, I’ve known of ASM, a Java bytecode engineering library. It basically lets you create Java bytecode within Java. I personally believe that choosing to use ASM rather than convert the code to Java, then compile the generated Java code is much more interesting and could lead to better code optimization that would be lost if I tried to emit Java code.

To start off with, I begin with the ASM user guide, which is a very detailed and surprising well written PDF document that outlines how to use ASM to its full potential. Honestly, I’ve never read documentation so good in a very long time! It includes well explained diagrams and examples to help you understand what you need to know to fully use it. By combining this resource with the Wikipedia article on the Java bytecode instruction set, I feel ready to write bytecode! (In hindsight, I should have used the much more detailed official JVM instruction set page)

I also install Eclipse’s bytecode outlining plugin which helps analyse bytecode and also includes a feature to display bytecode, as well as the JBC Java bytecode plugin which lets you edit bytecode for compiled classes in Eclipse. Whether it will be useful, who knows, but it’s good to have it there in case I need it.

I discover ASM’s main workflow of having these “Visitor” methods which basically let you write information about classes. You start with a ClassVisitor which lets you define a class file, and then “visit” individual parts to add extra information to it. For example, to add a new method, you call classVisitor.visitMethod and begin writing code into the MethodVisitor. It sounds complicated, but it’s actually pretty intuitive - you’re basically writing lines of bytecode one at a time.

While writing this ASM, I encounter two major obstacles: line numbers and frames.

### Line numbers

In Java, when an error occurs (due to a thrown exception for example), normally a stack trace is printed.

Exception in thread "main" java.lang.NumberFormatException: For input string: "3.1415"
at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
at java.lang.Integer.parseInt(Integer.java:580)
at ExampleCli.parseNumericArgument(ExampleCli.java:47)
at ExampleCli.parseCliOptions(ExampleCli.java:27)
at ExampleCli.main(ExampleCli.java:11)

Stack traces show the name of the class, the method name and most importantly the line number where the code went wrong. Having this line number is crucial for debugging where your error is in your code. Whether my language will have errors or not is still something I have to find out myself (with it being pure and all that, it shouldn’t have errors, but maybe I want undefined like in Haskell?)

In order to add the line number to a statement in a method, you basically need to use the following block in ASM, where LINE_NUMBER represents the line number:

Label lineNumber = new Label();
methodVisitor.visitLabel(lineNumber);
methodVisitor.visitLineNumber(LINE_NUMBER, lineNumber);

In order to do this, I need to actually record the line numbers in the first place! Luckily, JavaCC records the beginning and end line numbers for tokens (beginning is the line of the first character of a token and end is the line of the last character of a token). By adding line numbers to my AST nodes, I am able to record line numbers so in the event that everything goes pear-shaped, people can find out where their code went wrong.

### Frames

Honestly, this section is so confusing I pretty much don’t understand it. If you don’t want to get confused by my confusion, you can just read the last paragraph of this section. If you want to have a bad time, read section 3.1.5. Frames from the ASM guide.

In Java, you have threads. Each thread consists of an execution stack which is where instructions are executed. The things that actually go onto the stack are called frames. Every time a method is called in Java, a new frame is pushed onto the stack and when the method returns, that frame is popped off of the stack. Without going into too much detail, there’s also this set of stack map frames which basically says “this is what the type of the frame is after instruction X”. So for example (this is a big of a simplification, but bear with), if you call a method that returns an integer, the type of the frame would be an integer.

As of Java 6, you basically need to include this set of stack map frames which should indicate the state of frames before jump operations, and instructions that follow jump instructions. Trying to figure out what the type of frames are between jumps seems to be an incredibly complicated task - especially since I’m implementing a functional language which is wildly different to Java’s imperative structure.

Luckily, instead of trying to figure out all of the complicated structure of what state is what after what instruction, ASM includes this flag COMPUTE_FRAMES that simply computes the structure stuff for you.

## Conclusions

Learning the ins and outs of ASM definitely took some time (a few days), but it was no insurmountable task. The well written guide definitely helps in making sure you know exactly what each method in the ASM library does and once you understand how the JVM works under the hood (as a stack machine), it is surprisingly simple to use. Of course, since you’re dealing with a much lower level of programming, trying to understand jumps (such as if statements) requires a bit of thinking, but this is what I love the most about programming.

I am still in the process of writing this new programming language. The syntax is still very on the fence, there are some things about it that I’m unhappy with. Overall, I’ve gained invaluable knowledge about how to use ASM and the Java bytecode instruction set. Even though the project is in its infancy, I believe it will be able to grow into a much more powerful programming language that I hope to use in future Java projects!

Written on March 18, 2020


text:
It is currently 14 Dec 2017, 07:21

# Decision(s) Day!:

CHAT Rooms | Wharton R1 | Stanford R1 | Tuck R1 | Ross R1 | Haas R1

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# In the xy-plane, point (r, s) lies on a circle with center

Author Message
Manager
Joined: 30 May 2010
Posts: 189

Kudos [?]: 261 [0], given: 32

In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

24 Aug 2010, 21:45
00:00

Difficulty:

25% (medium)

Question Stats:

69% (00:35) correct 31% (01:09) wrong based on 136 sessions

### HideShow timer Statistics

In the xy-plane, point (r,s) lies on a circle with center at the origin. What is the value of $$r^2+s^2$$?

(1) The circle has radius 2.

(2) The point $$(sqrt{2}, -sqrt{2})$$ lies on the circle.

OPEN DISCUSSION OF THIS QUESTION IS HERE: https://gmatclub.com/forum/in-the-xy-pl ... 65616.html
[Reveal] Spoiler: OA

Kudos [?]: 261 [0], given: 32

CEO
Status: Nothing comes easy: neither do I want.
Joined: 12 Oct 2009
Posts: 2754

Kudos [?]: 1927 [1], given: 235

Location: Malaysia
Concentration: Technology, Entrepreneurship
Schools: ISB '15 (M)
GMAT 1: 670 Q49 V31
GMAT 2: 710 Q50 V35
Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

24 Aug 2010, 21:55
1
KUDOS
Equation of the circle is $$x^2+ y^2 = a^2$$ where a = radius

since r,s lies on the circle the equation becomes r^2+s^2 = a^2

statement 1: radius = $$a= 2 => r^2+s^2 = 2^2 = 4$$ , thus sufficient.
statement 2: we have given one point on the circle and we have the center at the origin.
Thus we can find out the distance between these 2 points which will be 2. This distance is basically the radius. Since we have the radius, the statement is sufficient.

Hence D
_________________

Fight for your dreams :For all those who fear from Verbal- lets give it a fight

Money Saved is the Money Earned

Jo Bole So Nihaal , Sat Shri Akaal

GMAT Club Premium Membership - big benefits and savings

Gmat test review :
http://gmatclub.com/forum/670-to-710-a-long-journey-without-destination-still-happy-141642.html

Kudos [?]: 1927 [1], given: 235

Manager
Joined: 30 May 2010
Posts: 189

Kudos [?]: 261 [0], given: 32

Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

24 Aug 2010, 22:45
I had forgotten the equation for the circle. Thanks!

Kudos [?]: 261 [0], given: 32

Senior Manager
Joined: 25 Feb 2010
Posts: 447

Kudos [?]: 116 [0], given: 10

Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

28 Aug 2010, 09:07
can some one please explain how B is correct ?
_________________

GGG (Gym / GMAT / Girl) -- Be Serious

Its your duty to post OA afterwards; some one must be waiting for that...

Kudos [?]: 116 [0], given: 10

Manager
Joined: 30 May 2010
Posts: 189

Kudos [?]: 261 [0], given: 32

Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

28 Aug 2010, 10:06
Draw a right triangle from the origin to that point. Now solve for the hypotenuse, and you get 2. This is the radius of the circle.

Kudos [?]: 261 [0], given: 32

Manager
Joined: 06 Apr 2010
Posts: 141

Kudos [?]: 969 [0], given: 15

Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

09 Dec 2010, 09:31
2
This post was
BOOKMARKED
In the xy-plane, point (r, s) lies on a circle with center at the origin. What is the value of r^2 + s^2?

(1) The circle has radius 2.
(2) The point ($$\sqrt{2}$$, $$-\sqrt{2}$$) lies on the circle.

Kudos [?]: 969 [0], given: 15

Math Expert
Joined: 02 Sep 2009
Posts: 42605

Kudos [?]: 135629 [1], given: 12705

Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

09 Dec 2010, 09:45
1
KUDOS
Expert's post
2
This post was
BOOKMARKED
udaymathapati wrote:
In the xy-plane, point (r, s) lies on a circle with center at the origin. What is the value of
$$r^2 + s^2$$?
(1) The circle has radius 2.
(2) The point (\sqrt{$$2$$}, -\sqrt{$$2$$}) lies on the circle.

THEORY:
In an x-y Cartesian coordinate system, the circle with center (a, b) and radius r is the set of all points (x, y) such that:
$$(x-a)^2+(y-b)^2=r^2$$

This equation of the circle follows from the Pythagorean theorem applied to any point on the circle: as shown in the diagram above, the radius is the hypotenuse of a right-angled triangle whose other sides are of length x-a and y-b.

If the circle is centered at the origin (0, 0), then the equation simplifies to:
$$x^2+y^2=r^2$$

BACK TO THE ORIGINAL QUESTION:
In the xy-plane, point (r, s) lies on a circle with center at the origin. What is the value of $$r^2 + s^2$$?

Now, as $$x^2+y^2=r^2$$ then the question asks about the value of radius^2.

(2) The point $$(\sqrt{2}, \ -\sqrt{2})$$ lies on the circle --> substitute x and y coordinates of a point in $$x^2+y^2=r^2$$ --> $$2+2=4=r^2$$. Sufficient.

_________________

Kudos [?]: 135629 [1], given: 12705

Non-Human User
Joined: 09 Sep 2013
Posts: 14840

Kudos [?]: 287 [0], given: 0

Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

11 Aug 2015, 10:22
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________

Kudos [?]: 287 [0], given: 0

Math Expert
Joined: 02 Sep 2009
Posts: 42605

Kudos [?]: 135629 [0], given: 12705

Re: In the xy-plane, point (r, s) lies on a circle with center [#permalink]

### Show Tags

14 Aug 2017, 04:43
jpr200012 wrote:
In the xy-plane, point (r,s) lies on a circle with center at the origin. What is the value of $$r^2+s^2$$?

(1) The circle has radius 2.

(2) The point $$(sqrt{2}, -sqrt{2})$$ lies on the circle.

OPEN DISCUSSION OF THIS QUESTION IS HERE: https://gmatclub.com/forum/in-the-xy-pl ... 65616.html
_________________

Kudos [?]: 135629 [0], given: 12705

Re: In the xy-plane, point (r, s) lies on a circle with center   [#permalink] 14 Aug 2017, 04:43
Display posts from previous: Sort by


text:
# Is it really not possible to obtain an analytical expression for when (if at all) a point $Q$ on a rotating stick will hit a point $P$?

Say we have a stick on length $L$ that travels toward a point $P$ with linear velocity $v$ in the direction of $P$ and rotational velocity $\omega$. The point and the stick are initially $l$ apart. Will a point $Q$ on the stick, a distance $r$ from its center, hit $P$?

Let the starting position of the stick be such that it points along the $x$-axis and that the center of the stick is at the origin. Looking from the point of view of the stick, the point $P$ will have a velocity $-v$ towards the $x$-axis (and the stick). The initial position of $P$ is $(d,l)$.

The equations of motion are thus \begin{align} \overline{P}&=\begin{pmatrix} d \\ l-vt \end{pmatrix} \\ \overline{Q}&=r\begin{pmatrix}\cos(\omega t) \\ \sin(\omega t) \end{pmatrix} \end{align}

and the question becomes "when is there a $t$ such that the two are equal?"

Introducing $\gamma\equiv\arccos\frac{d}{r}$ (which clearly shows the constraint $r\geq \vert d\vert$), we have

$$\frac{l-\gamma \frac{v}{\omega}}{r}=\sin \gamma$$

However, this looks transcendental.

Is there really no way of analytically figuring out whether or not $Q$ hits $P$? Can we determine whether or not the stick hits at all (for any $Q$)?

Edit: Just an idea: Perhaps one can use the Intermediate value theorem to show that there must exist a solution given some initial conditions?

Edit: Perhaps the question should be "For which $r$s (or some other, single parameter) is $\frac{l-\gamma \frac{v}{\omega}}{r}=\sin \gamma$ true (given $d,\ell,v,\omega$)? Can we say anything sensible about this?

• There is certainly a complicated region of space that $P$ can be in where the stick entirely misses it: i.stack.imgur.com/B5owf.png – Rahul Sep 11 '16 at 21:53
• @Rahul That is a beautiful illustration! Where did you find it/how did you make it? And does the space that the stick traces out have a name, i.e. is it some kind of well-known function? – Bobson Dugnutt Sep 11 '16 at 22:12
• It's just a plot of $Q-P$ for fixed $d,l,v,\omega$ and variable $t,r$. I made it using the ParametricPlot command in Mathematica. – Rahul Sep 11 '16 at 22:18

$$\frac{\ell - \gamma \frac{v}{\omega}}{r} = \sin\gamma. \tag{*}$$ Perhaps the problem is: Given $\ell,r,v,\omega$, solve for $\gamma$.
LINK gives Kepler's equation as $$M=E-e\sin E \tag{K}$$ where we should solve for $E$, given $M$ and $e$. We may substitute $$E=\gamma \\ e=\frac{-r\omega}{v} \\ M=\frac{\ell \omega}{v}$$ to convert (K) into (*).
• Thank you for your answer. Note that $\gamma(r)$. Also, please have a look at my latest edit - I'm sorry my question was not clear. – Bobson Dugnutt Sep 11 '16 at 22:12


text:
BrandeVenturella
27

# simplify each square root: 1. square root of -25 2. square root of 1.44 3. square root of + or -16/49 4. square root of 361 5. square root of 49 6. square root of + or -0.64 7. square root of -6.25 8. square root of 169/196 9. square root of 25/324

$1.\ \sqrt{-25}-isn't\ real\ number\to\sqrt{-25}=\sqrt{25(-1)}=\sqrt{25}\cdot\sqrt{-1}=5i\\\\2.\ \sqrt{1.44}=\sqrt{1.2^2}=1.2\\\\3.\ \sqrt{\frac{16}{49}}=\frac{\sqrt{16}}{\sqrt{49}}=\frac{\sqrt{4^2}}{\sqrt{7^2}}=\frac{4}{7}\\\\\sqrt{-\frac{16}{49}}=\frac{4}{7}i\\\\4.\ \sqrt{361}=\sqrt{19^2}=19\\\\5.\ \sqrt{49}=\sqrt{7^2}=7\\\\6.\ \sqrt{0.64}=\sqrt{0.8^2}=0.8\\\\\sqrt{-0.64}=0.8i$ $7.\ \sqrt{-6.25}=\sqrt{6.25(-1)}=\sqrt{6.25}\cdot\sqrt{-1}=\sqrt{2.5^2}\cdot\sqty{-1}=2.5i\\\\8.\ \sqrt\frac{169}{196}=\frac{\sqrt{169}}{\sqrt{196}}=\frac{\sqrt{13^2}}{\sqrt{14^2}}=\frac{13}{14}\\\\9.\ \sqrt\frac{25}{324}=\frac{\sqrt{25}}{\sqrt{324}}=\frac{\sqrt{5^2}}{\sqrt{18^2}}=\frac{5}{18}\\====================================$ $i=\sqrt{-1}\ is\ the\ imaginary\ unit\\---------------------\\If\ a\geq0\ then\ \sqrt{a^2}=a$


text:
summaryrefslogtreecommitdiffstats log msg author committer range
path: root/src/countdowndialog.h
blob: ed8778bf985f13bb3dc9e0e3e506474029f0a58c (plain)
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84  /*************************************************************************** * Copyright (C) 2007 by Danny Kukawka * * , * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of version 2 of the GNU General Public License * * as published by the Free Software Foundation. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ /*! * \file countdowndialog.h * \brief Headerfile for countdowndialog.cpp and the class \ref countDownDialog. */ /*! * \class countDownDialog * \brief class for countdown dialog related funtionality * \author Danny Kukawka, , * \date 2007 */ #ifndef COUNTDOWNDIALOG_H #define COUNTDOWNDIALOG_H #include "countdown_Dialog.h" class countDownDialog: public countdown_Dialog { Q_OBJECT public: //! default constructor countDownDialog(int timeout, TQWidget *parent = 0, const char *name = 0); //! default destructor ~countDownDialog(); //! set needed icons void setPixmap( TQString ); //! to set the message text for the user void setMessageText(TQString text); //! to show up the dialog bool showDialog(); private: //! Timer for the timeout /*! * This timer is used to change the progressbar and to close the dialog if * the \ref timeOut is over. */ TQTimer *PROGRESS; //! time the dialog should be displayed int timeOut; //! remaining time to show the dialog int remaining; //! to store the info if the countdown was chanceled bool chancel; private slots: //! to update the progressbar void updateProgress(); //! to catch the event if the 'Chancel' button get pressed void pB_cancel_pressed(); signals: //! emited if the dialog get closed void dialogClosed( bool result); }; #endif


text:
# A while walking towards a tower at a constant speed,  observed that the angle of elevation of the top of the  tower changed to 600 from 450. How much more than  will he take to reach of the tower?  (a) 5 min  (c) $5\left(\sqrt{3}-1\right)$min  (b) 5$\sqrt{3}$ min  (d) None of these

Dear Student,

Regards

• 0
What are you looking for?


text:
# Is HAMPATH in NL/L?

I know HAMPATH is NP complete problem. But is there a way to tell if it is either a NL or L problem? I tried searching a lot of places online but it feels like I am going nowhere. Thanks in advance for any leads

• Hint: NL$\subseteq$P. – Yuval Filmus Nov 30 '15 at 6:05

We don't know whether HAMPATH belongs to L or to NL. However, since NL$\subseteq$P, if HAMPATH belonged to L or to NL then it would follow that P=NP, which is conjectured not to be the case. So probably HAMPATH doesn't belong to L or to NL.