TL;DR; I am looking for a formula to do one random draw for
"$f_P(X)$ = the smallest number of a set of $X$ numbers, if each number is choosen with Probability $P$?"
First of all, I am sorry if I butcher some math linguistic, e.g. using "Probability" or "random draw" wrongly. Although I like math, I am a programmer by profession and by heart, so my terminology might be inaccurate. :-} (please correct me, though! :D)
Now, I am pondering over a math calculation problem for a code I am writing here (for a game, actually). The problem is the following: From a huge list of things, every item of the list has a very small probability of being "choosen". Lets make a concrete example: If you have Numbers from 1 to a Billion ($X=10^9$). And every number has a probability of being "choosen" of $P=0.001\%=10^{-5}$. What is an efficient way of doing one random sample selection set of all choosen numbers?
The straight-forward way of doing this would be to look at each number individually, flip a coin (with $P=10^{-5}$) and randomly either choose it or not, remembering all choosen numbers this way. Unfortunately, that means, I have to flip my coin 1 Billion times (once for each possible number). In the end, there will be only approximately $\frac{10^9}{10^{-5}}=1000$ numbers choosen, so I might have gotten away with only 1000 coin flips.
The next idea I had was to first randomize "how many numbers there will probably be choosen". Then make an urn with 1 Billion numbers in it and start drawing without "putting back". I am not 100% sure about the exact formulas involved here, but this idea has another issue: "Drawing numbers without putting back" from a large pool of numbers is not very efficient for the programming circumstances I had in mind either.
So finally my last idea was, that is should be possible to have a formula for the following statement (for one random draw):
"$f_P(X)$ = the smallest number of a set of $X$ numbers, if each number is choosen with Probability $P$ or $X+1$ if not a single number was choosen?"
Then, I could first run the formula with $X_0=f_P(10^9)$ to get my first number. Then again with $X_1=X_0 + f_P(10^9 - X_0)$ and so on... $X_{m+1} = X_m + f_P(10^9 - X_m)$ until $X_m \geq 10^9$.
This would hopefully result in a lot less dice rolling and should give the exact same probability distribution as the original "straight-forward" solution, right?
Now I am stuck trying to meld this into one formula.
I tried to start with a solution for a very simple case like $f_{0.1}(10)$. Well, the probability that $f_{0.1}(10)=1$ is clearly $10\%$ (namely if the first number is choosen. Then the others don't matter anymore). Then for $f_{0.1}(10)=2$ its $0.9*0.1 = 0.09$ (first is not choosen, but second is) and so on until for $f_{0.1}(10) = 11$ its about $0.9^{10} \approx 0.35$. I can calculate that for every number, multiply by the number and sum everything up to get my expected value.
Well, but that is a lot of multiplying and adding. That was not the point of the exercise ;-), as I wanted to reduce my number of needed calculations! Is there a way to get from this to a formula where I just plug in $X$ and $P$ and do a couple of operations and some coin flipping or dice rolling?
I am not sure whether I understand your question correctly, but I think the question you are asking is directly related to the question 'What is the expected value of the geometric distribution?', which you can easily find, e.g. on https://en.wikipedia.org/wiki/Geometric_distribution
A word of explanation on how I understand your question. The random process where each item in your list X has a probability p is simply a repitition of a Bernoulli experiment; the fact that you are asking the question "which item will have the first success?" is precisely encaptured by the geometric distribution. In principle, you might encounter the problem with your finite set X that (in your language) no number at all will be selected, which precisely means that no Bernoulli experiment will be succesfull. As long as your probability p is much bigger than 1/(size X) (as in your example with size(X)=10^9 and p=10^-5) the probability of no such success will be neglible, though, so you can safely work with the geometric distribution.