5
$\begingroup$

I code a random walk of length 100 drawn from a LaplaceDistribution:

Accumulate[RandomVariate[LaplaceDistribution[0, 1], 10000]]

I am having trouble counting the number of record events in a discrete random walk. A record occurs at time t if the value of the random walk at time t is greater than all values of the walk for all times less than t. I want a function that will let count the number of records that occur in a walk of length n.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Why do you first generate 10000 samples and then only keep 100 of them randomly? $\endgroup$ – Thies Heidecke Dec 3 '18 at 22:28
  • $\begingroup$ I've realised it is completely pointless to do that lol. $\endgroup$ – smallscot Dec 3 '18 at 22:51
  • $\begingroup$ No problem :) Just wanted to clarify if there's some deeper meaning behind it that i missed. $\endgroup$ – Thies Heidecke Dec 3 '18 at 22:53
  • $\begingroup$ Is the mean number of records in such a walk the desired end result? If so, then n Binomial[2 n, n]/2^(2 n - 1) with n the step number suffices... $\endgroup$ – ciao Dec 4 '18 at 0:48
6
$\begingroup$

Here's one take:

path = Accumulate[RandomVariate[LaplaceDistribution[0, 1], 1000]];
records = FoldList[Max, path];

ListPlot[{
  path,
  records
  }]

Mathematica graphics

records has lots of duplicates in it. It's a list where in each position we have the largest value up to that point. If we take the union of the values (or use DeleteDuplicates), we get the unique largest-so-far values, and if we count those we get the desired answer:

Length@Union[records]

52

$\endgroup$
  • $\begingroup$ Thank you. This is perfect. $\endgroup$ – smallscot Dec 3 '18 at 22:51
5
$\begingroup$

Let's generate data from a random walk first

SeedRandom[42]
walkdata = Accumulate[RandomVariate[LaplaceDistribution[0, 1], 100]]

random walk data plot

, then one way to get what you want is with a Fold:

Last@Fold[
  Function[{state,newvalue},
    With[{currentrecord=state[[1]],recordcounter=state[[2]]},
      If[newvalue > currentrecord,
        {newvalue,recordcounter+1},
        state
      ]
    ]
  ],
  {0,0},
  walkdata
]

33

During the fold we keep track of the currentrecord and the number of records (starting with {0,0}) and update it when we find a higher value, otherwise we keep the old. The endresult is the last record and the number of records we encountered from which we just keep the number of record updates (with Last).

Comparing it with C.E.s solution this mainly trades some code clarity (if that's most important definitely go with C.E.s version) for some potential speed up by saving the overhead of the Union function call. If you are dealing with long random walks or doing a lot of them this might become relevant. There is also the additional option to Compile if you need better performance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.