Markov Chain (MC)

A MC is a deterministic model where each state is labelled with exactly one observation (called label). It can be seen as a special case of HMM. More information here.

Example

Creation

We can create the model depicted above as follow:

>>> import jajapy as ja
>>> labelling=['a','b','c','d','a']
>>> transitions = [(0,1,0.8),(0,2,0.2),
>>>                (1,3,0.6),(1,2,0.4),
>>>                (2,0,0.5),(2,4,0.5),
>>>                (3,2,0.3),(3,3,0.7),
>>>                (4,2,0.2),(4,3,0.1),(4,4,0.7)]
>>> mc = ja.createMC(transitions, labelling, initial_state=0, name='My_MC')
>>> print(mc)
Name: My_MC
Initial state: s5
----STATE 0--a----
s0 -> s1 : 0.8
s0 -> s2 : 0.2

----STATE 1--b----
s1 -> s2 : 0.4
s1 -> s3 : 0.6

----STATE 2--c----
s2 -> s0 : 0.5
s2 -> s4 : 0.5

----STATE 3--d----
s3 -> s2 : 0.3
s3 -> s3 : 0.7

----STATE 4--a----
s4 -> s2 : 0.2
s4 -> s3 : 0.1
s4 -> s4 : 0.7

----STATE 5--init----
s5 -> s0 : 1.0

We can also generate a random MC

>>> random_model = ja.MC_random(nb_states=4,
                                random_initial_state=True,
                                alphabet=['a','b','c'])
>>> print(random_model)
Name: MC_random_4_states
Initial state: s4
----STATE 0--a----
s0 -> s0 : 0.32142857142857145
s0 -> s1 : 0.07142857142857142
s0 -> s2 : 0.35714285714285715
s0 -> s3 : 0.25

----STATE 1--b----
s1 -> s0 : 0.32
s1 -> s1 : 0.2
s1 -> s2 : 0.24
s1 -> s3 : 0.24

----STATE 2--c----
s2 -> s0 : 0.3225806451612903
s2 -> s1 : 0.16129032258064516
s2 -> s2 : 0.1935483870967742
s2 -> s3 : 0.3225806451612903

----STATE 3--a----
s3 -> s0 : 0.2413793103448276
s3 -> s1 : 0.3103448275862069
s3 -> s2 : 0.3103448275862069
s3 -> s3 : 0.13793103448275862

----STATE 4--init----
s4 -> s0 : 0.04
s4 -> s1 : 0.32
s4 -> s2 : 0.4
s4 -> s3 : 0.24

Exploration

>>> model.getLabel(0) # label of state 0
'a'
>>> model.getLabel(1) # label of state 1
'b'
>>> model.tau(0,1,'a') # probability of moving from s0 to s1 seeing 'a'
0.8
>>> model.tau(0,1,'b') # 0.0 since state 0 is not labelled with 'b'
0.0
>>> model.a(0,1) # same as model.tau(0,1,'a') since state 0 is labelled with 'a'
0.8
>>> model.getAlphabet()  # all possible observations
['init','a','b','c','d']

Running

>>> model.run(5) # returns a list of 5 observations
['init','a', 'b', 'd', 'd', 'c']
>>> s = model.generateSet(10,5) # returns a Set containing 10 traces of size 5
>>> s.sequences
[['init','a', 'b', 'd', 'd', 'd'], ['init','a', 'b', 'c', 'a', 'b'],
['init','a', 'b', 'd', 'c', 'a'], ['init','a', 'b', 'd', 'd', 'c']]
>>> s.times # the first sequence appears four times, the second twice, etc...
[4, 2, 3, 1]

Analysis

>>> model.logLikelihood(s) # loglikelihood of this set of traces under this model
-1.8009169143518982

Saving/Loading

>>> model.save("my_mc.txt")
>>> same_model = ja.loadMC("my_mc.txt")

Converting from/to Stormpy

>>> stormpy_sparse_model = model.toStormpy() # the next line is equivalent
>>> stormpy_sparse_model = ja.jajapyModeltoStormpy(model)
>>> same_model == ja.stormpyModeltoJajapy(stormpy_sparse_model)

Converting from/to Prism

>>> model.savePrism("my_mc.sm")
>>> same_model = ja.loadPrism("my_mc.sm")

Model

class jajapy.MC(matrix: ndarray, labelling: list, name: str = 'unknown_MC')

Creates an MC.

Parameters

matrixndarray: A (N x N) ndarray (with N the nb of states). Represents the transition matrix. matrix[s1][s2] is the probability of moving from s1 to s2.
labelling: list of str: A list of N observations (with N the nb of states). If labelling[s] == o then state of ID s is labelled by o. Each state has exactly one label.
namestr, optional: Name of the model. Default is “unknow_MC”

a(s1: int, s2: int) → float

Returns the probability of moving from state s1 to state s2.

Parameters

s1int: ID of the source state.
s2int: ID of the destination state.

Returns

float: Probability of moving from state s1 to state s2.

Example

>>> model.a(0,1)
0.6

generateSet(set_size: int, param, distribution=None, min_size=None, timed: bool = False) → Set

Generates a set (training set / test set) containing set_size traces.

Parameters

set_size: int: number of traces in the output set.
param: a list, an int or a float.: the parameter(s) for the distribution. See “distribution”.
distribution: str, optional: If distribution=='geo' then the sequence length will be distributed by a geometric law such that the expected length is min_size+(1/param). If distribution==None param can be an int, in this case all the seq will have the same length (param), or param can be a list of int. Default is None.
min_size: int, optional: see “distribution”. Default is None.
timed: bool, optional: Only for timed model. Generate timed or non-timed traces. Default is False.

Returns

output: Set: a set (training set / test set).

Examples

>>> set1 = model.generateSet(100,10)
>>> # set1 contains 100 traces of length 10
>>> set2 = model.generate(100, 1/4, "geo", min_size=6)
>>> # set2 contains 100 traces. The length of the traces is distributed following
>>> # a geometric distribution with parameter 1/4. All the traces contains at
>>> # least 6 observations, hence the average length of a trace is 6+(1/4)**(-1) = 10.

getAlphabet() → list

Returns the alphabet of this model.

Returns

list of str: The alphabet of this model

Example

>>> model.getAlphabet()
['a','b','c','d','done']

getLabel(state: int) → str

Returns the label of state.

Parameters

stateint: a state ID

Returns

str: a label

Example

>>> model.getLabel(2)
'Label-of-state-2'

logLikelihood(sequences: Set) → float

Compute the average loglikelihood of a set.

Parameters

sequences: Set: A set.

Returns

output: float: loglikelihood of sequences under this model.

Examples

>>> model.logLikelihood(set1)
-4.442498878506513

next(state: int) → tuple

Return a state-observation pair according to the distributions described by matrix

Returns

output(int, str): A state-observation pair.

Example

>>> model.next(0)
(1,'a')
>>> model.getLabel(0)
'a'
>>> model.next(0)
(1,'a')
>>> model.next(0)
(2,'a')
>>> model.a(0,1)
0.6
>>> model.a(0,2)
0.4

pi(s: int) → float

Return the probability of starting in state s.

Parameters

s: int: state ID.

Returns

outputfloat: the probability of starting in state s.

rename(name: str) → None

Change the name of the model.

Parameters

namestr: new name.

run(number_steps: int, current: int = -1) → list

Simulates a run of length number_steps of the model and return the sequence of observations generated.

Parameters

number_steps: int: length of the simulation.
currentint, optional.: If current it set, it starts from the state current. Otherwise it starts from an initial state.

Returns

output: list of str: trace generated by the run.

save(file_path: str) → None

Save the model into a text file.

Parameters

file_pathstr: path of the output file.

Examples

>>> model.save("my_model.txt")

savePrism(file_path: str) → None

Save this model into file_path in the Prism format.

Parameters

file_pathstr: Path of the output file.

tau(s1: int, s2: int, obs: str) → float

Returns the probability of moving from state s1 to s2 seeing label obs. (i.e. if s1 is not labelled with obs the probability is 0.0).

Parameters

s1: int: source state ID.
s2: int: destination state ID.
obs: str: seen label.

Returns

float: probability of moving from state s1 to s2 seeing label obs.

Example

>>> model.tau(0,1,'a')
0.6
>>> model.getLabel(0)
'a'
>>> model.tau(0,1,'b')
0.0
>>> model.getLabel(1)
'b'

toStormpy()

Returns the equivalent stormpy sparse model. The output object will be a stormpy.SparseDtmc.

Returns

stormpy.SparseDtmc: The same model in stormpy format.

updateLabelling(new_labels: list) → None

Update the states labelling.

Parameters

new_labels: list: a list of new labels. The length of the list must be equal to the number of states.

Other Functions

jajapy.createMC(transitions: list, labelling: list, initial_state, name: str = 'unknown_MC') → MC

An user-friendly way to create a MC.

Parameters

transitions[ list of tuples (int, int, float)]: Each tuple represents a transition as follow: (source state ID, destination state ID, probability).
labelling: list of str: A list of N observations (with N the nb of states). If labelling[s] == o then state of ID s is labelled by o. Each state has exactly one label.
initial_stateint or list of float: Determine which state is the initial one (then it’s the id of the state), or what are the probability to start in each state (then it’s a list of probabilities).
namestr, optional: Name of the model. Default is “unknow_MC”

Returns

MC: the MC describes by transitions, labelling, and initial_state.

Examples

>>> model = createMC([(0,1,1.0),(1,0,0.6),(1,1,0.4)],['b','a'],0,"My_MC")
>>> print(model)
Name: My_MC
Initial state: s2
----STATE 0--b----
s0 -> s1 : 1.0
----STATE 1--a----
s1 -> s0 : 0.6
s1 -> s1 : 0.4
----STATE 2--init----
s2 -> s0 : 1.0

jajapy.loadMC(file_path: str) → MC

Load an MC saved into a text file.

Parameters

file_pathstr: Location of the text file.

Returns

outputMC: The MC saved in file_path.

Examples

>>> model = loadMC("my_model.txt")

jajapy.MC_random(nb_states: int, labelling: list, random_initial_state: bool = True, sseed: Optional[int] = None) → MC

Generate a random MC.

Parameters

number_statesint: Number of states.
labellinglist of str: List of observations.
random_initial_state: bool, optional: If set to True we will start in each state with a random probability, otherwise we will always start in state 0. Default is True.
sseedint, optional: the seed value.

Returns

MC: A pseudo-randomly generated MC.

Examples

>>> model = MC_random(2,['a','b'],False)
>>> print(model)
Name: MC_random_2_states
Initial state: s2
----STATE 0--a----
s0 -> s0 : 0.625
s0 -> s1 : 0.375
----STATE 1--b----
s1 -> s0 : 0.9
s1 -> s1 : 0.1
----STATE 2--init----
s2 -> s0 : 1.0