Ponder This Challenge - December 2008 - Probability of random walk tetrominoes

Ponder This Challenge:

Consider a random walk on the 2-d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i-1, j), (i+1, j), (i, j-1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. These four points will form one of the five tetrominoes (considering mirror images to be the same). For each tetromino find the probability that it will be the one formed in this way.

Please make sure you clearly identify the tetrominoes when submitting a solution. You may wish to use the wikipedia letter designations, I,L,O,S and T. A few solutions did not receive credit
because I could not tell which tetrominoes were which. Also I am requiring exact values for the probabilities.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  XXX = 8/21    XX  = 4/21     XX = 4/21     XXX = 3/21     XXXX = 2/21
  X              XX            XX             X

  They can be found by working out the transition probabilities from smaller forms. The calculations are simplified by taking symmetry into account. For example at each step the unique domino has a 1/2 probability of becoming a bent tromino, a 1/4 probability of becoming a straight tromino and a 1/4 probability of remaining a domino. So the random walk has a 2/3 probability of forming the bent tromino and a 1/3 probability of forming the straight tromino. Similarly one can compute the probability of transitioning from each tromino to each tetromino (keeping track of whether the walker is in the middle or at the end of the tromino). Then sum over the ways of forming each tetromino to find the values above. I omit the details.

  Thanks to Jack Kennedy for the following illustration of the solution:

Solvers

• Andreas Kabel (12.02.2008 @03:48 AM EST)
• Kenneth Arnold (12.02.2008 @05:08 AM EST)
• Leo Broukhis (12.02.2008 @10:49 PM EST)
• Anneke van Steirteghem (12.02.2008 @10:59 AM EST)
• Dario Serino (12.02.2008 @11:15 AM EST)
• Bob English (12.02.2008 @12:03 AM EST)
• Jonathan Campbell (12.02.2008 @01:56 AM EST)
• Jack Kennedy (12.02.2008 @02:35 AM EST)
• Richard Bjorklund and Carl Hammarlund (12.02.2008 @03:00 AM EST)
• Michel Speiser (12.02.2008 @07:40 AM EST)
• Arthur Brietman (12.02.2008 @01:30 PM EST)
• Alexander Belton (12.02.2008 @02:14 PM EST)
• Alex Wagner (12.02.2008 @02:49 PM EST)
• Mark Perkins (12.02.2008 @03:03 PM EST)
• Michael Schaaf (12.02.2008 @04:07 PM EST)
• V Balakrishnan (12.02.2008 @05:19 PM EST)
• James Riordan (12.02.2008 @05:28 PM EST)
• Xiaoyang Guan (12.02.2008 @06:01 PM EST)
• Maris van Sprang (12.02.2008 @06:43 PM EST)
• Andreas Eisele (12.02.2008 @07:05 PM EST)
• Reinder Verlinde (12.02.2008 @07:42 PM EST)
• Michael Liepelt (12.02.2008 @07:45 PM EST)
• Adam Swejk (12.02.2008 @08:21 PM EST)
• Michael Traut (12.02.2008 @08:46 PM EST)
• Aditya K Prasad (12.03.2008 @12:18 AM EST)
• Gary M. Gerkin (12.03.2008 @03:25 AM EST)
• Jesse Kolman (12.03.2008 @03:41 AM EST)
• John Ritson (12.03.2008 @03:50 AM EST)
• Joe Riel (12.03.2008 @03:55 AM EST)
• John T. Robinson (12.03.2008 @05:42 AM EST)
• Christian Blatter (12.03.2008 @06:53 AM EST)
• Koen Vossen (12.03.2008 @01:20 PM EST)
• Ben Tarlow (12.03.2008 @02:29 PM EST)
• James Dow Allen (12.04.2008 @05:49 AM EST)
• Harold Gutch (12.04.2008 @11:08 AM EST)
• Are Hjørungnes (12.04.2008 @12:00 PM EST)
• Dan Dima (12.04.2008 @12:03 PM EST)
• Joseph C. Bonneau (12.04.2008 @01:18 PM EST)
• William C. Hasenplaugh (12.04.2008 @02:40 PM EST)
• John G. Fletcher (12.04.2008 @03:17 PM EST)
• Øyvind Grotmol (12.04.2008 @04:33 PM EST)
• Ashutosh Mehra (12.04.2008 @04:40 PM EST)
• David Blackston (12.04.2008 @05:03 PM EST)
• Thomas Geisweid (12.04.2008 @06:33 PM EST)
• Josh Buell (12.04.2008 @06:35 PM EST)
• Sangxia Huang (12.04.2008 @10:19 PM EST)
• Greg Janee (12.04.2008 @11:55 PM EST)
• Ariel Flat (12.05.2008 @01:53 AM EST)
• John Tromp (12.05.2008 @12:36 PM EST)
• Caltech Math Students (12.05.2008 @12:53 PM EST)
• Frank E. Mullin (12.05.2008 @01:03 PM EST)
• Erick Wong (12.05.2008 @06:44 PM EST)
• Jeff Steele (12.06.2008 @01:35 AM EST)
• Rashid Zia (12.06.2008 @02:53 AM EST)
• Jimmy He (12.06.2008 @07:17 AM EST)
• Sylvain Becker (12.06.2008 @07:32 AM EST)
• David Greer (12.06.2008 @12:34 PM EST)
• Michael P. Moyer (12.06.2008 @03:27 PM EST)
• Christopher Quayle (12.06.2008 @05:55 PM EST)
• Joseph DeVincentis (12.06.2008 @06:58 PM EST)
• Danny Antonetti (12.06.2008 @08:53 PM EST)
• Ioan Marius Popdan (12.07.2008 @06:06 AM EST)
• Carlo Piovesan (12.07.2008 @07:56 AM EST)
• Tom Maasha (12.07.2008 @04:24 PM EST)
• Rani Hod (12.07.2008 @04:41 PM EST)
• Alvaro Begue (12.07.2008 @04:48 PM EST)
• Matthew Paterson (12.07.2008 @08:45 PM EST)
• Sanjeev Gupta (12.08.2008 @03:04 AM EST)
• Albert Stadler (12.08.2008 @06:01 AM EST)
• Nyles Heise (12.08.2008 @07:00 AM EST)
• Michael Prähofer (12.08.2008 @11:43 AM EST)
• Ross Millikan (12.08.2008 @02:54 PM EST)
• Donald T. Dodson (12.08.2008 @05:09 PM EST)
• David Friedman (12.08.2008 @05:26 PM EST)
• Erik Hostens (12.08.2008 @08:17 PM EST)
• Glen Suares (12.08.2008 @11:46 PM EST)
• Ashish Mishra (12.09.2008 @12:14 AM EST)
• Clive Tong (12.09.2008 @07:35 AM EST)
• Lukasz Bolikowski (12.09.2008 @01:19 PM EST)
• Joachim Ripken (12.09.2008 @01:26 PM EST)
• Alessandro Scotti (12.09.2008 @01:39 PM EST)
• Chris Hills (12.09.2008 @04:53 PM EST)
• Eric Nivoix (12.09.2008 @08:27 PM EST)
• Dave Parashar (12.10.2008 @02:23 AM EST)
• Anthony P. Jones (12.10.2008 @03:25 AM EST)
• Laszlo Kozma (12.10.2008 @05:57 PM EST)
• Chris French (12.10.2008 @07:27 PM EST)
• Steven Langerwerf (12.11.2008 @06:10 AM EST)
• Greg McNulty (12.11.2008 @05:36 PM EST)
• Al Zimmermann (12.11.2008 @09:53 PM EST)
• P. Subrahmanya (12.12.2008 @06:06 AM EST)
• Uri Yanover (12.12.2008 @06:50 AM EST)
• Anton Luht (12.12.2008 @11:09 AM EST)
• Andrea Andenna (12.12.2008 @11:47 PM EST)
• Nagy Zoltan (12.13.2008 @07:00 PM EST)
• Oscar Portela (12.14.2008 @02:26 PM EST)
• Rahul Babbar and Rohit Babbar (12.14.2008 @04:00 PM EST)
• Niraj Jha (12.14.2008 @04:26 PM EST)
• Rickey Bowers (12.15.2008 @07:05 AM EST)
• Muharrem Gorkem (12.15.2008 @09:11 PM EST)
• Martin Giese (12.15.2008 @09:28 PM EST)
• Adam Daire (12.16.2008 @02:23 AM EST)
• Hui Wang (12.16.2008 @05:11 AM EST)
• Ian Smith (12.17.2008 @11:51 AM EST)
• Joe Moore (12.17.2008 @04:35 PM EST)
• Christopher G. Parham (12.17.2008 @05:18 PM EST)
• Vladimir Sedach (12.18.2008 @05:15 AM EST)
• Victor Balacescu (12.18.2008 @03:02 PM EST)
• Radu Borza (12.20.2008 @12:34 PM EST)
• Roger Antonsen (12.20.2008 @02:35 PM EST)
• Dragu Ionut-Bogdan (12.21.2008 @06:01 PM EST)
• Graeme McRae (12.21.2008 @06:14 PM EST)
• Jerry Wedekind (12.21.2008 @08:27 PM EST)
• Alexander Ivrii (12.22.2008 @07:00 AM EST)
• Keith Power (12.22.2008 @07:53 AM EST)
• Martin Thiim (12.22.2008 @12:56 PM EST)
• Clement Junca (12.22.2008 @01:11 PM EST)
• Gale Greenlee (12.22.2008 @05:50 PM EST)
• Amos Guler (12.25.2008 @08:15 AM EST)
• Bojan Basic (12.25.2008 @08:13 PM EST)
• C A Subramanian (12.25.2008 @12:36 PM EST)
• David Hentrich (12.26.2008 @08:07 AM EST)
• Varun Ahluwalia (12.26.2008 @05:24 PM EST)
• Kai Guttmann (12.27.2008 @12:38 PM EST)
• Renato Fonseca (12.28.2008 @05:23 PM EST)
• Yu Yat Hong (12.28.2008 @09:42 PM EST)
• Gaurav Saxena (12.30.2008 @03:42 PM EST)
• Jens Voz (12.30.2008 @06:32 PM EST)
• Boris Nikolaus (12.30.2008 @07:33 PM EST)
• Reiner Martin (12.31.2008 @05:22 PM EST)
• Alvaro Azpeitia (12.31.2008 @11:51 PM EST)
• Karl D'Souza (01.01.2009 @05:35 PM EST)