🔢 mathematics

A Linear Temporal Logic of Frequencies on Series of Events

This paper introduces LTLF, a novel temporal logic equipped with measure-sensitive modal quantifiers and a Kripke-style semantics to formally express, monitor, and predict the frequency properties of event series, thereby bridging the gap between logical reasoning and empirical observation in quantitative systems.

Original authors: Melissa Antonelli, Leonardo Ceragioli, Alessandro Buda, Giuseppe Primiero

Published 2026-04-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Melissa Antonelli, Leonardo Ceragioli, Alessandro Buda, Giuseppe Primiero

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a magician pull cards from a deck. You don't know if the deck is fair or rigged. You just see the cards come out one by one: Ace, King, Queen, Ace...

At any point in the show, you might ask yourself:

How often have I seen an Ace so far? (Is it happening too much?)
If this deck is supposed to be fair, is what I'm seeing possible? (Could a fair deck produce this sequence, or is it definitely rigged?)
If the deck is fair, what are the odds the next card is an Ace?
If I keep watching, what are the chances I'll end up with exactly 50% Aces by the end?

This paper introduces a new "language" (a logic called LTLF) designed specifically to answer these questions. It's like a super-powered calculator for patterns in time.

Here is a breakdown of the paper's ideas using simple analogies:

1. The Problem: The "Black Box" vs. The "Real World"

Usually, when we study logic or math, we look at things in two separate ways:

The Ideal: "In a perfect world, a coin flip is 50/50."
The Reality: "I flipped a coin 10 times, and it came up Heads 8 times."

Most existing logic tools struggle to put these two things in the same sentence. They can tell you what should happen, or what did happen, but not how the two relate to each other in real-time.

The Paper's Solution: LTLF is a tool that lets you hold the "Ideal" and the "Reality" side-by-side and compare them instantly.

2. The Five Magic Tools (Operators)

The authors created five special "buttons" or tools to ask different types of questions about a series of events (like coin flips, server errors, or machine learning predictions).

📦 The White Box (□): "What have I seen so far?"

Analogy: You are keeping a scorecard.
What it does: It counts the actual things that have happened up to this exact second.
Example: "So far, 60% of the flips were Heads."
Use case: Checking if a machine learning model is currently biased. "Is it predicting 'Yes' too often right now?"

🌑 The Black Box (■): "Is this possible in the Ideal World?"

Analogy: You are a detective checking an alibi. You have a "Perfect Scenario" (e.g., a fair coin). You look at the current evidence and ask, "Could a fair coin have produced this specific sequence so far?"
What it does: It ignores what actually happened and asks, "Is there any way the Ideal World could look like this right now?"
Example: "I saw 10 Heads in a row. Is it possible for a fair coin to do this? Yes, it's unlikely, but possible. But if I saw 100 Heads, the Black Box says: 'No, a fair coin could never do this.'"
Use case: Detecting fraud. If the "Ideal" is a fair system, and the "Reality" breaks the rules of possibility, you know something is wrong.

🔮 The Crystal Ball (◦): "What does the future hold based on the past?"

Analogy: You are a weather forecaster looking at a storm that is already half-over.
What it does: It looks at what happened so far and calculates the probability of the entire series ending up a certain way.
Example: "We have 5 flips left. We need 3 more Heads to reach our goal of 50% Heads. What are the odds we get there?"
Use case: Predicting if a project will finish on time or if a system will meet its safety quotas by the end of the day.

⏩ The Next Step (▷): "What happens next?"

Analogy: You are betting on the very next card.
What it does: It calculates the specific probability of the immediate next event, assuming the "Ideal" rules are still in play.
Example: "We have seen 9 Heads and 1 Tail. If the coin is fair, what is the chance the next flip is a Tail?" (The answer is high, because the system needs to balance out).
Use case: Real-time control. "If the server is getting too many errors, what is the chance the next request will fail?"

⭐ The Star (⋆): "The Big Picture"

Analogy: You are looking at a map of the whole journey, not just where you are standing.
What it does: It asks about the "Ideal" distribution itself, regardless of what is happening right now.
Example: "In a perfect world, what is the frequency of Heads?" (Answer: 50%).
Use case: Setting the rules. Defining what "fair" means before the experiment even starts.

3. Why is this useful? (The "Why Should I Care?")

The paper argues that this logic is perfect for Machine Learning and AI.

Imagine you have an AI that hires people.

The Ideal: You want the AI to hire 50% men and 50% women (Fairness).
The Reality: The AI has hired 10 people, and 9 are men.

Using old logic, you might just say, "That's bad."
Using LTLF, you can ask complex questions:

"Is this streak of 9 men impossible for a fair system?" (Black Box check).
"If we keep going, what is the probability we will end up with a 50/50 split?" (Crystal Ball check).
"If the next candidate is a woman, does that fix the bias?" (Next Step check).

Summary

This paper builds a new kind of "mathematical microscope" that lets us watch a process unfold over time. It doesn't just count what happened; it constantly compares the messy reality of what we see against the perfect theory of what we expect.

It's like having a referee in a game who can instantly tell you:

The score so far.
If the score is even possible under the rules.
What the odds are of the game ending in a tie.
What the next move should be to stay fair.

This helps us build better, fairer, and more predictable computer systems.

1. Problem Statement

The paper addresses the need for formal systems to monitor and control complex quantitative systems, particularly machine learning classifiers, at runtime. Existing evaluation methods often rely on post-hoc inference, which can be computationally wasteful and fail to anticipate unacceptable outputs.

The core challenge is to formally reason about finite series of events where outcomes have specific frequency distributions. Current temporal logics (like LTL, CTL) and their probabilistic/counting extensions (PCTL, Counting LTL) generally focus on:

Forward-looking semantics (predicting the future based on the present).
Absolute counting or probabilistic thresholds without explicitly comparing actual observed frequencies against a target theoretical distribution within a single logical structure.

The authors aim to bridge the gap between formal logical reasoning and empirical observation by creating a logic that can:

Measure the frequency of outcomes in a series as it unfolds.
Check compatibility between observed partial frequencies and a desired global frequency.
Predict future outcomes based on the assumption that the series will eventually satisfy a target distribution.

2. Methodology: The LTLF Framework

The authors introduce LTLF (Linear Temporal Logic of Frequencies), a propositional logic equipped with novel, measure-sensitive modal operators.

2.1 Semantics and Structure

Model: A LTLF structure is a tuple $M = (W, R_e, F_\Omega, a)$ $M = (W, R_{e}, F_{Ω}, a)$ .
- $W$ : A finite set of worlds representing time instants in a linear series.
- $R_e$ : A reflexive, transitive, anti-symmetric, and strongly connected relation (defining a linear order).
- $F_\Omega$ : A set of assignments compatible with a well-defined probability measure $\mu_\Phi$ over a sample space $\Omega$ . This represents the "ideal" or "target" distribution.
- $a$ : A specific assignment representing the "real" or "current" observation (the actual sequence of events observed so far).
Backward-Looking Approach: Unlike standard temporal logics that look forward, LTLF evaluates formulas by looking at the past (from the current world $w_m$ back to $w_1$ ) to calculate frequencies.

2.2 Key Operators

The logic introduces five primary modal operators, each serving a distinct function in frequency analysis:

$\square_q \phi$ (White Box / Observed Frequency):
- Definition: At world $w_m$ , $\square_q \phi$ holds if the relative frequency of $\phi$ in the history $\{w_1, \dots, w_m\}$ is at least $q$ .
- Dependency: Depends on both the current world and the specific observation assignment $a$ .
- Use: Measures the actual empirical frequency of an event up to the current point.
$\blacksquare_q \phi$ (Black Box / Compatibility):
- Definition: At world $w_m$ , $\blacksquare_q \phi$ holds if there exists an assignment $a' \in F_\Omega$ such that the frequency of $\phi$ in the history is at least $q$ .
- Dependency: Depends on the world $w_m$ but is independent of the current observation $a$ . It queries the space of all possible ideal distributions.
- Use: Checks if the current partial observation is compatible with the target distribution $F_\Omega$ . It asks: "Is it still possible for the series to end up matching the ideal frequency?"
$\circ_q \phi$ (Circle / Conditional Probability):
- Definition: At world $w_m$ , $\circ_q \phi$ holds if the frequency of $\phi$ in the history is at least $q \times n$ (where $n$ is the total length of the series).
- Use: Expresses the probability of an outcome relative to the total planned series length, given current observations.
$\triangleright_q \phi$ (Next / Future Probability):
- Definition: At world $w_m$ , $\triangleright_q \phi$ holds if, assuming the current observation is compatible with $F_\Omega$ , the probability that $\phi$ occurs at the next step ( $w_{m+1}$ ) is at least $q$ .
- Use: Predicts the likelihood of the next event based on the constraint that the final series must satisfy $F_\Omega$ .
$\star_q \phi$ (Star / Global Distribution):
- Definition: $\star_q \phi$ holds if the measure of assignments in $F_\Omega$ where $\phi$ is true is at least $q$ .
- Dependency: Independent of the current world and observation.
- Use: Represents the static, global probability of an event according to the target distribution (e.g., "The coin is biased such that Heads occurs 1/3 of the time").

3. Key Contributions

Novel Modalities: The introduction of the $\blacksquare$ (Black Box) operator is the core innovation. It allows the logic to explicitly formalize the relationship between observed reality ( $a$ ) and theoretical ideals ( $F_\Omega$ ) within a single evaluation step.
Backward-Looking Semantics: The logic adopts a unique perspective where temporal operators evaluate frequencies based on the past relative to the current state, diverging from standard forward-looking temporal logics.
Formal Problem Solving: The paper demonstrates how LTLF can solve five specific classes of problems regarding event series:
1. Measuring the frequency of an outcome in a series.
2. Checking compatibility between expected and future outcomes.
3. Verifying if an observation is consistent with a desired frequency.
4. Calculating the probability of realizing a desired frequency given current data.
5. Foreseeing future outcomes (a posteriori) based on realized data and target distributions.
Theoretical Results: The authors provide theorems establishing the interdefinability of operators, monotonicity, and specific conditions under which an observation is deemed compatible or incompatible with a target distribution (e.g., Theorem 5.5 and 5.6).

4. Results and Expressiveness

The paper provides rigorous proofs and examples (using coin tosses as a guiding toy model) to demonstrate the logic's capabilities:

Compatibility Checking: The logic can detect when an observation has deviated irreversibly from a target distribution. For example, if a target frequency for "Heads" is 0.5, and the first three tosses are "Tails", the logic can formally prove that the target frequency is no longer achievable ( $\neg \blacksquare_{0.5} \text{Head}$ ).
Probability Calculation: The authors derive formulas (Theorems 5.8 and 5.9) to calculate the exact probability that a partial observation will lead to a series satisfying the target distribution, distinguishing between equiprobable and non-equiprobable outcomes.
Future Prediction: The $\triangleright$ operator allows for dynamic prediction. If a series must end with 50% Heads, and the first two tosses are Tails, the logic correctly deduces that the next toss must be Heads (probability 1) to maintain the possibility of the target distribution.

5. Significance and Applications

Runtime Monitoring: LTLF provides a formal framework for runtime verification of quantitative systems. It allows systems to stop execution early if an outcome is proven to be incompatible with safety or fairness constraints.
Machine Learning Fairness: The logic is explicitly designed to model ML classifiers as probabilistic systems. It can be used to monitor classifiers to ensure their output distributions align with user expectations or fairness constraints (e.g., ensuring demographic parity) during operation, rather than just in post-hoc analysis.
Bridging Theory and Empiricism: By unifying the "ideal" (theoretical distribution) and the "actual" (observed series) in one logical structure, LTLF offers a new tool for analyzing experimental data and stochastic processes where the goal is to verify convergence to a specific distribution.

6. Future Work

The authors note that while the logic is expressive, several areas require further investigation:

Proof Systems: Developing a sound and complete proof system and meta-theoretical results (e.g., complexity analysis).
Branching Time: Extending the logic from linear time to tree structures to handle branching scenarios.
Applications: Further concrete applications in bias mitigation for machine learning classifiers.

In summary, LTLF is a significant advancement in temporal logic, offering a rigorous, backward-looking framework specifically tailored for analyzing the frequency properties of finite event series and their alignment with theoretical distributions.