State Space

Definition

Technically, the phrase state space refers to the space of potential possibilities. Watch the following video of a man making handmade noodles in Beijing, China. In this case, state space refers to the potential number of noodles he makes every time he folds the existing noodles in half. State Space and Decimal Numbers

If you have three decimal digits ( _ _ _ ), you can encode 1,000 different numbers (000–999). The state space refers to all of those potential values. In other words, a three-digit base10 number has 1,000 possible states.

The state space of number systems grows exponentially with the number of possible digits.

• If you have one decimal digit ( _ ), you can encode 10 different numbers (0–9).
• If you have two decimal digits ( _ _ ), you can encode 100 different numbers (00–99).
• If you have three decimal digits ( _ _ _ ), you can encode 1,000 different numbers (000–999).
• ...

Notice a pattern? Every time you add a decimal digit, the state space multiplies by 10 (e.g., 10x10=100, 100x10=1,000).

All Your Base Are Belong to Us

As seen above, number systems represent exponential growth. Each digit is a coefficient of an exponential term. The base of each exponential term is the base of the number system.

Decimal:

32410

= (3 ⨯ 102) + (2 ⨯ 101) + (4 ⨯ 100)

= 300 + 20 + 4

= 32410

Binary:

1001112

= (1 x 25) + (0 x 24) + (0 x 23) + (1 x 22) + (1 x 21) + (1 x 20)

= 32 + 4 + 2 + 1

=3910

Mathematically, any number can be described by the following notation, where i is the position of each digit in the number (i.e., i=0 represents the “ones” place, i=1 represents the “tens” place, i=2 represents the “hundreds” place, etc.): The base represents how much the state space grows multiplicatively each time a digit is added.

State Space and Binary Numbers

Unlike the base10 system, each place value in binary (or base2) has only two possibilities (0 or 1). The addition of each digit represents a doubling of the possible values represented:

• If you have one binary digit ( _ ), you can encode two different numbers (0–1).
• If you have two binary digits ( _ _ ), you can encode four different numbers (0–3).
• If you have three binary digits ( _ _ _ ), you can encode eight different numbers (0–7).
• ...

Every time you add a binary digit, the state space multiplies by two (e.g., 2 x 2 = 4, 4 x 2 = 8). The pattern here is the same, though the base differs.

State Space Is Not Just About Numbers

Consider the 20 Questions activity that you previously explored. Each time a “yes” or “no” (binary) question is resolved, the number of potential items that your question sequence can distinguish effectively doubles. With five questions, it’s possible to distinguish among 32 objects. With 10, the number grows to 1,024. With 20 questions, the number reaches 220 or 1,048,576 objects!

Imagine a very constrained space, in which I ask you to identify which direction you are facing in 1D space (i.e., “left” or “right"). How many yes/no questions must you ask to figure out the direction? The obvious answer is “2,” but that’s actually more than we need. Instead of asking “Is it left?” and “Is it right?”, we could just ask “Is it left?” or “Is it right?” The state space of one binary question contains two possibilities (21 = 2), so that‘s all we need.

For homework, consider a scenario in which you must identify which cardinal (N, S, E, W) or intercardinal (NE, NW, SE, SW) direction an object is facing. How many “yes” or “no” questions would it take to identify the direction? Naïvely, it would take eight questions (e.g., Is it “North?,” Is it “Northeast?,” Is it “East?,” etc.), but because we are using binary states, we know that it can be done in three questions.

Write Up the Following:

1. Give three dichotomous questions that will correctly identify an object’s cardinal or intercardinal orientation when answered. Note: There is not just one single correct answer here!

2. Create a table that maps each answer sequence to its matching direction. This table should have three columns (for each of the questions) and eight rows (for each of the directions). Note: Each sequence should be uniquely different than the others. Think about why this must be true.

Example Table:

Question 1 Question 2 Question 3
N Yes No Yes
NE
E
SE
S
SW
W
NW