Source-linked AI summary
Pragmatic Information, Computation, and the Efficient Market Hypothesis
Edward D. Weinberger
TL;DR
The paper addresses information theory’s lack of a measure for message meaning by examining pragmatic information and how receivers extract it. It relates extraction to computational capacity and reframes market efficiency as participant-specific computational efficiency.
Problem
Standard information measures do not quantify a transmitted message’s meaningfulness, motivating pragmatic information as a measure tied to belief changes relevant to decisions.
Method
The paper defines pragmatic information through a decision maker’s beliefs and analyzes extraction using computational models, including finite-state machines and formal-language complexity.
Results
The analysis concludes that pragmatic-information extraction depends on receiver computational capacity, while recognizing and modeling market states can require substantial computational resources.
Takeaways & Limitations
The efficient market hypothesis can be reframed as participant-specific computational efficiency: information may be pragmatically useful to some market participants but inaccessible to others.
Takeaways & Limitations
Complete market-state characterization requires the entire limit order book, private iceberg orders, and linked trading strategies, while inferring market production rules is generally NP-complete and may require years of data.
Abstract
from arXiv · showhide
We address a long standing gap in standard information theory, namely the inability of that theory to assign a measure to the amount of meaning in a transmitted message. \cite{Weinberger24} argues for a particular quantitative measure of meaning that \cite{Weinberger24} calls pragmatic information, which has many of the properties expected of it. We then prove that the amount of pragmatic information of a given message that can be extracted by a given receiver depends on the computational capacities of the receiver, in particular, the receiver's ability to recognize symbol strings at various levels of complexity within the Chomsky hierarchy of formal languages. A string may appear essentially random to a given receiver, but not to a receiver at a higher level in the hierarchy; hence, this receiver may not be able to extract any pragmatic information from such a string, even though another receiver at the appropriate level in the hierarchy could. Also, the maximum processing rates at which messages of different levels of complexity serve as a kind of pragmatic channel capacity, leading to a tradeoff between the amount of pragmatic information extracted and the extraction time. We then propose a re-framing of the efficient market hypothesis of quantitative finance to that of a participant-specific ``computational efficiency'', {\it i.e.} the claim that participants lack the computational resources necessary to use available pragmatic information to ``beat the market''. Given that market participants vary widely in computational resources, it is therefore no surprise some participants will find a given market computationally efficient, even though others will find inefficiencies. We argue that this situation will persist even in the face of any conceivable increase in compute.
1 Introduction
Standard information theory measures symbol transmission but not message meaning. The paper motivates pragmatic information as a meaning measure tied to receiver beliefs, decisions, computational abilities, and applications including market efficiency.
- A message acquires meaning through changes in a receiver’s prior beliefs, expressed through the likelihood of a particular decision.
- The paper studies how receiver computational abilities affect the amount of pragmatic information that can be extracted.
- Standard information theory addresses accurate symbol transmission, not whether a message conveys meaning or changes conduct.
- Pragmatic information distinguishes meaningful messages from random symbol strings according to their expected effects on a receiver.
- The framework is motivated partly by the efficient market hypothesis and may also relate to information-processing rates in human language.
2 A Definition of Pragmatic Information and Some Results that Justify It
The paper defines pragmatic information through how messages update a decision maker’s beliefs about a random variable and reviews properties supporting its interpretation as a measure of meaning. It also establishes decomposition, independence, and useful-message consequences of the definition.
- Pragmatic information measures belief changes produced when a message acts on a decision maker with prior probabilities over possible world states.
- Pragmatic information is nonnegative and is positive unless the message-induced probabilities equal the prior probabilities for every message.
- Pragmatically definitive messages maximize pragmatic information among available posterior distributions for fixed prior probabilities.
- Pragmatic information is additive for probabilistically independent message ensembles and completely independent decision makers, but message independence alone is insufficient.
- The definition classifies messages as disinformative, irrelevant, or useful according to their effects on the decision maker.
- If total pragmatic information is zero or negligible, the pragmatically useful-message subset must likewise contribute zero or negligible information.
3 Partitions of M
The paper studies how partitioning a message ensemble changes the information a decision maker can extract. It shows that Shannon entropy can grow without bound while pragmatic information remains bounded, and that finer partitions may add information but can impose disproportionate effort.
- Partitions of M: When many messages induce identical responses, the decision maker partitions the message ensemble into equivalence classes.
- Partitions of M: Shannon entropy can be arbitrarily large even though pragmatic information remains bounded by the decision maker’s output structure.
- Partitions of M: A different decision maker may use a different partition and extract more pragmatic information, subject to an upper bound.
- Partitions of M: Adding an output whose posterior equals its prior can reduce pragmatic information, showing that a larger state space does not necessarily increase it.
- Partitions of M: Finer partitions improve message-to-outcome mapping and correction of prior bias, but the additional effort may not be worthwhile when little new information is learned.
- Partitions of M: The partition framework connects pragmatic information to a possible rate-distortion theory based on the tradeoff between extraction effort and information gained.
4 The Effect of the Decision Maker’s Computational Capacity on Pragmatic Information
A receiver’s computational capacity determines how much pragmatic information it can extract: higher-level processors can recognize patterns that lower-level processors treat as random. The section also establishes limits, qualitative gains across the Chomsky hierarchy, and cases where pragmatic-information computation is undecidable.
- Computational limits: Finite-state receivers have a finite upper bound on pragmatic information, independent of message length or complexity.The bound depends only on the receiver’s a priori assumptions.
- Hierarchy effects: More powerful automata can extract qualitatively more pragmatic information from messages at higher levels of the Chomsky hierarchy.The paper connects strict dimension inequalities to increased pragmatic-information extraction.
- Hierarchy effects: Messages can appear random to weaker processors, preventing pragmatic-information extraction even when stronger processors can extract it.The paper gives deterministic sequences with dimF(S) = 1 or dimP(S) = 1 but dimT(S) = 0.
- Useful extraction: Enhanced computational abilities can increase pragmatically useful information without increasing the messages’ pragmatic information.The distinction arises when a receiver can better identify which messages are useful for decisions, even though Φ∆ itself is unchanged.
- Predictive interpretation: Pragmatic information can be related to predictive betting gains: conditioning on prior outcomes increases growth by the mutual information with the current outcome.The receiver’s computational model determines how conditional predictions, and therefore extracted pragmatic information, are formed.
- Computability boundary: The computation of Φ∆(M; Ω) can be undecidable when messages occupy the highest level of the Chomsky hierarchy.A general-purpose deterministic Turing-machine input processor can make Φ∆(M; Ω) Turing uncomputable.
5 Towards a “Channel Capacity” for Pragmatic Information
Pragmatic channel capacity depends on the time required to parse messages, which varies sharply with their position in the Chomsky hierarchy. Greater computational power enables recognition of more complex messages but generally reduces processing rates.
- Pragmatic channel capacity is the maximum rate at which meaning can be transmitted, with parsing time determining the effective rate.Pragmatic information remains zero until the message is parsed; for finite message ensembles, the rate can approach zero as message length grows.
- Regular languages: Finite-state machines parse regular-language messages in O(|S||m+|) time, supporting real-time processing at the lowest hierarchy level.
- Context-free languages: Context-free language recognition requires pushdown-automaton parsing and has substantially higher asymptotic complexity than regular-language recognition.The supplied passage describes boolean matrix multiplication as part of this parsing process and gives an apparent O(|m+|^3) running time before faster matrix methods are considered.
- Context-sensitive languages: Recognition becomes computationally intractable for context-sensitive languages, which are PSPACE-complete.
- Recursively enumerable languages: For general recursively enumerable languages, parsing time is generally unknowable in advance and may be arbitrarily large.A receiver may therefore wait arbitrarily long just to determine whether it understands a message.
- Only regular-language messages can generally be processed in real time, creating a tradeoff between computational power, extracted meaning, and processing speed.Higher hierarchy levels provide greater recognition power but dramatically slower processing, so a pragmatic information rate is defined only for regular languages.
6 Implications for the Efficient Market Hypothesis of Financial Economics
The paper reframes market efficiency as participant-specific computational efficiency: available information is useful only when a participant can process it well enough to guide profitable decisions. Because market states and patterns can require substantial computation, different participants can experience the same market as efficient or inefficient.
- Computational efficiency defines a market as efficient for a participant when none of that participant’s available information is pragmatically useful.This reframing accommodates exceptional performance by investors with greater computational resources.
- Markets efficient for one automata class form subsets of markets efficient for less powerful classes, and the subset relation can be strict.
- Beating the market involves reachability of profitable close-outs, not merely recognition of trade entry points.Profits require closing positions through profitable limit or market orders, making the relevant problem broader than identifying entries.
- Using all available market information is characterized as PSPACE-complete, making computational cost itself a source of market efficiency.
- Finite-state strategies such as trend following, mean reversion, index arbitrage, and triangular currency arbitrage can exploit market inefficiencies.
- Opportunities for these inefficiencies become increasingly fleeting as trading systems grow faster and more sophisticated.
- Market patterns can span multiple time scales, and more powerful computational models can succeed where finite-state models fail.Pushdown or linear-bounded automata can represent more general structures, including trends within trends.
- Market-state descriptions may be very large because profitable close-outs require considering visible and hidden order books across traded securities.This makes the input size |m+| large and creates problems for automata whose running time grows super-linearly with input length.
7 Directions for Future Research
The paper identifies several directions for extending pragmatic information theory, including dependence across decisions, cognitive biases, market complexity, and links to thermodynamic entropy.
- The current theory assumes decisions are independent of one another and of earlier inputs, leaving learning receivers outside its scope.The authors suggest messages could alter a receiver’s internal state or decision-making capabilities, while retaining the central role of computational ability.
- Cognitive biases such as loss aversion are framed as pragmatic noise that can prevent receivers from fully processing market information.The paper asks whether pragmatic information theory can develop an analogue of Shannon-theoretic noise-handling methods.
- Greater market complexity may require more processing power to separate useful information from pragmatic noise during bubbles and crashes.When that processing power is unavailable, the authors expect more pragmatic noise, which may itself trigger a bubble.
- The paper proposes further study of parallels among pragmatic information, Shannon theory, and thermodynamic entropy, especially regarding the efficient market hypothesis.It also interprets pragmatic information as the portion of total information available for potentially useful decisions, analogous to free energy.
A The Chomsky hierarchy of formal languages
The Chomsky hierarchy classifies formal languages by the grammatical rules needed to generate them, from regular languages through recursively enumerable languages. These levels correspond to increasingly expressive transformation systems and increasingly difficult membership questions.
- The membership problem asks whether a given string belongs to a language, and the hierarchy contains progressively more expressive language classes.The passage also notes that grammars may be deterministic or non-deterministic and that only some languages at one level belong to the next lower level.
- A formal language L is a subset of A∗, and its grammar specifies which strings belong to L through production rules.Production rules repeatedly replace a start symbol and non-terminals until terminal strings remain.
- The Chomsky hierarchy distinguishes regular, context free, context sensitive, and recursively enumerable languages by permitted production-rule forms.Context-sensitive rules use surrounding symbols as context, whereas recursively enumerable languages allow arbitrary transformations.
- Regular languages can express finite-state patterns, while context-free languages include patterns such as balanced parentheses that are not necessarily regular.The hierarchy’s examples illustrate that higher classes can impose relationships unavailable to simpler grammars.
- The language {w ∈ A∗ | w = a^n b^n c^n, n ≥ 1} is context sensitive but not context free.Its strings begin with equal counts of a’s, b’s, and c’s in that order, and production rules reproduce all such words.
- The Post correspondence problem exemplifies a recursively enumerable language that is not context sensitive.It asks whether tiles can be arranged so that the concatenated top and bottom strings match.
B The abstract automata that recognize the languages in the Chomsky hierarchy
Abstract automata recognize formal languages by processing input strings with different memory mechanisms. The hierarchy progresses from finite-state machines to pushdown, bounded-linear, and general Turing machines.
- An abstract automaton recognizes a language by determining whether an input string belongs to it, with recognition possible through any accepting derivation for a non-deterministic grammar.Automata, grammars, and languages may all be deterministic or non-deterministic.
- A finite state machine reads symbols using a finite set of states, an initial state, final states, and a transition table.Lambda transitions may occur without consuming an input symbol, and determinism does not reduce its language-recognition power.
- A pushdown automaton augments a finite state machine with an arbitrarily large stack that provides memory during processing.The stack supports operations such as retaining, replacing, or pushing symbols, and non-deterministic pushdown automata recognize strictly more languages than deterministic ones.
- Bounded linear and general Turing machines augment pushdown automata with a second stack, increasing their computational capabilities.A general Turing machine can equivalently be represented using states, a tape, a read head, and halting behavior.
C On the Turing Equivalence of the Matching Engine and Its Implications
The paper models smart order routing and limit-order-book actions using Minsky-machine components to establish Turing completeness. It then connects this computational power to market-state reachability and the practical limits of exchange infrastructure.
- A Minsky machine consists of registers, a controller, and instructions that increment or conditionally decrement registers while directing control flow.Its computational capabilities are equivalent to those of a Turing machine.
- The paper demonstrates Turing completeness of smart order routing on the limit order book by mapping Minsky-machine elements to SOR/LOB actions.The correspondence assumes a tick size of θ and is organized in Table 3.
- A resting limit sell order paired with an IOC buy order implements a DECJZ-like operation by reducing available inventory when a transaction occurs.The trade occurs when the IOC buy price crosses the relevant resting sell price.
- Most exchange matching engines do not provide the conditional execution assumed by the controller, whereas brokers’ smart order-routing systems do.These systems also face practical complications such as leg risk when only some basket trades execute at required prices.