A Caltech Library Service

The capacity of some Pólya string models

Elishco, Ohad and Farnoud, Farzad and Schwartz, Moshe and Bruck, Jehoshua (2016) The capacity of some Pólya string models. In: 2016 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 270-274. ISBN 978-1-5090-1807-9.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study random string-duplication systems, called Pólya string models, motivated by certain random mutation processes in the genome of living organisms. Unlike previous works that study the combinatorial capacity of string-duplication systems, or peripheral properties such as symbol frequency, this work provides exact capacity or bounds on it, for several probabilistic models. In particular, we give the exact capacity of the random tandem-duplication system, and the end-duplication system, and bound the capacity of the complement tandem-duplication system. Interesting connections are drawn between the former and the beta distribution common to population genetics, as well as between the latter system and signatures of random permutations.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle ItemTechnical Report Paper
Elishco, Ohad0000-0002-8551-1592
Farnoud, Farzad0000-0002-8684-4487
Schwartz, Moshe0000-0002-1449-0026
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2016 IEEE. This work was supported in part by the NSF Expeditions in Computing Program (The Molecular Programming Project).
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20160824-102815029
Persistent URL:
Official Citation:O. Elishco, F. Farnoud, M. Schwartz and J. Bruck, "The capacity of some Pólya string models," 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016, pp. 270-274. doi: 10.1109/ISIT.2016.7541303 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69897
Deposited By: Tony Diaz
Deposited On:24 Aug 2016 21:31
Last Modified:04 Oct 2019 17:31

Repository Staff Only: item control page