Normální číslo - Normal number

V matematice se říká , že reálné číslo je jednoduše normální v celočíselné bázi b, pokud je jeho nekonečná posloupnost číslic rozložena rovnoměrně v tom smyslu, že každá z hodnot b číslic má stejnou přirozenou hustotu  1/ b . Číslo je v základu b normální, pokud pro každé kladné celé číslo n mají všechny možné řetězce n číslic dlouhé hustotu  b ^{- n} .

Intuitivně číslo, které je prostě normální, znamená, že žádná číslice se nevyskytuje častěji než kterákoli jiná. Pokud je číslo normální, žádná konečná kombinace číslic dané délky se nevyskytuje častěji než jakákoli jiná kombinace stejné délky. Normální číslo lze považovat za nekonečnou posloupnost mincí ( binárních ) nebo rolí kostky ( základ 6 ). I když bude existovat sekvence jako 10, 100 nebo více po sobě jdoucích ocasů (binární) nebo pět (základ 6) nebo dokonce 10, 100 nebo více opakování sekvence, jako je ocasní hlava (dvě po sobě jdoucí mince) nebo 6 -1 (dva po sobě jdoucí hody kostkou), bude také stejně mnoho z jakékoli jiné sekvence stejné délky. Žádná číslice ani sekvence nejsou „upřednostňovány“.

Číslo je považováno za naprosto normální, pokud je normální ve všech celočíselných základnách větších nebo rovných 2.

I když lze poskytnout obecný důkaz, že téměř všechna reálná čísla jsou normální (což znamená, že množina neobvyklých čísel má Lebesgueovu míru nula), tento důkaz není konstruktivní a ukázalo se, že jen několik konkrétních čísel je normální. Například Chaitinova konstanta je normální (a nelze ji spočítat ). Obecně se věří, že (vypočítatelná) čísla √ 2 , π a e jsou normální, ale důkaz zůstává nepolapitelný.

Definice

Nechť Σ je konečná abeceda z b -digits a Σ ^∞ množina všech sekvencí , které mohou být vyvozeny z této abecedy. Nechť S ∈ Σ ^∞ je taková posloupnost. Pro každou A v å nechat N _S ( , n ) označuje počet, kolikrát se číslice A se objeví v prvních n číslic sekvencí S . Říkáme, že S je prostě normální, pokud je limit

${\ Displaystyle \ lim _ {n \ to \ infty} {\ frac {N_ {S} (a, n)} {n}} = {\ frac {1} {b}}}$

pro každé a . Nyní w být jakýkoliv konečný řetězec v å ^* a nechat N _S ( m , n ) je počet dob řetězec w objeví jako podřetězec v prvních n číslic sekvencí S . (Například pokud S = 01010101 ..., pak N _S (010, 8) = 3.) S je normální, pokud pro všechny konečné řetězce w ∈ Σ ^∗ ,

${\ Displaystyle \ lim _ {n \ to \ infty} {\ frac {N_ {S} (w, n)} {n}} = {\ frac {1} {b^{| w |}}}}}$

kde | w  | označuje délku řetězce w . Jinými slovy, S je normální, pokud se všechny řetězce stejné délky vyskytují se stejnou asymptotickou frekvencí. Například v normální binární sekvenci (posloupnost nad abecedou {0,1}) se 0 a 1 vyskytují s frekvencí ¹ ⁄ ₂ ; 00, 01, 10 a 11 každý se vyskytuje s frekvencí ¹ / ₄ ; 000, 001, 010, 011, 100, 101, 110 a 111 se vyskytují s frekvencí ¹ ⁄ ₈ atd. Zhruba řečeno, pravděpodobnost nalezení řetězce w v jakékoli dané poloze v S je přesně taková, jaká se očekávala, pokud sekvence měla byly vyrobeny náhodně .

Předpokládejme nyní, že b je celé číslo větší než 1 a x je skutečné číslo . Uvažujme expanzi nekonečné číselné sekvence S _{x, b} z x v soustavě pozičních čísel základny b (desetinnou čárku ignorujeme). Říkáme, že x je jednoduše normální v bázi b, pokud je posloupnost S _{x, b} jednoduše normální a že x je normální v bázi b, pokud je posloupnost S _{x, b} normální. Číslo x se nazývá normální číslo (nebo někdy naprosto normální číslo ), pokud je v základu b normální pro každé celé číslo b větší než 1.

Daná nekonečná posloupnost je buď normální, nebo není normální, zatímco reálné číslo s různou expanzí báze b pro každé celé číslo b ≥ 2 může být normální v jedné bázi, ale v jiné není (v takovém případě to není normální číslo ). Pro báze r a s s log r  / log s racionální (takže r = b ^m a s = b ⁿ ) je každé číslo normální v základu r normální v základu s . Pro báze r a s s iracionálním log r  / log s existuje nespočetně mnoho normálních čísel v každé bázi, ale ne v druhé.

Disjunctive sekvence je sekvence, ve kterém se každý konečný řetězec. Normální sekvence je disjunktivní, ale disjunktivní sekvence nemusí být normální. Bohatý číslo v základním b je ten, jehož expanze v základním b je disjunctive: ten, který je disjunctive každému základna se nazývá absolutně disjunctive nebo je řekl, aby byl lexikon . Normální číslo v základně b je bohaté na základnu b , ale ne nutně naopak. Skutečné číslo x je bohaté na základnu b právě tehdy, pokud je množina { xb ⁿ mod 1:  n ∈ N} hustá v jednotkovém intervalu .

Definovali jsme několik být prostě normální v základním b Pokud se zobrazí každá jednotlivá číslice s frekvencí 1 / B . Pro danou základnu b může být číslo jednoduše normální (ale ne normální nebo b -husté), b -husté (ale ne prostě normální nebo normální), normální (a tedy jednoduše normální a b -husté), nebo žádné z těchto . Číslo je naprosto neobvyklé nebo naprosto abnormální, pokud není jednoduše normální na žádné bázi.

Vlastnosti a příklady

Koncept normálního čísla představil Émile Borel  ( 1909 ). Pomocí lemma Borel -Cantelli dokázal, že téměř všechna reálná čísla jsou normální, a prokázal existenci normálních čísel. Wacław Sierpiński  ( 1917 ) ukázal, že je možné určit konkrétní takové číslo. Becher a Figueira ( 2002 ) dokázali, že existuje vyčíslitelné naprosto normální číslo. Ačkoli tato konstrukce nedává přímo číslice sestrojených čísel, ukazuje, že je v zásadě možné vyjmenovat všechny číslice konkrétního normálního čísla.

Množina neobvyklých čísel, přestože je „velká“ ve smyslu toho, že je nepočitatelná , je také nulová množina (protože její Lebesgueova míra jako podmnožina reálných čísel je nulová, takže v podstatě nezabírá žádné místo v reálném čísla). Také neobvyklá čísla (stejně jako normální čísla) jsou v realitách hustá: množina neobvyklých čísel mezi dvěma odlišnými reálnými čísly není prázdná, protože obsahuje každé racionální číslo (ve skutečnosti je nespočetně nekonečný a dokonce i společný ). Například existuje nespočetně mnoho čísel, jejichž desetinná rozšíření (v základu 3 nebo vyšším) neobsahují číslici 1 a žádné z těchto čísel není normální.

Champernowne je konstantní

0,1234567891011121314151617181920212223242526272829 ...,

získané spojením desítkových reprezentací přirozených čísel v pořadí, je v základu 10 normální. Podobně jsou různé varianty Champernownovy konstanty (provedené provedením stejného zřetězení v jiných základnách) v příslušných bázích normální (například základna) -2 Champernownova konstanta je normální na bázi 2), ale na jiných základnách nebyla prokázána normální.

Konstanta Copeland – Erdős

0,23571113171923293137414347535961677173798389 ...,

získané spojením prvočísel na základně 10, je normální na základně 10, jak dokázali AH Copeland a Paul Erdős  ( 1946 ). Obecněji tito autoři dokázali, že skutečný počet reprezentovaný v základu b zřetězením

0. f (1) f (2) f (3) ...,

kde f ( n ) je n ^-tý prvočísel vyjádřený v bázi b , je normální v bázi b . Besicovitch  ( 1935 ) dokázal, že číslo reprezentované stejným výrazem, s f ( n ) = n ² ,

0,149162536496481100121144 ...,

získané spojením čtvercových čísel v základně 10, je normální v základu 10. Harold Davenport a Erdős ( 1952 ) dokázali, že číslo reprezentované stejným výrazem, přičemž f je jakýkoli nekonstantní polynom, jehož hodnoty na kladných celých číslech jsou kladná celá čísla , vyjádřeno v základu 10, je v základu 10 normální.

Nakai a Shiokawa ( 1992 ) dokázali, že pokud f ( x ) je jakýkoli nekonstantní polynom se skutečnými koeficienty, že f ( x )> 0 pro všechna x > 0, pak skutečné číslo reprezentované zřetězením

0. [ f (1)] [ f (2)] [ f (3)] ​​...,

kde [ f ( n )] je celá část o f ( n ), vyjádřené v základním B , je normální v základním b . (Tento výsledek zahrnuje jako zvláštní případy všechny výše uvedené výsledky Champernowne, Besicovitch a Davenport & Erdős.) Autoři také ukazují, že stejný výsledek platí ještě obecněji, když f je jakákoli funkce formuláře

f ( x ) = α · x ^β + α ₁ · x ^{β ₁} + ... + α _d · x ^{β _d} ,

kde αs a βs jsou reálná čísla s β> β ₁ > β ₂ > ...> β _d ≥ 0, a f ( x )> 0 pro všechna x > 0.

Bailey a Crandall ( 2002 ) ukazují explicitní nespočetně nekonečnou třídu b -normálních čísel narušením Stonehamových čísel .

Bylo nepolapitelným cílem dokázat normálnost čísel, která nejsou uměle konstruována. Zatímco √ 2 , π , ln (2) , a e jsou silně považovány za normální, stále není známo, zda jsou normální nebo ne. Nebylo ani prokázáno, že všechny číslice se ve skutečnosti vyskytují nekonečně mnohokrát v desítkové expanzi těchto konstant (například v případě π není známo, že by platilo populární tvrzení „každý řetězec čísel se nakonec vyskytuje v π“) ). Rovněž se předpokládalo, že každé iracionální algebraické číslo je naprosto normální (což by znamenalo, že √ 2 je normální) a v žádné bázi nejsou známy žádné protipříklady. Žádné iracionální algebraické číslo však nebylo prokázáno jako normální v žádné bázi.

Nestandardní čísla

Žádné racionální číslo není v žádné bázi normální, protože číselné sekvence racionálních čísel jsou nakonec periodické . Racionální číslo však může být v konkrétní bázi jednoduše normální. Například v základu 10 je to prostě normální. ${\ displaystyle {\ frac {13 {,} 717 {,} 421} {1 {,} 111 {,} 111 {,} 111}} = {\ frac {123, \! 456, \! 789} {9 , \! 999, \! 999, \! 999}} = 0. {\ Overline {0123456789}}}}$

Martin ( 2001 ) uvádí příklad iracionálního čísla, které je naprosto abnormální. Nechat

${\ Displaystyle f \ left (n \ right) = {\ begin {cases} n^{\ frac {f \ left (n-1 \ right)} {n-1}}, & n \ in \ mathbb {Z} \ cap \ left [3, \ infty \ right) \\ 4, & n = 2 \ end {cases}}}$

${\ Displaystyle \ alpha = \ prod _ {m = 2}^{\ infty} \ left ({1-{\ frac {1} {f \ left (m \ right)}}}} \ right) = \ left ( 1-{\ frac {1} {4}} \ right) \ left (1-{\ frac {1} {9}} \ right) \ left (1-{\ frac {1} {64}} \ right ) \ left (1-{\ frac {1} {152587890625}} \ \ right) \ left (1-{\ frac {1} {6^{\ left (5^{15} \ right)}}}} \ right ) \ ldots = 0,656249999995656991 \ underbrace {99999 \ ldots 99999} _ {23,747,291,559} 8528404201690728 \ ldots}$

Pak α je Liouvilleovo číslo a je naprosto abnormální.

Vlastnosti

Mezi další vlastnosti normálních čísel patří:

• Každé nenulové reálné číslo je součinem dvou normálních čísel. To vyplývá z obecného faktu, že každé číslo je součinem dvou čísel ze sady, pokud má doplněk X míru 0.${\ Displaystyle X \ subseteq \ mathbb {R} ^{+}}$
• Pokud x je normální v základně B a ≠ 0 je racionální číslo, pak je také normální v základním b .${\ Displaystyle x \ cdot a}$
• Pokud je hustý (pro každého dostatečně velký n , ) a jsou základními b expanzemi prvků A , pak je počet , vytvořený zřetězením prvků A , v základu b normální (Copeland a Erdős 1946) . Z toho vyplývá, že Champernowneovo číslo je v základu 10 normální (protože množina všech kladných celých čísel je evidentně hustá) a že konstanta Copeland – Erdős je v základu 10 normální (protože z věty o prvočísle vyplývá, že množina prvočísel je hustá ).${\ Displaystyle A \ subseteq \ mathbb {N}}$${\ Displaystyle \ alpha <1}$${\ Displaystyle | A \ cap \ {1, \ ldots, n \} | \ geq n^{\ alpha}}$${\ displaystyle a_ {1}, a_ {2}, a_ {3}, \ ldots}$${\ Displaystyle 0.a_ {1} a_ {2} a_ {3} \ ldots}$
• Sekvence je normální právě tehdy, když se každý stejně dlouhý blok objeví se stejnou frekvencí. (Blok délky k je podřetězec délky k objevující se na místě v sekvenci, která je násobkem k : např. První blok délky k v S je S [1 .. k ], druhý blok délky k je S [ k +1..2 k ] atd.) To bylo implicitní v práci Ziv a Lempel ( 1978 ) a bylo to výslovně uvedeno v práci Bourkeho, Hitchcocka a Vinodchandrana ( 2005 ).
• Číslo je v základu b normální, a to pouze tehdy, je -li v základu b ^k pro všechny prostě normální . To vyplývá z předchozí normalizace bloku: Vzhledem k tomu, že n ^-tý blok délky k v expanzi její základny b odpovídá n ^-té číslici v expanzi její základny b ^k , je číslo v základně b ^k jednoduše normální právě tehdy, když bloky délky k se objeví v jeho základně b expanze se stejnou frekvencí.${\ Displaystyle k \ in \ mathbb {Z} ^{+}}$
• Číslo je normální právě tehdy, když je prostě normální v každé základně. To vyplývá z předchozí charakterizace normality základny b .
• Číslo je b -normální tehdy a jen tehdy, existuje -li sada kladných celých čísel, kde je číslo jednoduše normální v základnách b ^m pro všechny Žádná konečná sada nestačí k tomu, aby ukázala, že číslo je b -normální.${\ Displaystyle m_ {1} <m_ {2} <m_ {3} <\ cdots}$${\ Displaystyle m \ in \ {m_ {1}, m_ {2}, \ ldots \}.}$
• Všechny normální sekvence jsou uzavřeny pod konečnými variacemi : přidání, odebrání nebo změna konečného počtu číslic v jakékoli normální sekvenci ponechá normální. Podobně, pokud je konečný počet číslic přidán, odebrán nebo změněn v jakékoli jednoduše normální sekvenci, nová sekvence je stále jednoduše normální.

Připojení ke strojům s konečným stavem

Agafonov ukázal rané spojení mezi stroji s konečným stavem a normálními sekvencemi: každá nekonečná subsekvence vybraná z normální sekvence pravidelným jazykem je také normální. Jinými slovy, pokud člověk provozuje stroj s konečným stavem v normální sekvenci, kde každý ze stavů stroje s konečným stavem je označen buď „výstup“ nebo „žádný výstup“, a stroj vydá číslici, kterou přečte jako další po zadání „výstup“, ale nevydá další číslici po zadání „stavu bez výstupu“, pak bude sekvence, kterou vydává, normální.

Hlubší spojení existuje s gamblery s konečným stavem (FSG) a bezztrátovými kompresory s konečným stavem (ILFSC).

• Konečných stavu gambler (aka konečných stav martingale ) je konečný-státní stroj nad konečnou abecedou , jejíž každý stavů je označena procenta peněz vsadit na každou číslici v . Například u FSG nad binární abecedou aktuální stav q vsadí určité procento peněz hráče na bit 0 a zbývající část peněz hráče na bit 1. Peníze vsazené na číslici, která přijde jako další v vstup (celkové peníze krát procentuální sázka) se vynásobí a zbytek peněz je ztracen. Po načtení bitu FSG přechází do dalšího stavu podle vstupu, který přijal. FSG d uspěje na nekonečné sekvenci S, pokud od $ 1 vydělá neomezené peníze sázením na sekvenci; tj. pokud${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma = \ {0,1 \}}$${\ displaystyle q_ {0} \ v [0,1]}$${\ displaystyle q_ {1} = 1-q_ {0}}$${\ displaystyle | \ Sigma |}$

${\ Displaystyle \ limsup _ {n \ to \ infty} d (S \ upharpoonright n) = \ infty,}$

kde je množství peněz, které má hráč d po přečtení prvních n číslic S (viz limit superior ).${\ Displaystyle d (S \ upharpoonright n)}$

• Konečných stav kompresoru je konečný automat s výstupní řetězce označování jeho přechody stavů , včetně případně prázdný řetězec. (Protože se ze vstupní sekvence pro každý přechod stavu načítá jedna číslice, je nutné, aby bylo možné výstup prázdného řetězce dosáhnout, aby se vůbec dosáhlo jakékoli komprese). Informační bezeztrátový konečný stavový kompresor je konečný stavový kompresor, jehož vstup lze jednoznačně obnovit z jeho výstupu a konečného stavu. Jinými slovy, pro konečný stav kompresoru C se stavovou sadou Q je C bezztrátová informace, pokud funkce , mapující vstupní řetězec C na výstupní řetězec a konečný stav C , je 1–1 . Pomocí ILFSC lze implementovat kompresní techniky, jako je Huffmanovo kódování nebo Shannon -Fano kódování. ILFSC C komprimuje nekonečnou sekvenci S, pokud${\ displaystyle f: \ Sigma ^{*} \ to \ Sigma ^{*} \ times Q}$

${\ Displaystyle \ liminf _ {n \ to \ infty} {\ frac {| C (S \ upharpoonright n) |} {n}} <1,}$

kde je počet číslic výstupu ze strany C po přečtení prvních n číslice S . Kompresní poměr (dále mez nižší shora) může být vždy na stejnou hodnotu 1, 1-státní ILFSC že jednoduše kopíruje jeho vstupu k výstupu.${\ Displaystyle | C (S \ upharpoonright n) |}$

Schnorr a Temper ukázali, že žádný FSG nemůže uspět v žádné normální sekvenci, a Bourke, Hitchcock a Vinodchandran ukázali opak . Proto:

Sekvence je normální právě tehdy, pokud neexistuje žádný hráč s konečným stavem, který by v ní uspěl .

Ziv a Lempel ukázali:

Sekvence je normální právě tehdy, když je nekomprimovatelná jakýmkoli bezztrátovým kompresorem s konečným stavem informací

(ve skutečnosti ukázaly, že optimální kompresní poměr sekvence přes všechny ILFSC je přesně její míra entropie , kvantitativní měřítko její odchylky od normality, což je 1 přesně, když je sekvence normální). Protože algoritmus komprese LZ komprimuje asymptoticky stejně jako jakýkoli ILFSC, znamená to, že algoritmus komprese LZ může komprimovat jakoukoli neobvyklou sekvenci.

Tyto charakterizace normálních sekvencí lze interpretovat tak, že znamenají „normální“ = „náhodný konečný stav“; tj. normální sekvence jsou přesně ty, které vypadají náhodně pro jakýkoli počítač s konečným stavem. Porovnejte to s algoritmicky náhodnými sekvencemi , což jsou ty nekonečné sekvence, které vypadají náhodně pro jakýkoli algoritmus (a ve skutečnosti mají podobné charakterizace hazardu a komprese u strojů Turing nahrazujících stroje s konečným stavem).

Připojení k ekvidistribuovaným sekvencím

Číslo x je normální v základním b právě tehdy, když je sekvence je equidistributed modulo 1, nebo ekvivalentně, pomocí Weyl kritéria , a to pouze v případě, ${\ Displaystyle {\ left (b^{k} x \ right)} _ {k = 0}^{\ infty}}$

${\ Displaystyle \ lim _ {n \ rightarrow \ infty} {\ frac {1} {n}} \ sum _ {k = 0}^{n-1} e^{2 \ pi imb^{k} x} = 0 \ quad {\ text {pro všechna celá čísla}} m \ geq 1.}$

Toto spojení vede k terminologii, že x je v základně β pro jakékoli skutečné číslo β normální, a to pouze tehdy, je -li posloupnost ekvidistribuovaná modulo 1. ${\ Displaystyle \ left ({x \ beta ^{k}} \ right) _ {k = 0} ^{\ infty}}$

Poznámky

Viz také

• Champernowne konstanta
• Sekvence De Bruijn
• Věta o nekonečné opici
• Babelská knihovna

Reference

Další čtení

externí odkazy

• We are in Digits of Pi and Live Forever by Clifford A. Pickover
• Weisstein, Eric W. „Normální číslo“ . MathWorld .