Golang : Markov chains to predict probability of next state example
Putting these two Golang codes here for my own future reference. The codes are adapted from the DataCamp's Markov Chains Python tutorial and writing the codes in Golang helps me to understand better about how Markov Chains works in predicting the next state or outcome. Useful in many situations and especially in trading. Can be used to predict the next trend of either bearish, bullish or stagnant.
If you've no idea about what these codes trying to do. Head over to DataCamp's Markov Chains Python tutorial to learn about Markov Chains first.
Here you go!
Part 1 :
package main
import (
"fmt"
"strconv"
"strings"
"time"
"math/rand"
"github.com/gonum/matrix/mat64"
)
// statespace
var states = []string{"sleep", "icecream", "run"}
// possible sequences of events
var transitionFromSleep = []string{
"SS",
"SR",
"SI",
}
var transitionFromRun = []string{
"RS",
"RR",
"RI",
}
var transitionFromIceCream = []string{
"IS",
"IR",
"II",
}
var transitionMatrix mat64.Matrix
func main() {
// probabilities matrix(transition matrix)
// numbers are made up out of thin air...
transitionMatrixString := "[0.2 0.6 0.2;0.1 0.6 0.3; 0.2 0.7 0.1]"
transitionMatrix = matrix(transitionMatrixString)
// print all transitionMatrix elements
fmt.Printf("transitionMatrix :\n%v\n\n", mat64.Formatted(transitionMatrix, mat64.Prefix(""), mat64.Excerpt(0)))
// perform simple sanity check.
// all probabilities must sum up to 1, therefore we have 3 rows and the final
// result must be equal to 3
s := mat64.Sum(transitionMatrix)
s1 := fmt.Sprintf("%0.1f", s)
if s1 != "3.0" {
panic("Probabilites sum up must be equal to 3, each row sum up to 1. Check your transition matrix")
} else {
fmt.Println("Transition matrix checked out and proceeding to next stage!")
}
activityForecast(2)
}
func matrixByRow(a mat64.Matrix, rowNumber int) []float64 {
dst := []float64{0.0, 0.0, 0.0}
mat64.Row(dst, rowNumber, a)
return dst
}
func sampleSet(cdf []float64) int {
// https://stackoverflow.com/questions/50507513/golang-choice-number-from-slice-array-with-given-probability
rand.Seed(time.Now().UnixNano())
r := rand.Float64()
bucket := 0
for r > cdf[bucket] {
bucket++
if bucket == len(cdf) {
bucket--
break // need this to prevent runtime error: index out of range
}
}
return bucket
}
func activityForecast(days int) {
// default state
todayActivity := "sleep"
fmt.Println("Start state : ", todayActivity)
activityList := []string{}
activityList = append(activityList, todayActivity)
i := 0
// calculate the probability of the activityList
prob := 1.0
for i < days {
if todayActivity == "sleep" {
sleepNextProbabilityDistribution := matrixByRow(transitionMatrix, 0)
randomChoice := sampleSet(sleepNextProbabilityDistribution)
change := transitionFromSleep[randomChoice]
if change == "SS" {
prob = prob * 0.2
activityList = append(activityList, "sleep")
} else if change == "SR" {
prob = prob * 0.6
todayActivity = "run"
activityList = append(activityList, "run")
} else {
prob = prob * 0.2
todayActivity = "icecream"
activityList = append(activityList, "icecream")
}
} else if todayActivity == "run" {
runNextProbabilityDistribution := matrixByRow(transitionMatrix, 1)
randomChoice := sampleSet(runNextProbabilityDistribution)
change := transitionFromRun[randomChoice]
if change == "RR" {
prob = prob * 0.5
activityList = append(activityList, "run")
} else if change == "RS" {
prob = prob * 0.2
todayActivity = "sleep"
activityList = append(activityList, "sleep")
} else {
prob = prob * 0.3
todayActivity = "icecream"
activityList = append(activityList, "icecream")
}
} else {
sleepNextProbabilityDistribution := matrixByRow(transitionMatrix, 2)
randomChoice := sampleSet(sleepNextProbabilityDistribution)
change := transitionFromIceCream[randomChoice]
if change == "II" {
prob = prob * 0.1
activityList = append(activityList, "icecream")
} else if change == "IS" {
prob = prob * 0.2
todayActivity = "sleep"
activityList = append(activityList, "sleep")
} else {
prob = prob * 0.7
todayActivity = "run"
activityList = append(activityList, "run")
}
}
i = i + 1
}
fmt.Println("Possible states : ", activityList)
fmt.Println("End state after " + strconv.Itoa(days) + " days : " + todayActivity)
fmt.Println("Probability of the possible sequence of states : ", strconv.FormatFloat(prob, 'f', 6, 64))
}
// from https://www.socketloop.com/tutorials/golang-emulate-numpy-way-of-creating-matrix-example
// WARNING: this function does not perform error checking on input string
// You probably need to modify this function to perform sanity check on stuff such as:
// such as only 1 pair of [ ]
// all columns and rows have number or 0
// all rows are same size [pynum will throw "ValueError: Rows not the same size."]
func matrix(str string) *mat64.Dense {
// remove [ and ]
str = strings.Replace(str, "[", "", -1)
str = strings.Replace(str, "]", "", -1)
// calculate total number of rows
parts := strings.SplitN(str, ";", -1)
rows := len(parts)
// calculate total number of columns
colSlice := strings.Fields(parts[0])
columns := len(colSlice)
// replace all ; with space
str = strings.Replace(str, ";", " ", -1)
// convert str to slice
// taken from https://www.socketloop.com/tutorials/golang-convert-string-to-array-slice
elements := strings.Fields(str)
// populate data for the new matrix(Dense type)
data := make([]float64, rows*columns)
for i := range data {
floatValue, _ := strconv.ParseFloat(elements[i], 64)
data[i] = floatValue
}
M := mat64.NewDense(rows, columns, data)
return M
}
Sample output:
transitionMatrix :
⎡0.2 0.6 0.2⎤
⎢0.1 0.6 0.3⎥
⎣0.2 0.7 0.1⎦
Transition matrix checked out and proceeding to next stage!
Start state : sleep
Possible states : [sleep run run]
End state after 2 days : run
Probability of the possible sequence of states : 0.300000
Part 2 :
package main
import (
"fmt"
"strconv"
"strings"
"time"
"math/rand"
"github.com/gonum/matrix/mat64"
)
// statespace
var states = []string{"sleep", "icecream", "run"}
// possible sequences of events
var transitionFromSleep = []string{
"SS",
"SR",
"SI",
}
var transitionFromRun = []string{
"RS",
"RR",
"RI",
}
var transitionFromIceCream = []string{
"IS",
"IR",
"II",
}
var transitionMatrix mat64.Matrix
func main() {
// probabilities matrix(transition matrix)
// numbers are made up out of thin air...
transitionMatrixString := "[0.2 0.6 0.2;0.1 0.6 0.3; 0.2 0.7 0.1]"
transitionMatrix = matrix(transitionMatrixString)
// print all transitionMatrix elements
fmt.Printf("transitionMatrix :\n%v\n\n", mat64.Formatted(transitionMatrix, mat64.Prefix(""), mat64.Excerpt(0)))
// perform simple sanity check.
// all probabilities must sum up to 1, therefore we have 3 rows and the final
// result must be equal to 3
s := mat64.Sum(transitionMatrix)
s1 := fmt.Sprintf("%0.1f", s)
if s1 != "3.0" {
panic("Probabilites sum up must be equal to 3, each row sum up to 1. Check your transition matrix")
} else {
fmt.Println("Transition matrix checked out and proceeding to next stage!")
}
// to save every activityList
activityListSlice := [][]string{}
count := 0
numberOfIterations := 10000
// iterations
for i := 1; i < numberOfIterations; i++ {
activityListSlice = append(activityListSlice, activityForecast(2))
}
// check out all the 'activityList' we collected
//fmt.Println(activityListSlice)
// iterate through the list to get a count of all activities ending in the state : "Run"
for _, v := range activityListSlice {
if v[2] == "run" {
count++
}
}
// calculate the probability of starting from state: "sleep" and ending at state "run"
inner := float64(count) / float64(numberOfIterations)
percentage := inner * 100.00
fmt.Printf("Probability of starting at state: 'sleep' and ending at state 'run' : %0.2f%%\n", percentage)
}
func matrixByRow(a mat64.Matrix, rowNumber int) []float64 {
dst := []float64{0.0, 0.0, 0.0}
mat64.Row(dst, rowNumber, a)
return dst
}
func sampleSet(cdf []float64) int {
// https://stackoverflow.com/questions/50507513/golang-choice-number-from-slice-array-with-given-probability
rand.Seed(time.Now().UnixNano())
r := rand.Float64()
bucket := 0
for r > cdf[bucket] {
bucket++
if bucket == len(cdf) {
bucket--
break // need this to prevent runtime error: index out of range
}
}
return bucket
}
func activityForecast(days int) []string {
// default state
todayActivity := "sleep"
activityList := []string{}
activityList = append(activityList, todayActivity)
i := 0
// calculate the probability of the activityList
prob := 1.0
for i < days {
if todayActivity == "sleep" {
sleepNextProbabilityDistribution := matrixByRow(transitionMatrix, 0)
randomChoice := sampleSet(sleepNextProbabilityDistribution)
change := transitionFromSleep[randomChoice]
if change == "SS" {
prob = prob * 0.2
activityList = append(activityList, "sleep")
} else if change == "SR" {
prob = prob * 0.6
todayActivity = "run"
activityList = append(activityList, "run")
} else {
prob = prob * 0.2
todayActivity = "icecream"
activityList = append(activityList, "icecream")
}
} else if todayActivity == "run" {
runNextProbabilityDistribution := matrixByRow(transitionMatrix, 1)
randomChoice := sampleSet(runNextProbabilityDistribution)
change := transitionFromRun[randomChoice]
if change == "RR" {
prob = prob * 0.5
activityList = append(activityList, "run")
} else if change == "RS" {
prob = prob * 0.2
todayActivity = "sleep"
activityList = append(activityList, "sleep")
} else {
prob = prob * 0.3
todayActivity = "icecream"
activityList = append(activityList, "icecream")
}
} else {
sleepNextProbabilityDistribution := matrixByRow(transitionMatrix, 2)
randomChoice := sampleSet(sleepNextProbabilityDistribution)
change := transitionFromIceCream[randomChoice]
if change == "II" {
prob = prob * 0.1
activityList = append(activityList, "icecream")
} else if change == "IS" {
prob = prob * 0.2
todayActivity = "sleep"
activityList = append(activityList, "sleep")
} else {
prob = prob * 0.7
todayActivity = "run"
activityList = append(activityList, "run")
}
}
i++
}
return activityList
}
// from https://www.socketloop.com/tutorials/golang-emulate-numpy-way-of-creating-matrix-example
// WARNING: this function does not perform error checking on input string
// You probably need to modify this function to perform sanity check on stuff such as:
// such as only 1 pair of [ ]
// all columns and rows have number or 0
// all rows are same size [pynum will throw "ValueError: Rows not the same size."]
func matrix(str string) *mat64.Dense {
// remove [ and ]
str = strings.Replace(str, "[", "", -1)
str = strings.Replace(str, "]", "", -1)
// calculate total number of rows
parts := strings.SplitN(str, ";", -1)
rows := len(parts)
// calculate total number of columns
colSlice := strings.Fields(parts[0])
columns := len(colSlice)
// replace all ; with space
str = strings.Replace(str, ";", " ", -1)
// convert str to slice
// taken from https://www.socketloop.com/tutorials/golang-convert-string-to-array-slice
elements := strings.Fields(str)
// populate data for the new matrix(Dense type)
data := make([]float64, rows*columns)
for i := range data {
floatValue, _ := strconv.ParseFloat(elements[i], 64)
data[i] = floatValue
}
M := mat64.NewDense(rows, columns, data)
return M
}
Sample output:
transitionMatrix :
⎡0.2 0.6 0.2⎤
⎢0.1 0.6 0.3⎥
⎣0.2 0.7 0.1⎦
Transition matrix checked out and proceeding to next stage!
Probability of starting at state: 'sleep' and ending at state 'run' : 47.54%
References :
https://www.socketloop.com/tutorials/golang-linear-algebra-and-matrix-calculation-example
https://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html
https://www.datacamp.com/community/tutorials/markov-chains-python-tutorial
See also : Golang : Create matrix with Gonum Matrix package example
By Adam Ng(黃武俊)
IF you gain some knowledge or the information here solved your programming problem. Please consider donating to the less fortunate or some charities that you like. Apart from donation, planting trees, volunteering or reducing your carbon footprint will be great too.
Advertisement
Tutorials
+6.1k Golang : Combine slices of complex numbers and operation example
+13.3k Golang : Check if an integer is negative or positive
+36.7k Upload multiple files with Go
+10.7k Golang : Proper way to test CIDR membership of an IP 4 or 6 address example
+9.2k Golang : Copy map(hash table) example
+12.8k Golang : Increment string example
+33.1k Golang : All update packages with go get command
+6.9k Golang : Example of custom handler for Gorilla's Path usage.
+5k Golang : Return multiple values from function
+9.7k Golang : Edge detection with Sobel method
+18.5k Golang : Populate dropdown with html/template example
+7k Golang : Check to see if *File is a file or directory