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/