Pattern Recognition

Stage: 5 Challenge Level: Challenge Level:3 Challenge Level:3 Challenge Level:3

A grid can be coloured with Red and Yellow squares. A computer programmer has been given the task to determine automatically if a given grid is likely to have been coloured in randomly with equal chance of Red or Yellow in each small square. Each pattern is converted into a code and then the computer processes the code to decide if the grid was likely to have been generated completely randomly in this way. The result is shown in this interactivity (full screen version ):

This text is usually replaced by the Flash movie.


Using a mixture of experimentation and analysis, use the interactivity to try to create a hypothesis for the way in which the computer generates a code for each pattern. Test your hypothesis on new patterns, refining the hypothesis as necessary.

When you feel that you have understood the way in which the computer generates the codes, can you create a hypothesis to explain how the computer decides to declare a pattern unlikely?

Test your hypothesis by building up experimental evidence in its favour.

When you feel confident of the strength of your hypothesis, can you predict which of the following patterns would be considered random by the computer?



Discussion / extension points:
  1. Why do you think that the computer programmer made the choice in this way. Is it a good way? How else might you approach this problem?
  2. Can you create a pattern which is 'obviously' not random, yet fools the computer's algorithm?
  3. Can you spot unlikely patterns visually? Could you visually differentiate between these likely and unlikely samples?




If you would find it helpful, these patterns are found on this spreadsheet .



NOTES AND BACKGROUND

An experiment or process is typically declared to be random if there is no way of determining with certainty the outcome of the procedure in advance. Within any random process there are always some known constraints - for example, choosing a card from a pack has a limited 52 possibilities, although the actual result cannot be known in advance. Sometimes the possible results are equally likely and sometimes not.The word 'randomness' can cause a great deal of confusion, so as mathematicians, we like to specifiy as clearly as possible which aspects of a problem are constrained and which are variable. In these grids, we use 'random' to mean each square is coloured Red or Yellow with each colour equally likely and independently of the colours of any other squares. This is the assumption tested in this question. It makes use of the fact that several different random grids share similar properties. Those with the most commonly seen properties are declared to be most likely. To see how this might work, note that the chance of getting all the same colour is less than the chance of winning the national lottery 4 weeks in a row whereas is it exceedingly likely that the outcome will consist of more than 10 different 'islands' of colour.

search engine page

Published July 2008,August 2008.