473,320 Members | 1,978 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

markov query

markov query

I have noticed a couple markov implementations in python, but none
quite seem to do what i would like. Most seem to do an analysis of some
text and create a new text based on that... I think, (sorry i just
don't know terminology well) a markov table (or is it called a
transition table) to describe how to get from one event to another. So
if i have 3 events, say, A, B, and C which can come in any order, a
Markov chain describes the probability of what the next event will be
using a table. The following table demonstrates a first-order Markov
chain. There are three possible states. Either the current event is A,
B, or C. For each possible current state, there are three possible next
letters. Each row in the table indicates the relative probability of
going to the next letter. For example, if you are currently on letter
A, there is a 20% chance of repeating letter A, a 50% chance of going
to B, and a 30% chance of going to C. Note that the sum of changes for
each row is 100% (20 + 50 + 30 = 100).

Current -- next -- next -- next
A ----- B ----- C
A: 20% -- 50% -- 30%
B: 35% -- 25% -- 40%
C: 70% -- 14% -- 16%

Here the sequence C B and C C would be rare and the sequence C A
common.

This is a first-order Markov chain, which means that only the current
state affects the choice of the next event. A second-order Markov chain
would mean that the current state and the last state affect the choice
of the next event. A third-order Markov chain would indicate that the
current state and the last two states in the sequence will affect the
choice of the next state, and so on. Here is an example transition
table for a 2nd order Markov chain.

Current -- next -- next -- next
A ----- B ----- C
A A 15% 55% 30%
A B 20% 45% 35%
A C 60% 30% 10%
B A 35% 25% 40%
B B 49% 48% 3%
B C 60% 20% 20%
C A 5% 75% 20%
C B 0% 90% 10%
C C 70% 14% 16%

For example, if the current event is B and the last one was A, then the
probability of the next event being A is 20%, B is 45% and C is 35%.
The pattern C B A will never occur, and the pattern B B C will occur
rarely.

Does anyone know of any modules or packages that include markov tables
for creating patterns like shown above.
P.S. Does any one know first of all whether these are called markov
tables, transition tables or probability tables? I am not sure i am
referring to this correctly and what the differences would be if any

cheers,

kp

Mar 14 '06 #1
5 1871
Don't know of a Python module (although this doesn't look complex enough for a
package anyway...), but

kpp9c wrote:
P.S. Does any one know first of all whether these are called markov
tables, transition tables or probability tables? I am not sure i am
referring to this correctly and what the differences would be if any


as for terminology:

http://www.csse.monash.edu.au/~lloyd...tured/HMM.html
http://en.wikipedia.org/wiki/Hidden_Markov_model
Hope it helps,
Stefan
Mar 14 '06 #2
kpp9c wrote:
I have noticed a couple markov implementations in python, but none
quite seem to do what i would like. Most seem to do an analysis of some
text and create a new text based on that... I think, (sorry i just
don't know terminology well) a markov table (or is it called a
transition table) to describe how to get from one event to another.
Yes, a system which does this has to build a Markov chain from a data
set and then traverse it.
Does anyone know of any modules or packages that include markov tables
for creating patterns like shown above.
Any program that actually uses Markov chains to generate new text based
on existing input as you've described will necessarily create a Markov
chain. So if what you want is the Markov chain itself, then it's
already in there somewhere.
P.S. Does any one know first of all whether these are called markov
tables, transition tables or probability tables? I am not sure i am
referring to this correctly and what the differences would be if any


They're called Markov chains.

--
Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
Nothing spoils a confession like repentence.
-- Anatole France
Mar 14 '06 #3
> Yes, a system which does this has to build a Markov chain from a data
set and then traverse it. Any program that actually uses Markov chains to generate new text based
on existing input as you've described will necessarily create a Markov
chain.


I think you misunderstood. If you see my original post my whole point
was that this was exactly what i don't want. There are several
algorithms out that that already do that. I want to use a table that i
define from scratch to shape a stochastic process. In this case there
is no original input to analyze and i don't want a chain built by
analysis and i am not using necessarily texts.

Mar 15 '06 #4
>Yes, a system which does this has to build a Markov
chain from a data set and then traverse it.

Any program that actually uses Markov chains to generate
new text based on existing input as you've described


Hi. That isn't really what i have described. If i did i could use
exsisting algorithms. What you describe is exactly what i don't want in
this particular case. I am actually not wanting it to build a chain
from some input that it analyzes. There is no input. If you see, i am
trying to define a table that tells it how to proceed forward from
scratch as a stochastic process.

cheers,

-kp--

Mar 15 '06 #5
kpp9c wrote:
Yes, a system which does this has to build a Markov
chain from a data set and then traverse it.

Any program that actually uses Markov chains to generate
new text based on existing input as you've described


Hi. That isn't really what i have described. If i did i could use
exsisting algorithms. What you describe is exactly what i don't want in
this particular case. I am actually not wanting it to build a chain
from some input that it analyzes. There is no input. If you see, i am
trying to define a table that tells it how to proceed forward from
scratch as a stochastic process.


Any such program has two main parts, one that trains the transition matrix from
a data set, and one that generates output from that transition matrix. You
should be able to take such a program and only use the latter component with
your transition matrix, however you choose to create it. Googling for 'python
markov' generates several leads.

--
Robert Kern
ro*********@gmail.com

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

Mar 15 '06 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: jaysonsch | last post by:
Hello! I am having some problems with a database query that I am trying to do. I am trying to develop a way to search a database for an entry and then edit the existing values. Upon submit, the...
29
by: shank | last post by:
1) I'm getting this error: Syntax error (missing operator) in query expression on the below statement. Can I get some advice. 2) I searched ASPFAQ and came up blank. Where can find the "rules"...
9
by: netpurpose | last post by:
I need to extract data from this table to find the lowest prices of each product as of today. The product will be listed/grouped by the name only, discarding the product code - I use...
3
by: Harvey | last post by:
Hi, I try to write an asp query form that lets client search any text-string and display all pages in my web server that contain the text. I have IIS 6.0 on a server 2003. The MSDN site says...
4
by: Diamondback | last post by:
I have two tables, WIDGETS and VERSIONS. The WIDGETS table has descriptive information about the widgets while the VERSIONS table contains IDs relating to different iterations of those widgets...
14
by: Dave Thomas | last post by:
If I have a table set up like this: Name | VARCHAR Email | VARCHAR Age | TINYINT | NULL (Default: NULL) And I want the user to enter his or her name, email, and age - but AGE is optional. ...
2
by: Dom | last post by:
I need to run a query based on a query in Access. The second query has a number of conditions which all work well, but there is one more contition I need to set to make it run properly. the...
9
by: Scott David Daniels | last post by:
Here's one way (convert each set of transition percentages to a running sum up to one): import random class SingleStateMarkov(object): def __init__(self, probabilities, initial=None):...
5
by: dave | last post by:
Hi Guys, I've written a Markov analysis program and would like to get your comments on the code As it stands now the final input comes out as a tuple, then list, then tuple. Something like...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.