View source for Ghost leg

{{Short description|Method of random selection}}
{{Refimprove|date=June 2013}}
[[Image:Amidakuji2 (cropped).png|thumb|right|Covering the middle of the lines, a player chooses a start point (A). The lines are then revealed and the chosen start point traced to its terminus (3).]]
'''Ghost leg''' is a method of lottery designed to create random pairings between two sets of any number of things, as long as the number of elements in each set is the same.  This is often used to distribute things among people, where the number of things distributed is the same as the number of people.  For instance, chores or prizes could be assigned fairly and randomly this way.

It is known in Japanese as '''{{nihongo|Amidakuji|阿弥陀籤||"[[Amitābha|Amida]] lottery"}}''',{{refn|group=nb|So named because in the Muromachi period, print representations of the system were drawn radially (with starting points on the outside and endpoints on the inside), so resembling the "circle emitting rays" design popularly used to depict Amida's halo<ref>{{Cite book | url=https://books.google.com/books?id=p2QnPijAEmEC&q=amidakuji+amitabha&pg=PA28 | title=Japan Encyclopedia| isbn=9780674017535| last1=Frédéric| first1=Louis| year=2002}}</ref>}} in Korean as '''''Sadaritagi''''' (사다리타기, literally "ladder climbing") and in Chinese as '''''Guijiaotu''''' ({{zh|鬼腳圖}}, literally "ghost leg diagram").

The diagram consists of vertical lines with horizontal lines connecting two adjacent vertical lines scattered randomly along their length; the horizontal lines are called "legs".  The number of vertical lines equals the number of people playing, and at the bottom of each line there is an item - a thing that will be paired with a player.  The general rule for playing this game is: choose a line on the top, and follow this line downwards.  When a horizontal line is encountered, follow it to get to another vertical line and continue downwards.  Repeat this procedure until reaching the end of the vertical line.  Then the player is given the thing written at the bottom of the line.

If the elements written above the ghost leg are treated as a [[sequence]], and after the ghost leg is used, the same elements are written at the bottom, then the starting [[sequence]] has been transformed to another [[permutation]].  Hence, ghost leg can be regarded as a kind of permuting operator.

==Process==
As an example, consider assigning roles in a play to actors.

#To start with, the two sets are enumerated horizontally across a board. The actors' names would go on top, and the roles on the bottom. Then, vertical lines are drawn connecting each actor with the role directly below it.
#The names of the actors or roles are then concealed so that people do not know which actor is on which line, or which role is on which line.
#Next, each actor adds a leg to the board. Each leg must connect two adjacent vertical lines, and must not touch any other horizontal line.
#Once this is done, a path is traced from the top of each vertical line to the bottom. As the line is followed down, if a leg to the left or right is met, the leg must be followed to the adjacent vertical line that it connects to, then tracing down is resumed, continuing until the bottom of a vertical line is reached. The top item that the path started from is now paired with the bottom item that it ended on.

Another process involves creating the ladder beforehand, then concealing it. Then people take turns choosing a path to start from at the top. If no part of the amidakuji is concealed, then it is possible to fix the system so that a certain pairing is guaranteed, thus defeating the idea of random chance.

==Mathematics==
Part of the appeal for this game is that, unlike random chance games like [[rock, paper, scissors]], ''amidakuji'' will always create a 1:1 correspondence, and can handle arbitrary numbers of pairings. It is guaranteed that two items at the top will never have the same corresponding item at the bottom, nor will any item on the bottom ever lack a corresponding item at the top.

It also works regardless of how many horizontal lines are added. Each person could add one, two, three, or any number of lines, and the 1:1 correspondence would remain.

One way of realizing how this works is to consider the analogy of coins in cups. There are ''n'' coins in ''n'' cups, representing the items at the bottom of the ''amidakuji''. Then, each leg that is added represents swapping the position of two adjacent cups. Thus, in the end there will still be ''n'' cups, and each cup will have one coin, regardless of how many swaps are performed.

==Properties==
===Permutation===
A ghost leg transforms an input sequence into an output sequence with the same number of elements with (possibly) different order.
Thus, it can be regarded a permutation of ''n'' symbols, where ''n'' is the number of vertical lines in the ghost leg.,<ref>Ho 2012, p.31</ref> hence it can be represented by the corresponding [[permutation matrix]].

===Periodicity===
Applying a ghost leg a finite number of times to an input sequence eventually generates an output sequence identical to the original input sequence.

I.e., if ''M'' is a matrix representing a particular ghost leg, then {{nowrap|''M''<sup>''n''</sup> {{=}} ''I''}} for some finite ''n''.

===Reversibility===
For any ghost leg with matrix representation ''M'', there exists a ghost leg with representation ''M''<sup>−1</sup>, such that {{nowrap|''M'' ''M''<sup>−1</sup> {{=}} '''I'''}}

===Odd-even property of permutation===
As each leg exchanges the two neighboring elements at its ends, the number of legs indicates the [[Parity of a permutation|odd/even permutation]] property of the ghost leg. An odd number of legs represents an odd permutation, and an even number of legs gives an even permutation.

===Infinite ghost legs with same permutation===
It is possible to express every permutation as a ghost leg, but the expression is not one-to-one, i.e. a particular permutation does not correspond to a unique ghost leg. An infinite number of ghost legs represents the same permutation.

==Prime==
As there are an infinite number of ghost legs representing a particular permutation, those ghost legs have a kind of equivalence. Among those equivalent ghost legs, the ones which have smallest number of legs are called "prime".

===Bubble sort and highest simplicity===
A ghost leg can be constructed arbitrarily, but such a ghost leg is not necessarily prime. It can be proven that only those ghost legs constructed by [[bubble sort]] contains the fewest legs, and hence is prime. This is equivalent to saying that bubble sort performs the minimum number of adjacent exchanges to sort a sequence.

===Maximum number of legs of prime===
For a permutation with ''n'' elements, the maximum number of neighbor exchanging = <math>\frac{n(n-1)}{2}</math>

In the same way, the maximum number of legs in a prime with ''n'' tracks = <math>\frac{n(n-1)}{2}</math>

===Bubblization===
For an arbitrary ghost leg, it is possible to transform it into prime by a procedure called "bubblization".
When bubblization operates, the following two identities are repeatedly applied in order to move and eliminate "useless" legs.
#[[Image:GhostLeg4.svg|64 px]] ⇒ [[Image:GhostLeg5.svg|64 px]]
#[[Image:GL6.svg|64 px]] ⇒ [[Image:GhostLeg7.svg|64 px]]

When the two identities cannot be applied any more, the ghost leg is proven to be exactly the same as the ghost leg constructed by [[bubble sort]], thus bubblization can reduce ghost legs to primes.

==Randomness==
Since, as mentioned above, an odd number of legs produces an [[Parity of a permutation|odd permutation]] and an even number of legs produces an even permutation, a given number of legs can produce a maximum of half the total possible permutations (less than half if the number of legs is small relative to the number of tracks, reaching half as the number of legs increases beyond a certain critical number).

If the legs are drawn randomly (for reasonable definitions of "drawn randomly"), the evenness of the distribution of permutations increases with the number of legs. If the number of legs is small relative to number of tracks, the probabilities of different attainable permutations may vary greatly; for large numbers of legs the probabilities of different attainable permutations approach equality.

==In popular culture==
{{In popular culture|date=August 2017}}
[[File:Morikoro park - kids centre あみだくじ 2010 (5504326313).jpg|thumb|A ghost leg track on a floor in Morikoro Park in [[Aichi]], Japan]]
The 1981 arcade game ''[[Amidar]]'', programmed by [[Konami]] and published by [[Stern (game company)|Stern]], uses the same lattice as a maze. The game took its name from ''amidakuji''. and most of the enemy movement conformed to the game's rules.

An early [[Master System]] game called ''[[Psycho Fox]]'' uses the mechanics of an ''amidakuji'' board as a means to bet a bag of coins on a chance at a prize at the top of the screen. Later [[Sega Genesis]] games based on the same game concept ''[[DecapAttack]]'' and its Japanese predecessor ''Magical Hat no Buttobi Tabo! Daibōken'' follow the same game mechanics, including the ''amidakuji'' bonus levels. 

The 1990 [[Famicom]] release [[Kid Dracula (1990 video game)|Akumajo Special: Boku Dracula-Kun]] (localized in 2019 as [[Kid Dracula (1990 video game)|Kid Dracula]] as part of [[Castlevania Anniversary Collection]]) uses this ghost leg lottery after every stage as a means to choose one of four possible bonus games. A man with microphone yells “Amidakuji! Amidakuji!” before you pick your path A, B, C, or D. 

''[[Super Mario Land 2: 6 Golden Coins]]'' features an ''amidakuji-style'' bonus game that rewards the player with a power-up. ''[[New Super Mario Bros.]]'', ''[[Super Mario 64 DS]]'' and ''[[Wario: Master of Disguise]]'' feature an ''amidakuji''-style minigame in which the player uses the [[Nintendo DS|stylus]] to add new lines that must lead the player character down the winning path as he slides down the board.

In ''[[Mega Man X]]'' Bospider climbs down a web shaped rail similar to
''amidakuji'' to attack in the first Sigma's fortress stage.

Azalea Gym in [[Pokémon HeartGold and SoulSilver|''Pokémon HeartGold'' and ''SoulSilver'']] was redesigned with an ''amidakuji''-based system of carts to cross.  The correct choices lead to the gym leader; the wrong ones lead to other trainers to fight.

''[[Phantasy Star Online 2]]'' uses the principle of ''amidakuji'' for a randomly appearing bomb-defusing minigame. One must trace an ''amidakuji'' path around each bomb to determine which button defuses it; incorrect selections knock players away for a few seconds, wasting time.

In the Japanese drama ''[[Don Quixote (TV series)|Don Quixote]]'' (episode 10), the character Shirota ([[Shota Matsuda]]) uses ''amidakuji'' to help decide between candidate families for an adoption.

In ''[[Raging Loop]]'', a "ghost leg lottery" is described as an analogy for the selection of roles across a village for a ceremony that is central to the game's plot.

==Notes==
{{reflist|group=nb}}

==References==
{{Reflist}}

==External links==
{{commons category|Ghost leg}}
* https://web.archive.org/web/20091023070628/http://geocities.com/Athens/Acropolis/7247/amidakuji.html
* [http://www2.edc.org/makingmath/studentWork/amidaKuji/AmidaKujiByDavidSenft.pdf Ladders: A Research Paper by David Senft] (PDF)
* Man-Kit Ho, Hoi-Kwan Lau, Ting-Fai Man, Shek Yeung (2012). "Ghost Leg", ''Hang Lung Mathematics Awards Collection of Winning Papers, 2004''. International Press. {{ISBN|978-1-57146-254-1}}.

[[Category:Mathematical games]]
[[Category:Permutations]]
[[Category:Japanese games]]
[[Category:Amitābha]]
[[Category:Random number generation]]