5

(Apologies if my use of terms is off - I am not a mathematician by trade and what I did learn way back was in a different language)

What I know: the total length of the stream, the body of possible events, the pop-count for each event, and the range of each event (essentially the index of the last instance of this event).

What I want: Given an incoming stream of events I am trying to predict what the next event is likely to be, i.e. calculate the probability of the next event being a particular one of the known population.

Example:

Let's say the incoming stream is

ABABCCCC (not known by the receiver)

Known by the receiver:

Length=8

Count Range 
A: 2     3

B: 2     4

C: 4     8

Ignoring the range component we can trivially calculate the probability of each event by dividing its pop-count into the total message length:

   Count Range Prob
A: 2     3     0.25
B: 2     4     0.25
C: 4     8     0.50

When looking at the range we can calculate the local probability of each event being next (by local I mean considering only the current event).

   Count Range Local prob
A: 2     3     2/3 = 0.6666
B: 2     4     2/4 = 0.5
C: 4     8     4/8 = 0.5

But how do I combine the two types of probability into one value without enumerating all combinations and testing each one to see if it matches the constraints?

It's obvious from inspection that in this particular case the probability of the next event being a C is 0.0 here as having anything but A or B as the first event would prevent all of the As and Bs from occurring within their range, but it's not clear to me what the formal calculation should look like.

-

Some more context:

In the real scenario, number of unique events can run into the low thousands while the stream length can be up to a few billions while the million range will be more typical.

I can pre-calculate a few incoming events essentially for free so I want to pick the most probably one(s) for that in an attempt to save overall cost.

Events can come and go - one of the static events is Define New Event - I did not include this fact initially because it does not affect the issue at hand. Sometimes all live ranges will be so long that the individual ranges don't matter - I can just go with the straight probability based on pop-count alone, but every once in a while there'll be short bursts of events that are short-lived but whose probability will locally exceed those of the longer-lived, more populous events. Calculation does not have to be exact - if I can calculate a reasonable trend then that will definitely help.

500 - Internal Server Error
  • 151
  • 1
    Are the events supposed to be independent of each other (in other words, why does the latest instance of an event matter)? If they are dependent, what might the relationships be? – Henry Feb 01 '21 at 15:25
  • They are dependent only in the sense that range constraints on some events may prevent other events from occurring until later in the stream, as outlined in my last paragraph. – 500 - Internal Server Error Feb 01 '21 at 15:31
  • 1
    I suspect your interesting question does not have a straightforward useful (to you) answer. If you [edit] the question to provide more context we may be able to help. How large is the real problem you want to solve - how long a stream? How many events? Would approximations do? Precalculated values, perhaps from a simulation? The more context you provide the better. – Ethan Bolker Feb 01 '21 at 16:08
  • @EthanBolker: I tried to add some more context. – 500 - Internal Server Error Feb 01 '21 at 20:09

1 Answers1

2

Roughly using the probability of seeing a letter in that slot times the probability of that slot:

In this case the $P(A)=\frac 2 3 *\frac 3 8+ 0*\frac 5 8=1/4$.

$P(B)=1/3*3/8+1*1/8*0*4/8=1/4$

$P(C)=0*4/8+1*4/8=1/2$

You still get the same answers as the naive case!

By the way in this case there are only 3 possible sequences:

AABBCCCC

ABABCCCC

BAABCCCC

It is possible to calculate various conditional probabilities.

$P(A|A)=2/6=1/3$

$P（C|C)=1$, (excluding the last C), $P(A|C)=P(B|C)=0$. Notice the rule $P(A|C)+P(B|C)+P(C|C)=1$ holds.

$P(C|B)=1/2$

$P(A|“AB”)=1/4$

...

Not sure if you can do it without enumerating possibilities. Note: if you want an answer from a “mathematician” this is not the one.

Vons
  • 11,004