Limit probabilities for random sparse bit strings

MaRDI QIDQ1378516zbMATH OpenFDO

Authors Katherine St. John

Publication date 15 February 1998

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119196, http://www.emis.de/journals/EJC/Volume_4/Abstracts/v4i1r23.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

almost sure theoryinfinitely differentiable functionsrandom unary predicate under linear order

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Zero-one laws (60F20)

Review text

Summary: Let \(n\) be a positive integer, \(c\) a real positive constant, and \(p(n) = c/n\). Let \(U_{n,p}\) be the random unary predicate under the linear order, and \(S_c\) the almost sure theory of \(U_{n,\frac{c}{n}}\). We show that for every first-order sentence \(\phi\): \[ f_{\phi}(c) = \lim_{n\rightarrow\infty} \text{Pr}[U_{n,\frac{c}{n}} \text{ has property } \phi] \] is an infinitely differentiable function. Further, let \(S = \bigcap_c S_c\) be the set of all sentences that are true in every almost sure theory. Then, for every \(c>0\), \(S_c = S\).

Recommendations

• scientific article; zbMATH DE number 1136073
• Limiting probabilities of first order properties of random sparse graphs and hypergraphs
• Random sparse unary predicates

Cited in

(6)

• The distribution of condition numbers of rational data of bounded bit length
• Limits on the Computational Power of Random Strings
• On a Conjecture about Binary Strings Distribution
• Random sparse unary predicates
• scientific article; zbMATH DE number 1136073 (Why is no real title available?)
• Constrained Embedding Probability for Two Binary Strings

This page was built for publication: Limit probabilities for random sparse bit strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1378516)