#Mathematica, 154 bytes

    t={};s={1,1};(For[i=1,i<10^3,i++,While[Last@s!=#,s={1,2};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];AppendTo[t,s];s={1,2}];First@SortBy[t,Total])&