Random Sidon sequences (Q1283038): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:16, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random Sidon sequences |
scientific article |
Statements
Random Sidon sequences (English)
0 references
26 May 1999
0 references
Consider a subset \(A\) chosen randomly from the \( n \choose k_n\) subsets of size \(k_n\) of \([1, 2,\dots, n]\). The paper investigates the probability that such a set has the \(B_h\) property, that is, whether the sums of \(h\) elements of \(A\) are all distinct. It is proved that if \(k_n/n^{1/2h} \rightarrow \Lambda \) as \(n \rightarrow \infty \), then this probability tends to \( \exp \bigl( -\kappa _h \Lambda ^{2k} \bigr) \) with certain positive constants \(\kappa _h\). In particular, if \(k_n/n^{1/2h} \rightarrow 0\), then almost all sets have the \(B_h\) property, and if \(k_n/n^{1/2h} \rightarrow \infty \), then almost all do not have it. The proofs are based on Janson's inequality and the Stein-Chen approximation for positively related random variables.
0 references
Sidon sets
0 references