Omöjlighet av ett spelsystem
Principen om omöjligheten av ett spelsystem är ett begrepp i sannolikhet . Den säger att i en slumpmässig sekvens ändrar det metodiska urvalet av delsekvenser inte sannolikheten för specifika element. Den första matematiska demonstrationen tillskrivs Richard von Mises (som använde termen kollektiv snarare än sekvens).
Principen säger att ingen metod för att bilda en undersekvens av en slumpmässig sekvens (spelsystemet) förbättrar oddsen för en specifik händelse. Till exempel ger en sekvens av rättvisa myntkast lika och oberoende 50/50 chanser för huvud och svans. Ett enkelt system med att satsa på heads var 3:e, 7:e eller 21:e kast, etc., ändrar inte oddsen att vinna i det långa loppet . Som en matematisk konsekvens av beräkningsteorin kan mer komplicerade vadslagningsstrategier (som en martingal ) inte heller förändra oddsen i det långa loppet.
Von Mises matematiska demonstration definierar en oändlig sekvens av nollor och ettor som en slumpmässig sekvens om den inte är partisk genom att ha egenskapen frekvensstabilitet . Med denna egenskap stabiliseras frekvensen av nollor i sekvensen på 1/2, och varje möjlig delsekvens som väljs med någon systematisk metod är inte heller partisk.
Sekvensvalskriteriet är viktigt, för även om sekvensen 0101010101... inte är partisk, resulterar valet av de udda positionerna i 000000... vilket inte är slumpmässigt. Von Mises definierade inte helt vad som utgjorde en "riktig" urvalsregel för undersekvenser, men 1940 definierade Alonzo Church det som vilken rekursiv funktion som helst som efter att ha läst de första N elementen i sekvensen avgör om den vill välja elementnummer N+1. Church var en pionjär inom området för beräkningsbara funktioner, och definitionen han gjorde förlitade sig på Church Turing-uppsatsen för beräkningsbarhet.
I mitten av 1960-talet föreslog AN Kolmogorov och DW Loveland oberoende av varandra en mer tillåtande urvalsregel. Enligt deras uppfattning var Churchs rekursiva funktionsdefinition för restriktiv genom att den läste elementen i ordning. Istället föreslog de en regel baserad på en delvis beräkningsbar process som efter att ha läst några N element i sekvensen bestämmer om den vill välja ett annat element som inte har lästs ännu.
AN Kolmogorovs arbete med att betrakta en ändlig sekvens slumpmässigt (med avseende på en klass av datorsystem) om något program som kan generera sekvensen är minst lika lång som sekvensen i sig.