Loading…

Asymptotic Divergences and Strong Dichotomy

The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet \Sigma . The theorem asserts that, for any such sequence S , the following two things are true. (1) If S is not normal in the sense...

Full description

Saved in:

Bibliographic Details
Published in:	IEEE transactions on information theory 2021-10, Vol.67 (10), p.6296-6305
Main Authors:	Huang, Xiang, Lutz, Jack H., Mayordomo, Elvira, Stull, Donald M.
Format:	Article
Language:	English
Subjects:	Asymptotic methods Asymptotic properties Divergence Entropy Finite-state dimension finite-state gambler Frequency measurement Gambling Kullback-Leibler divergence Length measurement normal sequences Normality Random variables Strings Technological innovation Theorems Upper bound Upper bounds
Citations:	Items that this one cites
Online Access:	Get full text
Tags:	Add Tag No Tags, Be the first to tag this record!

cited_by
cites	cdi_FETCH-LOGICAL-c286t-995ab2a7311a1f0ba1db1688603a17640fd89a7b6dbb001953e06e9660cc72db3
container_end_page	6305
container_issue	10
container_start_page	6296
container_title	IEEE transactions on information theory
container_volume	67
creator	Huang, Xiang Lutz, Jack H. Mayordomo, Elvira Stull, Donald M.
description	The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet \Sigma . The theorem asserts that, for any such sequence S , the following two things are true. (1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S ), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S . (2) If S is normal, then any finite-state gambler loses money at an exponential rate betting on S . In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence {\mathrm {div}}(S\|\|\alpha) of a probability measure \alpha on \Sigma from a sequence S over \Sigma and the upper asymptotic divergence {\mathrm {Div}}(S\|\|\alpha) of \alpha from S in such a way that a sequence S is \alpha -normal (meaning that every string w has asymptotic frequency \alpha (w) in S ) if and only if
doi_str_mv	10.1109/TIT.2021.3085425
format	article
fullrecord	<record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1109_TIT_2021_3085425</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>9445108</ieee_id><sourcerecordid>2572664002</sourcerecordid><originalsourceid>FETCH-LOGICAL-c286t-995ab2a7311a1f0ba1db1688603a17640fd89a7b6dbb001953e06e9660cc72db3</originalsourceid><addsrcrecordid>eNo9kM1LAzEQxYMoWKt3wcuCR9k6k91kk2OpX4WCB9dzSLLZusVuarIV9r83pcXTMMN7bx4_Qm4RZoggH-tlPaNAcVaAYCVlZ2SCjFW55Kw8JxMAFLksS3FJrmLcpLVkSCfkYR7H7W7wQ2ezp-7XhbXrrYuZ7pvsYwi-X6ez_fKD347X5KLV39HdnOaUfL4814u3fPX-ulzMV7mlgg-5lEwbqqsCUWMLRmNjkAvBodBY8RLaRkhdGd4Yk3pIVjjgTnIO1la0McWU3B9zd8H_7F0c1MbvQ59eKsoqylME0KSCo8oGH2NwrdqFbqvDqBDUAYlKSNQBiTohSZa7o6Vzzv3LExWGIIo_VqBbEQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2572664002</pqid></control><display><type>article</type><title>Asymptotic Divergences and Strong Dichotomy</title><source>IEEE Electronic Library (IEL) Journals</source><creator>Huang, Xiang ; Lutz, Jack H. ; Mayordomo, Elvira ; Stull, Donald M.</creator><creatorcontrib>Huang, Xiang ; Lutz, Jack H. ; Mayordomo, Elvira ; Stull, Donald M.</creatorcontrib><description><![CDATA[The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula>. The theorem asserts that, for any such sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>, the following two things are true. (1) If <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. (2) If <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is normal, then any finite-state gambler loses money at an exponential rate betting on <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence <inline-formula> <tex-math notation="LaTeX">{\mathrm {div}}(S\|\|\alpha) </tex-math></inline-formula> of a probability measure <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula> from a sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula> and the upper asymptotic divergence <inline-formula> <tex-math notation="LaTeX">{\mathrm {Div}}(S\|\|\alpha) </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> in such a way that a sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-normal (meaning that every string <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> has asymptotic frequency <inline-formula> <tex-math notation="LaTeX">\alpha (w) </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>) if and only if <inline-formula> <tex-math notation="LaTeX">{\mathrm {Div}}(S\|\|\alpha)=0 </tex-math></inline-formula>. We also use the Kullback-Leibler divergence to quantify the total risk <inline-formula> <tex-math notation="LaTeX">{\mathrm {Risk}}_{G}(w) </tex-math></inline-formula> that a finite-state gambler <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> takes when betting along a prefix <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. (<inline-formula> <tex-math notation="LaTeX">1~' </tex-math></inline-formula>) The infinitely-often exponential rate of winning in 1 is <inline-formula> <tex-math notation="LaTeX">2^{{\mathrm {Div}}(S\|\|\alpha)\|w\|} </tex-math></inline-formula>. (<inline-formula> <tex-math notation="LaTeX">2~' </tex-math></inline-formula>) The exponential rate of loss in 2 is <inline-formula> <tex-math notation="LaTeX">2^{- {\mathrm {Risk}}_{G}(w)} </tex-math></inline-formula>. We also use (1 <inline-formula> <tex-math notation="LaTeX">' </tex-math></inline-formula>) to show that <inline-formula> <tex-math notation="LaTeX">1- {\mathrm {Div}}(S\|\|\alpha)/c </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">c= \log (1/ \min _{a\in \Sigma }\alpha (a)) </tex-math></inline-formula>, is an upper bound on the finite-state <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-dimension of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> and prove the dual fact that <inline-formula> <tex-math notation="LaTeX">1- {\mathrm {div}}(S\|\|\alpha)/c </tex-math></inline-formula> is an upper bound on the finite-state strong <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-dimension of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>.]]></description><identifier>ISSN: 0018-9448</identifier><identifier>EISSN: 1557-9654</identifier><identifier>DOI: 10.1109/TIT.2021.3085425</identifier><identifier>CODEN: IETTAW</identifier><language>eng</language><publisher>New York: IEEE</publisher><subject>Asymptotic methods ; Asymptotic properties ; Divergence ; Entropy ; Finite-state dimension ; finite-state gambler ; Frequency measurement ; Gambling ; Kullback-Leibler divergence ; Length measurement ; normal sequences ; Normality ; Random variables ; Strings ; Technological innovation ; Theorems ; Upper bound ; Upper bounds</subject><ispartof>IEEE transactions on information theory, 2021-10, Vol.67 (10), p.6296-6305</ispartof><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) 2021</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c286t-995ab2a7311a1f0ba1db1688603a17640fd89a7b6dbb001953e06e9660cc72db3</cites><orcidid>0000-0003-1004-3891 ; 0000-0002-9109-5337 ; 0000-0002-4815-6130</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/9445108$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27923,27924,54795</link.rule.ids></links><search><creatorcontrib>Huang, Xiang</creatorcontrib><creatorcontrib>Lutz, Jack H.</creatorcontrib><creatorcontrib>Mayordomo, Elvira</creatorcontrib><creatorcontrib>Stull, Donald M.</creatorcontrib><title>Asymptotic Divergences and Strong Dichotomy</title><title>IEEE transactions on information theory</title><addtitle>TIT</addtitle><description><![CDATA[The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula>. The theorem asserts that, for any such sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>, the following two things are true. (1) If <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. (2) If <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is normal, then any finite-state gambler loses money at an exponential rate betting on <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence <inline-formula> <tex-math notation="LaTeX">{\mathrm {div}}(S\|\|\alpha) </tex-math></inline-formula> of a probability measure <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula> from a sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula> and the upper asymptotic divergence <inline-formula> <tex-math notation="LaTeX">{\mathrm {Div}}(S\|\|\alpha) </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> in such a way that a sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-normal (meaning that every string <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> has asymptotic frequency <inline-formula> <tex-math notation="LaTeX">\alpha (w) </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>) if and only if <inline-formula> <tex-math notation="LaTeX">{\mathrm {Div}}(S\|\|\alpha)=0 </tex-math></inline-formula>. We also use the Kullback-Leibler divergence to quantify the total risk <inline-formula> <tex-math notation="LaTeX">{\mathrm {Risk}}_{G}(w) </tex-math></inline-formula> that a finite-state gambler <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> takes when betting along a prefix <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. (<inline-formula> <tex-math notation="LaTeX">1~' </tex-math></inline-formula>) The infinitely-often exponential rate of winning in 1 is <inline-formula> <tex-math notation="LaTeX">2^{{\mathrm {Div}}(S\|\|\alpha)\|w\|} </tex-math></inline-formula>. (<inline-formula> <tex-math notation="LaTeX">2~' </tex-math></inline-formula>) The exponential rate of loss in 2 is <inline-formula> <tex-math notation="LaTeX">2^{- {\mathrm {Risk}}_{G}(w)} </tex-math></inline-formula>. We also use (1 <inline-formula> <tex-math notation="LaTeX">' </tex-math></inline-formula>) to show that <inline-formula> <tex-math notation="LaTeX">1- {\mathrm {Div}}(S\|\|\alpha)/c </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">c= \log (1/ \min _{a\in \Sigma }\alpha (a)) </tex-math></inline-formula>, is an upper bound on the finite-state <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-dimension of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> and prove the dual fact that <inline-formula> <tex-math notation="LaTeX">1- {\mathrm {div}}(S\|\|\alpha)/c </tex-math></inline-formula> is an upper bound on the finite-state strong <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-dimension of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>.]]></description><subject>Asymptotic methods</subject><subject>Asymptotic properties</subject><subject>Divergence</subject><subject>Entropy</subject><subject>Finite-state dimension</subject><subject>finite-state gambler</subject><subject>Frequency measurement</subject><subject>Gambling</subject><subject>Kullback-Leibler divergence</subject><subject>Length measurement</subject><subject>normal sequences</subject><subject>Normality</subject><subject>Random variables</subject><subject>Strings</subject><subject>Technological innovation</subject><subject>Theorems</subject><subject>Upper bound</subject><subject>Upper bounds</subject><issn>0018-9448</issn><issn>1557-9654</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNo9kM1LAzEQxYMoWKt3wcuCR9k6k91kk2OpX4WCB9dzSLLZusVuarIV9r83pcXTMMN7bx4_Qm4RZoggH-tlPaNAcVaAYCVlZ2SCjFW55Kw8JxMAFLksS3FJrmLcpLVkSCfkYR7H7W7wQ2ezp-7XhbXrrYuZ7pvsYwi-X6ez_fKD347X5KLV39HdnOaUfL4814u3fPX-ulzMV7mlgg-5lEwbqqsCUWMLRmNjkAvBodBY8RLaRkhdGd4Yk3pIVjjgTnIO1la0McWU3B9zd8H_7F0c1MbvQ59eKsoqylME0KSCo8oGH2NwrdqFbqvDqBDUAYlKSNQBiTohSZa7o6Vzzv3LExWGIIo_VqBbEQ</recordid><startdate>20211001</startdate><enddate>20211001</enddate><creator>Huang, Xiang</creator><creator>Lutz, Jack H.</creator><creator>Mayordomo, Elvira</creator><creator>Stull, Donald M.</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0003-1004-3891</orcidid><orcidid>https://orcid.org/0000-0002-9109-5337</orcidid><orcidid>https://orcid.org/0000-0002-4815-6130</orcidid></search><sort><creationdate>20211001</creationdate><title>Asymptotic Divergences and Strong Dichotomy</title><author>Huang, Xiang ; Lutz, Jack H. ; Mayordomo, Elvira ; Stull, Donald M.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c286t-995ab2a7311a1f0ba1db1688603a17640fd89a7b6dbb001953e06e9660cc72db3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Asymptotic methods</topic><topic>Asymptotic properties</topic><topic>Divergence</topic><topic>Entropy</topic><topic>Finite-state dimension</topic><topic>finite-state gambler</topic><topic>Frequency measurement</topic><topic>Gambling</topic><topic>Kullback-Leibler divergence</topic><topic>Length measurement</topic><topic>normal sequences</topic><topic>Normality</topic><topic>Random variables</topic><topic>Strings</topic><topic>Technological innovation</topic><topic>Theorems</topic><topic>Upper bound</topic><topic>Upper bounds</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Huang, Xiang</creatorcontrib><creatorcontrib>Lutz, Jack H.</creatorcontrib><creatorcontrib>Mayordomo, Elvira</creatorcontrib><creatorcontrib>Stull, Donald M.</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998-Present</collection><collection>IEEE Xplore</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics & Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on information theory</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Huang, Xiang</au><au>Lutz, Jack H.</au><au>Mayordomo, Elvira</au><au>Stull, Donald M.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Asymptotic Divergences and Strong Dichotomy</atitle><jtitle>IEEE transactions on information theory</jtitle><stitle>TIT</stitle><date>2021-10-01</date><risdate>2021</risdate><volume>67</volume><issue>10</issue><spage>6296</spage><epage>6305</epage><pages>6296-6305</pages><issn>0018-9448</issn><eissn>1557-9654</eissn><coden>IETTAW</coden><abstract><![CDATA[The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula>. The theorem asserts that, for any such sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>, the following two things are true. (1) If <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. (2) If <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is normal, then any finite-state gambler loses money at an exponential rate betting on <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence <inline-formula> <tex-math notation="LaTeX">{\mathrm {div}}(S\|\|\alpha) </tex-math></inline-formula> of a probability measure <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula> from a sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">\Sigma </tex-math></inline-formula> and the upper asymptotic divergence <inline-formula> <tex-math notation="LaTeX">{\mathrm {Div}}(S\|\|\alpha) </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> in such a way that a sequence <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> is <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-normal (meaning that every string <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> has asymptotic frequency <inline-formula> <tex-math notation="LaTeX">\alpha (w) </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>) if and only if <inline-formula> <tex-math notation="LaTeX">{\mathrm {Div}}(S\|\|\alpha)=0 </tex-math></inline-formula>. We also use the Kullback-Leibler divergence to quantify the total risk <inline-formula> <tex-math notation="LaTeX">{\mathrm {Risk}}_{G}(w) </tex-math></inline-formula> that a finite-state gambler <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> takes when betting along a prefix <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes <inline-formula> <tex-math notation="LaTeX">w </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>. (<inline-formula> <tex-math notation="LaTeX">1~' </tex-math></inline-formula>) The infinitely-often exponential rate of winning in 1 is <inline-formula> <tex-math notation="LaTeX">2^{{\mathrm {Div}}(S\|\|\alpha)\|w\|} </tex-math></inline-formula>. (<inline-formula> <tex-math notation="LaTeX">2~' </tex-math></inline-formula>) The exponential rate of loss in 2 is <inline-formula> <tex-math notation="LaTeX">2^{- {\mathrm {Risk}}_{G}(w)} </tex-math></inline-formula>. We also use (1 <inline-formula> <tex-math notation="LaTeX">' </tex-math></inline-formula>) to show that <inline-formula> <tex-math notation="LaTeX">1- {\mathrm {Div}}(S\|\|\alpha)/c </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">c= \log (1/ \min _{a\in \Sigma }\alpha (a)) </tex-math></inline-formula>, is an upper bound on the finite-state <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-dimension of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula> and prove the dual fact that <inline-formula> <tex-math notation="LaTeX">1- {\mathrm {div}}(S\|\|\alpha)/c </tex-math></inline-formula> is an upper bound on the finite-state strong <inline-formula> <tex-math notation="LaTeX">\alpha </tex-math></inline-formula>-dimension of <inline-formula> <tex-math notation="LaTeX">S </tex-math></inline-formula>.]]></abstract><cop>New York</cop><pub>IEEE</pub><doi>10.1109/TIT.2021.3085425</doi><tpages>10</tpages><orcidid>https://orcid.org/0000-0003-1004-3891</orcidid><orcidid>https://orcid.org/0000-0002-9109-5337</orcidid><orcidid>https://orcid.org/0000-0002-4815-6130</orcidid><oa>free_for_read</oa></addata></record>
fulltext	fulltext
identifier	ISSN: 0018-9448
ispartof	IEEE transactions on information theory, 2021-10, Vol.67 (10), p.6296-6305
issn	0018-9448 1557-9654
language	eng
recordid	cdi_crossref_primary_10_1109_TIT_2021_3085425
source	IEEE Electronic Library (IEL) Journals
subjects	Asymptotic methods Asymptotic properties Divergence Entropy Finite-state dimension finite-state gambler Frequency measurement Gambling Kullback-Leibler divergence Length measurement normal sequences Normality Random variables Strings Technological innovation Theorems Upper bound Upper bounds
title	Asymptotic Divergences and Strong Dichotomy
url	http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T07%3A05%3A27IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Asymptotic%20Divergences%20and%20Strong%20Dichotomy&rft.jtitle=IEEE%20transactions%20on%20information%20theory&rft.au=Huang,%20Xiang&rft.date=2021-10-01&rft.volume=67&rft.issue=10&rft.spage=6296&rft.epage=6305&rft.pages=6296-6305&rft.issn=0018-9448&rft.eissn=1557-9654&rft.coden=IETTAW&rft_id=info:doi/10.1109/TIT.2021.3085425&rft_dat=%3Cproquest_cross%3E2572664002%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c286t-995ab2a7311a1f0ba1db1688603a17640fd89a7b6dbb001953e06e9660cc72db3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2572664002&rft_id=info:pmid/&rft_ieee_id=9445108&rfr_iscdi=true