A Random Generator Expected Time Sequence

Suppose we have a binary random generator, that is, one that picks between two possibilities with equal probability. Now let’s say we want to create any finite-option random generator, specifically that picks between any n possibilities for any natural number n, incorporating just usages of this binary random generator. If n is a power of 2, one can just distribute the results over the ending possibilities of running the binary random generator \log_2 n times; as an example, if we want to choose between 8 equally likely possibilities, our first run can choose between one set of 4 and the other, our second run can choose between one set of 2 in the 4 and the other, and our third can determine which one to choose out of the 2 we have narrowed down to, a total of \boxed{3} runs of the binary random generator.

But say we want to choose between a number of options that is not a power of 2, say 3. What can we do now?

We can still choose between them with equal probability, using a binary random generator. We build the same type of decision tree as we do for 4 possibilities, but one of the end results is labeled “re-run,” that is, an instruction to go through the process again, hoping that the next time we end up on one of the three other end results (which starting here I will term “leaves”), corresponding to the three choices among which the random generator we have hired will choose. Note that this process could take an infinite amount of time, but with infinitesimal probability; the expected amount of callings of the binary generator is still finite, and can be computed. Call the expected value of the number of callings of the binary generator E. We can then write the equation E=2+\frac{1}{4}E. The process will always take at least 2 usages, but has a \frac{1}{4} chance of needing to be run again, in which case it is expected to take an additional whatever-the-expectation-was-in-the-first-place, since if one ends up in the re-run leaf, it is as if the system said “try again,” and one is back where one started. Solving this simple equation, we get that E=\boxed{2 \frac{2}{3}}, so the expected number of usages of the binary generator needed is actually just under 3, not as quick as in the case with four choices, but definitely not only doable but in fact swifter on average than the next power of 2 after 4, the case with 8 choices.

In fact, we can take this approach with all integers that are not powers of 2. For example, in the case where we are choosing among 7 choices, we can assign one of 8 ending leaves as a re-run leaf and see that we are expected to run the binary generator E=3+\frac{1}{8}E \implies E=\boxed{3 \frac{3}{7}} times. If we are choosing among 6 choices, doing the same but with marking two leaves as re-run leaves gives us E=3+\frac{1}{4}E \implies E=4 for an expected value of number of times the generator is run.

In the case of 6 choices, though, we can do better. Since each of the two re-run leaves are chosen equally likely, and each of the results of the first binary decision are equally likely, we could re-route the locations these leaves go to as the two possibilities after the first decision rather than before the first decision. But what is the expected value of the number of times the generator will need to be used now? If we place the two re-run leaves as close together as possible, it is E=\frac{1}{2}(3)+\frac{1}{2}(1+D), where D is the expected value of the number of times the generator must be used from after the first decision is made (hence, the addition of 1 in the term containing D) and the result is the one where the re-run leaves are possibilities. Building an equation for D, D=2+\frac{1}{4}(2)+\frac{1}{4}D \implies D=\frac{10}{3}. Using this value of D and solving for E above, we get E=\frac{1}{2}(3)+\frac{1}{2}(1+\frac{10}{3})=\frac{3}{2}+\frac{13}{6}=\frac{11}{3}=3 \frac{2}{3}. Note that if we alternatively place the two re-run leaves as far away from each other, then we get the case of making one decision and then redirecting to the case of 3 choices on either result of the first binary generator run, thus having expected value of total binary generator runs be 1+2 \frac{2}{3} (1 for the initial decision, then the expected number of runs for the case with 3 choices), again evaluating to \boxed{3 \frac{2}{3}}.

What if we have 5 choices? There now seems to be a forest of possibilities of where re-run leaves redirect. We could even incorporate the method to choose between 3, each result of which directs to three choose-between-2 cases, where one of the final leaves redirects to the root. We can see that 3 is a clear lower bound for the number of usages of the binary generator needed, but is there a way to easily tell what system of redirections is most efficient?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s