I had a bunch of relatives from Korea visit over the summer, and naturally an arm wrestling tournament broke out. What I found most interesting though was how they set up the initial match-ups. They didn’t draw straws, pick names out of a hat, roll a die, or eeny meeny miny moe. Instead, they made a grid.
I learned that this is a common way of randomizing things in Asia. In Korea it’s called 사다리, in China 畫鬼腳, and in Japan 阿弥陀籤. The Korean and Chinese translate to ghost leg, their poetic word for “ladder”.
How it works is this. You list the things you want to randomize at the top of your paper. You write the categories you want to randomly place them into at the bottom. Draw vertical lines connected each pair — these make up the “legs” of the ladder. Then randomly draw in “rungs”, or you can fold over the options to cover them up and have someone else do it. Once that’s done, follow each path down the ladder, taking every rung you reach. This post gives a visual step-by-step of how it works, and this paper offers a mathematical analysis.
What I decided to do was create an interactive web version of this. I started with an HTML table, which leads to a few benefits. Since a table is already a grid, it’s straightforward to style it using CSS. The image above shows the result.
Also, instead of dynamically creating the table, I made it so anyone can easily make their own table with labels and as many columns and rows as they like. Then by simply assigning it to the “ghostleg” class and copying over the JavaScript and CSS (which you’re welcome to do), they can have their own customized version. By using thead and tfoot, the section of the code to input all your labels is right at the top, not buried in the table markup.
I looped through each table row, counting the number of cells and picking a random place to draw a rung (or skip the row). Finally, a hover function was attached that highlights the path from each item to its random outcome.
Play around with Ghost Legs, or have a look at the code.
That is a very smooth setup. What’s really nice is that by quickly being able to see the paths, one can see the really neat outcome that each choice gets lined up with exactly one other choice.
I suppose the mathematicalese is that each rung is a transposition and any permutation can be described by a sequence of transpositions. So we get a random permutation in this way by having enough random transpositions.
Another visualization that could be useful is to have colored nodes and as one descends the rows, one can see the colored nodes switching. This would correspond to an algorithm in which at each step we pick a position in the array to shuffle and then swap the entry with, say, its left neighbor.
Is there any constraint on the number of rows/rungs? Thinking about a deck of cards to be shuffled, this is rather like cutting the deck, exchanging the two exposed cards, then putting the two sides back together, and cutting/exchanging repeatedly. Clearly a few cuts would be insufficient. But I wonder at which point the deck is generally random enough? (as a guess, order n) And how would “long” rungs (transposition between any two elements, not just adjacent) affect the transition to randomness?
Interesting thoughts. Just like there’s the rule of thumb about 7 shuffles of the deck, when is a ladder good enough in terms of rows and rungs? Especially given how big these ladders can get: http://www.tofugu.com/2010/06/16/amidakuji-how-to-make-your-decisions-random-japanese-style/
I see this as a lot like Plinko. Except you’re looking at a binomial distribution with that, versus a trinomial distribution here…
Hey, old post I know, but I thought I would give a heads up – the demo is broken because of https mixed content issues :)
Thanks for the tip, fixed!