Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T13:02:36Z http://mathoverflow.net/feeds/question/102418 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102418/expected-number-of-identical-vertex-pairs-with-the-same-euclidean-distance-on-a-r Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice Polyrhythm 2012-07-17T02:20:08Z 2012-07-18T01:15:18Z <p>Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs of vertices, noting the color of each vertex in a pair and the Euclidean distance between them. Finally, I count the number of pairs of vertices with the both the same vertex color combination and Euclidean distance as a previously recorded pair, $P$. For example, if I've previously recorded a "red" and a "blue" vertex with Euclidean distance $d_i$ between them, which we'll write as a tuple: {$c_1, c_2, d_i$}, another example of a "red" and "blue" vertex pairing with the same Euclidean distance, {$c_1,c_2,d_i$} or {$c_2,c_1,d_i$} (order of the colors does not matter), would increase $P$ by one. </p> <p>With a hat tip to Gerhard Paseman, we can write that $P = $${N*M}\choose{2}$$-T$, where $T$ is the total number of distinct tuples: {$c_i,c_j,d_k$}, where the order of the colors do not matter and vertices of the same color are allowed.</p> <p>As a function of $N$, $M$, and $k$, what is the expected value of $P$? </p> http://mathoverflow.net/questions/102418/expected-number-of-identical-vertex-pairs-with-the-same-euclidean-distance-on-a-r/102466#102466 Answer by Joseph O'Rourke for Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice Joseph O'Rourke 2012-07-17T16:49:17Z 2012-07-18T01:15:18Z <p>Here is a little data (not an answer) for small arrays for anyone who wants to compare against a theoretical calculation. I looked at square $n \times n$ arrays, $k=2$ colors only. Here are the counts for $P$, after $100$ random trials: $$(2, 2.4), (3, 24.2), (4, 95.5), (5, 260.3), (6, 575.0), (7, 1100.1), (8, 1919.0)$$ In other words, just to interpret the last piece of data: In random $8 \times 8$ arrays, of the $\binom{64}{2}=2016$ pairs, there were on average $T=97.0$ distinct distance/color pairs (using Gerhard's definition for types $T$), leaving $P=1919.0$ repeated pairs; note $T+P=2016$. (In one trial, the distance $\sqrt{65}$ and colors $(2,2)$ occurred only once, whereas the distance $\sqrt{41}$ and colors $(1,2)$ occurred $25$ times.) Here is a graph of the same data: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/ColoringLattice.jpg" alt="Coloring Lattice Plot"></p> <p><b>Added</b>. Now that the OP has indicated an interest in variation with the number of colors $k$, here is the same type of data, but for $k=2,3,4,5,6$: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/ColoringLattice6.jpg" alt="2,3,4,5,6 colors"></p>