Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Markov Chain Monte Carlo Without All the Bullshit (2015)

jeremykun.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#41

Post by JohnKemeny »

seanhunter wrote: post #37
JohnKemeny wrote: post #35

Earlier quoted context omitted.

A random walk on a graph is a stochastic process that starts at a vertex and, at each step, moves to a randomly chosen neighboring vertex. Formally: Given a graph, a random walk is a sequence of vertices [v1, v2, ..., vk] such that each v{i+1} is selected uniformly at random from the neighbors of vi. In weighted graphs, the next vertex is chosen with probability proportional to edge weights.

I’m pretty sure it’s not a requirement that the distribution is uniform and also not path-dependent as per the example I gave - a random walk where you’re not allowed to visit a node more than once.

Here's a reference for the definition I'm using:

https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf

It's from lecture notes (pdf) from a course in Spectral Graph Theory by Professor Daniel Spielman at Yale.

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#42

Post by whatever1 »

jvanderbot wrote: post #40
seanhunter wrote: post #8

Hmm. I'm not an expert, but some of this seems definitely not to be accurate. Some of the "Bullshit" turns out perhaps to be quite important. Take the statement: > Markov Chain is essentially a fancy name for a random walk on a graph Is that really true? I definitely don't think so. To my understanding, a Markov process is a stochastic process that has the additional (aka "Markov") property that it is "memoryless". T…

Markov property is about state, yes, but can't you expand state to accommodate your non Markov example? As in, the state you track is no longer the probability that you have ended at a given node at time T, but instead includes a new vector of the probability you have visited the node at any time in the past (which can be obtained from PDF of location from previous time step + stochastic "diffusion"). So, we're rando…

This is very typical in reinforcement learning. You just expand the state to include some more time periods. It definitely raises some academic eyebrows (since it’s not technically memory less), but hey if it works, it works

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#43

Post by jvanderbot »

whatever1 wrote: post #42
jvanderbot wrote: post #40

Earlier quoted context omitted.

Markov property is about state, yes, but can't you expand state to accommodate your non Markov example? As in, the state you track is no longer the probability that you have ended at a given node at time T, but instead includes a new vector of the probability you have visited the node at any time in the past (which can be obtained from PDF of location from previous time step + stochastic "diffusion"). So, we're rando…

This is very typical in reinforcement learning. You just expand the state to include some more time periods. It definitely raises some academic eyebrows (since it’s not technically memory less), but hey if it works, it works

It is memoryless just in a different state space.

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#44

Post by fidotron »

There is definite truth to the idea stats people have a habit of writing deliberately impenetrable prose. (Probably due to proximity to economists and political scientists).

I happened to need to implement a markov chain for playing rock, paper, scissors in https://luduxia.com/showdown - once you actually understand it the code is short and took no more than 20 minutes to write, and was by far the easiest part of the entire effort, which was surprising. Vertically centering a div is harder, and involves dealing with even more jargon.

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#45

Post by seanhunter »

JohnKemeny wrote: post #41
seanhunter wrote: post #37

Earlier quoted context omitted.

I’m pretty sure it’s not a requirement that the distribution is uniform and also not path-dependent as per the example I gave - a random walk where you’re not allowed to visit a node more than once.

Here's a reference for the definition I'm using: https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf It's from lecture notes (pdf) from a course in Spectral Graph Theory by Professor Daniel Spielman at Yale.

Those notes look interesting thanks. I’ve really never heard of someone saying you have to have uniform probability for a random walk on a graph. In fact the context where I’m most familiar with them (lattice/grid pricers) it’s always specified something like “the probability of branch a is p and b is 1-p” (ie explicitly not uniform) and they aren’t a weighted graph in the normal sense.

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#46

Post by srean »

seanhunter wrote: post #45
JohnKemeny wrote: post #41

Earlier quoted context omitted.

Here's a reference for the definition I'm using: https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf It's from lecture notes (pdf) from a course in Spectral Graph Theory by Professor Daniel Spielman at Yale.

Those notes look interesting thanks. I’ve really never heard of someone saying you have to have uniform probability for a random walk on a graph. In fact the context where I’m most familiar with them (lattice/grid pricers) it’s always specified something like “the probability of branch a is p and b is 1-p” (ie explicitly not uniform) and they aren’t a weighted graph in the normal sense.

It doesn't have to be uniform or memory less.

However, in general when people mention random walks without further qualifications they are usually talking about the uniform and memoryless case.

That vanilla case can be generalized extensively, on kinds of state spaces, kinds of index sets, kinds of dependence and so on.

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#47

Post by whatever1 »

jvanderbot wrote: post #43
whatever1 wrote: post #42

Earlier quoted context omitted.

This is very typical in reinforcement learning. You just expand the state to include some more time periods. It definitely raises some academic eyebrows (since it’s not technically memory less), but hey if it works, it works

It is memoryless just in a different state space.

In the state space that includes all of the time periods, with infinitesimal granularity since the birth of the universe.

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#48

Post by Scea91 »

or_am_i wrote: post #32

> The “bullshit” here is the implicit claim of an author that such jargon is needed. Maybe it is to explain advanced applications (like attempts to do “inference in Bayesian networks”), but it is certainly not needed to define or analyze the basic ideas. "The bullshit here is the implicit claim of an author that German language is needed. Maybe it is for advanced applications (like Goethe's poetry), but it is certain…

Yes, its pretty simple. Different audiences prefer different style. Experts prefer brevity and jargon, they don't need explanations of concepts they already understand. Beginners prefer less jargon and inline explanations as they'd need to hunt for references otherwise to understand the text.

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#49

Post by MichaelDickens »

zero_k wrote: post #29

Science communication is so important. I write scientific papers and I always write a blog post about the paper later, because nobody understands the scientific paper -- not even the scientists. The scientists regularly read my blog instead. The "scientific style" has become so obtuse and useless that even the professionals read the blog instead. True insanity.

What would happen if you wrote the paper like a blog post and submitted it to journals? (With some structural changes to meet journal requirements, like having an abstract)

Re: Markov Chain Monte Carlo Without All the Bullshit (2015)

#50

Post by conjectures »

Common pattern where a bright spark asks, 'why you all so complicated?' Proceeds to assume we're dealing with a finite graph / set.

All the complication is needed to handle the fact that the state can be a random vector of real numbers in a possibly varying dimensional space. It's not jerking off on jargon for its own sake.

Sure, there are simple cases - doesn't make the general case 'bullshit'.

Post reply on HN