Hi! Thank you very much for your comments!
Yes, i believe that the algorithms that i was going to implement from Graph’s theory are going to be very useful to the Stochastic processes. The NetworkX package does not support symbolic expressions and so implementation of some functions from Graph theory, mainly directed graphs, would be really useful (for example, in the case that the transient matrix of a Markov chain has symbolic expressions).
Moreover, the module I was suggesting will only have the functions that are going to be used by ‘’stats’’. If it’s still ok, I will give special care to make that really clear in my proposal. Any more suggestions will be really appreciated.
Thank you!
Is the graph theory part needed to implement the stats ideas. In
general, graph theory is out of scope for SymPy (see
https://github.com/sympy/sympy/wiki/GSoC-2020-Ideas#non-ideas). If
some graph theory algorithms are required to do symbolics, that is
fine, but you should make that clear in the proposal.
Aaron Meurer
On Wed, Mar 25, 2020 at 2:46 PM Basilis Kalos <kalosba...@gmail.com> wrote:
>
> Hello all!
>
> I'm sending you the first draft of my application. Any comments and sugestions will be greatly appreciated.
>
> Thank you!
>
> https://docs.google.com/document/d/1J2N4DhXXlFj_YQ-isqIwvl1zzIg-OaC87RLIGgHTbgY/edit?usp=sharing
>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sy...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6JggiydyeFp2OCgdsocncbBiM-6z-vz2zyNr3o%2BHaKVRA%40mail.gmail.com.
Hi all, thank you very much for your useful
comments!
The functionalities I was suggesting, are mainly intended to be implemented for the Markov chains modules in the stochastic processes package and they are:
For example, let’s say that we have a discrete Markov chain of finite space. We could use the first two functionalities described above to implement the central theorem of Markov chains. More specifically if we implement the first one and find the chain to be both aperiodic and irreducible, then we can be sure that the stable distribution exists. The code, as it is now implemented, it has already a function to find the stable distribution, but it does not always succeed. The advantage of the proposed solution is that it will offer a more concrete way to derive the existence of a stable distribution or in the case that the code cannot derive a solution, inform the user that it still exists.
Furthermore, as the algorithm is now, it calculates only the stable distribution of the whole chain. However, it might be the case that the chain is not irreducible and so a stable distribution for the whole chain can not exist. By implementing the second functionality described above, we could divide the chain in communication classes. Continuing we would be able to implement the central theorem to each one of this classes (as there by definition irreducible) and find a stable distribution for each one of this.
Let’s say for example that the chain consists from two communication classes: an open class T and closed class C. If we tried to find the limiting distribution of that chain by calculating the stable distribution, it may not exist. By dividing the chain into classes T and C and calculate the stable distributions of this classes, we could find the limiting distribution.
The third functionality can be very useful to calculate P(Eq(X(j), 2), Eq(X(1), 3)), for every j, as this is equal to the sum of the probability of all walks from the state 1 to the state j. Moreover, it could be used by the first to functionalities. For example, to find all states j that belong to the same class as i, we will have to find walks from the state i to the state j and from the state j to the state i.
Lastly, I’m not suggesting changing the API to define chains through graphs, but to make a module that will implement these functionalities to a Chain as is already defined by the current API. Moreover, if we define a chain with the matrix K = [[a, 1-a], [1-b, b]] where a and b are symbols, then the networkX package cannot work around it. By implementing the algorithms as described above, we could give us the advantage to work with transition probabilities that are defined by symbols.
These functionalities do not have to be a separate Graph module, but they can easily be a part of the current stochastic processes.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/f2d1a667-a7b8-421b-b7f5-fe8887b5ae73%40googlegroups.com.
--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sy...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6JggiydyeFp2OCgdsocncbBiM-6z-vz2zyNr3o%2BHaKVRA%40mail.gmail.com.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d4bc41f2-fcf2-4b8a-b7b2-5d66658fe126%40googlegroups.com.
Can you please provide some examples from other CAS(Wolfram, etc.) for the features which you plan to implement?
> If we tried to find the limiting distribution of that chain by calculating the stable distribution, it may not exist. By dividing the chain into classes T and C and calculate the stable distributions of this classes, we could find the limiting distribution.It would be better to understand if some examples are given where the current code fails.
> The third functionality can be very useful to calculate P(Eq(X(j), 2), Eq(X(1), 3)), for every j, as this is equal to the sum of the probability of all walks from the state 1 to the state j. Moreover, it could be used by the first to functionalities. For example, to find all states j that belong to the same class as i, we will have to find walks from the state i to the state j and from the state j to the state i.Any examples where the current code fails or is inefficient? Can you please provide a rough time complexity analysis of the algorithm you plan to implement and compare it with the current code?
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d4bc41f2-fcf2-4b8a-b7b2-5d66658fe126%40googlegroups.com.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d42e6bf4-4164-40c3-b1f0-1ed4e502d5d9%40googlegroups.com.
Thanks for pointing out. This is because the Markov Chain in the example is reducible and therefore it doesn't have a unique solution to sP = s. Have you described algorithms(a rough idea or any paper/document where such algorithms are given) in you proposal to find communication classes of reducible markov chains. Would it be possible to use Tarjan's algorithm or Kosuraja's algorithm for finding strongly connected components using the transition matrix(acting as adjacency matrix)?
> There are three phases for GSoC and a community bonding period at the start. Please plan work such that most of the coding part lies in those three phases. Currently, your proposal has plan for four phases, it is not clear which phase corresponds to community bonding. Also, more code(not necessarily clean and fully working) can be added in implementation parts.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d42e6bf4-4164-40c3-b1f0-1ed4e502d5d9%40googlegroups.com.