# Markov Random Field - Understanding the Definition

1. Aug 18, 2007

### Palindrom

First encounter with the term, I'd like some help understanding it. I know there are several approaches, but this one is important to me because I'm trying to understand an article that uses it throughout its text.

Definition: Let G=(V,E) be a finite (connected) graph and let S be a finite set. A random element X taking values in $$S^V$$ is said to be a Markov random field if for each $$W\subset V$$, the conditional distribution of X(W) given X(V\W) depends on X(V\W) only through its values on $$\partial W$$.

It goes on to write this mathematically, which I will write down here if you ask me to. My problem is with the phrase "A random element X taking values in...".
I just want to know from where to where X is. Obviously X takes values in $$S^V$$, so this is the range of X. What is its domain?

2. Aug 18, 2007

### EnumaElish

Obviously X's domain is W. E.g. X(w) = 1 if w = Head, X(w) = 0 if w = Tail. Then W = {Head, Tail).

3. Aug 18, 2007

### Palindrom

I don't have W, I have only V and S.

Did you mean V? So $$X:V\rightarrow S^V$$?

I don't see the sense of that - V doesn't represent states, it is the vertices's set of the graph.

Could you explain?

4. Aug 18, 2007

### EnumaElish

You are right, W is a subset of V; so the domain is V.

5. Aug 19, 2007

### Palindrom

I can't see why. Needless to say I believe you, but I don't understand it.

You're telling me that $$X:V\rightarrow S^V$$? I can't see why, V represents locations, not outcomes in some experiment. I mean, are we assigning to each atom a configuration of the whole system?

Besides, what is the probability measure on V?

Last edited: Aug 19, 2007
6. Aug 19, 2007

### EnumaElish

I should have differentiated between a vector X of random variables and a set X of random variables. From your definition, X is a set of random variables. Each vertex v of V represents an element of X.

In the 2-D Isling model, (V,E) looks like:
????
????
????
????
where each ? is a vertex v with two possible values (+,-) and 4 neighbors (North, East, South, West), unless it is sitting on the boundary.

Had X been defined as a vector, the domain of X would have been the sample space $\Omega$ which underlies the joint probability P(X = x).

But for a subset U of V, X(U) denotes the image of "those vertices that are included in U." (When X is a set, there is an implicit selection process w/r/t which vertices to include in the set.)

Although the v's in V have the joint domain $\Omega$, the domain of the set X is defined as V. This emphasizes the selection process. At least that's how I understand it.

A more complete notation would be to write $\bold X(V(\Omega_V))$ = SV. Although with some misuse of notation one might write $\Omega_V$ for V. This would fold the selection process into the sample space.

A free e-book can be found at: http://www.ams.org/online_bks/conm1/

Last edited: Aug 20, 2007