PreprintarXiv licencearXiv
The Expected Number of Distinct Substrings in an Alphabet String
Abstract
Consider a sequence of i.i.d.~trials X={X1, X2, …, Xn} where p(Xi=j)=1/d; j=1,2,…, d, or more generally p(Xi=j)=pj; ∑1≤ j≤ dpj=1. We consider the variable D that counts the number of distinct substrings of all lengths,1≤ k≤ n in X and prove results concerning E(D).
Related
- Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
- Global universality of the expected number of zeros of non-analytic random signals
- The Tight Upper Bound on the Number of Distinct Squares in Circular Words
- On the Number of Distinct Topological Bases of a Finite Set of Size N
- A Combinatorial Proof of Partition Identities for the Number of Distinct Part Sizes
BibTeX
@misc{godbole2026expected,
title = {{The Expected Number of Distinct Substrings in an Alphabet String}},
author = {Anant Godbole},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19409},
eprint = {2609.19409},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19409},
}
RIS
TY - UNPB
TI - The Expected Number of Distinct Substrings in an Alphabet String
AU - Anant Godbole
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19409
UR - https://arxiv.org/abs/2609.19409
AB - Consider a sequence of i.i.d.~trials X={X_1, X_2, …, X_n} where p(X_i=j)=1/d; j=1,2,…, d, or more generally p(X_i=j)=p_j; ∑_1≤ j≤ dp_j=1. We consider the variable D that counts the number of distinct substrings of all lengths,1≤ k≤ n in X and prove results concerning E(D).
ER -