Ekvidistribuerad sekvens - Equidistributed sequence

I matematik sägs en sekvens ( s ₁ , s ₂ , s ₃ , ...) av reella tal vara lika fördelade eller jämnt fördelade , om andelen termer som faller i ett delintervall är proportionell mot längden på det delintervallet. Sådana sekvenser studeras i Diophantine approximation theory och har tillämpningar på Monte Carlo-integration .

Definition

En sekvens ( s ₁ , s ₂ , s ₃ , ...) av reella tal sägs vara lika fördelade på ett icke-degenererat intervall [ a , b ] om för något delintervall [ c , d ] av [ a , b ] vi har

{\ displaystyle \ lim _ {n \ to \ infty} {\ left | \ {\, s_ {1}, \ dots, s_ {n} \, \} \ cap [c, d] \ right | \ över n} = {dc \ över ba}.}

(Här betecknar notationen | { s ₁ , ..., s _n } ∩ [ c , d ] | antalet element av de första n- elementen i sekvensen som ligger mellan c och d .)

Till exempel, om en sekvens är lika fördelad i [0, 2], eftersom intervallet [0,5, 0,9] upptar 1/5 av längden på intervallet [0, 2], när n blir stort, är andelen av den första n medlemmar i sekvensen som faller mellan 0,5 och 0,9 måste närma sig 1/5. Löst sagt kan man säga att varje medlem i sekvensen är lika sannolikt att falla var som helst inom sitt intervall. Detta är dock inte att säga att ( s _n ) är en sekvens av slumpmässiga variabler ; snarare är det en bestämd sekvens av verkliga tal.

Avvikelse

Vi definierar diskrepans D _N för en sekvens ( s ₁ , s ₂ , s ₃ , ...) med avseende på intervallet [ a , b ] som

{\ displaystyle D_ {N} = \ sup _ {a \ leq c \ leq d \ leq b} \ left \ vert {\ frac {\ left | \ {\, s_ {1}, \ dots, s_ {N} \, \} \ cap [c, d] \ right |} {N}} - {\ frac {dc} {ba}} \ right \ vert.}

En sekvens fördelas sålunda om skillnaden D _N tenderar till noll som N tenderar till oändlighet.

Ekvidistribution är ett ganska svagt kriterium för att uttrycka det faktum att en sekvens fyller segmentet och lämnar inga luckor. Till exempel kommer ritningarna av en slumpmässig variabel enhetlig över ett segment att fördelas i segmentet, men det kommer att finnas stora luckor jämfört med en sekvens som först räknar upp multiplar av ε i segmentet, för vissa små ε, på ett lämpligt valt sätt och fortsätter sedan att göra detta för mindre och mindre värden på ε. För starkare kriterier och för konstruktioner av sekvenser som är mer jämnt fördelade, se sekvensen med låg avvikelse .

Riemann integrerat kriterium för jämfördelning

Kom ihåg att om f är en funktion som har en Riemann-integral i intervallet [ a , b ], så är dess integral gränsen för Riemann-summor som tagits genom att sampla funktionen f i en uppsättning punkter valda från en fin partition av intervallet. Därför, om någon sekvens är lika fördelad i [ a , b ], förväntas det att denna sekvens kan användas för att beräkna integralen i en Riemann-integrerbar funktion. Detta leder till följande kriterium för en lika fördelad sekvens:

Antag att ( s ₁ , s ₂ , s ₃ , ...) är en sekvens som ingår i intervallet [ a , b ]. Då är följande villkor ekvivalenta:

Sekvensen är lika fördelad på [ a , b ].
För varje Riemann-integrerbar ( komplexvärderad ) funktion f : [ a , b ] → ℂ gäller följande gräns:

{\ displaystyle \ lim _ {N \ to \ infty} {\ frac {1} {N}} \ sum _ {n = 1} ^ {N} f \ left (s_ {n} \ right) = {\ frac {1} {ba}} \ int _ {a} ^ {b} f (x) \, dx}

Bevis

Observera först att definitionen av en ekvidistribuerad sekvens är ekvivalent med integralkriteriet när f är indikatorfunktionen för ett intervall: Om f = 1 _{[ c , d ]} är vänster sida andelen punkter i sekvensen som faller i intervallet [ c , d ] och höger sida är exakt

{\ displaystyle \ textstyle {\ frac {dc} {ba}}.}

Detta betyder 2 ⇒ 1 (eftersom indikatorfunktioner är Riemann-integrerbara) och 1 ⇒ 2 för f är en indikatorfunktion för ett intervall. Det återstår att anta att det integrerade kriteriet gäller för indikatorfunktioner och bevisa att det gäller även för allmänna Riemann-integrerbara funktioner.

Observera att båda sidorna av den integrerade kriterieekvationen är linjära i f , och därför gäller kriteriet för linjära kombinationer av intervallindikatorer, det vill säga stegfunktioner .

För att visa att det gäller f är en allmän Riemann-integrerbar funktion, antar först att f är verkligt värderat. Genom att använda Darboux definition av integralen har vi för varje ε> 0 två stegsfunktioner f ₁ och f ₂ så att f ₁ ≤ f ≤ f ₂ och Observera att: ${\ displaystyle \ textstyle \ int _ {a} ^ {b} (f_ {2} (x) -f_ {1} (x)) \, dx \ leq \ varepsilon (ba).}$

{\ displaystyle {\ frac {1} {ba}} \ int _ {a} ^ {b} f_ {1} (x) \, dx = \ lim _ {N \ to \ infty} {\ frac {1} {N}} \ sum _ {n = 1} ^ {N} f_ {1} (s_ {n}) \ leq \ liminf _ {N \ to \ infty} {\ frac {1} {N}} \ sum _ {n = 1} ^ {N} f (s_ {n})}

{\ displaystyle {\ frac {1} {ba}} \ int _ {a} ^ {b} f_ {2} (x) \, dx = \ lim _ {N \ to \ infty} {\ frac {1} {N}} \ sum _ {n = 1} ^ {N} f_ {2} (s_ {n}) \ geq \ limsup _ {N \ to \ infty} {\ frac {1} {N}} \ sum _ {n = 1} ^ {N} f (s_ {n})}

Genom att subtrahera ser vi att gränsen överlägsen och lägre gräns för skiljer sig åt högst ε. Eftersom ε är godtycklig har vi existensen av gränsen, och enligt Darboux definition av integralen är den rätt gräns. ${\ displaystyle \ textstyle {\ frac {1} {N}} \ sum _ {n = 1} ^ {N} f (s_ {n})}$

Slutligen, för komplexvärderade Riemann-integrerbara funktioner, följer resultatet igen från linjäritet och från det faktum att varje sådan funktion kan skrivas som f = u + vi , där u , v är verkligt värderade och Riemann-integrerbara. ∎

Detta kriterium leder till idén om Monte-Carlo-integration , där integraler beräknas genom att sampla funktionen över en sekvens av slumpmässiga variabler som är lika fördelade i intervallet.

Det är inte möjligt att generalisera integralkriteriet till en klass av funktioner som är större än bara de Riemann-integrerbara. Till exempel, om Lebesgue-integralen beaktas och f anses vara i L ¹ , misslyckas detta kriterium. Som ett motexempel, ta f för att vara indikatorfunktionen för någon ekvidistribuerad sekvens. Sedan i kriteriet är vänster sida alltid 1, medan höger sida är noll, eftersom sekvensen är räknad , så f är noll nästan överallt .

I själva verket anger de Bruijn – Post-satsen det motsatta av ovanstående kriterium: Om f är en funktion så att kriteriet ovan gäller för en lika fördelad sekvens i [ a , b ], är f Riemann-integrerbar i [ a , b ].

Ekvidistributionsmodul 1

En sekvens ( a ₁ , a ₂ , a, ₃ , ...) av reella tal sägs vara ekvidistribuerad modulo 1 eller enhetligt fördelad modulo 1 om sekvensen för fraktionerade delar av en _n , betecknad med ( a _n ) eller med a _n - ⌊ a _n ⌋, fördelas i intervallet [0, 1].

Exempel

Illustration av fyllningen av enhetsintervallet ( x -ax) med de första n termerna i Van der Corput-sekvensen, för n från 0 till 999 ( y -ax). Gradering i färg beror på aliasing.

Den equidistribution teorem : Sekvensen för alla multipler av en irrationell α ,

0, α , 2 α , 3 α , 4 α , ...

är lika fördelad modulo 1.

Mer allmänt, om p är ett polynom med minst en annan koefficient än den konstanta termen irrationell så är sekvensen p ( n ) jämnt fördelad modulo 1.

Detta bevisades av Weyl och är en tillämpning av van der Corputs skillnadssats.

Sekvensloggen ( n ) är inte jämnt fördelad modulo 1. Detta faktum är relaterat till Benfords lag .
Sekvensen för alla multiplar av en irrationell α med successiva primtal ,

2 α , 3 α , 5 α , 7 α , 11 α , ...

är lika fördelad modulo 1. Detta är en berömd sats för analytisk talteori , publicerad av IM Vinogradov 1948.

Den van der Corput sekvensen är equidistributed.

Weyls kriterium

Weyls kriterium anger att sekvensen a _n är lika fördelad modulo 1 om och endast om för alla icke-noll heltal ℓ,

{\ displaystyle \ lim _ {n \ to \ infty} {\ frac {1} {n}} \ sum _ {j = 1} ^ {n} e ^ {2 \ pi i \ ell a_ {j}} = 0.}

Kriteriet är uppkallat efter och formulerades först av Hermann Weyl . Det gör det möjligt att jämföra fördelningsfrågor till exponentiella summor , en grundläggande och allmän metod.

Skiss av bevis

Om sekvensen är lika fördelad modulo 1, kan vi tillämpa Riemann-integralkriteriet (beskrivet ovan) på funktionen som har integrerad noll på intervallet [0, 1]. Detta ger Weyls kriterium omedelbart.

{\ displaystyle \ textstyle f (x) = e ^ {2 \ pi i \ ell x},}

Omvänt, anta att Weyls kriterium håller. Då gäller Riemann-integralkriteriet för funktionerna f enligt ovan, och av kriteriets linjäritet gäller det att f är vilken trigonometrisk polynom som helst . Genom teoremet Stone – Weierstrass och ett approximationsargument sträcker sig detta till alla kontinuerliga funktioner f .

Slutligen, l f vara indikatorfunktionen för ett intervall. Det är möjligt att binda f uppifrån och ner av två kontinuerliga funktioner på intervallet, vars integraler skiljer sig med en godtycklig ε. Av ett argument som liknar den bevis på Riemannintegralen kriteriet, är det möjligt att förlänga resultatet till någon intervallindikatorfunktion f , därigenom bevisa equidistribution modulo en av den givna sekvensen. ∎

Generaliseringar

En kvantitativ form av Weyls kriterium ges av ojämlikheten mellan Erdős och Turán .
Weyls kriterium sträcker sig naturligt till högre dimensioner , förutsatt att den naturliga generaliseringen av definitionen av jämfördelning modulo 1:

Sekvensen v _n av vektorer i R ^k är equidistributed modulo 1 om och endast om för varje icke-nollvektor ℓ ∈ Z ^k ,

{\ displaystyle \ lim _ {n \ to \ infty} {\ frac {1} {n}} \ sum _ {j = 0} ^ {n-1} e ^ {2 \ pi i \ ell \ cdot v_ { j}} = 0.}

Exempel på användning

Weyls kriterium kan användas för att enkelt bevisa ekvidistributionssatsen , och säga att sekvensen av multiplar 0, α , 2 α , 3 α , ... av något reellt tal α är lika fördelad modulo 1 om och bara om α är irrationell.

Antag att α är irrationell och betecknar vår sekvens med en _j = jα (där j börjar från 0, för att förenkla formeln senare). Låt ℓ ≠ 0 vara ett heltal. Eftersom α är irrationell kan ℓα aldrig vara ett heltal, så kan det aldrig vara 1. Använd formeln för summan av en ändlig geometrisk serie , ${\ textstyle e ^ {2 \ pi i \ ell \ alpha}}$

{\ displaystyle \ left | \ sum _ {j = 0} ^ {n-1} e ^ {2 \ pi i \ ell j \ alpha} \ right | = \ left | \ sum _ {j = 0} ^ { n-1} \ vänster (e ^ {2 \ pi i \ ell \ alpha} \ höger) ^ {j} \ höger | = \ vänster | {\ frac {1-e ^ {2 \ pi i \ ell n \ alfa}} {1-e ^ {2 \ pi i \ ell \ alpha}}} \ höger | \ leq {\ frac {2} {\ vänster | 1-e ^ {2 \ pi i \ ell \ alpha} \ höger |}},}

en begränsad gräns som inte beror på n . Därför, efter att ha delat med n och låt n tenderar till oändlighet, tenderar vänster sida till noll, och Weyls kriterium är uppfyllt.

Omvänt, observera att om α är rationell så är denna sekvens inte lika fördelad modulo 1, eftersom det bara finns ett begränsat antal alternativ för den del av en _j = jα .

Komplett enhetlig distribution

En sekvens av reella tal sägs vara k-enhetligt fördelad mod 1 om inte bara sekvensen av fraktionerade delar är jämnt fördelad i utan också sekvensen , där den definieras som , är jämnt fördelad i . ${\ displaystyle (a_ {1}, a_ {2}, \ dots)}$ ${\ displaystyle a_ {n} ': = a_ {n} - [a_ {n}]}$ ${\ displaystyle [0,1]}$ ${\ displaystyle (b_ {1}, b_ {2}, \ dots)}$ ${\ displaystyle b_ {n}}$ ${\ displaystyle b_ {n}: = (a '_ {n + 1}, \ prickar, a' _ {n + k}) \ i [0,1] ^ {k}}$ ${\ displaystyle [0,1] ^ {k}}$

En sekvens av reella tal sägs vara helt jämnt fördelad mod 1 den fördelas enhetligt för varje naturligt tal . ${\ displaystyle (a_ {1}, a_ {2}, \ dots)}$ ${\ displaystyle k}$ ${\ displaystyle k \ geq 1}$

Till exempel är sekvensen jämnt fördelad mod 1 (eller 1-enhetligt fördelad) för vilket irrationellt tal som helst , men är aldrig ens 2-enhetligt fördelat. Däremot är sekvensen helt jämnt fördelad för nästan alla (dvs. för alla utom för en uppsättning mått 0). ${\ displaystyle (\ alpha, 2 \ alpha, \ dots)}$ ${\ displaystyle \ alpha}$ ${\ displaystyle (\ alpha, \ alpha ^ {2}, \ alpha ^ {3}, \ dots)}$ ${\ displaystyle \ alpha> 1}$ ${\ displaystyle \ alpha}$

van der Corputs skillnadssats

En teorem av Johannes van der Corput säger att om för varje h är sekvensen s _{n + h} - s _n jämnt fördelad modulo 1, så är s _{n också} .

En van der Corput-uppsättning är en uppsättning H av heltal så att för varje h i H är sekvensen s _{n + h} - s _n jämnt fördelad modulo 1, så är s _{n också} .

Metriska satser

Metriska satser beskriver beteendet hos en parametriserad sekvens för nästan alla värden för någon parameter α : det vill säga för värden för α som inte ligger i någon exceptionell uppsättning Lebesgue-mått noll.

För vilken som helst sekvens av distinkta heltal b _n , sekvensen ( b _n α är) equidistributed mod 1 för nästan alla värden av α .
Sekvensen ( α ⁿ ) är ekvidistribuerad mod 1 för nästan alla värden på α > 1.

Det är inte känt om sekvenserna ( e ⁿ ) eller ( $π$ ⁿ ) är lika fördelade mod 1. Det är emellertid känt att sekvensen ( α ⁿ ) inte är lika fördelad mod 1 om α är ett PV-nummer .

Välfördelad sekvens

En sekvens ( s ₁ , s ₂ , s ₃ , ...) av reella tal sägs vara väl fördelad på [ a , b ] om vi för något delintervall [ c , d ] av [ a , b ] har

{\ displaystyle \ lim _ {n \ to \ infty} {\ left | \ {\, s_ {k + 1}, \ dots, s_ {k + n} \, \} \ cap [c, d] \ right | \ over n} = {dc \ over ba}}

enhetligt i k . Det är uppenbart att varje välfördelad sekvens är jämnt fördelad, men det motsatta håller inte. Definitionen av väl fördelad modulo 1 är analog.

Sekvenser som distribueras med avseende på en godtycklig åtgärd

För ett godtyckligt sannolikhetsmätutrymme sägs en sekvens av punkter vara lika fördelade med avseende på om medelvärdet av punktmått konvergerar svagt till : ${\ displaystyle (X, \ mu)}$ ${\ displaystyle (x_ {n})}$ ${\ displaystyle \ mu}$ ${\ displaystyle \ mu}$

{\ displaystyle {\ frac {\ sum _ {k = 1} ^ {n} \ delta _ {x_ {k}}} {n}} \ Rightarrow \ mu \.}

I varje Borel- sannolikhetsmått på ett avskiljbart , mätbart utrymme, finns det en lika fördelad sekvens med avseende på måttet; faktiskt följer detta omedelbart av det faktum att ett sådant utrymme är standard .

Det allmänna fenomenet med jämnfördelning kommer mycket upp för dynamiska system associerade med Lie-grupper , till exempel i Margulis lösning på Oppenheim-gissningen .

Se även

Anteckningar

Referenser

Kuipers, L .; Niederreiter, H. (2006) [1974]. Enhetlig fördelning av sekvenser . Dover-publikationer. ISBN 0-486-45019-8 .
Kuipers, L .; Niederreiter, H. (1974). Enhetlig fördelning av sekvenser . John Wiley & Sons Inc. ISBN 0-471-51045-9 . Zbl 0281.10001 .
Montgomery, Hugh L. (1994). Tio föreläsningar om gränssnittet mellan analytisk talteori och harmonisk analys . Regional konferensserie i matematik. 84 . Providence, RI: American Mathematical Society . ISBN 0-8218-0737-4 . Zbl 0814.11001 .

Vidare läsning

Granville, Andrew; Rudnick, Zeév, red. (2007). Jämfördelning i talteori, en introduktion. Proceedings of the NATO Advanced Study Institute on equidistribution in number theory, Montréal, Canada, 11–22 juli 2005 . NATO Science Series II: Matematik, fysik och kemi. 237 . Dordrecht: Springer-Verlag . ISBN 978-1-4020-5403-7 . Zbl 1121.11004 .
Tao, Terence (2012). Fourier-analys av högre ordning . Forskarstudier i matematik . 142 . Providence, RI: American Mathematical Society . ISBN 978-0-8218-8986-2 . Zbl 1277.11010 .

Languages

In other projects