Questions tagged [markov-chain]

A stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.

3
votes
2answers
78 views

Simulation of an alien population

Background I've come across a puzzle (Problem 10 from this list of sample interview questions): One day, an alien comes to Earth. Every day, each alien does one of four things, each with equal ...
17
votes
1answer
302 views

Solve the phase state between two haplotype blocks using markov transition probabilities

I have spent about more than a year in python, but I come from biology background. I should say I have got some understanding of for-loop and nested-for-loop to workout the solution to the problem I ...
1
vote
0answers
612 views

NodeJS Random sentence generator using Markov chain

Program generate sentences using Markov model and 3 text files Text file example: Antoine de Saint-Exupery, who was a French author, journalist and pilot wrote The Little Prince in 1943, one ...
5
votes
1answer
133 views

N state probability in an M/M/2 queue

I'm no ace when it comes to mathematical problems, so I've decided to go over some old college coursework and put it to code. The function works just fine and the returned values are spot on, but I'm ...
5
votes
1answer
2k views

Hidden Markov Model with Viterbi

I have a Hidden Markov model class with basically a single method: getting the best parse of a sequence of input tokens based on Viterbi. While I have no hardcore benchmarks, I'd love some pointers ...
6
votes
1answer
106 views

Mark V. Shaney: a script to produce gibberish

What follows in an attempt at implementing Mark V. Shaney using contemporary Python. One question has already been asked while working on a generator in the code, but included here is the entire ...
32
votes
2answers
4k views

Markov country name generator

I wrote a country name generator in Python 3.5. My goal was to get randomized names that would look as much like real-world names as possible. Each name needed to have a noun and an adjective form (e....
4
votes
1answer
82 views

Picking a random state from a set based on probabilities

I'm writing a Markov Chain implementation, and need to be able to pick a random state from a set of states, where each state has a different probability of being chosen. In my caffeine-high, I wrote ...
2
votes
0answers
86 views

Getting the math right for a Hidden Markov Model in Java

In an effort to learn and use hidden markov models, I am writing my own code to implement them. I am using this wiki article to help with my work. I do not wish to resort to pre-written libraries, ...
7
votes
4answers
1k views

Viterbi algorithm implementation in C

This is an implementation of the viterbi algorithm in C, following from Durbin et. al.'s book Biological Sequence Analysis (2002). There's more info in the heading about usage and what exactle the ...
0
votes
1answer
2k views

Generating text from a Markov chain in Java

I have this small program that constructs a Markov chain from Tolstoy's War and Peace and allows the user to play with it by generating sentences of variable length in words. MarkovChain.java ...
4
votes
1answer
375 views

Sentence generation using Markov Chains

I have written an implementation for sentence generation using Markov Chains. Would be great if you could review it. ...
2
votes
0answers
43 views

MCMC Metropolis Hastings for German Tank Puzzle

I have implemented the following MCMC algorithm for the german tank puzzle found here I just want to make sure everything is legit and that I am not getting the right answer by chance. ...
6
votes
2answers
379 views

Vanilla Markov chain in 18 lines

I am looking for advice on how I can improve this code. The objective is to make a vanilla Markov Chain text generator in the most concise way. I'm looking for advice on style, naming, 'elegance', and ...
5
votes
1answer
4k views

Markov Chain in Python

For learning purposes, I'm trying to implement a Markov Chain from scratch in Python. The goal is, provided a file with a list of words, and some sequence, to predict the next letter according the ...
4
votes
1answer
738 views

Generic Template Markov Chain

This is a simple real state based markov chain (I'm using real states instead of a markov matrix to enable making an animated version later). My goal was to make the markov chain as generic and ...
14
votes
2answers
2k views

Song lyric generator using Markov Chains - Python

I have written a pop song generator which uses the Markovify library to produce lyrics based on (just for testing purposes) songs by Avril Lavigne. In order to make the generator a bit more ...
1
vote
1answer
740 views

Entity resolution with NLTK

I am trying to write a script of Python code, for entity extraction and resolution. The excerpts of the algorithm: It is trying to extract the entity as PoS Tag with Hidden Markov Model(HMM). After ...
1
vote
0answers
96 views

Estimate Hidden Markov Model with both continuous and discrete observations, possible missing data

My code estimates a Hidden Markov Model (HMM) using the expectations-maximization (EM) algorithm. I followed https://www.princeton.edu/~rvan/orf557/hmm080728.pdf with modifications to allow for panel ...
3
votes
1answer
457 views

Cumulative transition matrix Markov Chain simulation

I have a cumulative transition matrix with probabilities for all the possible states from 1 to 5. Now the algorithm for simulating future states is following: the initial state is selected randomly, ...
5
votes
1answer
559 views

Markov chain text generation in Python

I'm willing to listen to any advice you have for improving it. ...
4
votes
3answers
1k views

Implementation of a sparse Markov Chain

I need to create a sparse Markov chain. It is supposed to receive text, so the number of rows or columns can easily go up to 20000. Besides, if I want to consider higher orders of the Markov chain (...
1
vote
0answers
334 views

Markov chain chatbot producing poor results

In my high school AP computer science class we're making a very basic chatbot that replies with predefined answers. I decided to have a bit more fun with it My program is basically this answer on ...
13
votes
2answers
700 views

Speeding up Python depth-first search in large graph

I'm building a Markov text poetry generator. The main method, which is attached below, performs a depth-first search through the Markov chain, which is implemented as a NetworkX digraph of Word ...
4
votes
1answer
455 views

Markov chain-based word salad generator

I like Markov chains. Last time I used one, I made one that generates words. This time, I made one that generates sentences, given a set of words and valid connections. This time, it's not weighted ...
15
votes
1answer
205 views

Name/word generator using DTMC in Ruby

I just wrote a basic DTMC algorithm focused on generating names, though it could be used to generate lots of other things. It's designed to be run from the command line, so input is taken from a file, ...
5
votes
1answer
572 views

Markov chain-based random text generator in Perl

This is the first thing I've written in Perl besides one-liners. It just generates random text based on a text file. I was inspired by this. Any tips on making this better are welcome. I'd especially ...
3
votes
2answers
308 views

Markov Chain generator

I'm not sure if a Markov Chain generator is the proper term for this, really all it does is create the chain, it doesn't generate any text from it. The code is below, and I'd appreciate any feedback: ...
7
votes
1answer
924 views

Optimizing variable order Markov Chain Implementation

I've created a variable order Markov chain built on top of a tree, but I can't train on datasets >1MB worth of text without running out of memory. I'm sure the tree can be replaced by something else ...
4
votes
2answers
1k views

Haskell markov text generator

I'm new to Haskell, and here is my first not-totally-trivial program. It's the first program I tend to write in any language -- a Markov text generator. I'm wondering what I can change to make it more ...
11
votes
1answer
13k views

Implementation of a Markov Chain

I read about how markov-chains were handy at creating text-generators and wanted to give it a try in python. I'm not sure if this is the proper way to make a markov-chain. I've left comments in ...
3
votes
2answers
3k views

Small Markov chain Monte Carlo implementation

I've written a small markov chain monte carlo function that takes samples from a posterior distribution, based on a prior and a binomial (Bin(N, Z)) distribution. I'd be happy to have it reviewed, ...