The number of distinct adjacent pairs in geometrically distributed words
A sequence of geometric random variables of length $n$ is a sequence of $n$ independent and identically distributed geometric random variables ($\Gamma_1, \Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for $1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5686/pdf |
| _version_ | 1797269985615151104 |
|---|---|
| author | Margaret Archibald Aubrey Blecher Charlotte Brennan Arnold Knopfmacher Stephan Wagner Mark Ward |
| author_facet | Margaret Archibald Aubrey Blecher Charlotte Brennan Arnold Knopfmacher Stephan Wagner Mark Ward |
| author_sort | Margaret Archibald |
| collection | DOAJ |
| description | A sequence of geometric random variables of length $n$ is a sequence of $n$
independent and identically distributed geometric random variables ($\Gamma_1,
\Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for
$1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent two
letter patterns in such sequences. Initially we directly count the number of
distinct pairs in words of short length. Because of the rapid growth of the
number of word patterns we change our approach to this problem by obtaining an
expression for the expected number of distinct pairs in words of length $n$. We
also obtain the asymptotics for the expected number as $n \to \infty$. |
| first_indexed | 2024-04-25T01:57:04Z |
| format | Article |
| id | doaj.art-13e2db8c67414eb38411f9abbcbf2c2f |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:04Z |
| publishDate | 2021-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-13e2db8c67414eb38411f9abbcbf2c2f2024-03-07T15:43:24ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-01-01vol. 22 no. 4Analysis of Algorithms10.23638/DMTCS-22-4-105686The number of distinct adjacent pairs in geometrically distributed wordsMargaret ArchibaldAubrey BlecherCharlotte BrennanArnold KnopfmacherStephan WagnerMark WardA sequence of geometric random variables of length $n$ is a sequence of $n$ independent and identically distributed geometric random variables ($\Gamma_1, \Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for $1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent two letter patterns in such sequences. Initially we directly count the number of distinct pairs in words of short length. Because of the rapid growth of the number of word patterns we change our approach to this problem by obtaining an expression for the expected number of distinct pairs in words of length $n$. We also obtain the asymptotics for the expected number as $n \to \infty$.https://dmtcs.episciences.org/5686/pdfmathematics - combinatorics05a15, 05a05 |
| spellingShingle | Margaret Archibald Aubrey Blecher Charlotte Brennan Arnold Knopfmacher Stephan Wagner Mark Ward The number of distinct adjacent pairs in geometrically distributed words Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05a15, 05a05 |
| title | The number of distinct adjacent pairs in geometrically distributed words |
| title_full | The number of distinct adjacent pairs in geometrically distributed words |
| title_fullStr | The number of distinct adjacent pairs in geometrically distributed words |
| title_full_unstemmed | The number of distinct adjacent pairs in geometrically distributed words |
| title_short | The number of distinct adjacent pairs in geometrically distributed words |
| title_sort | number of distinct adjacent pairs in geometrically distributed words |
| topic | mathematics - combinatorics 05a15, 05a05 |
| url | https://dmtcs.episciences.org/5686/pdf |
| work_keys_str_mv | AT margaretarchibald thenumberofdistinctadjacentpairsingeometricallydistributedwords AT aubreyblecher thenumberofdistinctadjacentpairsingeometricallydistributedwords AT charlottebrennan thenumberofdistinctadjacentpairsingeometricallydistributedwords AT arnoldknopfmacher thenumberofdistinctadjacentpairsingeometricallydistributedwords AT stephanwagner thenumberofdistinctadjacentpairsingeometricallydistributedwords AT markward thenumberofdistinctadjacentpairsingeometricallydistributedwords AT margaretarchibald numberofdistinctadjacentpairsingeometricallydistributedwords AT aubreyblecher numberofdistinctadjacentpairsingeometricallydistributedwords AT charlottebrennan numberofdistinctadjacentpairsingeometricallydistributedwords AT arnoldknopfmacher numberofdistinctadjacentpairsingeometricallydistributedwords AT stephanwagner numberofdistinctadjacentpairsingeometricallydistributedwords AT markward numberofdistinctadjacentpairsingeometricallydistributedwords |