probability that a random element of Z/NZ can be written as a subset sum of others How could one calculate the probability that any element in $\mathbb{Z}/N\mathbb{Z}$ can be written as a subset sum of $n$ random elements in $\mathbb{Z}/N\mathbb{Z}$?  
In other words, say I pick $n$ random elements $x_1,\ldots,x_n$ for $n << N$ (for example, if $N = 2^k$ then $n=k$).  Then for a random element $r\in{\mathbb{Z}/N\mathbb{Z}}$, what is the probability that $r$ can be written as $\sum_i b_ix_i$, where the $b_i$ values are restricted to be either $0$ or $1$?  
In theory, I expect the probability for the case of $n=k$ and $N=2^k$ to be close to $1$, since if $n=k$ there are $2^k$ choices for the sum, so if $N=2^k$ we could expect this to hit every element.  The obvious problem is that there might be some collisions (for example, $x_1 = x_2 + x_5 + x_8$), and I'm running into trouble bounding the probability of these collisions (which again should be low if the $x_i$ are picked truly at random); it may be totally easy but I'm not seeing it.  It would also be nice to have a more general formula for any choice of $N$ and $n$.
Anyway, any help would be great.  Thanks!
P.S. I suppose one other way of thinking about this is asking, for a random subset $A\subset \mathbb{Z}/N\mathbb{Z}$ such that $|A| = n$, what is the probability that $\mathbb{Z}/N\mathbb{Z}$ can be thought of as a $\mathbb{Z}/2\mathbb{Z}$-module free on $A$.  Not sure if this will make more or less sense (it seems overly complicated at least to me), but it should be the same thing.
 A: Use the second moment method. Let $\bar{b}=(b_1,\ldots,b_n)$ be a coefficients vector like in your question. Let $I_{\bar{b}}$ be the indicator of the event $r=<\bar{b},x>$. Then its easy to see that $\mathbb{E}(I_{\bar{b}})=1/N$. Its also pretty easy to check that $\mathbb{E}(I_{\bar{b}}I_{\bar{b'}})=1/N$ for distinct $\bar{b}$ and $\bar{b'}$. In other words, they are pairwise independent.
Let $X=\sum_{\bar{b}\in\{0,1\}^n} I_{\bar{b}}$. Then $\mathbb{E}(X)=2^n/N$ and $Var(X)=2^n(N-1)/N^2$ and using Chebyshev's inequality gives you that $\mathbb{P}(X=0)$ is small when $2^n \gg N$. 
Gideon Amir and I use a similar method in this paper.
When $2^n \approx N$ I believe the probability does not go to 1, but I don't have the time right now to think about this.
A: If you pick $n$ elements at random, then you get $2^n$ subset sums, unless there is a collision, just as you said. There are $N^n/n! + O(N^{n-1})$ choices for your $x_1,\ldots,x_n$ if you ignore permutations. There are $O(2^{2n})$ possible ways of getting a collision and, for each kind of collision $O(N^{n-1})$ possible $x_1,\ldots,x_n$, since one of them is determined by the others. So, your probability is at most $2^n/N$ and at least $2^n/N(1+O(2^{2n}n!/N)$. This estimate is not so good when $n$ is about $\log N$ (as in your example) but is good for smaller $n$. You can probably refine my estimates.
