Math Is Fun Forum

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Generating transition matrix

From the discussion here: http://www.mathisfunforum.com/viewtopic … 19518&p=13

Posting my program in Sage to get the expected number of keystrokes, for my later reference!

st="abracadabra"                         # The string pattern    
nn=len(st)                               # The string length
mx=[[0]*(nn+1) for i in range(nn+1)]     # The initialized markov chain
nchars=26                                # Number of possible characters
for i in range(1,nn):                    # Set the probabilities row by row
    seen=st[:i]                          # The substring seen till index 'i'
    seenst=set(seen)                     # Unique chars seen
    
# Get the proper transition state, by watching the repeated substrings
# E.g. in 123121, 
#  consider the states to be "others", "1", "12", "123", "1231", "12312" and "123121"
#  If we see 123123, we must go to the state "123" from "12312"
    for ele in seenst:                   
        nlongest=0                       
        tmpst=seen+ele                       
        for k in range(1,len(tmpst)):
            if st.find(tmpst[-k:]) == 0:  # The last k chars in the state
                nlongest=k
        mx[i][i+1]=1/nchars
        if st[i] != ele and nlong != 0:
            mx[i][nlong]=1/nchars
    mx[i][0]=1-sum(mx[i])
mx[0][0]=(nchars-1)/nchars    
mx[0][1]=(1)/nchars
mx[nn][nn]=1
print sum((identity_matrix(nn)-matrix(mx)[0:nn,0:nn]).inverse()[0].list())

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."