User szabolcs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T05:16:30Z http://mathoverflow.net/feeds/user/8776 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69600/probability-that-a-certain-markov-process-has-produced-a-given-state Probability that a certain Markov process has produced a given state Szabolcs 2011-07-06T05:43:30Z 2012-02-06T15:25:11Z <p>I am looking for advice on the following practical problem. Please keep in mind that this came up in a practical application.</p> <p>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).</p> <p>We have two transition probability matrices, $A$ and $B$.<br> I can <em>probably</em> calculate $A_{ij}$ for any two states $i$ and $j$ if needed, but what I can do <em>easily</em> is just propagate the states (simulate the process).</p> <p>Suppose we start from some arbitrary state and let the system evolve for a very long time, obtaining a state $k$.</p> <p>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$?</p> <p>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?</p> <p><em>Note:</em> I think this Markov chain is reversible.</p> <p><sub>(I expect that the question will probably need clarifications once I manage to understand it more deeply. Please help with this.)</sub></p> http://mathoverflow.net/questions/70987/constructing-szemeredi-partitions-on-a-computer Constructing Szemerédi partitions on a computer Szabolcs 2011-07-22T13:20:50Z 2011-07-22T14:06:19Z <p>Are there <em>practical</em> ways to construct the <a href="http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma" rel="nofollow">Szemerédi partitions</a> of a given graph (on a computer)? I found <a href="http://en.wikipedia.org/wiki/Algorithmic_version_for_Szemer%C3%A9di_regularity_partition" rel="nofollow">this algorithmic version</a> 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.</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/68041/showing-block-diagonal-structure-of-matrix-by-reordering Showing block diagonal structure of matrix by reordering Szabolcs 2011-06-17T10:25:48Z 2011-06-18T10:29:16Z <p>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.</p> <p>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.</p> <p>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.</p> <p>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?</p> <p>Any pointers are welcome. I'm sure there must be an easy solution to this.</p> http://mathoverflow.net/questions/67963/defining-a-canonical-ordering-of-matrix-rows-columns Defining a canonical ordering of matrix rows/columns Szabolcs 2011-06-16T15:47:57Z 2011-06-17T02:57:16Z <p>I would like to find a way to define a <strong>canonical ordering</strong> of rows/columns in a matrix.</p> <p>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.</p> <p><em>Note:</em> 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$$</p> <p><em>Note 2:</em> 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.</p> <p><strong>EDIT</strong> I have a suspicion that an ordering relation that satisfies the above condition might not exist. Is this possible?</p> <p><strong>EDIT 2</strong>: I am rephrasing the question per several requests. Actually my problem is:</p> <p>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.</p> <p>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. </p> <p>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 &lt;-> 2 will not keep the adjacency matrix invariant (but e.g. exchanging both vertices 1 &lt;-> 2 <em>and</em> 3 &lt;-> 4 will).</p> <p><strong>Please close this question.</strong></p> http://mathoverflow.net/questions/67419/finding-number-of-independent-variables-in-statistical-dataset Finding number of independent variables in "statistical" dataset Szabolcs 2011-06-10T10:24:23Z 2011-06-10T15:37:19Z <p>I would like to know if there are any standard techniques (that I don't know about) to solve the following problem.</p> <p>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)$.</p> <p>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?</p> <p>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 <em>number</em> of independent variables for now, not the nature of relationship between them.</p> <p><strong>Note:</strong> 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.</p> <p><strong>Note 2:</strong> Please help tag the question appropriately...</p> <p><strong>EDIT</strong></p> <p>Another way to put it:</p> <p>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?</p> http://mathoverflow.net/questions/66444/generalization-of-scalar-product-to-k-dimensional-subspaces-as-opposed-to-1-dime Generalization of scalar product to k-dimensional subspaces (as opposed to 1-dimensional subspaces, i.e. vectors) Szabolcs 2011-05-30T13:02:47Z 2011-05-30T17:21:03Z <p>This came up in a practical problem (physics).</p> <p>In the following, we work with real numbers only, and consider every vector to be normalized to 1.</p> <p>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.</p> <p>I need a generalization of this "similarity measure" to $k$-dimensional subspaces.</p> <p>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$).</p> http://mathoverflow.net/questions/60829/fast-algorithm-for-counting-the-number-of-acyclic-paths-on-a-directed-graph Fast algorithm for counting the number of acyclic paths on a directed graph Szabolcs 2011-04-06T16:03:29Z 2011-04-06T16:07:32Z <p>In short, I need a <strong>fast</strong> algorithm to count how many acyclic paths are there in a simple directed graph.</p> <p>By <em>simple</em> graph I mean one without self loops or multiple edges. A <em>path</em> can start from any node and must end on a node that has no outgoing edges. A path is <em>acyclic</em> if no edge occurs twice in it.</p> <p>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.</p> <p>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.</p> <p>The sample dataset: <a href="http://pastie.org/1763781" rel="nofollow">http://pastie.org/1763781</a> (each line is an edge-pair)</p> <p>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): <a href="http://pastie.org/1763790" rel="nofollow">http://pastie.org/1763790</a></p> <p><em>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.</em></p> <p>Note: Same question previously posted on <a href="http://stackoverflow.com/questions/5569256/fast-algorithm-for-counting-the-number-of-acyclic-paths-on-a-directed-graph">stackoverlow</a>, hope this is not against the rules. Later realized the question has more to do with maths.</p> http://mathoverflow.net/questions/69600/probability-that-a-certain-markov-process-has-produced-a-given-state/87675#87675 Comment by Szabolcs Szabolcs 2012-02-07T09:14:16Z 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. http://mathoverflow.net/questions/70987/constructing-szemeredi-partitions-on-a-computer/70989#70989 Comment by Szabolcs Szabolcs 2011-07-25T13:55:05Z 2011-07-25T13:55:05Z But then apparently one needs a graph of a minimum size for a given $\epsilon$. http://mathoverflow.net/questions/70987/constructing-szemeredi-partitions-on-a-computer/70989#70989 Comment by Szabolcs Szabolcs 2011-07-25T13:37:41Z 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: <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.681" rel="nofollow">citeseer.ist.psu.edu/viewdoc/&hellip;</a> http://mathoverflow.net/questions/69600/probability-that-a-certain-markov-process-has-produced-a-given-state/69604#69604 Comment by Szabolcs Szabolcs 2011-07-06T07:16:12Z 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. http://mathoverflow.net/questions/69600/probability-that-a-certain-markov-process-has-produced-a-given-state Comment by Szabolcs Szabolcs 2011-07-06T07:09:05Z 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. http://mathoverflow.net/questions/68041/showing-block-diagonal-structure-of-matrix-by-reordering/68064#68064 Comment by Szabolcs Szabolcs 2011-06-18T10:41:01Z 2011-06-18T10:41:01Z Oops, good you pointed that out http://mathoverflow.net/questions/68041/showing-block-diagonal-structure-of-matrix-by-reordering/68064#68064 Comment by Szabolcs Szabolcs 2011-06-18T09:25:46Z 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? http://mathoverflow.net/questions/68041/showing-block-diagonal-structure-of-matrix-by-reordering Comment by Szabolcs Szabolcs 2011-06-17T12:48:48Z 2011-06-17T12:48:48Z Just imagine that you write down a block-diagonal matrix and add some extra elements. Of course by <i>looking</i> at this thing one can tell that it is an &quot;almost&quot; block-diagonal matrix. I am looking for something that <i>captures this intuition</i>. Coming up with a precise definition is part of the problem. http://mathoverflow.net/questions/68041/showing-block-diagonal-structure-of-matrix-by-reordering/68050#68050 Comment by Szabolcs Szabolcs 2011-06-17T12:45:49Z 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. http://mathoverflow.net/questions/67960/cycle-of-length-4-in-an-undirected-graph/67966#67966 Comment by Szabolcs Szabolcs 2011-06-17T07:15:07Z 2011-06-17T07:15:07Z @TonyK, you are right, it does not work. http://mathoverflow.net/questions/67963/defining-a-canonical-ordering-of-matrix-rows-columns/67971#67971 Comment by Szabolcs Szabolcs 2011-06-16T18:30:05Z 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. http://mathoverflow.net/questions/67963/defining-a-canonical-ordering-of-matrix-rows-columns/67971#67971 Comment by Szabolcs Szabolcs 2011-06-16T17:19:33Z 2011-06-16T17:19:33Z Thanks, this is useful! http://mathoverflow.net/questions/67960/cycle-of-length-4-in-an-undirected-graph/67966#67966 Comment by Szabolcs Szabolcs 2011-06-16T16:09:38Z 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. http://mathoverflow.net/questions/67419/finding-number-of-independent-variables-in-statistical-dataset/67447#67447 Comment by Szabolcs Szabolcs 2011-06-13T18:17:37Z 2011-06-13T18:17:37Z @Michael, what keywords did you use to search for this? http://mathoverflow.net/questions/67419/finding-number-of-independent-variables-in-statistical-dataset/67447#67447 Comment by Szabolcs Szabolcs 2011-06-13T14:04:10Z 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.