Parking for Dummies and a square-root n for Kurt

The focus of the talk to what extend elementary methods can be applied to obtain a basic understanding of the problem (and thus to avoid the generating function method, which I don't understand). Naturally, the results obtained will be weaker than those obtained by Pascal, Daniel and their co-authors.

One question of interest is after how many cars the lot is full, or in the other language, how many coupons have to be bought until a copy of each is obtained.

Hopefully, I shall show the following. Let $n$ be an integer, namely the number of spaces/coupons and $c >2$. Let $p(n,c)$ be the probability that after $cn$ cars the lot is not completely filled (buying $cn$ coupons and reasonable swapping does not suffice to get them all). Then

$\exp(-c) (1 - 1/n)^c \le p(n,c) \le \exp(-c) + K (c \exp(-2c) + \exp(-\sqrt{n}/8)$,

where $K$ is a constant like 8 or so.

In simple word, the "failure probability" is around $\exp(-c)$. Note that this is just the probability that the first coupon is not obtained. Such findings, while surprising at first, are rather typical for randomized asymptotic stuff. Recall, e.g., that the threshold for $G(n,p)$ becoming connected equals the one for having no isolated vertices.

The bound above probably is a simple corollary of the result Pascal talked about.

Added today: In the same spirit is the answer to Kurt's "is there a reason for the square-root n" question, that is, why does an expected number of \sqrt{n} out of n parkers not find a space. For an intuitive "why" (and a rigorous lower bound proof), it suffices to know that with constant probability, more than $n/2+\Theta(\sqrt{n})$ coin throws turn up heads. An upper bound of $O(\sqrt{n \log(n)})$ follows along the same lines using a stupid union bound, which brings me to a problem I have on my list for while now. It's most likely not an "open problem", but something I'd like to understand:

If you have $n$ independent random variables $X_1, ..., X_n$, each in $[0,1]$, and $n$ subsets $I_1, \ldots, I_n$ of the first $n$ integers, then with reasonable probability we have $|\sum_{i \in I_j} X_i - E(\sum_{i \in I_j} X_j)| \le O(\sqrt{n \log n})$ for all $j = 1, ..., n$. This is union bound plus Chernoff bound. This estimate is sharp in most cases. What I'd like to know is what happens if $I_j = \{1, \ldots, j\}$. Of course, the $O(\sqrt{n \log n})$ is still valid, but most likely in this case we can bound all deviations by $O(\sqrt{n})$. If you have any idea on that, in particular an elementary one, I'd be extremely happy to know.

Warnings: (a) This is not the Mittagsseminar. If someone want to give a talk there, I move to somewhen else. (b) This is the outcome of a train ride from Scheidt to Mannheim, so no guarantee for anything. (c) All of the above aims at understanding why the main phenomena of this problem are as they are and at simple proofs. Such simple methods do not suffice to prove the same precise results as the generating functions approach followed by Pascal and co-authors.

Duration: Probably about 30mins, but who knows... But drop in or out any time you like :-)