I just read a blog post here at MSU about The Infinite Jukebox, a web tool that will analyze a song (either one you upload or one from their library) and map out links between segments of the song that have approximately the same beat. You then see a visualization of the song as a loop, with the links (arcs) added, forming a directed graph. (The visualization does not display arcs as arrows, though, just as, well, arcs.)
When you replay the song in The Infinite Jukebox, as it passes the tail node of each arc, it randomly chooses whether to keep going on the original path or cross the arc and continue playing, along the original path, from the head node. Thus the "infinite" part of the site's name -- the song will continue until you stop it.
I don't know the algorithm they use for playback, but it appears superficially to be a Markov process, so perhaps this really is a random walk over the song's graph.
If you want to try it out, I can recommend The Trashmen's version of "Surfin' Bird", which I was happy to discover is in the site's library. The randomly looped version sounds suspiciously like the original (which is what I expected). Although the visualization of the progress through the song is interesting, for the full multimedia experience you'll want to have the You Tube video playing (muted) on a second screen.
Sadly, their library does not include "Papa-Oom-Mow-Mow" by The Rivingtons, and I don't happen to own a copy, so I could not compare the action of The Infinite Jukebox on that with what it did to "Surfin' Bird". As I listened to the looped "Surfin' Bird", though, I couldn't help but think "and thus another enhanced interrogation technique is born".
Showing posts with label Markov chains. Show all posts
Showing posts with label Markov chains. Show all posts
Thursday, August 28, 2014
Saturday, June 30, 2012
The White Knight Returns
Back in May, on his excellent blog The Endeavor, John D. Cook posed (and subsequently answered) the following problem: if a knight begins in one corner of an empty chessboard and moves randomly, each time choosing uniformly over the available moves from its current position, what is the mean number of moves until it returns to the corner from which it started?
Several people posed exact or approximate answers in the comments. The approximate answers were based on simulation. The most elegant solution among the comments, posted by 'deinst', modeled the problem as a reversible Markov chain on a graph. John Cook's answer used a rather powerful theorem about a random walk on a graph, which I think boils down to the same logic used by 'deinst'. (Cook also includes Python code for a simulation.)
When I read the problem, my first reaction was also to model it as a Markov chain, but sadly I've forgotten most of what I knew about MC's, including the concept of reversibility. I did, at least, recall the essentials of first passage time. The question reduces to computing the expected first passage time from the corner square to itself. The Wikipedia link for first passage times is not entirely helpful, as it is not specific to Markov chains, but the concept is easy to explain. Let the corner in which the knight starts be position $s$, and let $\mu_j$ denote the expected number of moves required until the knight first returns to position $s$, given that it is currently at position $j$ (i.e., the expected first passage time from $j$ to $s$). The answer to the puzzle is $\mu_s$, the expected first passage time from $s$ to itself. Further, let $M_j$ denote the set of positions that the knight can reach in one move, given that it is currently at position $j$. Letting $p_{jk}$ denote the probability that a knight at position $j$ next moves to position $k$, the first passage times $\mu_\cdot$ satisfy the following system of linear equations:\[ \mu_{j}=1+\sum_{k\in M_{j}\backslash\{s\}}p_{jk}\mu_{k}\quad\forall j. \] In our case, $p_{jk} = 1/|M_j|$ if $k\in M_j$ and 0 otherwise. The solution to this system has $\mu_s=168$ (matching the answers of John Cook and deinst).
Other than a quick refresher on Markov chains, my main interest in this was that I'm teaching myself Python while also trying to get a handle on using Sage. So I wrote a Sage notebook to set up and solve the first passage time equations. Here is the content of that notebook, in case anyone is curious. (Please bear in mind I'm new to Python.)
One last note: I had originally intended to give the post a Christian Bale buzz by titling it "The Dark Night Returns". Turns out DC Comics beat me to that title. Oh, well.
Several people posed exact or approximate answers in the comments. The approximate answers were based on simulation. The most elegant solution among the comments, posted by 'deinst', modeled the problem as a reversible Markov chain on a graph. John Cook's answer used a rather powerful theorem about a random walk on a graph, which I think boils down to the same logic used by 'deinst'. (Cook also includes Python code for a simulation.)
When I read the problem, my first reaction was also to model it as a Markov chain, but sadly I've forgotten most of what I knew about MC's, including the concept of reversibility. I did, at least, recall the essentials of first passage time. The question reduces to computing the expected first passage time from the corner square to itself. The Wikipedia link for first passage times is not entirely helpful, as it is not specific to Markov chains, but the concept is easy to explain. Let the corner in which the knight starts be position $s$, and let $\mu_j$ denote the expected number of moves required until the knight first returns to position $s$, given that it is currently at position $j$ (i.e., the expected first passage time from $j$ to $s$). The answer to the puzzle is $\mu_s$, the expected first passage time from $s$ to itself. Further, let $M_j$ denote the set of positions that the knight can reach in one move, given that it is currently at position $j$. Letting $p_{jk}$ denote the probability that a knight at position $j$ next moves to position $k$, the first passage times $\mu_\cdot$ satisfy the following system of linear equations:\[ \mu_{j}=1+\sum_{k\in M_{j}\backslash\{s\}}p_{jk}\mu_{k}\quad\forall j. \] In our case, $p_{jk} = 1/|M_j|$ if $k\in M_j$ and 0 otherwise. The solution to this system has $\mu_s=168$ (matching the answers of John Cook and deinst).
Other than a quick refresher on Markov chains, my main interest in this was that I'm teaching myself Python while also trying to get a handle on using Sage. So I wrote a Sage notebook to set up and solve the first passage time equations. Here is the content of that notebook, in case anyone is curious. (Please bear in mind I'm new to Python.)
Define the board
board = [(i, j) for i in range(8) for j in range(8)]
Assign a variable for the expected first passage time (to the lower left corner) from each square of the board
vlist = {b : var('r_' + str(b[0]) + '_' + str(b[1])) for b in board}
List the eight moves a knight can make
moves = [(i, j) for i in [-2, -1, 1, 2] for j in [-2, -1, 1, 2] if abs(i) + abs(j) == 3]
Define a function that takes a position and move and returns the new position if the move is legal, None otherwise
def move(position, change):
if (position in board) and (change in moves):
landing = (position[0] + change[0], position[1] + change[1])
return landing if landing in board else None
else:
return None
Compute all legal moves from each board position
legal = {p : [move(p, m) for m in moves if not(move(p, m) is None)] for p in board}
Set up the first passage time equations
eqns = [vlist[b] == 1.0 + (1.0/len(legal[b]))*sum([vlist[x] for x in legal[b] if x != (0, 0)]) for b in board]
Solve the equations
sols = solve(eqns, vlist.values(), solution_dict = True)
Verify that the solution is unique
len(sols) == 1
True
Find the mean first passage time from position (0,0) to itself
sols[0][vlist[(0,0)]]
168
One last note: I had originally intended to give the post a Christian Bale buzz by titling it "The Dark Night Returns". Turns out DC Comics beat me to that title. Oh, well.
Subscribe to:
Posts (Atom)