• About Markov chains in mathematics and more..

    From Wisdom90@21:1/5 to All on Tue Mar 31 15:01:17 2020

    Read this:

    About Markov chains in mathematics and more..

    In mathematics, many Markov chains automatically find their own way to
    an equilibrium distribution as the chain wanders through time. This
    happens for many Markov chains, but not all. I will talk about the
    conditions required for the chain to find its way to an equilibrium distribution.

    If in mathematics we give a Markov chain on a finite state space and
    asks if it converges to an equilibrium distribution as t goes to
    infinity. An equilibrium distribution will always exist for a finite
    state space. But you need to check whether the chain is irreducible and aperiodic. If so, it will converge to equilibrium. If the chain is
    irreducible but periodic, it cannot converge to an equilibrium
    distribution that is independent of start state. If the chain is
    reducible, it may or may not converge.

    So i will give an example:

    Suppose that for the course you are currently taking there are two
    volumes on the market and represent them by A and B. Suppose further
    that the probability that a teacher using volume A keeps the same volume
    next year is 0.4 and the probability that it will change for volume B
    is 0.6. Furthermore the probability that a professor using B this
    year changes to next year for A is 0.2 and the probability that it
    again uses volume B is 0.8. We notice that the matrix of transition is:

    0.4 0.6

    0.2 0.8

    The interesting question for any businessman is whether his
    market share will stabilize over time. In other words, does it exist
    a probability vector (t1, t2) such that:

    (t1, t2) * (transition matrix above) = (t1, t2) [1]

    So notice that the transition matrix above is ​​irreducible and aperiodic, so it will converge to an equilibrum distribution that is (t1, t2) that
    i will mathematically find, so the system of equations of [1] above is:

    0.4 * t1 + 0.2 * t2 = t1
    0.6 * t1 + 0.8 * t2 = t2

    this gives:

    -0.6 * t1 + 0.2 * t2 = 0
    0.6 * t1 - 0.2 * t2 = 0

    But we know that (t1, t2) is a vector of probability, so we have:

    t1 + t2 = 1

    So we have to solve the following system of equations:

    t1 + t2 = 1
    0.6 * t1 - 0.2 * t2 = 0

    So i have just solved it with R, and this gives the vector:


    Which means that in the long term, volume A will grab 25% of the market
    while volume B will grab 75% of the market unless the advertising
    campaign does change the probabilities of transition.

    So notice that in my previous post i have talked about invariants of the system, here is my previous post read it carefully:

    About Turing completeness and parallel programming..

    You have to know that a Turing-complete system can be proven
    mathematically to be capable of performing any possible calculation or
    computer program.

    So now you are understanding what is the power of "expressiveness" that
    is Turing-complete.

    For example i am working with the Tool that is called "Tina"(read about
    it below), it is a powerful tool that permits to work on Petri nets and
    be able to know about the boundedness and liveness of Petri nets, for
    example Tina supports Timed Petri nets that are Turing-complete , so the
    power of there expressiveness is Turing-complete, but i think this level
    of expressiveness is good for parallel programming and such, but
    it is not an efficient high level expressiveness. But still Petri nets
    are good for parallel programming.

    Read the rest of my previous thoughts to know more:

    About deadlocks and race conditions in parallel programming..

    I have just read the following paper:

    Deadlock Avoidance in Parallel Programs with Futures


    So as you are noticing you can have deadlocks in parallel programming
    by introducing circular dependencies among tasks waiting on future
    values or you can have deadlocks by introducing circular dependencies
    among tasks waiting on windows event objects or such synchronisation
    objects, so you have to have a general tool that detects deadlocks, but
    if you are noticing that the tool called Valgrind for C++ can detect
    deadlocks only happening from Pthread locks , read the following to
    notice it:


    So this is not good, so you have to have a general way that permits
    to detect deadlocks on locks , mutexes, and deadlocks from introducing
    circular dependencies among tasks waiting on future values or deadlocks
    you may have deadlocks by introducing circular dependencies among tasks
    waiting on windows event objects or such synchronisation objects etc.
    this is why i have talked before about this general way that detects
    deadlocks, and here it is, read about it in my following thoughts:

    Yet more precision about the invariants of a system..

    I was just thinking about Petri nets , and i have studied more Petri
    nets, they are useful for parallel programming, and what i have noticed
    by studying them, is that there is two methods to prove that there is no deadlock in the system, there is the structural analysis with place
    invariants that you have to mathematically find, or you can use the reachability tree, but we have to notice that the structural analysis of
    Petri nets learns you more, because it permits you to prove that there
    is no deadlock in the system, and the place invariants are
    mathematically calculated by the following system of the given
    Petri net:

    Transpose(vector) * Incidence matrix = 0

    So you apply the Gaussian Elimination or the Farkas algorithm to the
    incidence matrix to find the Place invariants, and as you will notice
    those place invariants calculations of the Petri nets look like Markov
    chains in mathematics, with there vector of probabilities and there
    transition matrix of probabilities, and you can, using Markov chains mathematically calculate where the vector of probabilities
    will "stabilize", and it gives you a very important information, and you
    can do it by solving the following mathematical system:

    Unknown vector1 of probabilities * transition matrix of probabilities =
    Unknown vector1 of probabilities.

    Solving this system of equations is very important in economics and
    other fields, and you can notice that it is like calculating the
    invariants , because the invariant in the system above is the vector1 of probabilities that is obtained, and this invariant, like in the
    invariants of the structural analysis of Petri nets, gives
    you a very important information about the system, like where market
    shares will stabilize that is calculated this way in economics. About reachability analysis of a Petri net.. As you have noticed in my Petri
    nets tutorial example (read below), i am analysing the liveness of the
    Petri net, because there is a rule that says:

    If a Petri net is live, that means that it is deadlock-free.

    Because reachability analysis of a Petri net with Tina gives you the
    necessary information about boundedness and liveness of the Petri net.
    So if it gives you that the Petri net is "live" , so there is no
    deadlock in it.

    Tina and Partial order reduction techniques..

    With the advancement of computer technology, highly concurrent systems
    are being developed. The verification of such systems is a challenging
    task, as their state space grows exponentially with the number of

    Partial order reduction is an effective technique to address this
    problem. It relies on the observation that the effect of executing
    transitions concurrently is often independent of their ordering.

    Tina is using “partial-order” reduction techniques aimed at preventing combinatorial explosion, read more here to notice it:


    About modelizations and detection of race conditions and deadlocks in
    parallel programming..

    I have just taken further a look at the following project in Delphi
    called DelphiConcurrent by an engineer called Moualek Adlene from France:


    And i have just taken a look at the following webpage of Dr Dobb's journal:

    Detecting Deadlocks in C++ Using a Locks Monitor


    And i think that both of them are using technics that are not as good as analysing deadlocks with Petri Nets in parallel applications , for
    example the above two methods are only addressing locks or mutexes or reader-writer locks , but they are not addressing semaphores or event
    objects and such other synchronization objects, so they are not good,
    this is why i have written a tutorial that shows my methodology of
    analysing and detecting deadlocks in parallel applications with Petri
    Nets, my methodology is more sophisticated because it is a
    generalization and it modelizes with Petri Nets the broader
    range of synchronization objects, and in my tutorial i will add soon
    other synchronization objects, you have to look at it, here it is:


    You have to get the powerful Tina software to run my Petri Net examples
    inside my tutorial, here is the powerful Tina software:


    Also to detect race conditions in parallel programming you have to take
    a look at the following new tutorial that uses the powerful Spin tool:


    Here is how to install Spin Model Checker on windows:

    I invite you to look at this video to learn how to install Spin model
    checker and iSpin:


    I have installed them and configured them correctly and i am working
    with them in parallel programming to detect race conditions etc.

    This is how you will get much more professional at detecting deadlocks
    and race conditions in parallel programming.

    Thank you,
    Amine Moulay Ramdane.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)