StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POOptimal choice from 4 or 5 uniformly distributed random numbers with unknown range
text
Body
copied!<p>Consider a hidden set of <code>k</code> random numbers <code>{r1,r2...rk}</code> chosen with uniform probability distribution from the range <code>[0..N]</code>, <strong>where N is unknown to me</strong>. In each time interval, the number <code>ri</code> is revealed to me and I have the choice of either choosing <code>ri</code> as my final number <code>c</code>, if I haven't already made a choice for <code>c</code>, or moving on to the next time interval. When <code>ri</code> is revealed to me I can no longer choose any of <code>r1,r2..r(i-1)</code>. If I haven't chosen a number by the time <code>rk</code> is revealed then, by default, that becomes <code>c</code>.</p> <p><em>I want to optimise c, in the sense maximizing its expected value.</em> </p> <p>If <code>N</code> was known then the answer is obvious. Similarly, if <code>k</code> is large then I can use the early values of <code>ri</code> to estimate <code>N</code>.</p> <p>Progress so far:</p> <p>if <code>k = 1</code> then there is no choice. By default <code>c=r1</code>. The expected value of <code>c</code> is <code>N/2</code>.</p> <p>if <code>k = 2</code> then all choice algorithms are identical with expected value <code>N/2</code>.</p> <p>If <code>k = 3</code> then the best algorithm is </p> <pre><code>if r2/r1 >= 0.75 then c=r2 else c=r3 </code></pre> <p>The expected value of <code>c</code> is approximately <code>0.58N</code>.</p> <p>If <code>k = 4</code> then the best I have come up with is </p> <pre><code>if r2/r1 > 0.920 then c=r2 elseif r3/r1 > 0.665 then c=r3 else c=r4 </code></pre> <p>The expected value of <code>c</code> is approximately <code>0.64N</code>. I believe I should be able to do a little better by 'using' both the values of <code>r1</code> and <code>r2</code> in choosing if to accept <code>r3</code> as my chosen value but an analytical solution escapes me.</p> <p>Can anyone provide a better algorithm for <code>k=4</code> and/or <code>k=5</code>?</p> <p><strong>Notes re Secretary problem:</strong> In all versions of the SP i can find, you onl;y have information on the relative rank of candidates to those that have already appeared. But in this problem you have a value for each candidate (of course from an unknown range [0..N]) and by utilising the ratio of values you can do better. For example, the SP solution to the k=3 problem (choose p2 if p2 > p1 else choose p3) has an expected return of o.5833N, whereas my solution (choose p2 if p2/p1 > 0.75 else choose p3) has an expected return of 0.5937. </p> <p>My best return so far for the problem for any k is:</p> <pre><code> i = 0 repeat inc(i) until (r[i]/Max(r[1]..r[i-1]) > V[i]) or (i=k) c=r[i] </code></pre> <p>where for any chosen k, v[i] (or call it v[k,i] if you prefer) is a pre-chosen array of real values. The standard solutions to the secretary problem uses only values of inf and 1 in V V=[inf,...inf,1,...,1], whereas I can do better (at least for small k) by using reals in V. But I believe my solution is still sub-optimal as I utilize only the value of Max(r1..ri), whereas there must be 'hidden' information in the distribution of r1..ri values at each decision point.</p> <p>Best solutions to date:</p> <pre><code>k = 3 : v = [inf,0.75] : cexp = 0.58N k = 4 : v = [inf,0.92,0.66] : cexp = 0.665N k = 5 : v = [inf,inf,0.82,0.63] : cexp = 0.6683N </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload