The Optimal Sink and the Best Source in a Markov Chain View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2011-06

AUTHORS

Yuri Bakhtin, Leonid Bunimovich

ABSTRACT

It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though. Our results can be used, e.g., for a choice of the initial distribution in numerical experiments with the fastest convergence to equilibrium/stationary distribution, for characterization of the elements of a dynamical network according to their ability to absorb and transmit the substance (“information”) that is circulated over the network, for determining optimal stopping moments (stopping signals/words) when dealing with sequences of symbols, etc. More... »

PAGES

943

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10955-011-0223-x

DOI

http://dx.doi.org/10.1007/s10955-011-0223-x

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1031960639


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Georgia Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "School of Mathematics, Georgia Tech, 30332-0160, Atlanta, GA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bakhtin", 
        "givenName": "Yuri", 
        "id": "sg:person.01327752120.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327752120.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Georgia Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "School of Mathematics, Georgia Tech, 30332-0160, Atlanta, GA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bunimovich", 
        "givenName": "Leonid", 
        "id": "sg:person.01175765647.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01175765647.16"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s10955-009-9747-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001264356", 
          "https://doi.org/10.1007/s10955-009-9747-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10955-009-9747-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001264356", 
          "https://doi.org/10.1007/s10955-009-9747-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s002200050697", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008311335", 
          "https://doi.org/10.1007/s002200050697"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11856-011-0030-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008775638", 
          "https://doi.org/10.1007/s11856-011-0030-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9904-1947-08927-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008941732"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02784515", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019839574", 
          "https://doi.org/10.1007/bf02784515"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02784515", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019839574", 
          "https://doi.org/10.1007/bf02784515"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/0951-7715/20/7/011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059109664"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/0951-7715/23/3/012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059109976"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/0951-7715/23/3/012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059109976"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/009117904000000883", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064389208"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/009117905000000242", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064389251"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aop/1078415835", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064403427"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3934/dcds.2004.10.589", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1071733055"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3934/dcdsb.2005.5.565", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1071736029"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2011-06", 
    "datePublishedReg": "2011-06-01", 
    "description": "It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though. Our results can be used, e.g., for a choice of the initial distribution in numerical experiments with the fastest convergence to equilibrium/stationary distribution, for characterization of the elements of a dynamical network according to their ability to absorb and transmit the substance (\u201cinformation\u201d) that is circulated over the network, for determining optimal stopping moments (stopping signals/words) when dealing with sequences of symbols, etc.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10955-011-0223-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1040979", 
        "issn": [
          "0022-4715", 
          "1572-9613"
        ], 
        "name": "Journal of Statistical Physics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "5", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "143"
      }
    ], 
    "name": "The Optimal Sink and the Best Source in a Markov Chain", 
    "pagination": "943", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "984139ee26a91750908363bbe07717f48bfcf91f19ecf15e0dd98b3300e1c021"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10955-011-0223-x"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031960639"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10955-011-0223-x", 
      "https://app.dimensions.ai/details/publication/pub.1031960639"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T16:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000513.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs10955-011-0223-x"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10955-011-0223-x'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10955-011-0223-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10955-011-0223-x'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10955-011-0223-x'


 

This table displays all metadata directly associated to this object as RDF triples.

108 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10955-011-0223-x schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N62bc9ec44c23488a860576f60cefa4a6
4 schema:citation sg:pub.10.1007/bf02784515
5 sg:pub.10.1007/s002200050697
6 sg:pub.10.1007/s10955-009-9747-8
7 sg:pub.10.1007/s11856-011-0030-8
8 https://doi.org/10.1088/0951-7715/20/7/011
9 https://doi.org/10.1088/0951-7715/23/3/012
10 https://doi.org/10.1090/s0002-9904-1947-08927-8
11 https://doi.org/10.1214/009117904000000883
12 https://doi.org/10.1214/009117905000000242
13 https://doi.org/10.1214/aop/1078415835
14 https://doi.org/10.3934/dcds.2004.10.589
15 https://doi.org/10.3934/dcdsb.2005.5.565
16 schema:datePublished 2011-06
17 schema:datePublishedReg 2011-06-01
18 schema:description It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though. Our results can be used, e.g., for a choice of the initial distribution in numerical experiments with the fastest convergence to equilibrium/stationary distribution, for characterization of the elements of a dynamical network according to their ability to absorb and transmit the substance (“information”) that is circulated over the network, for determining optimal stopping moments (stopping signals/words) when dealing with sequences of symbols, etc.
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf N07d193e1b073405f99d89cf9bdcd26ca
23 Ne83b53ac12b04881a3eae3fd8ba245a6
24 sg:journal.1040979
25 schema:name The Optimal Sink and the Best Source in a Markov Chain
26 schema:pagination 943
27 schema:productId N27001afde74d4211ac3940723d03caf1
28 N5e760e36d65b453fa8ef56f7e571f92c
29 Na2d15bd546954cf5a587e6613856ea93
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031960639
31 https://doi.org/10.1007/s10955-011-0223-x
32 schema:sdDatePublished 2019-04-10T16:42
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Nf231d1fcf8904a5f893726b8d0ef8087
35 schema:url http://link.springer.com/10.1007%2Fs10955-011-0223-x
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N07d193e1b073405f99d89cf9bdcd26ca schema:volumeNumber 143
40 rdf:type schema:PublicationVolume
41 N27001afde74d4211ac3940723d03caf1 schema:name dimensions_id
42 schema:value pub.1031960639
43 rdf:type schema:PropertyValue
44 N5e760e36d65b453fa8ef56f7e571f92c schema:name doi
45 schema:value 10.1007/s10955-011-0223-x
46 rdf:type schema:PropertyValue
47 N60ffa7ea9f0d467e851be8f88e960ade rdf:first sg:person.01175765647.16
48 rdf:rest rdf:nil
49 N62bc9ec44c23488a860576f60cefa4a6 rdf:first sg:person.01327752120.28
50 rdf:rest N60ffa7ea9f0d467e851be8f88e960ade
51 Na2d15bd546954cf5a587e6613856ea93 schema:name readcube_id
52 schema:value 984139ee26a91750908363bbe07717f48bfcf91f19ecf15e0dd98b3300e1c021
53 rdf:type schema:PropertyValue
54 Ne83b53ac12b04881a3eae3fd8ba245a6 schema:issueNumber 5
55 rdf:type schema:PublicationIssue
56 Nf231d1fcf8904a5f893726b8d0ef8087 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
59 schema:name Mathematical Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
62 schema:name Pure Mathematics
63 rdf:type schema:DefinedTerm
64 sg:journal.1040979 schema:issn 0022-4715
65 1572-9613
66 schema:name Journal of Statistical Physics
67 rdf:type schema:Periodical
68 sg:person.01175765647.16 schema:affiliation https://www.grid.ac/institutes/grid.213917.f
69 schema:familyName Bunimovich
70 schema:givenName Leonid
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01175765647.16
72 rdf:type schema:Person
73 sg:person.01327752120.28 schema:affiliation https://www.grid.ac/institutes/grid.213917.f
74 schema:familyName Bakhtin
75 schema:givenName Yuri
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327752120.28
77 rdf:type schema:Person
78 sg:pub.10.1007/bf02784515 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019839574
79 https://doi.org/10.1007/bf02784515
80 rdf:type schema:CreativeWork
81 sg:pub.10.1007/s002200050697 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008311335
82 https://doi.org/10.1007/s002200050697
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/s10955-009-9747-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001264356
85 https://doi.org/10.1007/s10955-009-9747-8
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/s11856-011-0030-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008775638
88 https://doi.org/10.1007/s11856-011-0030-8
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1088/0951-7715/20/7/011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059109664
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1088/0951-7715/23/3/012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059109976
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1090/s0002-9904-1947-08927-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008941732
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1214/009117904000000883 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064389208
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1214/009117905000000242 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064389251
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1214/aop/1078415835 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064403427
101 rdf:type schema:CreativeWork
102 https://doi.org/10.3934/dcds.2004.10.589 schema:sameAs https://app.dimensions.ai/details/publication/pub.1071733055
103 rdf:type schema:CreativeWork
104 https://doi.org/10.3934/dcdsb.2005.5.565 schema:sameAs https://app.dimensions.ai/details/publication/pub.1071736029
105 rdf:type schema:CreativeWork
106 https://www.grid.ac/institutes/grid.213917.f schema:alternateName Georgia Institute of Technology
107 schema:name School of Mathematics, Georgia Tech, 30332-0160, Atlanta, GA, USA
108 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...