Percolation theory looks at problems such as the probability of being able to traverse some region with random obstacles. It is motivated by problems such as modeling the flow of a fluid in a porous medium.
Here’s a percolation problem for QR codes: What is the probability that there is a path from one side of a QR code to the opposite side? How far across a QR code would you expect to be able to go? For example, the QR code below was generated from my contact information. It’s not possible to go from one side to the other, and the red line shows what I believe is the deepest path into the code from a side.
This could make an interesting programming exercise. A simple version would be to start with a file of bits representing a particular QR code and find the deepest path into the corresponding image.
The next step up would be to generate simplified QR codes, requiring certain bits to be set, such as the patterns in three of the four corners that allow a QR reader to orient itself.
The next step in sophistication would be to implement the actual QR encoding algorithm, including its error correction encoding, then use this to encode random data.
(Because of the error correction used by QR codes, you could scan the image above and your QR reader would ignore the red path. It would even work if a fairly large portion of the image were missing because the error correction introduces a lot of redundancy.)
Higher than the probability of someone scanning said QR code, no doubt.
One can use the error correction capacity of the QR codes to add a few white pixels and have a percolating QR-code with the same data with probability close to 1 !
The most influential factor in percolation behavior in QR Codes is probably the masking patterns applied to a symbol. If you follow the specification to the letter, QR Codes actively discourage long runs and blocks of the same color, and any deviation from a 50/50 mix of black/white modules. Selecting masking patterns with different priorities could create longer percolation paths. A slightly more dicey tweak could be to flip modules obstructing otherwise-good paths trusting that the error correction will fix it during decoding.
The probability depends of course on the size of the QR code – a quick and dirty program yields the following probabilities for a path from the left side to the right side:
QR code size Probability
21 0.4956
25 0.1578
29 0.0783
33 0.0347
37 0.0118
41 0.00744
45 0.001295
49 0.00102041
53 0.00014577
57 0.00019208
61 0.00014599
65 0.00003687
69 0.000064568
Numbers were obtained by encoding 350*(Size QR) random strings of appropriate length into a QR code and use a simple flood fill algorithm to find out if ‘the other side’ can be reached.
@Oliver: Do you know how these numbers compare with what you would get for a random array of the same size (i.e., each pixel independently selected to be black or white with 0.5 probability)?
@Ted: Not yet :-)
But great idea – I’ll come back to that once the computer is done…
This could be challenging to compute because of the structured nature of QR codes (see https://en.wikipedia.org/wiki/QR_code#/media/File:QR_Code_Structure_Example_3.svg).
@Aaron – Yes, encoding your own QR code is complicated. But doable (and educational). However, the good people of Wolfram implemented a QR encoder in their language, so I do not have to rely on my own version…
I meant if you wanted to compute this in closed form, rather than by doing sampling.
For this system, which corresponds to “site” percolation on the square lattice, the percolation threshold is 0.592746 (see “Percolation Threshold” Wikipedia page), so if blacks and whites are about 50-50 and random, you will rarely get percolation. If you add two given diagonals to the neighbors of each site (thus, a total of six neighbors), the system will correspond to site percolation on the triangular lattice, where the threshold is 1/2. Or you can alternate having sites with the usual four nearest neighbors, and sites with all diagonals (eight nearest neighbors). This corresponds to the “union-jack” lattice where the threshold is 1/2 once again. For a random array of black and white squares, you will have percolation (a crossing path) approximately 1/2 of the time on a square system when you are at the critical threshold, but much less than 1/2 when you are below the threshold for large systems.