5
$\begingroup$

Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,

$$Y := \inf \{n \in \mathbb N \, | \, \text{There exists a }k\text{-term arithmetic progression in } S \cap \{1, \dots, n\}\}.$$

What is the expected value of $Y$?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ The expected number of arithmetic progressions is around $\frac{N^2}{2^{k+1} k}$, so the order of magnitude of $Y$ should be around $2^{\frac{k+1}2} \sqrt k$. I think you could bound the variance and use Chebyshev's inequality to make this formal $\endgroup$
    – Daniel Weber
    Commented Feb 8 at 18:37
  • 2
    $\begingroup$ I computed some approximate results (starting at $k = 2$): 3.9932, 8.4313, 14.8136, 24.8434, 37.7542, 59.709, 88.4907, 130.4022. (Each of these is just the result of running it 10,000 times) $\endgroup$
    – paste bee
    Commented Feb 8 at 18:44
  • $\begingroup$ @CommandMaster: Could you please write out your derivation details as an answer? $\endgroup$
    – Hans
    Commented Mar 19 at 3:20

1 Answer 1

Reset to default
4
$\begingroup$

See Maximal Arithmetic Progressions in Random Subsets by Benjamini, Yadin and Zeitouni, ECP 12: 365-376 (2007) and the erratum in ECP 17: 1-1 (2012). See also the extensions in

M.-Z. Zhao and H.-Z. Zhang, On the longest length of arithmetic progressions, arXiv:1204.1149 (2012).

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .