User szabolcs - MathOverflow

Probability that a certain Markov process has produced a given state

2011-07-06T05:43:30Z

I am looking for advice on the following practical problem. Please keep in mind that this came up in a practical application.

In the context of Markov chains, we have $N$ states, with $N$ very large. (In this application $N$ is on the order of $10^{100000}$ or so.) Every state is reachable from every other state (possibly in more than one step).

We have two transition probability matrices, $A$ and $B$.
I can probably calculate $A_{ij}$ for any two states $i$ and $j$ if needed, but what I can do easily is just propagate the states (simulate the process).

Suppose we start from some arbitrary state and let the system evolve for a very long time, obtaining a state $k$.

Given this state $k$, what is the probability that the system has been evolved using $A$? What is the probability that it was evolved using $B$?

In other words: I can easily simulate both processes on a computer. Given some state $k$, are there practical techniques to find out which of the two processes is more likely to have produced it?

Note: I think this Markov chain is reversible.

_{(I expect that the question will probably need clarifications once I manage to understand it more deeply. Please help with this.)}

Constructing Szemerédi partitions on a computer

2011-07-22T13:20:50Z

Are there practical ways to construct the Szemerédi partitions of a given graph (on a computer)? I found this algorithmic version of the lemma (also see the references within), but I was unable to find any implementations, so I am wondering if these algorithms are practical at all.

Please note that I am not a mathematician and I am very new to this topic. I am trying to find out if it this will be useful for me. I was hoping that someone familiar with the field will be able to provide some guidance and help avoid a likely blind alley.

Also, can partitioning the graph like this recursively be used to define/compute a vertex ordering (ordering = labelling by natural numbers), so that the vertices in the same partition will be adjacent in the ordering?

Showing block diagonal structure of matrix by reordering

2011-06-17T10:25:48Z

Suppose we have a block-diagonal matrix $M$, but the block diagonal structure is not immediately apparent from looking at the matrix because the rows/columns are shuffled.

I wish to find a reordering of rows and columns, $M' = P M P^{-1}$, where $P$ is a permutation matrix, that will make the block structure apparent.

When this problem is solved, I wish to do the same for the case when the matrix does not have a perfect block structure, but there are a few non-zero elements scattered here and there.

One idea is to look at the eigenvectors, and the position of non-zero elements in each eigenvector will show the elements (i.e. row/column indices) belonging to t he respective blocks. Is this correct?

Any pointers are welcome. I'm sure there must be an easy solution to this.

Defining a canonical ordering of matrix rows/columns

2011-06-16T15:47:57Z

I would like to find a way to define a canonical ordering of rows/columns in a matrix.

If two rows/columns cannot be ordered according to this canonical ordering (i.e. they're the "same"), then it must be true that exchanging them leaves the matrix invariant.

Note: In this context by reordering rows/columns of a matrix $M$ I mean transforming it using a permutation matrix $P$: $$M' = P M P^T$$

Note 2: I want to use this to have a unique representation of any graph using an adjacency matrix. The adjacency matrix depends on the vertex ordering.

EDIT I have a suspicion that an ordering relation that satisfies the above condition might not exist. Is this possible?

EDIT 2: I am rephrasing the question per several requests. Actually my problem is:

A graph can be represented by an adjacency matrix. However, this matrix depends on the ordering of vertices. I was looking for a canonical ordering of graph vertices that would make the adjacency matrix unique.

I was hoping that it is possible to do this by choosing the "correct" binary relation on the sit of graph vertices. However, I managed to prove that no such binary relation exists, which makes the problem too complicated to bother with for my practical application. So please do not spend more time on the question.

In short, it's possible to construct a graph for which any potentially suitable binary relation would consider vertices 1 and 2 equivalent, however exchanging 1 <-> 2 will not keep the adjacency matrix invariant (but e.g. exchanging both vertices 1 <-> 2 and 3 <-> 4 will).

Please close this question.

Finding number of independent variables in "statistical" dataset

2011-06-10T10:24:23Z

I would like to know if there are any standard techniques (that I don't know about) to solve the following problem.

Suppose we have $n$ variables, $\mathbf{q} = (a_1, a_2, \ldots, a_n)$, but not all of them are independent. For example, the values could be determined by only a single variable, e.g. $(x, x^2, x^3)$, or only two, e.g. $(x, y, x^2, xy, y^2)$.

Now suppose we have some measurement data for $\mathbf{q}$, which might have small errors (i.e. the relationship between the variables is valid only to some error). How can we find how many of the $n$ variables are independent of each other?

If the question is not clear, please ask. I see that there are problems, e.g. in $(x, x^2, x^3)$, $x$ can determine the value of the rest of the variables, but $x^2$ cannot (if there are negative values). Nevertheless any suggestions are most welcome. I am only interested in the number of independent variables for now, not the nature of relationship between them.

Note: I know about techniques in the case when the relationship between them is linear. I am interested in the non-linear (but continues) case now.

Note 2: Please help tag the question appropriately...

EDIT

Another way to put it:

I have some points in an $n$-dimensional Euclidean space. The points lie very close to a $k$-dimensional surface. How can I estimate the value of $k$ if I know the coordinates of the points?

Generalization of scalar product to k-dimensional subspaces (as opposed to 1-dimensional subspaces, i.e. vectors)

2011-05-30T13:02:47Z

This came up in a practical problem (physics).

In the following, we work with real numbers only, and consider every vector to be normalized to 1.

To find how "similar" two vectors are (actually, two lines passing through the origin, I don't care about the direction), one can use the scalar product. If the two lines are the same, then the scalar product of the corresponding vectors is 1 or -1. If they are "similar", it's close to 1. If they're perpendicular, it's 0.

I need a generalization of this "similarity measure" to $k$-dimensional subspaces.

For example, for $k=2$ I have the following problem: I have vectors $a_1 \perp a_2$ which define a plane in an $n$-dimensional space, and vectors $b_1 \perp b_2$. I need a measure that 1. tells me how close these planes are to each other, in terms of $a_1, a_2, b_1, b_2$. is a generalization of the simple scalar product (i.e. it's the same as the scalar product for $k=1$).

Fast algorithm for counting the number of acyclic paths on a directed graph

2011-04-06T16:03:29Z

In short, I need a fast algorithm to count how many acyclic paths are there in a simple directed graph.

By simple graph I mean one without self loops or multiple edges. A path can start from any node and must end on a node that has no outgoing edges. A path is acyclic if no edge occurs twice in it.

My graphs (empirical datasets) have only between 20-160 nodes, however, some of them have many cycles in them, therefore there will be a very large number of paths, and my naive approach is simply not fast enough for some of the graph I have.

What I'm doing currently is "descending" along all possible edges using a recursive function, while keeping track of which nodes I have already visited (and avoiding them). The fastest solution I have so far was written in C++, and uses std::bitset argument in the recursive function to keep track of which nodes were already visited (visited nodes are marked by bit 1). This program runs on the sample dataset in 1-2 minutes (depending on computer speed). With other datasets it takes more than a day to run, or apparently much longer.

The sample dataset: http://pastie.org/1763781 (each line is an edge-pair)

Solution for the sample dataset (first number is the node I'm starting from, second number is the path-count starting from that node, last number is the total path count): http://pastie.org/1763790

Please let me know if you have ideas about algorithms with a better complexity. I'm also interested in approximate solutions (estimating the number of paths with some Monte Carlo approach). Eventually I'll also want to measure the average path length.

Note: Same question previously posted on stackoverlow, hope this is not against the rules. Later realized the question has more to do with maths.

Comment by Szabolcs

2012-02-07T09:14:16Z

Actually I can calculate any single element of the transition matrix, but of course I cannot calculate all elements at the same time ($N$ is too big). But I think what you said would still apply.

Comment by Szabolcs

2011-07-25T13:55:05Z

But then apparently one needs a graph of a minimum size for a given $\epsilon$.

Comment by Szabolcs

2011-07-25T13:37:41Z

@Calvin Condon, thank you for the pointer. I am not a mathematician, and very new to this topic, but the abstract of this paper gave me the impression that this partitioning should work for any graph, and should be implementable in practice: citeseer.ist.psu.edu/viewdoc/…

Comment by Szabolcs

2011-07-06T07:16:12Z

Yes, there is about zero chance of reaching state $k$ from some random state due to the huge number of possible states. A state is actually described by a $\sim 100\times 100$ matrix where each element can have $\sim 100-1000$ different values.

Comment by Szabolcs

2011-07-06T07:09:05Z

@Snark, yes, it's similar to that. I'd also like to know how much more likely one hypothesis is than the other. Of the $k$ state, I only have one. The systems are variations on the discrete-time voter model on a 2D grid (modified so as to let it have a steady state in some sense). However, I'd really like to know if there exists some general ways to accomplish this.

Comment by Szabolcs

2011-06-18T10:41:01Z

Oops, good you pointed that out

Comment by Szabolcs

2011-06-18T09:25:46Z

In essence, this also corresponds to interpreting the matrix as a graph, then starting from a node, visiting all nodes that can be visited, thus finding the largest connected component containing the starting node. Is this correct?

Comment by Szabolcs

2011-06-17T12:48:48Z

Just imagine that you write down a block-diagonal matrix and add some extra elements. Of course by looking at this thing one can tell that it is an "almost" block-diagonal matrix. I am looking for something that captures this intuition. Coming up with a precise definition is part of the problem.

Comment by Szabolcs

2011-06-17T12:45:49Z

Indeed. But the interesting case is when is not perfectly diagonal, i.e. there are a few links between those components, but not too many.

Comment by Szabolcs

2011-06-17T07:15:07Z

@TonyK, you are right, it does not work.

Comment by Szabolcs

2011-06-16T18:30:05Z

@Xander, but here it is still necessary to define a vertex-ordering if we wish to compare two separate graphs. I'm looking for a representation that is identical for isomorphic graphs.

Comment by Szabolcs

2011-06-16T17:19:33Z

Thanks, this is useful!

Comment by Szabolcs

2011-06-16T16:09:38Z

If your graph is too big to represent it through an adjacency matrix stored as a dense array, you can try using sparse arrays, which will essentially be the same as working with the edge list. Perhaps it will be useful if search for algorithms for sparse matrix multiplication. I have no experience with this though.

Comment by Szabolcs

2011-06-13T18:17:37Z

@Michael, what keywords did you use to search for this?

Comment by Szabolcs

2011-06-13T14:04:10Z

@Michael, thank you, this is useful! I didn't react to your answer up til now because I was travelling.