# Generate a random Fibonacci sequence

I want to generate the random sequence defined by $a_n = a_{n-2} + \beta(n)a_{n-1}$ where $\beta$ takes values $\pm1$. My attempt is

 RecurrenceTable[{a[n] == a[n - 2] + (-1)^(RandomInteger[{0, 1}])*a[n - 1],
a[0] == 1, a[1] == 1}, a, {n, 0, 10}]


But of course, RandomInteger only computes on the first loop, and then saves that value for all subsequence computations. I found this solution here:

 r[n_]:=RandomInteger[{0,1}];
rfib[0] = 1;
rfib[1] = 1;
rfib[n_] := rfib[n] = rfib[n - 2] + (-1)^r[n]*rfib[n - 1];
Table[rfib[i],{i,0,10}]


However, I am wondering if my original intuition can be salvaged. I.e., is there a way to use RandomInteger inside RecurrenceTable and get a new integer each time?

Edit:

After posting this and looking for something else, I found this post. From this, I can write the code as

 rr[n_?NumericQ]:=RandomInteger[{0,1}];
RecurrenceTable[{a[n] == a[n - 2] + (-1)^(rr[n])*a[n - 1],
a[0] == 1, a[1] == 1}, a, {n, 0, 10}]


as I originally wanted to.

• Where does this come from? Is it meant to model some particular physical problem? – bill s Sep 15 '17 at 12:34

One way to approach this is to directly implement the recursion:

Clear[a];
a[n_] := a[n] = RandomChoice[{-1, 1}] a[n - 1] + a[n - 2];
a[0] = a[1] = 1;


For example, the first 20 terms might be:

a[#] & /@ Range[20]
{1, 2, 1, -1, -2, -1, 1, 2, 1, 3, 2, -1, -3, -4, -1, 3, 4, 7, 3, -4}

• Doesn't RandomInteger[{-1,1}] allow for the choice of zero? Other than that question, I see how this works. As a side note, I want my subtractions to go left to right, so I would put the random $\pm1$ with the $n-1$ term. – Trevor Sep 15 '17 at 11:53
• OK -- I've changed the placement of the randomness, and used RandomChoice instead of RandomInteger. – bill s Sep 15 '17 at 12:34

Just another way:

func[a0_, a1_, n_] := Module[{r = RandomChoice[{-1, 1}, n]},
FoldList[{#1[[2]], #1[[1]] + #2 #1[[2]]} &, {a0, a1}, r]] [[All,
1]]


Examples:

• I was looking at FoldList but my ultimate goal was to generate the arcsine distribution that occurs when one varies the heads/tails probability of random Fibonacci sequences (when the coin is fair, you get Viswanath's number as the growth rate, and when the coin is 100% heads, you get the Golden Ratio,) so I needed a clean/fast way to get very large terms. FoldList just didn't feel right to me for that. Your example is quite nice, though. – Trevor Sep 15 '17 at 11:55
• @Trevor "Doesn't feel nice" isn't really an argument. :P Is there an actual practical problem you expect? Performance? Then I would make a compiled function, but still retain this basic design. I did not pay attention when I posted my answer (as you can see it's very similar), but now that I read ubpdqn's carefully, I think his should perform better as it generates the random number in bulk (instead of calling RandomChoice in each iteration) – Szabolcs Sep 15 '17 at 13:04

I would use NestList or Nest:

NestList[
{Last[#], {1, RandomChoice[{-1, 1}]}.#} &,
{1, 1}, (* two initial values in the sequence *)
100
][[All, 2]]


This is directly compilable:

cf = Compile[{{a0, _Integer}, {a1, _Integer}, {n, _Integer}},
NestList[
{Last[#], {1, RandomChoice[{-1, 1}]}.#} &,
{a0, a1},
n
][[All, 2]]
]


There is no MainEvaluate in the compiled function, but it will switch back to standard evaluation as soon as the values exceed $2^{63}-1$ (on a 64-bit machine).