[Question]
  [
The [random Fibonacci sequence](https://en.wikipedia.org/wiki/Random_Fibonacci_sequence) is defined as follows:
$$
f\_n = 
\begin{cases}
f\_{n-1}+f\_{n-2} \text{ with probability } 1/2 \\
f\_{n-1}-f\_{n-2} \text{ with probability } 1/2 \\
\end{cases}
$$
$$
f\_1 = f\_2 = 1
$$
i.e. whether the next term is the sum or difference of the previous two is chosen at random, independently of previous terms. Your task is to implement this sequence.
Each random realization of the sequence must use consistent values. For example, if \$f\_3 = 2\$, \$f\_4\$ must then be either \$2+1 = 3\$ or \$2-1 = 1\$. This can be thought of as the sequence "remembering" previous values. This means that [this](https://tio.run/##XY09DsIwDIXn@hRvjFWKlCKWSj0JYkBqAhnqRFYYOH1IAixMtt7P99IrP6KcSgl7ipqhN9niTrQ5D2@EFxqChyAILvaA@bpAXX6qwFK3PoVjO0GyaRnGusLW5vCNVtBkGWN/ZqY/ffrp5KMitK2Kuztz7vMYK42GpI3vTWAu5Q0) example program is invalid, as previous values in the sequence are not maintained by later values. Furthermore, you should explain how your program meets the \$1/2\$ probability requirement.
As is standard for [sequence](/questions/tagged/sequence "show questions tagged 'sequence'") challenges, you can perform one of three tasks:
* Take a positive integer \$n\$ as input and output \$f\_n\$
* Take a positive integer \$n\$ as input and output \$f\_1, f\_2, ..., f\_n\$
* Output the sequence indefinitely with no end
Again, as is standard, you may use either \$0\$ or \$1\$ indexing, but the two initial values \$f\_1 = f\_2 = 1\$ must be used.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest code, in bytes, wins.
## Examples
```
n -> possible values of f_n | probabilities of values
1 -> 1                      | 1
2 -> 1                      | 1
3 -> 2, 0                   | 1/2, 1/2
4 -> 3, 1, -1               | 1/4, 1/2, 1/4
5 -> 5, 3, 1, -1            | 1/8, 1/8, 3/8, 3/8
6 -> 8, 4, 2, 0, -2         | 1/16, 1/8, 1/4, 5/16, 1/4
```
  
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~8~~ 7 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
λ₂D(‚Ω+
```
-1 byte thanks to *@ovs*.
Prints the infinite sequence.
[Try it online.](https://tio.run/##yy9OTMpM/f//3O5HTU0uGo8aZp1bqf3/PwA)
**Explanation:**
```
λ        # Create a recursive environment to output the infinite sequence,
         # implicitly starting at a(0)=1
         #  (push a(n-1) implicitly)
 ₂       #  Push a(n-2) (NOTE: all negative a(n) are 0, so a(-1)=0)
  D      #  Duplicate a(n-2)
   (     #  Negate the copy: -a(n-2)
    ‚    #  Pair them together: [a(n-2), -a(n-2)]
     Ω   #  Pop and push a random item
      +  #  And add it to the a(n-1)
         # (after which the infinite list is output implicitly)
```
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 20 [bytes](https://github.com/abrudz/SBCS)
```
{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkGXI862tP@Vz/q3aqjcWi9oZa9keajrqWH1hs9apsIFKzVB6p81LvF8D9Q3f80LlOuNC5DAwA "APL (Dyalog Unicode) – Try It Online")
Takes n from stdin and prints first n terms.
```
{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1  ⍝ Full program. Input: n
{              }/⎕⍴1  ⍝ Reduce a vector of n ones...
           ¯2↑⍵  ⍝ Last two items ([0 1] for the first iteration)
   (¯1*?2)       ⍝ 1 or -1
          ⊥      ⍝ Base convert (or polynomial evaluate),
                 ⍝ giving f(x-2)+f(x-1) or -f(x-2)+f(x-1) with 50% chance each
 ⍵,              ⍝ Append to the previous iteration
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~14~~ ~~13~~ 11 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Outputs the `n`th term, 1-indexed. Uses JavaScript's `Math.random()` as seen [here](https://github.com/ETHproductions/japt/blob/master/src/japt-interpreter.js#L133).
```
@Zä+iÍö)Ì}g
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFrkK2nN9inMfWc&input=OA), [check the first `n` terms](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFrkK2nN9inMfWhC7A&input=OA) or [view the distributions across 10,000 runs](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=TLLGQFrkK2nN9inMfWfD%2bSD8IPHKy84rIjp7RMovTCB4MiBzIPk2fSUiw7c&input=OA)
```
@Zä+iÍö)Ì}g     :Implicit input of integer U
@               :Function taking an array as argument via parameter Z
 Zä             :  Consecutive pairs of Z reduced by
   +            :    Literal "+"
    i           :    Insert
     Í          :      "n" at index 2 with wrapping, resulting in "n+"
                :      (Hooray for shortcut abuse!)
      ö         :    Random character from that string, where XnY=Y-X
       )        :  End reduction
        Ì       :  Get last element
         }      :End function
          g     :Starting with [0,1], repeatedly run it through that function,
                : pushing the result back to it each time
                :Implicit output of Uth element, 0-indexed
```
To explain how the shortcut abuse works here: `Í` is Japt's shortcut for `n2<space>` which is primarily intended to be used for converting binary strings to integers (e.g., `"1000"Í="1000"n2 =8`). However, when you pass a 2 character+space shortcut like that to another method - in this case `i` - the space is used to close that method and the 2 characters are split & passed to that method as separate arguments. Which is handy here as the `i` method for strings expects one argument containing the string to be inserted and another, optional integer argument for the index it's to be inserted at.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 10 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
I'm pretty sure 10 is as good as it'll get in Jelly; I had some much longer solutions along the way.
```
1ṫ-ḅØ-XṭƲ¡
```
A monadic Link accepting an integer, which yields all values up to and including that 0-indexed index  
(i.e. \$n \to [f\_0, f\_1,\cdots, f\_n]\ |\ f\_0=f\_1=1 : f\_n = f\_{n-1} \pm f{n-2} \$).
**[Try it online!](https://tio.run/##AR8A4P9qZWxsef//MeG5qy3huIXDmC1Y4bmtxrLCof///zk5 "Jelly – Try It Online")**
### How?
```
1ṫ-ḅØ-XṭƲ¡ - Link: integer, n
1          - set the left argument to 1
         ¡ - repeat this n times:
        Ʋ  -   last four links as a monad f(left):  e.g. left = [1,1,2,3,5,8]
 ṫ-        -     tail from 1-based, modular index -1            [5,8]
                 (tailing 1 from index -1 yields [1])
    Ø-     -     signs (a nilad)                                [-1,1]
   ḅ       -     convert from base (vectorises)                 [3,13]
                                        (i.e. [5×-1¹+8×-1°, 5×1¹+8×1°])
      X    -     random choice                                  3?
       ṭ   -     tack                                           [1,1,2,3,5,8,3]
```
[Answer]
# perl -061 -M5.010, 46 43 bytes
```
say$,while($,,$/)=($/,$/+$,-2*$,*(.5<rand))
```
[Try it online!](https://tio.run/##K0gtyjH9/784sVJFpzwjMydVQ0VHR0Vf01ZDRR9Ia6vo6BppqehoaeiZ2hQl5qVoav7//y@/oCQzP6/4v66BmeF/XV9TPQNDAwA "Perl 5 – Try It Online")
This prints the infinite series.
Saved three bytes using a suggestion from Nahuel Fouilleul.
## How does it work?
First trick is the command line switch `-061`. This sets the input record to `1` (as the ASCII value of `1` is 49, aka 61 in octal). The input record separator is `$/`.
We then use two variables to keep state, `$,`, which initially is the empty string, but Perl will treat that as `0` when used as a number. `$/` is set to `1`, as discussed above. In an infinite loop, we set `$,` to `$/`, and `$/` to `$, + $/`, and then, with probability .5, subtract `2 * $,` from the latter. We then print `$,`.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 45 bytes
Outputs f(n) using RandomInteger 0 or 1
```
#&@@Nest[+##|(-1)^Random@0[[0]]#&@@#&,0|1,#]&
```
[Try it online!](https://tio.run/##FczBCsIwDADQXxECRbGy9AOEgEdBxHkrFaKGOlhb2OJB2L9HPT94hfUlhXV4sOW9gSM6yaxxC7Csd2Fzu3B9tkIYI6b0Z3Ael@AhOTtPQ9UVHeXTt0np0N5VZ7ryfZSYIyQfEJPr6HdkoYBmXw "Wolfram Language (Mathematica) – Try It Online")
*-6 bytes from @att*
I also tried this `46 bytes`
```
If[#>1,#0[#-1]+(-1)^RandomInteger[]#0[#-2],#]&     
```
but the sequence could not "remember" the previous values
[Answer]
# Python 2, ~~66~~ 64 bytes
Outputs the sequence infinitely.
```
from random import*
a=b=1
while 1:print a;a,b=b,b+choice([-a,a])
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P60oP1ehKDEvBUhl5hbkF5VocSXaJtkacpVnZOakKhhaFRRl5pUoJFon6iTZJukkaSdn5Gcmp2pE6ybqJMZq/v8PAA "Python 2 – Try It Online")
### Python 2, 73 bytes
Outputs the nth term of the sequence.
```
from random import*
a,b=0,1
exec"a,b=b,b+choice([-a,a]);"*input()
print a
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P60oP1ehKDEvBUhl5hbkF5VocSXqJNka6BhypVakJiuBOEk6SdrJGfmZyaka0bqJOomxmtZKWpl5BaUlGppcBUWZeSUKif//GwMA "Python 2 – Try It Online")
[Answer]
# [J](http://jsoftware.com/), 28 22 bytes
*-6 thanks to Bubbler!*
```
0{1&({,]#.~_1^?@2)&1 1
```
[Try it online!](https://tio.run/##VYq7CgIxEEX7/YpLAnlIHGcsR8RFwUosbOO63YL@QiC/HmO3Frc459xPM@QXHBUeCQzt2xIuj9u1cREXSpos1Vlep3EfnUAa7mfCwCUUXbcxO/71Yd3FUt7M3f5fYvN@CAdkfWrNilAJiWB3VGOXWEzgCGFmO0XDeFOHLw "J – Try It Online")
```
0{1&({,]#.~_1^?@2)&1 1
  1&      …       &1 1 a verb that will apply 1&… on 1 1 y (the input) times 
              ?@2        0 or  1
           _1^           1 or _1
       ]#.~              to base, e.g. 3 5:
                           (3* 1^1)+(5* 1^0) = 8 or
                           (3*_1^1)+(5*_1^0) = 2
     {,                  prepend tail of list, i.e. 5 8 or 5 2
0{                     take first element
```
[Answer]
# JavaScript (ES6), ~~68 67 66 53~~ 52 bytes
*Saved 2 bytes thanks to @Shaggy*
Returns the **n**-th term, 0-indexed.
```
f=(n,p=1,q=0)=>n?f(n-1,Math.random()<.5?p+q:p-q,p):p
```
[Try it online!](https://tio.run/##PY7BTsMwDIbvPIUPg9prGtqJCxsdN26IB5gmLbQptN2SrIkQqOpevbhF42DZv7/f@t2oL@WLrnYhMbbU41jlaITLM3HOU8q35rlCk2TCxeflJcFXFT5lp0xpT0jLh7sVCUdrN1a2QwM5pBsw8ASP3OKYoL8BmJAPKjDtBwHtn6tlV5am03Q1AnTaM@VA2sx6Otvxcs/b5PKvJjhwFdZ4e9TyaD/woHDRm4FgDYv@7b3RRZCt/vFzNMmTcsjJW86NIQKMuM1o1@7hnj8hGexL/a1LXNFkuaWIZGNrg5GAiIYDvzSMvw "JavaScript (Node.js) – Try It Online")
### Commented
```
f = (                // f is a recursive function taking:
  n,                 //   n = 0-indexed input
  p = 1,             //   p = previous value
  q = 0              //   q = penultimate value
) =>                 //
  n ?                // if n is not equal to 0:
    f(               //   do a recursive call:
      n - 1,         //     decrement n
      Math.random()  //     set p to either:
      < 0.5 ? p + q  //       p + q
            : p - q, //       or p - q
      p              //     copy the previous value in q
    )                //   end of recursive call
  :                  // else:
    p                //   return the last value
```
[Answer]
# [><>](http://esolangs.org/wiki/Fish), 22 bytes
```
1|.00<-x+40.08&:{&:}n:
```
[Try it Online!](https://tio.run/##S8sszvj/v0YhztCQq0I3xo4rRtvOKq/WSq3aSs3u/38A)
This is usually a terrible language for challenges involving randomness, since the only source of randomness in ><> is `x`.
But in this case things works out alright. `x` sends the instruction pointer in a random direction, so it either wraps around to itself in the y-direction, or hits a `+` or `-` with equal probability.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~58 57~~ 47 bytes
```
a,b;f(x){a=--x?f(b=x),b+=rand(x=b)%2?a:-a,x:1;}
```
[Try it online!](https://tio.run/##bc5LCoMwFIXhuau4FISE3oCJD4qSuhEnidbiwFCsg4C49jS2DhLoGX8/nJ49@945hboZiaWbkozZdiRaWor6KhdlBmKlpqloVc0U2po3u5vMCrOaDBC6JfA@FJB1mh8ko7RJ4LV4MQK5cGB3SAfo/IB35oIj4TERf4iISR4SgZDBj@UxK0KWI3AExuG0RWzL0JYY8NOXsa9Cf0Mo8HvEJ@IMqiPw290H "C (gcc) – Try It Online")
* Saved 1 thanks to @ceilingcat
* Saved 10 thanks to @Dominic van Essen
Recursive solution which starts all the calls needed before executing them, the last call initialize values.
```
a,b;         - aux variables
f(x){        - function tacking an integer **n** and 
               returning **n**th term 1 indexed.
a=           - return trough eax register
--x?f(b=x)   - call recursively before doing the job
x=b          - local x used as temp
,b+=rand()%2?a:-a  - rnd fib step
,x           - assign temp(x) to a
:1;}         - stop recursion and initialize a to 1
```
[Answer]
# [R](https://www.r-project.org/), ~~69~~ ... 55 bytes
-1 byte thanks to Giuseppe (which led to a further -4 bytes), and
-1 byte thanks to Dominic van Essen (which led to a further -1 byte)
```
F=0:1;repeat cat(" ",{F=F[2]+F[1]*(0:-1)^sample(2)}[1])
```
[Try it online!](https://tio.run/##K/r/383WwMrQuii1IDWxRCE5sURDSUFJp9rN1i3aKFbbLdowVkvDwErXUDOuODG3ICdVw0izFiio@f8/AA "R – Try It Online")
Prints the sequence indefinitely, separated by spaces.
`F` is initialized as the vector `[1 1]`.
At each step, draw a random permutation of the vector `[1 2]` with `sample(2)`. This means that `(0:-1)^sample(2)` is either `[0^1 (-1)^2]=[0 1]` or `[0^2 (-1)^1]=[0 -1]` (with probability 1/2 each). In both cases, `F[1]` takes the previous value of `F[2]`, and depending on the random draw, `F[2]` becomes either `F[2]+F[1]`or `F[2]-F[1]`. Finish the step by printing the first value of `F`.
Note that I can make this 2 bytes shorter by using a stupid delimiter between sequence values: [Try online](https://tio.run/##K/r/383WwMrQuii1IDWxRCE5sUQjRKfazdYt2ihW2y3aMFZLw8BK11AzrjgxtyAnVcNIsxYoqPn/PwA "R – Try It Online") a 53 byte version which uses the string `TRUE`  as delimiter.
[Answer]
# [Raku](https://github.com/nxadm/rakudo-pkg), 26 bytes
```
{1,1,*+* *(-1,1).pick...*}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/2lDHUEdLW0tBS0MXyNTUK8hMztbT09Oq/V@cWKmQFh1naBD7HwA "Perl 6 – Try It Online")
Outputs a lazy infinite list. This is pretty much identical to the normal fibonacci program, but with `*(-1,1).pick` tacked on to randomly flip the sign of the second parameter.
[Answer]
# [Python 3](https://docs.python.org/3/), 77 bytes
```
from random import*
f=lambda n,t=0,o=1:o if n<2else f(n-1,o,o+choice((-t,t)))
```
A recursive function which accepts \$n\$ and yields a possible \$f\_n\$.
**[Try it online!](https://tio.run/##DcY7DsMgDADQvafwaFIj5SN1qMphaIIVpGAj6iWnp0zv1dtOla13blqgRTkGuVRtNj04XLF8jwhCFmbSsLwVMoN81nT9EjCKX0hJn/upeU@I3sicc722LIaMr/E/ "Python 3 – Try It Online")** Or see the [first few as sampled 10K-distributions](https://tio.run/##TY3BDoIwEETvfMXGU1dLQvVG7MkPMVhaaVJ2SVkPhvDtCMrBuUwyyXszvKVjuixLyNxDbqhdK/YDZzkWwaamf7QNkBZbabamZogB6Hr2afQQFJVGs@aT6zg6r1QpWhDxZ3OckncSmcZdCTd@kfhcFIEzEETaLp9eGQ2mwrqANUOOJCocyE401zDtjPquihBhg@9/cLUGcT7g8gE "Python 3 – Try It Online").
[Answer]
# [Red](http://www.red-lang.org), 75 bytes
```
func[n][a: b: 1 loop n - 1[set[a b]reduce[b b +(a * pick[1 -1]random 2)]]a]
```
[Try it online!](https://tio.run/##ZY07DoMwEER7TjFylY8QMekocoi0qy38WUsoxLYMKMcnBJQiyrTz3kwRv9zFE1fFRJ@ezSjiEdOrCh2WMEdHkcl0sB00hpQyImpoGmUiA8tF/OyELCzOB4MTcu8epFFr3hfRHpkNL0WymGm19QVUYU0ufaRsfDNI@BQtVH2D4q3crtov@o@HVbhizMbJLvAPOEGpipc3 "Red – Try It Online")
Returns the `n`th term.
[Answer]
# x86 machine code, 21 bytes
The rdtsc version is the same size for x86-64 machine code.
[`rdrand reg`](https://www.felixcloutier.com/x86/rdrand) (3 bytes) gives us a truly random number. Branching on its sign bit is cheap. By testing only 1 bit, the 50/50 probability is obviously satisfied exactly with zero bias.
[`rdtsc`](https://www.felixcloutier.com/x86/rdtsc) (2 bytes) gives us a "reference cycle" timestamp whose low bits are *somewhat* random (it takes at least 25 cycles to run back-to-back RDTSC instructions, but the counter isn't running *that* much faster than we're sampling it). Testing one bit with `test al, 1` leads to significant correlation between consecutive decisions, but `test al,al` / `jnp` (branch on the parity flag, horizontal xor of the low 8 bits) gives surprisingly good results, and could be used on pre-IvyBridge machines that lack `rdrand`. Both of them golf to the same overall size in 32-bit mode.
[Try it online!](https://tio.run/##fVRLb5wwEL7zK@YStVXZDSRNVC3KIS@pvfSQ5LBSFK0MDODW2FvbZNn8@e3YUBY2Dw4Yj@2Z@R6GGYN1KrYzyUy92yXZuoEfzGxQiEAXPD1ZwOhJIJpxmWMLmWqkBS7h9noZgkbbaGn8/GoZuK2t0gBoeOhePiKQUSRtQ3ik0Nf4aZKYaj1GT3ABcei/Z7GbRP7kb8zaF5jnSmIwF0qtFz6sc2syePtJ4PZmubi9XFKSB17jvWX1Gq5d16gDf9yisW5kIoRvr44LtYGUWwNMI0EwKC1nQmxBM5mrOoGKl1W3QyoLRkHdZFXXrnxxw1yqlcSSWfRR@vSpHR37pQ5Jy/Lcrzl2Br4IqEvjxsCD7zYnb9FNoaCDxQQvJcTnXr6RekkyqIf5nGpl7cUZlPwZDdgKQV6cd5RkzCDlM42wZj5oicy1xlofyPK/AB8xT6wfishl5s6/c2Yv/0hx6DR/tdm1HsGi5wFi2HBbqcZ6yrgsg2QomE0KEgVSrZGAFAVmlrCToLMYelYWoCQFmKTAmtKpAiLic8O2pieKiriFeGpDZwkiNOcTX9E8dK993zGkW4tgKqXJhcQ6VTJME44yBF7XcOypPgbTpHDyydAtq9cCa/Kec1rFsj@9wczUYEMFJ6Ql29Bu4AaKZu/YsQkxb9/3oBc6bz/0oLfbES96bR2IAfJpfCDX6czD5tJY3RDrSu7/EF0z4UCeQz4OTjMdcOLbp3SQkmVzEg@M874DT9J1ugRHKHNe7CZXoxQqZQJWxjJtg27ogNXq2V@NEM5G@DK6@eB/h30jdzcP99fwjNr8R3N4K6mYRpZvqb4wOM0CQ5a7y183kzRd/bS/a13vwWjFiRP398lC1H6PJgStsOX2M5X/AqcnM0fE5dXP3T8 "Assembly (nasm, x64, Linux) – Try It Online")
NASM listing for `rdrand` version: `EAX rfib(ECX)`, callable from C with MS `__fastcall`
```
21                         rfib:          ;;; 0-indexed.  ecx=5 gives the n=6 test case results.
22 00000020 31C0               xor eax, eax
23 00000022 99                 cdq                         ; EDX = fib[-1] = 0
24 00000023 40                 inc eax                     ; fib[0] = 1
25 00000024 E30E               jecxz   .done               ; ecx=0 : return 1 without looping
27                         .loop:
28 00000026 0FC7F7             rdrand  edi
29 00000029 85FF               test    edi, edi        ; 1 byte shorter than sar reg, imm / xor / sub 2's complement bithack
30 0000002B 7902               jns    .no_negate       ; the top bit is fully random
31 0000002D F7DA               neg    edx
32                         .no_negate:
33 0000002F 0FC1D0             xadd    eax, edx        ; like xchg + add, and same size
34 00000032 E2F2               loop   .loop
35                         .done:
36 00000034 C3                 ret
 size = 0x35 - 0x20 = 0x15 = 21 bytes
```
Note that `xadd` doesn't actually save any bytes vs. `xchg eax, edx` / `add eax, edx`. It's just fun. And it's "only" 3 uops, instead of 4 total, on Intel Skylake with register operands. (Normally the instruction is only used with the `lock` prefix and a memory destination, but it fully works with registers).
Test case:
```
  bash loop to test the ECX=5 case
$ asm-link -m32 -dn random-fib.asm &&
 { declare -A counts; counts=(); 
  for i in {1..10000}; do ./random-fib; ((counts[$?]++));done; 
  for i in "${!counts[@]}"; do echo "result: $(( i > 128 ? i-256 : i )):   
${counts[$i]} times";done }
result: 8:   617 times
result: 4:   1290 times
result: 2:   2464 times
result: 0:   3095 times
result: -2:   2534 times
```
---
NASM listing for **`rdtsc` version**: `EBX rfib2(ECX)`. This version would be the same size in 64-bit mode; doesn't need 1-byte `inc`. RDTSC writes EAX and EDX so we can't take advantage of `cdq` in the init.
```
 2                         rfib2:            ; 0-index count in ECX, returns in EBX
 3 00000000 31F6               xor  esi, esi
 4 00000002 8D5E01             lea  ebx, [esi+1]           ; fib[0] = 1, fib[-1] = 0
 5 00000005 E30D               jecxz .done
 6                         .loop:
 7 00000007 0F31               rdtsc                       ; EDX:EAX = TimeStamp Counter
 8                         
 9 00000009 84C0               test    al, al               ; low bits are essentially random; high bits not so much
10 0000000B 7B02               jnp    .no_negate
11 0000000D F7DE               neg     esi
12                         .no_negate:
13 0000000F 0FC1F3             xadd    ebx, esi
14 00000012 E2F3               loop   .loop
15                         .done:
16                             ; returns in EBX
17 00000014 C3                 ret
 size = 0x15 = 21 bytes
```
Test results for ECX=5:
```
result: 8:   668 times         (ideal: 625)
result: 4:   1217 times        (ideal: 1250)
result: 2:   2514 times        (ideal: 2500)
result: 0:   3135 times        (ideal: 3125)
result: -2:   2466 times       (ideal: 2500)
```
vs. with `test al, 1` / `jnz` to use just the low bit of the TSC as the random value:
```
  # test al,1  / jnz   version: correlation between successive results.
result: 8:   115 times
result: 4:   79 times
result: 2:   831 times
result: 0:   3070 times
result: -2:   5905 times
```
`test al,4` happens to work reasonably well for long runs on my Skylake CPU (i7-6700k) which ramps up to 3.9GHz at the energy\_performance\_preference=balance\_performance I'm using, vs. a reference (TSC) frequency of 4008 MHz ([more info on x86 constant-TSC stuff](https://stackoverflow.com/questions/13772567/how-to-get-the-cpu-cycle-count-in-x86-64-from-c/51907627#51907627)). I imagine there's some strange alchemy of branch prediction, and `rdtsc` itself having ~25 cycle throughput (core clocks) on Skylake (<https://uops.info>).
Results are generally better distributed with `test al,al` / `jnp` though, so prefer that to take entropy from all 8 low bits. When CPU frequency is low (idle), so the TSC is not close to the same frequency as the core, taking entropy from a single bit might work even better, although the parity of the low 8 bits is probably still best.
I haven't tested on a CPU with turbo disabled where non-boost core clock exactly equals the TSC reference clock. That could more easily lead to bad patterns if the `rdtsc` throughput happens to be a power of 2 or something, perhaps favouring some sequence that lets branch prediction lock on.
All my testing has been with one invocation of the function per process startup. A Linux static executable is pretty efficient to start up, but is still *vastly* more expensive than calling the function in a loop from inside the process.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 38 bytes
Prints the sequence indefinitely. Adapted from [J42161217's answer](https://codegolf.stackexchange.com/a/211171/98349).
```
#0[Echo@+##,RandomChoice@{#,-#}]&[0,1]
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78/1/ZINo1OSPfQVtZWScoMS8lP9c5Iz8zOdWhWllHV7k2Vi3aQMcw9v///wA "Wolfram Language (Mathematica) – Try It Online")
Ungolfed:
```
f[a_, b_] := ( Echo[a+b]; f[a+b, RandomChoice[{a,-a}]] );
f[0, 1]
```
[Answer]
# [R](https://www.r-project.org/), ~~55~~ ~~54~~ ~~53~~ ~~52~~ ~~51~~ ~~49~~ ~~48~~ 47 bytes
*Edit: -1 byte, and again -1 byte thanks to Giuseppe, -1 byte thanks to AZTECCO*
```
cat(1);repeat cat(" ",T<-sign(rt(1,1))*F+(F=T))
```
[Try it online!](https://tio.run/##K/r/PzmxRMNQ07ootSA1sUQBxFNSUNIJsdEtzkzP0ygCSuoYampquWlruNmGaGr@//8fAA "R – Try It Online") or [check the n=6 distribution](https://tio.run/##TY7BboMwEETP@Cu2itTYBVQcqRxQ3GO@gFuUAzFLWZWsW2MaVVW@nRqUSr3t7O7MPD/P8wZa7IgRmhG6iW0gxxAc2B7tO7Q0Bk/nadlWwnd0NuLvS7L6Ecm1pwEl73PO9aKTep@P9MbSB6kzrdTTIZUHUyuR3ERSi5sQm3v4lUIPbEqQZRxwwAtyANeBb7h1F4htjhtrCUb8nJAtKnhckD6G5huIQT/r6BwrYd3EwTzoaldo0TkvaT1Xu5eyKBYqNgu7LCPF@nvkVBf6ZP6LVEc4fyZu5VczTGjWuDyesu29aWt8NLRytcVVDFfHbFWvxUnM8y8).
Full program taking no input. Returns full random fibonacci sequence.
Program to return `n`th element using the same approach is [48 bytes](https://tio.run/##jY7NToQwFIXX06e4xsRpBWI7iSwY65InYDeZRSlFGuFW2@LEGJ8dC2ri0s3N/fvOOX5ZUAatkLLjZbCjofhQYCFYI4N9QuojFblg7LbOaC0bdsyapSTkGjrTWzSgAvQz6mgdQnSgB6OfobMhetvO67YifqKJS7VmxPe2lb8ARfZB/mXaZJx8rq7f@hcbB0BZAi1TY0YzGYzgevAKOzdBMnGotLYQzOtsUBsGN2uql1G9g0UQdyKRoSLazRjllagOXJDeeWq3c3W4LzlP6XYo18i0ZGS3/Z4wE1yc5d8hEymcby129E2Ns5GbXJFO@f7HaS99Ajq6YWmVxNkp36ZHfibL8gU).
Commented:
```
cat(1);             # First, print the first element (1) 
                    # (T is initialized to 1 by default,
                    # and F is initialized to 0).
repeat              # Now, repeat indefinitely:
 cat(" ",           # output " ", followed by...
  T<-               #   T, updated to equal...
     sign(rt(1,1))  #   the sign of 1 randomization of 
                    #     the t-distribution with 1 degree-of-freedom
                    #     (distribution is centred around zero,
                    #     so sign is [+1,-1] with probability [.5,.5])...
     *F             #   times F (second-last value)...
       +(F=T))      #   plus T (last value)...
                    #   while updating F to equal T.
```
[Answer]
# Dotty, 75 bytes
```
val| :Stream[Int]=1#::1#::(|zip|.tail map(_*((math.random*2).toInt*2-1)+_))
```
[Try it online](https://scastie.scala-lang.org/I8IXodG1R0WSFd6avRN2hw)
Same as below.
# Scala, ~~91~~ ~~87~~ ~~85~~ 84 bytes
*Saved 4 bytes thanks to corvus\_192*
```
val| :Stream[Int]=1#::1#::(|zip|.tail map{t=>t._2+t._1*((math.random*2).toInt*2-1)})
```
[Try it online](https://scastie.scala-lang.org/b4lxtOFoQA2SfdZ77rWWKg)
`|` is a `Stream` so that previous elements are remembered. To get the nth element, you can use `|(n-1)` (it's 0-indexed). To get the first n elements, use `|.take(n)` (`l.take(n).toList` to force it).
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 28 bytes
```
≔⁰θ≔¹ηＦＮ«≔⁺η×θ⊖⊗‽²ι≔ηθ≔ιη»Ｉθ
```
[Try it online!](https://tio.run/##NY27CsIwGIVn8xT/@AciqINLJ7GLixTxBdI0mkAu5uYiPnuMtD3L4YNzEYpH4bmp9ZSSfjrcMQi0IwvtGahGDx8BL@5V8rXYUUakFD5ks4QGUxIqBndtZcLAoJciSitdlhP2voym@Y27yVs80L8Y6La69tV8uaKeP79kiNplPPOUMVDa1Xqs27f5AQ "Charcoal – Try It Online") Link is to verbose version of code. Outputs the `n`th number. Explanation:
```
≔⁰θ≔¹η
```
Start with 0 as the `i`th number and `1` as the `i+1`th number.
```
ＦＮ«
```
Loop `n` times.
```
≔⁺η×θ⊖⊗‽²ι
```
Calculate the next number.
```
≔ηθ≔ιη
```
Shuffle the values around.
```
»Ｉθ
```
Output the `n`th number.
29 bytes to output the first `n` numbers:
```
Ｆ²⊞υ¹ＦＮ⊞υ⁺§υ±¹×§υ±²⊖⊗‽²Ｉ✂υ⁰±²
```
[Try it online!](https://tio.run/##bYy9DsIwEIP3PkXGi1Qk2oGlE6JLlyoCXiBNDhopPyi5IN4@NCww4MWyP8tqlVEFaUu5hcig50zktEJuWceH5tNN/pFpzm7BCPzLhc0JjjR5ja@aZ7xLQug4b9nVOPwH@wpHVBEdekINY8iL3fwsvQ6u8qqhEdF4gpNMBBdrFNaP/e/NNirlUHZP@wY "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
Ｆ²⊞υ¹
```
Start with `1` as the first and second numbers.
```
ＦＮ
```
Loop `n` times.
```
⊞υ⁺§υ±¹×§υ±²⊖⊗‽²
```
Calculate the next number.
```
Ｉ✂υ⁰±²
```
Output all but two of the numbers.
[Answer]
# [Icon](https://github.com/gtownsend/icon), 70 bytes
```
procedure n()
f:=[1,1]
while write(f[2])&push(f,f[1]+?[1,-1]*f[2])
end
```
[Try it online!](https://tio.run/##y0zOz/ufk5mXrVCUmJeSn/u/oCg/OTWltChVIU9DkyvNyjbaUMcwlqs8IzMnVaG8KLMkVSMt2ihWU62gtDhDI00nLdowVtseqEjXMFYLLMOVmpeCZExuYibIJAUggFiRWZUK5YPEQYoB "Icon – Try It Online")
Prints the sequene indefinitely.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~56~~ ~~53~~ 52 bytes
*Edit: -3 bytes thanks to AZTECCO, -1 byte thanks to ceilingcat*
```
x;y;r(n){for(x=y=1;--n;)x=~-(rand()&2)*y+(y=x);x=y;}
```
[Try it online!](https://tio.run/##LY7LCsIwEEX3/YpBUGZai49FNzF/4qbGVFPMpKYptEj99ZiAq7lwzxmuqh9KxTiLRXhk@nTO4ywXeRJ1zYJm@a3Rt3xH2p2pXCpc5EwiEWKNhxLG1g4vDW4KwxQgycCyAWzCE/RLW80BXAf5gbPQmZvjVikDo35PmpUmKA@FSZBtDSN9ChgzCxiM1XgkEgXk2sjmn/p088Y@Lewv8tSIvqqyCINPfYeb7f3Km71Hk@y1WGP8AQ "C (gcc) – Try It Online")
Non-recursive answer in C.  
Function that returns `n`th (one-based) element of random fibonacci sequence.
```
x;y;                # x & y hold last and last-but-one elements;
r(n){               # n is index of element we're looking for;
for(x=y=1;          # initialise first two elements to 1;
 --n;)              # now loop by decreasing n until it is zero,
 x=                 # update x to become equal to:
   ~-(rand()&2)*y   # plus-or-minus y...
   +(y=x)           # plus x
                    # (while updating y to equal the current x).
    ;x=y;}          # after looping, return y.
```
**Note**: Following some discussion in the comments here and in [AZTECCO's answer](https://codegolf.stackexchange.com/questions/211166/implement-the-random-fibonacci-sequence/211181#211181), a consensus was reached that it is not necessary to initialize the random seed *within a function*. Of course, that this means that the *calling program* should do so, or the function may give the same sequence of pseudo-random output every time the calling program is run.
A [74 byte](https://tio.run/##JY7BboMwEETvfMUqUipvXJRQKTlku82P9EId05iENTUg2Yr4dhfa08zojUZjym9jco6U6E5BCT7vWl@q8xBquaoXQWp8UJETVyQly8eBMLL6o7h9u6RzmVCrxBEpcqQ573cw1F3/sOCnsZ9GWAZA@AjqNN7APmxnZQTfwLrhO2jcl5faGAeD/ZmsGIuw2xduKXW1E4XPAtbg@Ej/rl10fdXygdr36kSt1msL@rDgRm2210/ZvAblEGku5px/AQ) variant of the function can itself initialize the random seed itself (but only on first call, so that subsequent calls from the same program run give different output).
[Answer]
# [Bash](https://www.gnu.org/software/bash/), 65 bytes
```
a=1;b=1;while :;do echo $a;t=$b;:$[b+=$RANDOM&1?$a:-$a];a=$t;done
```
[Try it online!](https://tio.run/##DYoxC8IwFAZ3f8UHPkSRgnVsCCK4quAqDi/2xVQkKUmkg/rbY4aD4zjDyRW7XOFTWLfKVCY3vASd6gPk7gKIVdZkVEdXs9Z02Z8O5@Oi3RF3DfFNsaZcZy/lN7P4wgn3aLYbzPF8p4zkwgQ7xKo1su@RchhhQ4RwEgSLKKNwHvyj/AE "Bash – Try It Online")
Endlessly outputs the latest and greatest version of the sequence.
[Answer]
# [Swift](https://swift.org/), 77 bytes
```
sequence(first:(1,1)){a,b in(b,.random() ?a+b:a-b)}.lazy.forEach{print($0.0)}
```
Outputs until `Int` overflow.
[Answer]
# [Lua](https://www.lua.org/), 81 bytes
```
t={1,1}for i=1,...do t[i]=t[i]or t[i-1]+t[i-2]*(math.random(2)*2-3)print(t[i])end
```
[Try it online!](https://tio.run/##yylN/J@bWJKhV5SYl5KfW5yamqKRX6xXkpmbqqGp@b/EttpQx7A2Lb9IIdPWUEdPTy8lX6EkOjPWFkQARYGUrmGsNogyitXSQDJKw0hTy0jXWLOgKDOvRAOkXDM1L@X///@GBgA "Lua – Try It Online")
Takes number of members to be printed as an argument. Replace `...` with `1/0`  to print sequence forever at const of one byte.
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 9 bytes
```
‡₍+-℅d11Ḟ
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCIiLCLigKHigo0rLeKEhWQxMeG4niIsIiIsIjYiXQ==)
Prints the infinite list.
```
        Ḟ # Create an infinite list from...
      11  # [1, 1]
‡    d    # And a function taking two arguments...
 ₍  ℅     # Choose randomly from...
  +-      # sum of previous two, difference of previous two
```
[Answer]
# Excel VBA, ~~49~~ 48 bytes
Saved 1 byte thanks to [Taylor Raine](https://codegolf.stackexchange.com/questions/211166/implement-the-random-fibonacci-sequence/255269?noredirect=1#comment570230_255269) and using the VBA native function instead of evaluating the Excel function.
```
b=1:Do:c=a+b*IIf(Rnd()<.5,1,-1):a=b:b=c:?a:Loop
```
Code is input and run in the immediate window. Output is the infinite sequence. Here's what it looks like if it was formatted into a subroutine instead:
```
b = 1
Do
    c = a + b * IIf(Rnd() < .5,1,-1)
    a = b
    b = c
    Debug.Print a
Loop
```
The [Rnd() function](https://learn.microsoft.com/en-us/office/vba/language/reference/user-interface-help/rnd-function) outputs a value in the range [0,1) hence the `<.5` check. I out the 6th term in the sequence 1,000 times (since that's an example in the question) and found the following distribution of values:
| **Value** | **Count** | **Percent** |
| --- | --- | --- |
| -8 | 45 | 4.5% |
| -4 | 48 | 4.8% |
| -2 | 252 | 25.2% |
| 0 | 322 | 32.2% |
| 2 | 264 | 26.4% |
| 4 | 47 | 4.7% |
| 8 | 22 | 2.2% |
 ]