1

I want a function which takes, as input, the number of seconds elapsed since the last time it was called, and returns true or false for whether an event should have happened in that time period. I want it such that it will fire, on average, once per X time passed, say 5 seconds. I also am interested if it's possible to do without any state, which the answer from this question used.

I guess to be fully accurate it would have to return an integer for the number of events that should've happened, in the case of it being called once every 10*X times or something like that, so bonus points for that!

Community
  • 1
  • 1
Claudiu
  • 224,032
  • 165
  • 485
  • 680
  • how is this different than: foo(time_elapsed) { return floor(time_elapsed/X); }? – fairidox Feb 14 '11 at 05:22
  • @anonymous_21321: it's a discrete event. it doesn't happen .2 at a time, it happens all at once. – Claudiu Feb 14 '11 at 13:33
  • @anonymous_21321: oh even worse, if i want 1 event every second, and your func is always called with 0.2, it'll never fire an event! – Claudiu Feb 14 '11 at 13:45
  • I think if you want to model the process as _random_, your function should return a _probability_, and not a boolean value. – Dr. belisarius Feb 14 '11 at 22:30
  • @belisarius: hmm an interesting point. that works for me! provide an answer that does it and i'll look it over. it shouldnt do something silly like return 1.0 if interval >= X though – Claudiu Feb 15 '11 at 02:20
  • I'm in doubt about answering, because what you have there is a Poison process, and that is already in @Norman's answer. You just need to mess with probabilities, and not boolean values. Instead of asking if _an event should have happened_ you should ask _What is the probability of having N events ocurred?_ – Dr. belisarius Feb 15 '11 at 02:45
  • @belisarius: oh i see your point. you would split Norman's answer in two. One would return an array with the probability of that many events having happened at each index, e.g. [0.9, 0.08, 0.01, 0.001, ...], cut off at some point cause no reason to go on to infinity. so returns a probability distribution. then another function can take it and return how many events have happened. that works, but i don't see where i wouldn't always use both functions together. – Claudiu Feb 15 '11 at 15:19
  • @Claudiu Because the sentence _how many events have happened_ is essentially rotten. You have to think in terms of probabilities. What you have is an **Expectancy** value for the number of events that _may_ have occurred. – Dr. belisarius Feb 15 '11 at 15:36
  • @belisarius: ah true, i failed to mention that i'm making a graphical application where i want something to happen randomly, with these characteristics, so in my case i do want events to [i]actually[/i] happen. so yea in the past 0.15 seconds, 0 event may have happened with 90%, 1 event with 9%, 2 events with .9%, etc., but i don't really care, i just want to know whether i should actually make an event happen. to make that explicit by rephrasing my rotten sentence, "another function can take it and simulate events happening based on those probabilities" – Claudiu Feb 15 '11 at 16:44
  • @Claudiu Now you are really on the good track! :D – Dr. belisarius Feb 15 '11 at 17:00

2 Answers2

2

It sounds like you're describing a Poisson process, with the mean number of events in a given time interval is given by the Poisson distribution with parameter lambda=1/X.

The way to use the expression on the latter page is as follows, for a given value of lambda, and the parameter value of t:

  1. Calculate a random number between zero and one; call this p
  2. Calculate Pr(k=0) (ie, exp(-lambda*t) * (lambda*t)**0 / factorial(0))
  3. If this number is bigger than p, then the number of simulated events is 0. END
  4. Otherwise, calculate Pr(k=1) and add it to Pr(k=0).
  5. If this number is bigger than p, then the answer is 1. END
  6. ...and so on.

Note that, yes, this can end up with more than one event in a time period, if t is large compared with 1/lambda (ie X). If t is always going to be small compared to 1/lambda, then you are very unlikely to get more than one event in the period, and so the algorithm is simplified considerably (if p < exp(-lambda*t), then 0, else 1).

Note 2: there is no guarantee that you will get at least one event per interval X. It's just that it'll average out to that.

(the above is rather off the top of my head; test your implementation carefully)

Norman Gray
  • 11,978
  • 2
  • 33
  • 56
  • note 2 is important! otherwise it would not be fully random. so i would iterate on k until i get a number >= p. i guess some optimization is needed, although it should be pretty unlikely to ever need to iterate too much since the chance of multiple events happening in a small interval is low – Claudiu Feb 14 '11 at 16:31
  • Why would you iterate? In a given interval t, you'll get the possibility of 0, 1, 2, ... events, and the Poisson distribution lets you get the right proportion of each. If the interval t is small then yes, you can make the _approximation_ that the probability of more than 1 event is small, but that becomes a poor approximation as t increases towards X (= 1/lambda). – Norman Gray Feb 14 '11 at 19:41
  • Step 6: "... and so on" = iterate steps 2-5, no? if Pr(k=0)>p, return 0; if Pr(k=0)+Pr(k=1)>p, return 1; if Pr(k=0)+Pr(k=1)+Pr(K=2)>p, return 2, etc... that is iteration – Claudiu Feb 15 '11 at 02:21
  • @Claudiu You're quite right, sorry -- I completely misread your comment. As you say, the number of events, k, would be small if (lambda*t) is small compared to X. – Norman Gray Feb 15 '11 at 11:17
0

Asssume some event type happens on average once per 10 seconds, and you want to print a simulated list of timestamps on which the events happened.

A good method would be to generate a random integer in the range [0,9] each 1 second. If it is 0 - fire the event for this second. Of course you can control the resolution: You can generate a random integer in the range [0,99] each 0.1 second, and if it comes 0 - fire the event for this DeciSecond.

Assuming there is no dependency between events, there is no need to keep state.

To find out how many times the event happens in a given timeslice - just generate enough random integers - according to the required resolution.

Edit

You should use high resolution (at least 20 randoms per period of one event) for the simulation to be valid.

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85
  • consider i don't control elapsed time - it's just called with the elapsed time. i dnno if it works. say i want 1 event per second. so if elapsed time is 1, then you would have me fire it, guaranteed. if elapsed time is 0.5 twice, youd have a 50% chance on two occasions, which gives 75% chance for the event to happen at least once in one second. if elapsed time is 0.33 three times, that gives 89% chance for it to happen. it's no good, its not consistent. – Claudiu Feb 14 '11 at 13:38
  • Sure it's no consistent - you are changing the resolution! The probabily for the the event to happen at least once per seconds converges to limit((1-1/x)^x)=1/e – Lior Kogan Feb 14 '11 at 18:26
  • Nonetheless, The average number of events per period will be 1. Try to simulate it with resolution of period/10000, for 100,000 periods. You should have a total of about 100,000 events. – Lior Kogan Feb 14 '11 at 18:44
  • @Lior: hmm yeah i see that it works, though i don't understand why.. an explanatino would be nice; but the issue is still that i don't control the resolution, so what to do if the resolution is worse than the interval? – Claudiu Feb 15 '11 at 02:28
  • Actually you do control the resolution. Suppose the event happens on average once per second, and you want to simulate the number of events in 5 seconds: run 5*x trails with probability of (1/x) for each trail, where x is your resolution (20 or higher). – Lior Kogan Feb 15 '11 at 06:11
  • You don't need to simulate anything here -- the process is very well-understood mathematically, so you can go straight to the answer (the Poisson distribution) without simulation. That's both faster _and_ easier than simulation. – Norman Gray Feb 15 '11 at 11:20
  • @Lior: ah i didn't state it in this question, but i'm creating a graphical app where the resolution is basically the FPS, which depends on a number of factors outside of my control – Claudiu Feb 15 '11 at 16:41