1
$\begingroup$
  1. I have a data set which looks like this:! http://i.imgur.com/vrDpuQ5.png

    Histogram: http://i.imgur.com/2U5QtQM.png

    There are about 10000 entries in total the Outcomes(EventId#) can be either $1,2,3,\ldots,18,19$ so from 1-19.

  2. Although it is highly debatable if the events are independent, let's assume for simplicity's sake that they are for now. The reality is that for the smaller EventId's (1,2,3) are more likely to occur after each other and especially after EventId 19. Then again, let's ignore this for now.

  3. I am looking specifically for what methodology/formula/principles would allow me to calculate the probability of EventID/Number $n$ to occur between two numbers $x_1$ and $x_2$. Or as can be seen in the first picture of the data set, the probability of the EventId/Number "17" occuring betwen two number/EventId "18". The amount of numbers between $x_1$ and $x_2$ and whether they are located before or after the number $n$, is irrelevant to us, as long as they do not exceed the numbers $n$ and $x_1$ and $x_2$.

So throughout the entire data set we are looking for the probability of events / subseries(?) like these:

2,15,3,6,7,8,2,17,16,2,13,6,7,2,3,1,6,15,   
 **18,3,6,1,2,9,10,17,14,1,6,16,4,14,18**,2,3,5,1,2

or this:

5,8,2,3,11,15,1,**18,2,3,17,3,11,6,14,16,2,1,6,18**,
 2,1,1,9,8,1,13,11,2,7,9,1,2,3,7,2,1,7

So how would I approach solving this problem. What is the solution I am looking for?

I have tried looking at almost everything the internet would offer me as a solution, cumulative distribution functions, empirical distribution functions, multivariate distribution, exponential distribution, etc., but from my understanding is that most of these things really just deal with a number/EventID occurring that is between number $x_1$ and Number $x_2$. Which is fine but it doesn't necessarily deal with for example: EventId 18 happening, and then waiting until EventId 17 happens and then waiting again until we have EventId 18. The same obviously could apply to EventId 5 happening then waiting for EventId 10 and then waiting for EventId 15 all the while not allowing any numbers/EventId in between to be higher than 10 and 15.

Now assuming I can have / expand this data set into a much much larger data set and I have much more data available, sooner or later the obvious logical conclusion is in fact that EventId 1 2 and 3 tend to follow EventId 19 and 18 more often than for the other EventId's.

But I would have to do more analysis on this using Markov chains or some other tool I assume which is why I said for the moment being, let's just assume that the EventId's are independent and random.

So yeah, I'm pretty much stuck, if anyone has an idea how to approach this problem then I'd appreciate it, quite a lot.

$\endgroup$
  • $\begingroup$ If you assume independence, then the probability is just the marginal probability.... by assumption. That's what independence means. $\endgroup$ – DWin Aug 8 '13 at 6:55
  • $\begingroup$ I see, so i probably should read through this: en.wikipedia.org/wiki/Marginal_distribution in my statistics books =) Thanks $\endgroup$ – Orbital Aug 8 '13 at 12:02
2
$\begingroup$

If coming up with an analytical solution is too difficult, you still have the option to estimate the probability of the occurrence of subsequences through simulation. One advantage of this approach is that it's pretty straight-forward to try out different assumptions. A disadvantage might be that it takes longer to compute the probabilities.

I quickly put together a little Python script to estimate the probability of observing the subsequence $18, ..., 17, ..., 18$ in a sequence $X_1, ..., X_T$ of length $T$ when the $X_t$ are independent and $P(X_t = 17) = 0.05$ and $P(X_t = 18) = 0.03$.

enter image description here

This is known as the Monte Carlo method. A simple example would be estimating the probability that rolling a die gives a six, $P(X = 6)$. The typical way we would estimate this is of course throwing the die $N$ times and counting the number of times it comes up six. We can think of this as estimating the expectation value

$$P(X = 6) = \sum_{x \in \{1, \dots, 6\}} P(X = x) s(x) = E[s(X)] \approx \frac{1}{N} \sum_{n = 1}^N s(x_n)$$

where $s(x) = 1$ if $x = 6$ and $s(x) = 0$ otherwise.

The Monte Carlo method can be applied whenever we can write the quantity of interest as an expectation. In principle, we don't even need to know $P(X = x)$, we just need to be able to draw samples from the distribution. In your case, $X$ is a sequence of numbers and $s(x)$ is 1 whenever $x$ contains the desired subsequence.

$\endgroup$
  • $\begingroup$ This... this is actually very helpful, i am not too well versed in python (just starting out while I am finishing up my studies on C# and C++). But i think i will be able to follow. Just a quick question: Could you recommend some book or a wikipedia page in order to understand the fundamentals of estimating occurences of subequences better? $\endgroup$ – Orbital Aug 8 '13 at 12:03
  • $\begingroup$ I added a few more hints. $\endgroup$ – Lucas Aug 8 '13 at 13:12
  • $\begingroup$ This is hugely awesome, i checked your answer as the solution to my question, again i cannot express enough gratitude towards your help. I think I should be able to do the rest by myself in R. Thanks! $\endgroup$ – Orbital Aug 8 '13 at 14:49

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.