The Internet Juggling Database

endeesjafrcaitherudanlel
IJDb Home > IJDb Compendium > Geek Juggling > Juggling Notation > State Diagrams

State Diagrams

Mark Thomas - 11th February, 2002.
Before I begin:
  • Knowledge of the Siteswap system is assumed.
  • To get the most from this article, you will need Microsoft Excel 97 or later.

Introduction

In the last 20 years, there have been many exciting new mathematical discoveries to the world of juggling. Possibly the most important of these was the discovery of siteswaps. These were developed by several different people at the same time.

More recently, the discovery of State Transition diagrams has been very important. These ideas were developed by Jack Boyce. I will try to explain a little about these in the following article, and also include some discoveries that I have made.

What the Diagrams mean

In a state diagram, the series of numbers is basically an instant in time. The numbers tell you where the balls are in that instant. However, it does not tell you the location of the balls, merely when they are next due to land.

In a state diagram, a 1 means a ball is in this position, and a 0 indicates a gap. A string of binary, is basically a queue of balls, and the order in which they are to be thrown. Balls are thrown from the right, and move to the left. Every time a ball is thrown, all the others in the queue move 1 place to the left. Lets look at the most basic example:

111 - This is the basic state for a 3 ball cascade. If we were to throw a 3 (this would be the green ball), this ball would move 3 spaces to the left, and would join the end of the queue. The new position we would arrive at would be: 111, which is essentially the same state, thus the 3 ball cascade may continue.

What would happen if we were now to throw a 4? Starting again from 111, if we throw a 4 (this again would be the green ball), we would move to the state - 1011. Now lets throw a 2 (note: technically, a 2 is a low throw which is caught in the hand that threw it, however, usually, jugglers don't bother to throw it, and just hold it till it is next thrown). Throwing a 2 (the blue ball) takes you to the state 111.

How is this useful?

You are probably thinking what the point of this system is. Well, by drawing careful diagrams, it is very easy to create new siteswaps, and connect existing ones. I will begin by drawing a table to cover the states with 3 balls, up to throw height 5:
Throw type:
Number: State: 0 1 2 3 4 5
1 111 - - - 1 2 3
2 1011 - - 1 - 4 5
3 10011 - - 2 4 - 6
4 1101 - 1 - - 7 8
5 10101 - 2 - 7 - 9
6 11001 - 4 7 - - 10
7 1110 1 - - - - -
8 10110 2 - - - - -
9 11010 4 - - - - -
10 11100 7 - - - - -

To use this table, first choose the state you would like to start from. For basic purposes, this we shall use state 1 (111). When you are juggling a 3 ball cascade, every throw is a 3, and every throw takes you from and to the same state - state 1. If you throw a 5, looking along the row for state 1, it tells you that this would take you to state 3 (10011). From here, if you throw a 3, looking along the row for state 3, the chart shows that you would go to state 4 (1101). From here you could throw a 1, which would take you to state 1, and return you to the cascade. Hence, you have thrown a single round of 531. When using this chart, you can throw any number the chart indicates for a given state. Also, every pattern with throw height of 5 or less, with 3 balls can be found in this chart.This chart still has limitations however.

It only allows throws of up to height 5 - it can be extended, but the chart very rapidly becomes huge. Also, it is not always clear what is going on. It is not a particularly visual method of conveying these patterns.

A better way of displaying the possible transitions from a state, is to create a grid with all possible states (up to a maximum throw height and with a certain number of balls) on both axis, and mark on the grid ways of moving from one state to the next. The vertical axis tells you the current state, and the horizontal axis tells you where you end up after a throw of a certain height.

Another thing you may have noticed about this chart is that all states up to 1111 are listed, not just those for 3 balls. By listing all possibilities, patterns emerge, which are not so clear if you only list the possible states for a certain number of balls.

Ok, so how do we use this chart. Lets try throwing 441 from a 3 ball cascade. We know that the base state for a 3 ball cascade is 111, so lets start at 111 (number 7 on the chart). First we want to throw a 4. Follow along row 7, until you find a 4. You can see that this is in column 11, which means you are now in state 11 (1011). Starting again, this time in state 11, we want to throw another 4. Following along row 11, we see that now we have arrived in state 13. Finally, by following along state 13 until you find a 1, you return to state 7, which is where we started!

You may notice that there is a diagonal line down the middle of the chart. This line is intended as a reference point. For example, imagine you are in state 11 (1011) and you throw a 4. This takes you to state 13. Rather than returning to state 13 and starting again, you can move down (or up) the column to where you find the grey square. Then you can find the next throw from this grey square by moving right or left along the row. Below the example of 441 is shown.

Notice that by using the grey squares as reference points, you never need to return to the state numbers. Remember you always move horizontally when choosing your next throw. Try finding siteswaps in the chart that you already know, and try finding new ones. You'll find it pleasantly easy.

You also may notice the +'s and -'s. If you look at the binary states that end with a '0', you'll notice that the only two options available are 0 and +. You can 'throw' a 0, or pick up a new ball, which is represented by +. Following either takes you to the next state. Note that when a ball is picked up, it is thrown immediately.

  • Download a state chart containing all states up to throw height 8 (Microsoft Excel 95 or later needed) - statechart.xls (103KB)
One of the more useful features of this chart is the ability to find transition stages. Suppose you are in state 15 (1111), and you want to juggle 561, which is thrown from state 23 (10111). If you find the grey reference square for each state, you can clearly see that throwing a 5 will take you from state 15 to 23. Now suppose you want to switch from 561 to 714. 714 is thrown from state 27 (11011). You'll see that another 5 will take you into state 27.

Let's try binary

From here on, I will be assuming you understand the binary system of numbers. Binary is a numerical system of base 2, where the only possible numbers are 0's and 1's. Therefore, this would be an ideal system for notating state diagrams, as a state diagram also uses just 0's and 1's. The one drawback with using decimals to notate binary, is that it is hard to follow which ball is which. However, this isn't really a problem, as we will eventually see.

If we take the basic state in a three ball cascade (111), we can see this is 7 in decimal. In fact, if you take the base pattern for N balls, the decimal for its binary state is 2N-1. We will see why this is later. Now if you were to throw a 4 from here, it would take you to state 1011, which is 11 in binary. There is a simple formula which connects the starting state, throw made and the finishing state.

S = starting state
T = throw made
F = final state = (S + 2T - 1)/2

Ok, but I want to do some multiplexing...
As you probably know, siteswap deals with simultaneous throws from the same hand by putting those throws in square brackets, eg. [54] means throw a 5 and 4 at the same time. The way which state diagrams handle multiplex is very simple. Instead of a 1, to indicate a ball, you use a 2 to indicate 2 balls in that space. For example, suppose you are juggling 4 balls in a fountain, then you 'throw' a 2, you will go from state 1111 to state 121.

Now we can have 1's and 2's in the state line, the binary system is no longer of any use. We could try counting in base 3, allowing 0's, 1's and 2's, but calculations are difficult in the rarely used base 3 system. Also, suppose we wated to gather and throw 3 balls at a time.

The solution I have found to this is to use decimal. This would allow up to 9 balls to be caught and thrown simultaneously from a single hand - far beyond the human capabilities, but by no means a complete solution. However. the most useful feature of using decimal, is that the string of data you input is the state line exactly as you would write it. This makes the system far easier to use. If we return to the formula we used earlier:

(S + 2T - 1) / 2

and change it to:

(S + 10T - 1) / 10

we can now input the state line exactly as it appears. However there needs to be further modification to handle multiplex throws. For every ball thrown in the multiplex, you must add 10T, where T = throw height. Also, you must subtract N, instead of 1, where N = number of balls thrown in multiplex. So we get:

Where Ti is in turn each of the different throws made simultaneously from the throwing hand. If you were in the state 113, and you wanted to throw a [543] multiplex to return to a 5 ball cascade (11111) you would do the following calculation:

(113 + 105 + 104 + 103 - 3) / 10 = 11111

How can I find new patterns using this?

Now we can combine multiple simultaneous throws (multiplexes) with the graphic charts from earlier. The new chart will operate in the same way as the uniplex one, but it will be much larger per maximum throw height to accommodate the many more possible states. The chart is numbered in base 3, meaning the maximum number of balls that can be thrown simultaneously is 2. Any higher base of number would mean the chart would become impracticably large.

Download a state chart containing all base 3 states up to throw height 5 (Microsoft Excel 95 or later needed) - multistatechart.xls (197KB)

© Mark Thomas 2002.