Torsten Sillke, (Analysis of 1989) Problem: Expected number of pattern in a matrix. Given a random rectangular 0-1-matrix with size n*m. The entries are independet distributed with Prob(X=0) = p and Prob(X=1) = q. What is the expected number of the pattern C? 0 1 (the pattern C) 1 0 What is the expected number of the pattern D? 0 1 0 1 1 1 1 or 0 0 0 (the pattern D) 1 0 1 0 If one replaces each number with a Truchet-tile, the pattern C above represent the simple 'circles'. This question was considered by Pickover. To make computer experiments was the worst he could do for tackling this problem. Binary to Truchet Tile encoding +--+--+ +--+--+ | / | | \ | 0 -> +- -+ 1 -> +- -+ | / | | \ | +--+--+ +--+--+ The Circle Pattern C (Truchet Tile Code) +--+--+--+--+ | / | \ | +- -+- -+ | / | \ | +--+--+--+--+ | \ | / | +- -+- -+ | \ | / | +--+--+--+--+ The Dumbell Pattern D (Truchet Tile Code) +--+--+--+--+ | / | \ | +- -+- -+ | / | \ | +--+--+--+--+--+--+ | \ | \ | \ | +- -+- -+- -+ | \ | \ | \ | +--+--+--+--+--+--+ | \ | / | +- -+- -+ | \ | / | +--+--+--+--+ Example: n = 5, m = 10. The matrix is: 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 0 The pattern C occurs 4 times. The pattern D occurs 1 times. Solution: E(#Pattern C) = (n-1)*(m-1)*p^2*q^2 E(#Pattern D) = (n-2)*(m-2)*(p^4*q^2 + p^2*q^4) Hint: Linearity of the Expectation Is as in the example above p=q=1/2 and n=5, m=10, then E(#Pattern C) = (5-1)*(10-1)/16 = 9/4 = 2.25 E(#Pattern D) = (5-2)*(10-2)/64 = 3/8 = 0.375 It is not hard but cumbersome to calculate the variance too. References: Mathematical Recreations, Scientific American, ca 1989. The Expectation was not calculated, Pickover made some computer estimates. - C. A. Pickover; Picturing Randomness with Truchet Tiles, Journal of Recreational Mathematics 21:4 (1989) 256-259 (P. said: "For random orientations, the circle fraction is approximately 0.054 (number of closed circles in the pattern divided by the number of tiles.)") - C. A. Pickover; Computer, Patterns, Chaos and Beauty, Springer Verlag, New York, 1987 - Jean-Bernard ROUX; Le pavage de Truchet, http://hypo.ge-dip.etat-ge.ch/www/math/html/node56.html (with mathematica programs for drawing the figures) - C. S. Smith; The Tiling Patterns of Sebastian Truchet and the Topology of Structural Hierarchy, Leonardo, 20:4 (1987) 373-385 -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/