Markov Chain Quine

JavaScript, 217 215 bytes

a="a=q;a=a.replace('q',uneval(a));for(b=c='a';d=a.split(c),c=d[Math.random()*~-d.length+1|0][0];b+=c);alert(b)";a=a.replace('q',uneval(a));for(b=c='a';d=a.split(c),c=d[Math.random()*~-d.length+1|0][0];b+=c);alert(b)

Note that this uses uneval, which is only supported by Firefox. Sample runs:

a=ale(a.lend[Ma=d[Macepla.ler(b+=c)b=q;fom(a=q;a=dort(b+1|0],c);a.lit(a)
at(c=c;d[0],c=q;ath+1|0][0];dorerac=ac=d[Ma),c;)*~-d[Ma=alenepl(b+=ac=c;a=c;d[2];d.re(c;fom()
a="a[0],und=d=a)
angt(b),und=d.l(b=a)
a)
ale(a.rth.revanepleplit(b)
ac);fore(b)*~-d.r(b+1|0];fora';a)*~-d.splalith+=dorth+=c=";ath+=a.length+=';ale(b)
a.r(b=c=a)b+1|0],und[0][0];d.splerath.spleneva)";ath.r(ceneplith+=d=aceple(c;)*~-d=';ala';)b='ac;fom(b=c;a.ler(b=d=d[Ma.rt(c=cendor()*~-d='a=";ac;a.spla)b=ceva=';a=d.rt(angt(alength+1|0],c;angt()
al(ac=dorth+1|0][0][0][0][Ma.split()

As you can see, it's mostly gibberish, but that is to be expected ;) The OP has created a JSFiddle which demonstrates that the chance of an output being syntactically valid JS is about 6.3%.

If self-reading functions were allowed, this could be 78 bytes of ES6:

f=(c="f",p=("f="+f).split(c),q=p[Math.random()*~-p.length+1|0][0])=>q?c+f(q):c

Very, very rarely, this outputs syntactically valid JS:

f=>e?c+f():c
f=>e?c=>engt():c
f=>e?c=(e):c
f=>e?c=>e=>ength.split():c
f=p=>q?c+f():c
f(q).sp=",p[Mat(q?c=(),plith.lith.sp.sp[0]).lendom().lith+f=>q=p.lendom(",p=p=>q?c+f():c
f(q),q?c=(c=(q)*~-p[0]):c
f().random(),q?c=(c=p[0]):c
f=>q?c=(q="+f"+f).rath.split(c):c
f="+1|0])=().lith.rat()*~-p=>q?c=p[Mat(c=",q?c=p.rath.splendom()*~-plength.splith.lendom(c):c

My favorite of the function names it's created is .splendom() (split + length + random)

Pip, 64 bytes

This was fun.

t:V Y\"m:"Yt@0T9=A OyY@>RC(t(Xy).'.)"ST["t:V Y"RPy";Vm"C9]\";Vm<tab>

<tab> represents a literal tab character (0x09). Try it online!

How?

TL;DR: escaped-string syntax, repr, and eval.

For strings that need to contain literal " characters, Pip has escaped strings, using \" as the delimiter. A standard quine using escaped strings would look like this:

V Y\""V Y".RPy\"

That is: Yank (storing as y) a string containing "V Y".RPy and eVal it. RPy takes the repr of y, to which we prepend the literal string V Y. Finally, output the result of the eval.

The structure of the Markov quine is similar, except that we want to save the code instead of outputting it and then do some stuff with it afterwards. t:V Y\"...\" assigns the eval result to t. Inside the eval'd code, m:"..." assigns a string of code to m, which we will evaluate at the end with Vm.

ST["t:V Y"RPy";Vm"C9] builds a list containing

"t:V Y"  Literal string
RPy      Repr(y)
";Vm"    Literal string
C9       Tab character

and converts it to a string, which by default concatenates all the items. This section is equivalent to "V Y".RPy in the original quine. Since it is the last expression in the big eval string, its value is what the V operator returns, and thus what gets assigned to t.

Thus, after the eval and assignment, t is equal to the full code, and m contains

Yt@0T9=A OyY@>RC(t(Xy).'.)

Now Vm evaluates that as code. Let's break down what happens.

                            We'll use y to hold the current character in the chain
Yt@0                        Yank first character of t into y (chain always starts there)
         Oy                 Output y without newline each time we...
    T9=A                    Loop till ASCII code of y equals 9 (tab)
                            Since there's only one literal tab, at the end of the program,
                              this satisfies the Markov chain ending requirement
                   Xy       Generate a regex that matches y
                  (  ).'.   Concatenate . to regex: now matches y followed by any character
                (t       )  Find all matches in t (returns a list)
              RC            Random choice from that list
           Y@>              Slice off the first character and yank the remaining one into y

A couple notes:

• Ending the code with a literal tab was shorter than doing a regex test for "next character or end of string."
• The regex I used does not work properly if there are doubled characters in the code; for instance, applying it to xxy would return only xx and not xy in the matches. Fortunately, however, there are no doubled characters in this code, so it doesn't matter.

Perl, 103 bytes

Based on the standard quine and my answer to this question:

$_=q{$_="\$_=q{$_};eval";@s='$';{push@s,(@n=/(?<=\Q$s[-1]\E)(.|$)/g)[rand@n];$s[-1]&&redo}print@s};eval

Example Output

$_=q{$_=q{$_=";@sh@s=";eval
$_="\$_=q{$_='$_=q{$_}pus=\$_=";@n=";@ndo};{pus=';edo};@n]\Q$_};{$_};@s=q{$_=';@s[rand@s=/g)(@s,(@s,(@sh@s[-1];@ndo};ed@s[-1]\E)(.|$_}prevan]&ral";evan];{$_}pus='$_};ed@sh@sh@s[-1]\$_='$_};evando};eval
$_=q{$_=";ed@s[-1];evand@s="\Q$_=";@s[-1]\Q$_=q{$_=";@nd@sh@sh@s='$_=q{$_=q{$_='$_="\Q$_='$_};{pus=\$_=q{$_}pral
$_=";evando};@nd@sh@s,(@n]\$_=";@s,(@s[-1];{$_=q{$_}pral
$_=";eval
$_='$_=q{$_="\$_="\Q$_=";ed@sh@s=\E)(.|$_=q{$_=q{$_=q{$_=q{$_}pus=/(?<=q{$_};eval
$_=";ed@sh@s[-1]\Q$_=';edo};{$_=q{$_=";@nt@s,(@n]&&&&&&&ral";@nd@s,(@s[-1]\$_}pus=\E)(.|$_=';@nt@s[ral

Similarly to the other question, some results generate valid Perl:

$_=q{$_};{$_};eval";@sh@s[-1]\$_='$_};evan]\Q$_}preval";eval
$_=q{$_};{$_=q{$_=';@nd@s=q{$_};@s[-1]\E)(@s[-1]\E)(@n=';edo};{$_}predo};eval
$_=q{$_=q{$_};edo};@n=q{$_=q{$_};@s[rin='$_=q{$_}pus=/g)(.|$_=q{$_};edo};eval
$_=q{$_};eval
$_=q{$_=";@ndo};{$_}preval

but the chances are slightly lower, at ~2%.