Showing How the Omega Equation is Obtained for the 1-D and 2-D CVM – Part 2:

 

The cluster variation method (CVM) lets us characterize a system in terms of local patterns, and not just the numbers of units in on (A) and off (B) states. It works with a more complex entropy term. The natural question is: How do obtain this more complex entropy?

This post continues a discussion begun in the last post, on how we actually get the Omega equation (defining total number of microstates available). This is used to obtain our entropy equation, and feeds directly into obtaining the free energy for the CVM grid. The previous post, Expressing Total Microstates (Omega) for the 1-D Cluster Variation Method – Part 1, dealt exclusively with the 1-D case, but didn’t complete the derivation. In this post, we’ll move further with discussing both the 1-D and 2-D cases for the 2-D CVM.

 

 

Cutting to the Chase: The Two Omega Equations (1-D and 2-D CVM)

 

We envision the 1-D CVM system as a zigzag chain, as shown in Figure 1(b).

The Omega equation for this zigzag chain, expressing the total number of microstates available for a double row, is given as

and the number of ways of constructing a single row is give as

where refers to the total number of units in the system (for the zigzag chain), as is the total number of units in a row, and the rows are of equal length.

For the 2-D CVM, we envision a grid as shown in the following Figure 2.

In constructing the 2-D CVM grid (in the diagonal view, as shown in Figure 2), Kikuchi and Brush state:

The number of ways of adding the (k+1)th row when the part of the system up to the (k)th row in Fig. 2 [originally Figure 1 in the Kikuchi and Brush paper] has been completed is the ratio of Omega{double}/Omega{single}. Thus the number of ways of adding N1 rows and completing the entire system is [Omega{double}/Omega{single}]^(N1). (Kikuchi and Brush, 1967)

Thus, Kikuchi and Brush give the Omega (total number of microstates) for the 2-D grid as

where and are defined above for the initial zigzag chain and the subsequent layered single rows.

We notice now that the expression for involves , whereas the expression for involves only . As Kikuchi and Brush note, for cases where is large, we can use Stirling’s approximation and write

which is identical with Eqn. I.11 of Kikuchi and Brush (1967).

 

 

A Small Revision in Notation

 

I used the phrase “in-row-pair” in giving the equation for at the beginning of this post. This was to make clear the correlation with how the single row appears in Fig. 1(a).

When we look at Figure 2, we see that the distance between two units in the same row is longer than the distance between two units that are diagonally adjacent in two different rows. E.g., the distance C-E is longer than the distance C-D. The C-D pair in Figure 2 is an example of a diagonal between rows, and the C-E pair (which I will henceforth write as C- -E) is an in-row pair.

In the original Kikuchi (1951) paper, he built up the 2-D CVM grid from square units and from right angles comprising the corners of these units. In that paper, the configuration variable y(i) referred to pairs along the edges of the square or the right angle.

The Kikuchi and Brush (1967) paper introduced the notion of building up the 2-D CVM grid which could be interpreted as the original square grid turned on its diagonal, leading to the rows being staggered with regard to each other. Thus, the square defined by C-D-E-F in Figure 2 would have been a fundamental square building block in the original Kikuchi work.

The fundamental unit in the Kikuch-Brush approach (at least, the line that we’re following here) is based on the angle. An example would be the C-D-E angle in Figure 2. Thus, the C-D pair in Figure 2 corresponds to the side of the original square. It’s the shortest distance between two points. The C- -E pair in Figure 2 is the diagonal across a square. It was not used in the original Kikuchi equations, but is used in the later Kikuchi-Brush equations.

The following notational bullet list is for those of you trying to read both the Kikuchi and the Kikuch-Brush papers, and are jumping back and forth between notations:

• Point means the same in both papers, and is denoted by the configuration variable x(i).
• Pair means the shortest distance between the two points, and is denoted by the configuration variable y(i) in both papers.
• Diagonal pair means the distance between two diagonally-opposite corners in a square, and is denoted by the configuration variable w(i) in the Kikuchi-Brush paper, and is not used in the original Kikuchi paper. Further, because when we look at the 2-D grid in the Kikuchi-Brush paper, we see the original grid turned to the diagonal (with the sides trimmed appropriately so that it has a new square-like shape), we see this formerly “diagonal” pair now be on the same row. So, in the Kikuchi-Brush paper, they call this a “diagonal pair.” However, it looks as though it’s a straight-line (or in-line) pair, and not a diagonal. This can be confusing if we’re reading the Kikuchi-Brush paper without first reading the original Kikuchi paper, because the in the Kikuchi-Brush paper, the y(i) configurations look as though they’re on the diagonal.
• The angles are denoted z(i) throughout.

 

 

Getting Back to Omega for the 2-D CVM Grid

 

Now, we’re going to combine our equations for and , and incorporate the fact that we’re building the 2-D CVM grid as a series of layering a single row on top of an underlying double (zigzag) row. We’ll always think of what we’re adding as a single row, and we’ll always think of adding it onto a single zigzag chain (even if that zigzag chain is at the edge of a larger grid). We get the whole grid by repeating this process N1 times, for a grid where the total number of nodes is N = N1*N2.

(And yes, really we’re repeating the process N1 – 2 times, because we’re adding N1 – 2 single rows to a pre-existing initial zigzag chain for a total of N1 rows, but we’re approximating here as we expect that both N1 and N2 are large.)

We’re going to combine exponents. We write

or

or, since N = N1*N2,

or

or

We haven’t done everything that we’d like to, yet. We haven’t yet, for example, identified how we rationalize the expression for adding a single node to a zigzag chain. This will be deferred to a later post.

At this stage, though, we can see that the Omega for the 2-D (staggered-rows) grid involves a squared dependence on the nearest-neighbor pairs (the y(i)) and also the next-nearest neighbor pairs (the w(i)) in the numerator. (The y(i) are squared here, but will simply be multiplied by two when we take the logarithm in going to the entropy formulation.) Similarly, we’ll have the (squared) triplets as well as the points in the denominator.

One of our next most important tasks will be to characterize the shape of the entropy term, which we’ll obtain as the log of the Omega.

 

 

Live free or die, my friend –

AJ Maren

Live free or die: Death is not the worst of evils.
Attr. to Gen. John Stark, American Revolutionary War

 

 

Key References

 

Cluster Variation Method – Essential Papers

• Kikuchi, R. (1951). A theory of cooperative phenomena. Phys. Rev. 81, 988-1003, pdf, accessed 2018/09/17.
• Kikuchi, R., & Brush, S.G. (1967), “Improvement of the Cluster‐Variation Method,” J. Chem. Phys. 47, 195; online as: online – for purchase through American Inst. Physics. Costs $30.00 for non-members.
• Maren, A.J. (2016). The Cluster Variation Method: A Primer for Neuroscientists. Brain Sci. 6(4), 44, https://doi.org/10.3390/brainsci6040044; online access, pdf; accessed 2018/09/19.
• Pelizzola, A. (2005), “Cluster variation method in statistical physics and probabilistic graphical models,” J. Physics A: Mathematical & General, 38 (33) R308; online as: Pellizola CVM PDF; available for purchase through IOP Science, see also Pellizola-abstract in Cluster Variation Methods page.
• Yedidia, J.S.; Freeman, W.T.; Weiss, Y., “Understanding Belief Propagation and Its Generalizations”, Exploring Artificial Intelligence in the New Millennium, ISBN 1558608117, Chap. 8, pp. 239-236, January 2003 (Science & Technology Books). Also available online as Mitsubishi Electronic Research Laboratories Technical Report MERL TR-2001-22, online as: http://www.merl.com/reports/docs/TR2001-22.pdf

 

The 1D CVM – Code, Documentation, and V&V Documents (Including Slidedecks)

• GitHub for 1-D Object-Oriented Python Snippets
• Code: 1D-CVM_OO_basic-config-vars_V-and-V_1-1_2018-09-23.py (Python 3.6; self-contained)
• Documentation / V&V: 1D-CVM _Object-oriented-code_V-and-V_Two-base-patterns_2018-10-10-18.pptx

 

Previous Related Posts

• Expressing Total Microstates (Omega) for the 1-D Cluster Variation Method – Part 1
• Transition to Object-Oriented Python for the Cluster Variation Method
• Wrapping Our Heads around Entropy
• Figuring Out the Puzzle (in a 2-D CVM Grid).
• 2-D Cluster Variation Method: Code Verification and Validation
• The Big, Bad, Scary Free Energy Equation (and New Experimental Results)
• A “First Principles” Approach to Artificial General Intelligence
• Seven Essential Machine Learning Equations: A Cribsheet (Really, the Précis)