COMP 200 Elements of Computer Science &
COMP 130 Elements of Algorithms and Computation
Spring 2012

Markov Chain Analysis of Chuck Berry's Johnny B. Goode

These lyrics generate the following chains and sample riffs.

1st-Order Markov Chains

The probabilities

The following assumes that we split the text into case-sensitive words and ignore whitespace and punctuation. The 1-word sequences are listed in alphabetical order.

{('the',): {'evergreens': 0.1111111111111111, 'shade': 0.1111111111111111, 'sun': 0.1111111111111111, 'drivers': 0.1111111111111111, 'trees': 0.1111111111111111, 'woods': 0.1111111111111111, 'rhythm': 0.1111111111111111, 'railroad': 0.1111111111111111, 'leader': 0.1111111111111111},
 ('where',): {'lives': 1.0},
 ('track',): {'.': 1.0},
 ('from',): {'miles': 1.0},
 ('will',): {'be': 1.0},
 ('to',): {'read': 0.16666666666666666, 'stop': 0.16666666666666666, 'hear': 0.16666666666666666, 'carry': 0.16666666666666666, 'New': 0.16666666666666666, 'the': 0.16666666666666666},
 ('go',): {'go': 0.5714285714285714, '!': 0.2857142857142857, ',': 0.07142857142857142, 'Johnny': 0.07142857142857142},
 ('but',): {'he': 1.0},
 ('someday',): {'you': 1.0},
 ('by',): {'the': 0.5, 'used': 0.5},
 ('he',): {'could': 0.5, 'never': 0.5},
 ('And',): {'you': 1.0},
 ('ever',): {'learned': 1.0},
 ('evergreens',): {',': 1.0},
 ('cabin',): {'made': 1.0},
 ('Maybe',): {'some': 1.0},
 ('write',): {'a': 1.0},
 ('Johnny',): {'go': 0.7058823529411765, 'B': 0.29411764705882354},
 ('sit',): {'beneath': 1.0},
 ('He',): {'used': 1.0},
 ('way',): {'back': 1.0},
 ('your',): {'music': 0.5, 'name': 0.5},
 ('his',): {'guitar': 0.6666666666666666, 'mama': 0.3333333333333333},
 ('that',): {'country': 0.5, 'the': 0.5},
 ('a-playing',): {'in': 1.0},
 ('!',): {'Go': 0.6666666666666666, 'He': 0.06666666666666667, 'Well': 0.06666666666666667, 'aah': 0.13333333333333333, 'Aah': 0.06666666666666667},
 ('in',): {'a': 0.2, 'light': 0.2, 'the': 0.4, 'Louisiana': 0.2},
 ('leader',): {'of': 1.0},
 ('like',): {'a-ringing': 1.0},
 ('till',): {'the': 1.0},
 ('stop',): {'and': 1.0},
 ('oh',): {'my': 1.0},
 ('wood',): {',': 1.0},
 ('so',): {'well': 1.0},
 ('saying',): {':': 1.0},
 ('play',): {'his': 0.3333333333333333, 'your': 0.3333333333333333, '.': 0.3333333333333333},
 ('him',): {':': 1.0},
 ('lives',): {'a': 1.0},
 ('tonight',): {'!': 1.0},
 ('a-ringing',): {'a': 1.0},
 ('well',): {',': 1.0},
 ('mama',): {'told': 1.0},
 ('.',): {'And': 0.08333333333333333, 'Oh': 0.08333333333333333, 'Many': 0.08333333333333333, 'People': 0.08333333333333333, 'Goode': 0.4166666666666667, 'Maybe': 0.08333333333333333, 'Go': 0.16666666666666666},
 ('you',): {'will': 0.6666666666666666, 'play': 0.3333333333333333},
 ('Oh',): {'sitting': 1.0},
 ('big',): {'old': 1.0},
 ('some',): {'day': 1.0},
 ('Aah',): {'Johnny': 1.0},
 ('sack',): {',': 1.0},
 ('and',): {'say': 0.3333333333333333, 'wood': 0.3333333333333333, 'a-playing': 0.3333333333333333},
 ('goes',): {'down': 1.0},
 ('clay',): {'and': 1.0},
 ('used',): {'to': 1.0},
 ('of',): {'a': 0.5, 'clay': 0.5},
 ('old',): {'band': 1.0},
 ('drivers',): {'made': 1.0},
 ('around',): {',': 1.0},
 ('guitar',): {'just': 0.5, 'in': 0.5},
 ('Go',): {'go': 0.25, 'Johnny': 0.75},
 ('woods',): {'among': 1.0},
 ('passing',): {'by': 1.0},
 ('boy',): {'named': 0.5, 'can': 0.5},
 ('my',): {',': 0.5, 'oh': 0.5},
 ('made',): {'of': 0.5, '.': 0.5},
 ('told',): {'him': 1.0},
 ('back',): {'up': 1.0},
 ('carry',): {'his': 1.0},
 ('book',): {'so': 1.0},
 ('trees',): {'by': 1.0},
 ('shade',): {',': 1.0},
 ('Louisiana',): {'close': 1.0},
 ('could',): {'play': 1.0},
 ('down',): {'down': 0.3333333333333333, 'in': 0.3333333333333333, '.': 0.3333333333333333},
 ('close',): {'to': 1.0},
 ('bell',): {'.': 1.0},
 ('say',): {':': 1.0},
 (',',): {'saying': 0.07692307692307693, 'drumming': 0.07692307692307693, 'sit': 0.07692307692307693, 'there': 0.07692307692307693, 'but': 0.07692307692307693, 'to': 0.07692307692307693, 'that': 0.07692307692307693, 'way': 0.07692307692307693, 'go': 0.23076923076923078, 'where': 0.07692307692307693, 'he': 0.07692307692307693},
 ('Deep',): {'down': 1.0},
 ('Goode',): {'!': 0.6, 'tonight': 0.2, ',': 0.2},
 ('young',): {'country': 1.0},
 ('can',): {'play': 1.0},
 ('rhythm',): {'that': 1.0},
 ('be',): {'a': 0.3333333333333333, 'the': 0.3333333333333333, 'in': 0.3333333333333333},
 ('B',): {'.': 1.0},
 ('name',): {'will': 1.0},
 ('sitting',): {'and': 1.0},
 ('aah',): {'Johnny': 1.0},
 ('hear',): {'you': 1.0},
 ('beneath',): {'the': 1.0},
 (':',): {'someday': 0.3333333333333333, 'my': 0.3333333333333333, 'Johnny': 0.3333333333333333},
 ('read',): {'or': 1.0},
 ('drumming',): {'to': 1.0},
 ('People',): {'passing': 1.0},
 ('country',): {'boy': 0.6666666666666666, 'cabin': 0.3333333333333333},
 ('Well',): {'his': 1.0},
 ('Orleans',): {',': 1.0},
 ('sun',): {'goes': 1.0},
 ('man',): {'.': 1.0},
 ('gunny',): {'sack': 1.0},
 ('there',): {'stand': 1.0},
 ('band',): {'.': 1.0},
 ('people',): {'coming': 1.0},
 ('learned',): {'to': 1.0},
 ('a',): {'bell': 0.14285714285714285, 'country': 0.14285714285714285, 'young': 0.14285714285714285, 'gunny': 0.14285714285714285, 'book': 0.14285714285714285, 'big': 0.14285714285714285, 'man': 0.14285714285714285},
 ('coming',): {'from': 1.0},
 ('or',): {'write': 1.0},
 ('up',): {'in': 1.0},
 ('Many',): {'people': 1.0},
 ('never',): {'ever': 1.0},
 ('miles',): {'around': 1.0},
 ('New',): {'Orleans': 1.0},
 ('music',): {'till': 1.0},
 ('railroad',): {'track': 1.0},
 ('stand',): {'a': 1.0},
 ('among',): {'the': 1.0},
 ('named',): {'Johnny': 1.0},
 ('light',): {',': 1.0},
 ('just',): {'like': 1.0},
 ('day',): {'your': 1.0}}

Sample riffs

"tonight ! Go Johnny go go ! Go go go go go Johnny go ! Go Johnny go Johnny B . And you will be a book so well , saying : Johnny B . Maybe some day your name will be a gunny sack , go go ! Go Johnny B . Go Johnny B . Go go go go ! Go go go ! aah Johnny go go ! Go Johnny go go Johnny go ! Go go go Johnny B . Goode ! Go Johnny B . People passing by the shade , sit beneath the trees"

"but he never ever learned to stop and a-playing in a gunny sack , he never ever learned to stop and a-playing in the railroad track . Go Johnny go Johnny go go go go ! Well his guitar in the rhythm that country cabin made of a bell . Go Johnny go , saying : my , to the shade , he could play his guitar in the shade , go ! Go Johnny go go , go go ! Go Johnny B . Goode tonight ! Go Johnny go go ! aah Johnny go go go go ,"

2nd-Order Markov Chain

The probabilities

{('made', '.'): {'People': 1.0},
 ('beneath', 'the'): {'trees': 1.0},
 ('Goode', '!'): {'Well': 0.5, 'He': 0.5},
 ('Go', 'Johnny'): {'go': 1.0},
 ('sun', 'goes'): {'down': 1.0},
 (',', 'where'): {'lives': 1.0},
 ('down', '.'): {'Maybe': 1.0},
 ('a', 'big'): {'old': 1.0},
 ('music', 'till'): {'the': 1.0},
 ('your', 'name'): {'will': 1.0},
 ('country', 'boy'): {'named': 0.5, 'can': 0.5},
 ('the', 'trees'): {'by': 1.0},
 ('and', 'a-playing'): {'in': 1.0},
 ('day', 'your'): {'name': 1.0},
 ('stop', 'and'): {'say': 1.0},
 ('the', 'shade'): {',': 1.0},
 ('.', 'And'): {'you': 1.0},
 ('railroad', 'track'): {'.': 1.0},
 ('Go', 'go'): {',': 1.0},
 ('young', 'country'): {'boy': 1.0},
 (':', 'my'): {'oh': 1.0},
 (',', 'there'): {'stand': 1.0},
 ('up', 'in'): {'the': 1.0},
 ('Deep', 'down'): {'in': 1.0},
 ('stand', 'a'): {'country': 1.0},
 ('and', 'wood'): {',': 1.0},
 ('clay', 'and'): {'wood': 1.0},
 ('goes', 'down'): {'.': 1.0},
 ('in', 'light'): {',': 1.0},
 ('Johnny', 'B'): {'.': 1.0},
 ('go', 'go'): {'go': 0.5, '!': 0.5},
 ('guitar', 'in'): {'a': 1.0},
 ('big', 'old'): {'band': 1.0},
 ('.', 'Maybe'): {'some': 1.0},
 ('drivers', 'made'): {'.': 1.0},
 ('the', 'railroad'): {'track': 1.0},
 ('like', 'a-ringing'): {'a': 1.0},
 ('man', '.'): {'And': 1.0},
 ('Johnny', 'go'): {'go': 1.0},
 ('learned', 'to'): {'read': 1.0},
 ('the', 'drivers'): {'made': 1.0},
 ('till', 'the'): {'sun': 1.0},
 ('band', '.'): {'Many': 1.0},
 ('just', 'like'): {'a-ringing': 1.0},
 ('Many', 'people'): {'coming': 1.0},
 ('a', 'man'): {'.': 1.0},
 ('be', 'in'): {'light': 1.0},
 ('leader', 'of'): {'a': 1.0},
 ('Oh', 'sitting'): {'and': 1.0},
 ('play', '.'): {'Go': 1.0},
 ('New', 'Orleans'): {',': 1.0},
 ('you', 'will'): {'be': 1.0},
 ('book', 'so'): {'well': 1.0},
 ('of', 'a'): {'big': 1.0},
 ('name', 'will'): {'be': 1.0},
 ('the', 'leader'): {'of': 1.0},
 ('evergreens', ','): {'there': 1.0},
 ('country', 'cabin'): {'made': 1.0},
 ('his', 'guitar'): {'just': 0.5, 'in': 0.5},
 ('a-ringing', 'a'): {'bell': 1.0},
 ('he', 'could'): {'play': 1.0},
 ('that', 'country'): {'boy': 1.0},
 ('play', 'your'): {'music': 1.0},
 ('a-playing', 'in'): {'the': 1.0},
 ('your', 'music'): {'till': 1.0},
 ('.', 'Goode'): {'!': 0.6, 'tonight': 0.2, ',': 0.2},
 ('!', 'Aah'): {'Johnny': 1.0},
 ('the', 'evergreens'): {',': 1.0},
 ('aah', 'Johnny'): {'B': 1.0},
 ('to', 'carry'): {'his': 1.0},
 ('so', 'well'): {',': 1.0},
 ('.', 'People'): {'passing': 1.0},
 ('ever', 'learned'): {'to': 1.0},
 (',', 'he'): {'never': 1.0},
 ('the', 'woods'): {'among': 1.0},
 ('coming', 'from'): {'miles': 1.0},
 ('to', 'read'): {'or': 1.0},
 ('People', 'passing'): {'by': 1.0},
 (',', 'go'): {'Johnny': 1.0},
 ('be', 'the'): {'leader': 1.0},
 ('never', 'ever'): {'learned': 1.0},
 ('in', 'in'): {'Louisiana': 1.0},
 ('a', 'bell'): {'.': 1.0},
 ('of', 'clay'): {'and': 1.0},
 ('Aah', 'Johnny'): {'B': 1.0},
 ('where', 'lives'): {'a': 1.0},
 ('to', 'the'): {'rhythm': 1.0},
 ('in', 'a'): {'gunny': 1.0},
 ('people', 'coming'): {'from': 1.0},
 (',', 'way'): {'back': 1.0},
 ('bell', '.'): {'Go': 1.0},
 ('cabin', 'made'): {'of': 1.0},
 ('can', 'play'): {'.': 1.0},
 ('wood', ','): {'where': 1.0},
 ('say', ':'): {'my': 1.0},
 (':', 'Johnny'): {'B': 1.0},
 ('will', 'be'): {'a': 0.3333333333333333, 'the': 0.3333333333333333, 'in': 0.3333333333333333},
 ('made', 'of'): {'clay': 1.0},
 ('some', 'day'): {'your': 1.0},
 ('my', 'oh'): {'my': 1.0},
 ('drumming', 'to'): {'the': 1.0},
 ('light', ','): {'saying': 1.0},
 ('told', 'him'): {':': 1.0},
 ('sitting', 'and'): {'a-playing': 1.0},
 ('from', 'miles'): {'around': 1.0},
 ('Orleans', ','): {'way': 1.0},
 ('!', 'Go'): {'go': 0.1, 'Johnny': 0.9},
 ('old', 'band'): {'.': 1.0},
 ('!', 'Well'): {'his': 1.0},
 (',', 'sit'): {'beneath': 1.0},
 ('or', 'write'): {'a': 1.0},
 ('a', 'country'): {'cabin': 1.0},
 ('He', 'used'): {'to': 1.0},
 ('be', 'a'): {'man': 1.0},
 ('boy', 'can'): {'play': 1.0},
 ('shade', ','): {'drumming': 1.0},
 (',', 'but'): {'he': 1.0},
 ('!', 'aah'): {'Johnny': 1.0},
 ('passing', 'by'): {'used': 1.0},
 ('saying', ':'): {'Johnny': 1.0},
 ('down', 'in'): {'in': 1.0},
 ('lives', 'a'): {'young': 1.0},
 ('my', ','): {'that': 1.0},
 ('named', 'Johnny'): {'B': 1.0},
 ('play', 'his'): {'guitar': 1.0},
 ('to', 'stop'): {'and': 1.0},
 ('.', 'Go'): {'go': 1.0},
 ('trees', 'by'): {'the': 1.0},
 ('And', 'you'): {'will': 1.0},
 ('go', 'Johnny'): {'go': 1.0},
 ('a', 'book'): {'so': 1.0},
 ('the', 'rhythm'): {'that': 1.0},
 ('a', 'young'): {'country': 1.0},
 ('to', 'hear'): {'you': 1.0},
 ('you', 'play'): {'your': 1.0},
 ('in', 'Louisiana'): {'close': 1.0},
 ('go', '!'): {'Go': 0.75, 'aah': 0.16666666666666666, 'Aah': 0.08333333333333333},
 ('and', 'say'): {':': 1.0},
 ('boy', 'named'): {'Johnny': 1.0},
 ('miles', 'around'): {',': 1.0},
 (',', 'to'): {'hear': 1.0},
 (',', 'that'): {'country': 1.0},
 ('rhythm', 'that'): {'the': 1.0},
 ('sack', ','): {'sit': 1.0},
 ('there', 'stand'): {'a': 1.0},
 ('gunny', 'sack'): {',': 1.0},
 ('by', 'the'): {'railroad': 1.0},
 ('track', '.'): {'Oh': 1.0},
 ('could', 'play'): {'his': 1.0},
 ('B', '.'): {'Goode': 1.0},
 ('hear', 'you'): {'play': 1.0},
 ('way', 'back'): {'up': 1.0},
 ('among', 'the'): {'evergreens': 1.0},
 ('around', ','): {'to': 1.0},
 ('carry', 'his'): {'guitar': 1.0},
 ('tonight', '!'): {'Go': 1.0},
 ('to', 'New'): {'Orleans': 1.0},
 ('!', 'He'): {'used': 1.0},
 ('by', 'used'): {'to': 1.0},
 ('used', 'to'): {'carry': 0.5, 'stop': 0.5},
 (',', 'saying'): {':': 1.0},
 ('Well', 'his'): {'mama': 1.0},
 ('him', ':'): {'someday': 1.0},
 ('his', 'mama'): {'told': 1.0},
 ('he', 'never'): {'ever': 1.0},
 ('guitar', 'just'): {'like': 1.0},
 ('close', 'to'): {'New': 1.0},
 ('that', 'the'): {'drivers': 1.0},
 ('a', 'gunny'): {'sack': 1.0},
 ('.', 'Oh'): {'sitting': 1.0},
 ('well', ','): {'but': 1.0},
 ('oh', 'my'): {',': 1.0},
 ('write', 'a'): {'book': 1.0},
 ('read', 'or'): {'write': 1.0},
 ('Maybe', 'some'): {'day': 1.0},
 ('Goode', 'tonight'): {'!': 1.0},
 ('.', 'Many'): {'people': 1.0},
 ('but', 'he'): {'could': 1.0},
 ('mama', 'told'): {'him': 1.0},
 (':', 'someday'): {'you': 1.0},
 ('the', 'sun'): {'goes': 1.0},
 ('back', 'up'): {'in': 1.0},
 ('sit', 'beneath'): {'the': 1.0},
 (',', 'drumming'): {'to': 1.0},
 ('someday', 'you'): {'will': 1.0},
 ('go', ','): {'go': 1.0},
 ('in', 'the'): {'woods': 0.5, 'shade': 0.5},
 ('woods', 'among'): {'the': 1.0},
 ('Louisiana', 'close'): {'to': 1.0},
 ('Goode', ','): {'he': 1.0}}

Sample riffs

Since almost all of the keys have only one option for the successor word, riffs will look a lot like the original text.

"leader of a big old band . Many people coming from miles around , to hear you play your music till the sun goes down . Maybe some day your name will be the leader of a big old band . Many people coming from miles around , to hear you play your music till the sun goes down . Maybe some day your name will be in light , saying : Johnny B . Goode ! He used to stop and say : my oh my , that country boy can play . Go go , go Johnny go"

"so well , but he could play his guitar just like a-ringing a bell . Go go , go Johnny go go ! aah Johnny B . Goode ! He used to carry his guitar in a gunny sack , sit beneath the trees by the railroad track . Oh sitting and a-playing in the woods among the evergreens , there stand a country cabin made of clay and wood , where lives a young country boy named Johnny B . Goode tonight ! Go Johnny go go go go go go ! Go Johnny go go ! Go go"