📊 First-Order Optimal Testing (FOOT) Algorithm

Overview

This repository implements a First-Order Optimal Testing (FOOT) algorithm designed to minimize the expected number of binary tests required to identify an unknown outcome among a finite set of possibilities.

The project investigates the relationship between Shannon entropy (the theoretical lower bound) and an information gain–driven decision strategy, evaluating how closely a greedy algorithm approximates optimal performance.

Problem Formulation

Given:

• 10 possible outcomes
• A set of binary diagnostic tests

Each test partitions the outcome space into two subsets (0 / 1).
The objective is to construct a decision strategy that minimizes the expected number of tests required to uniquely determine the correct outcome.

Methodology

Test Generation

• Generate 15 unique binary test vectors
• Ensure balanced distribution of 0s and 1s
• Remove duplicates
• Select the 10 tests with highest entropy

Probability Modeling

• Generate a random probability distribution over 10 outcomes

• Normalize probabilities such that:

  Σ pᵢ = 1

Decision Strategy

For each possible true outcome:

1. Start with the full outcome set
2. Select the test with maximum information gain
3. Eliminate inconsistent outcomes
4. Repeat until a single outcome remains

The average number of tests across all outcomes is computed.

Theoretical Foundation

Shannon Entropy

Entropy measures uncertainty:

H(X) = − Σ p(x) log₂ p(x)

Entropy represents the theoretical minimum number of binary tests required.

Information Gain

Each test reduces uncertainty:

Gain = H(before) − H(after)

The algorithm greedily selects the test that maximizes gain at every step.

Evaluation Metrics

The implementation reports:

• Shannon entropy (theoretical lower bound)

• Average number of tests required

• Efficiency ratio:

  Ratio = Average Tests / Entropy

A ratio close to 1 indicates near-optimal performance.

Results

The algorithm achieves near-optimal efficiency, with the average number of tests closely approaching the entropy bound.

Key observations:

• Balanced, high-entropy tests significantly improve efficiency
• Poor test structure leads to redundant splits and reduced performance
• Information gain–based selection approximates optimal decision trees

Graphical Results

Graph 1 – Entropy vs Average Test Count

Graph 2 – Information Gain Distribution

Graph 3 – Efficiency Ratio Analysis

Conclusion

This project demonstrates that Shannon entropy provides a tight lower bound on binary decision complexity.

A greedy information gain strategy achieves near-optimal performance, validating entropy-driven decision design in practical test selection scenarios.