Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 2014-01-14 05:19:40

gAr
Member
Registered: 2011-01-09
Posts: 3,481

### 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."

Offline