A blog about using cellular automata to model financial and investment markets.
Automata, Cellular automata. What are they? And what do they do? Through the body of this introduction, you will learn the fundamentals of CA and automatan based programming. We will go over the principles of automata, the classical representations of them, and what those might look like implemented in actual code. We will also explore automata and their abstractions from a mathematical and theoretical perspective.
Before we can understand the idea of a cellular automata, we need to understand what automatan, also called machines, really are. An automata is neither an object nor a function. Automata have similarities to objects found in object-oriented programming, and functions found in functional programming. Yet, they are not purely one or the other. Automata can hold data, such as values, fields, even data structures. However, automata have no concept of acting as parameters to functions or bodies of code. Nor can they be constructed or destructed, as objects can be.
One of the most stark differences between automata and classical programming paradigms is the concept of scope. In typical programming paradigms, you have values or objects whose lifetime, the relative period of time they have accessible data in the program, is determined by the start and end of a scope. The start and end is always explicit, based of the entering and exiting of a block of code. An example of this is a do while loop:
do
{
int x = 3;
x += 1;
} while(0);
In the above while loop, the integer x is created inside the scope of the loop. The value of x is incremented by 1, before the loop terminating, and the scope hence closing. We can say the lifetime of x starts at ends within theose curly braces { and }. Nearly all programming languages use clearly defined lifetimes, such the one shown. Automata lifetimes are not always defined from the start. The lifetime of an automata can also be modified during the course of a simulation or a program.
An automata in it’s most fundamental representation can be defined as:
Let
Qbe a set of states { s_0, s_1, … s_n }, wheres_0is the initial state. There is a functionT, where for all states in Q,T(s) in Qis true.
Basic automata can be constructed from a set of discrete states with change via a transition function. For now, let’s look at an implementation of a fundamental automata.
A one dimensional automata is a machine which contains a single, finite row of cells. Each cell functions as an independent machine, locked in an order with neighboring machines that is constant throughout runtime. The cells transition through a concept of generations. One or more rules are applied to the cell’s neighborhoods, for every cell in the automata. Changes to any cell are written to a new row of cells, that represent the incoming, next generation.
For this automata, we will start with a row of 21 cells, all of them holding one signed integer, that will start with the value 1 or 0. We pick a multiple of 3 because we want the row to be iterable by a neighborhood of 3. A neighborhood size for any autoamata should always be greater than 1.
#define CELL_COUNT 21
static int CELLS[CELL_COUNT] = { 1, 0, 0, 1, 1, 0, 0, 0, 1 /*Rest is 0*/ };
In order for the row of cells to evolve or change, we need to apply specific rules onto it, and create subsequent generations of the cells. For this automata, we will only use local rules, which involve the cells adjacent to one another. In other articles and posts, more complex rules such as those involving the entire row or colony will be discussed.
The rules we will use are based off a pattern of 3 cells that, if match, result in a new cell of some value in the enxt generation. It is important to note this example transitions immutably. Other automata may also transition mutably or produce events that mutate cells prior to transition. Below is the definition of the rule type:
typedef struct {
int match1;
int match2;
int match3;
int next;
} rule_t;
match1, match2, and match3 hold the first, second, and third cell values that much be matched in order for result to be born into the next generation. Now, we can decide exactly what rules we want to have being applied.
static rule_t RULES[] = {
{1, 1, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 0, 0, 1},
{1, 0, 0, 0}
};
To simplify our first trial, we will pick five rules. They count only account for the values 0 or 1. Other automata can obviously hold many more and more complex values than just 0 and 1. As we go iterate through CELLS, if at any point a rule does not match it’s pattern, we try the next rule. If none match, we will just emit a 1 cell to the next generation.
Now let’s produce our first generation, with a transition function:
void cells_transition(int* next_gen, const int* cells)
{
unsigned i;
for(i = 0; i < CELL_COUNT - 2; i++)
{
unsigned j;
int found = 0;
for(j = 0; j < (sizeof(RULES)/sizeof(rule_t)); j++)
{
if(RULES[j].match1 == cells[i] &&
RULES[j].match2 == cells[i + 1] &&
RULES[j].match3 == cells[i + 2]
)
{
next_gen[i] = RULES[j].next;
found = 1;
}
}
if(!found)
next_gen[i] = 1;
}
}
For those unfamiliar with the C language, sizeof(<array>)/sizeof(<type>) is an expression to calculate the number of items in an array
Running that automatan for several generations will produce the following results. The first row is the 0 generation before any rules are applied.
1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0
0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0
1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0
1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 0
1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0
We can observe that, regions of 0 cells appear to inhabit a moving and alternating pattern, slowly shifting from either nearly all 0 or all 1, to 101 sequencing. For more information on elementary cellular automata, see this link.
The full source code sample to produce the above cellular patterns is available here
Elementary automata are quite limited in their ability to model and predict real world scenarios. They can only represent binary entities. In order to accurately depict a market, we need to use automata that can hold multiple values. Specifically, we want to use automata with fields that can hold quanities, such as the supply of an item or a currency.
For this next example, we will use a very simple trader model called the buyer_t:
typedef struct {
float cash;
float supply;
} buyer_t;
Note: On most platforms, the float type is implemented as a single precision, 32 bit floating point number.
A buyer_t is a cell which possess two quantities, cash and supply. Cash is an anonymous currency (one and only one kind exists) that can be traded between buyer_t for more supply. Supply represents a singular, annonymous item that can be bought with cash. In a real market, there will be many items, and every cell or entity would possess multiple supplies. However, many mechanicisms and changes can still be studied from fundamental scenarios like this.
For comparison, the Python version of the buyer_t would look like this:
class Buyer(object):
def __init__(self, cash=0.0, supply=0.0):
self.cash = cash
self.supply = supply
Several facets of the buyer behavior will be explored and discussed.
One of the most rudimentary concepts of a market is the price of an item. Price is often though of as a quotient of demand and supply, such that having high demand and low supply leads to a higher price. For this example, a buyer does not have a fixed, quantized demand. Yet, they can show a willingness and desire to buy more supply based on several factors. For two buyers to make a transaction, one sells some of their supply for cash, while the other pays cash to obtain more supply.
Keeping cash and supply within a balancing state is one way to determine a price. A balancing state means a state where two values will attempt to influence decisions in order to best make themselves as equal to each other as possible. This would imply that if a buyer_t has a lot of cash but only a small amount of supply, the price for their supply will be very high. We can also change this balancing state by either using a cash / supply ratio or supply / cash ratio. For now, we will stick with cash/supply, because we want price to increase as supply decreases.
Another factor of the buyer automata is spending. Once a price is determined for a particular buyer, another buyer can determine they will spend money according to that price. If we follow the principle of equilibrium, a buyer will spend more when their money is high and their supply is low. The buyer automata uses floating point numbers to allow for a more realistic pricing and supply modeling (e.g 0.5 pounds of rice). The quantity that a buyer chooses to buy must be dependant on their total amount of cash, and the amount of cash relative to their supply. First, we can determine the amount of items they will buy with
B_i = B_p / S_p
Where,
B_p is the buyer’s priceS_p is the seller’s priceIn expanded form, this will be:
B_i = (B_c / B_s) / (S_c / S_s)
Where,
B_c, S_c , are the buyer’s and seller’s cashB_s, S_s, are the buyer’s and seller’s supplyIt’s very important for the buying cell’s price to be on the top part of the equation, because we want to derive a quantity for the transaction that best fits the buying cell. Transactions in this automata arrangement are done with respective to both prices, but a transaction is always a purchase. Every cell will get a chance to purchase in every generation.
Now that we have established how each buyer_t will determine the amount of supply it wants to purchase from another cell, and the price it will pay, we need to determine the order in which cells will perform transactions or react. For the course of this article, only the round robin approach will be covered.
Round robin ordering instructs each cell to buy and sell with all other cells once per generation. The order of this singular buy and sell is determined manually by the order in which the cells reside in the internal buffer or array. This approach allows for the most simple scheme of allowing the cells to interact. More complex automata will have far more sophisticated ordering methods, even one’s which changes the order at every generation.
We can implement the model of a buyer_t performing transactions via the following:
float buyer_price(const buyer_t* b)
{
return b->cash / b->supply;
}
float buyer_wanted_supply(const buyer_t* buying, const buyer_t* selling)
{
return(buying->cash / buying->supply) / (selling->cash / selling->supply);
}
void buyer_transaction(buyer_t* buying, buyer_t* selling)
{
float change_amount = buyer_wanted_supply(buying, selling);
float cash_amount = change_amount * buyer_price(selling);
buying->supply += change_amount;
buying->cash -= cash_amount;
selling->supply -= change_amount;
selling->cash += cash_amount;
}
void buyer_trade(buyer_t* cells, unsigned size)
{
unsigned i;
for(i = 0; i < size; i++) {
unsigned j;
for(j = i + 1; j < size; j++) {
buyer_transaction(cells + i, cells + j);
}
}
}