Hitting a line in a $d$ dimensional cube Let $F$ be a finite field of order $n$, and let $d$ be an integer. A line in $F^d$ is a function $\ell: F \to F^d$ given by $\ell(t) = x + t*h$, where $x,h \in F^d$, $h \neq 0$, and $t*h = (tx_1, \ldots, tx_d)$.
For $3 \le k \le n$, how many uniformly chosen points in $F^d$ are needed to be drawn such that with high probability (say $2/3$), the set of drawn points contains $k$ different points from (any) line?
Clarification: the last line refers to a set that contain at least one line (not all lines). 
Edit: a rough estimation regarding the number of draws needed (e.g., $O(n^d)$, $O(n^{d/2})$, $poly(d \log n)$, $O(d \log n)$, etc.) would also be very helpful.
 A: I think you need to consider arcs (when $d=2$) or caps (when $d>3$).  The normal definition of an cap is a collection of points, no three on a common line (an arc actually only coincides with this definition in a plane).  What you are interested in are the number of $(s,k-1)$-caps (common literature will refer to $(k,d)$-arcs in planes, this is a generalization); this will be a set of $s$ points such that no more than $k-1$ are on a common line. Any set of size $s$ will either be a $(s,k-1)$-cap, or else have the property you are interested in.
Unfortunately the best reference I can find is mangled in the postscript conversion (weak).
[Old answer refers to the problem of ensuring every line contains at least $k$ points]
This is not an easy problem at all. The first question would be, how many points do you need in a set $\mathcal{S}$ for it to even be possible that every line contains at least $k$ points of $\mathcal{S}$? Such a set is called a $k$-fold blocking set (with respect to lines).  You can see some details here.  I think this type of problem is more difficult in affine spaces than in projective spaces.  To do an analysis of the probability, you would need to know how many $k$-fold blocking sets of size $s$ there were, and you could compare that to ${q^d \choose s}$.
Unfortunately I can't give you an answer, just point out that these are well-studied objects (with lots of related open problems). Probably the most interesting (and well studied) area of research is on small blocking sets in projective planes (a search on google scholar for the term "blocking sets" will turn up lots of results).
