markov query

Discussion in 'Python' started by kpp9c, Mar 14, 2006.

  1. kpp9c

    kpp9c Guest

    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
    kpp9c, Mar 14, 2006
    #1
    1. Advertising

  2. Stefan Behnel, Mar 14, 2006
    #2
    1. Advertising

  3. 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 && && 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
    Erik Max Francis, Mar 14, 2006
    #3
  4. kpp9c

    kpp9c Guest

    > 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.
    kpp9c, Mar 15, 2006
    #4
  5. kpp9c

    kpp9c Guest

    >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--
    kpp9c, Mar 15, 2006
    #5
  6. kpp9c

    Robert Kern Guest

    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


    "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
    Robert Kern, Mar 15, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    7
    Views:
    539
  2. kpp9c
    Replies:
    8
    Views:
    305
    Max M
    Mar 16, 2006
  3. Replies:
    2
    Views:
    295
  4. Replies:
    0
    Views:
    104
  5. vsv
    Replies:
    1
    Views:
    111
    Dave Burt
    Apr 11, 2006
Loading...

Share This Page