Semirandomness

Semirandomness is a concept used in computer science and information theory to describe sequences or objects that exhibit some, but not all, properties of true randomness. While a truly random sequence is unpredictable and has no discernible patterns, a semirandom one may appear random at first glance or in many statistical tests, but still possess underlying structure or predictability.

One way to understand semirandomness is through the lens of algorithmic information theory. A sequence is considered random if its shortest possible description is roughly the same length as the sequence itself. A semirandom sequence, in contrast, can be generated by a relatively simple algorithm, meaning its description is much shorter than the sequence. This implies that the sequence is not truly random, as its generation process is deterministic, even if the output appears chaotic.

Another perspective comes from pseudorandomness. Pseudorandom number generators (PRNGs) produce sequences that are statistically indistinguishable from random sequences for many practical purposes. However, because they are generated by deterministic algorithms with a fixed seed, the entire sequence is determined by that seed. If the seed is known, or if the PRNG is flawed, the "randomness" can be broken. Semirandomness can be seen as a broader category that encompasses pseudorandomness, as well as other forms of sequences that possess partial random-like qualities.

The concept of semirandomness is relevant in areas like cryptography, where predictable patterns can compromise security, and in scientific simulations, where the quality of randomness can affect the validity of results. Distinguishing between true randomness and semirandomness is crucial for understanding the limitations and applications of various generative processes.