2
$\begingroup$

I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$.

Another agent $B$ will observe $k$ consecutive elements from the sequence. Then it will update its belief about the probability of $p_i$ using a belief update rule (let's say a simple frequentist, i.e., the number of occurrences of each digit divided by $k$).

The question is how can I generate the sequence such that $B$'s belief $q$ is close to $p$, i.e., $d(p,q)$ is minimized where $d(p,q)$ is the dsitance function of two distributions, e.g., $d(p,q)=(\sum_i (p_i-q_i)^2)^0.5$.

Note that I don't know how $B$ will choose the $k$ numbers. Let's consider the worst case (i.e., worst $p'$).

$\endgroup$
  • $\begingroup$ is this an appropriate paraphrase of the question - is there a sequence $p$ such that every substring of length $k$ has "almost" $p_i$ $i$'s? $\endgroup$ – gabgoh Nov 4 '10 at 6:14
  • $\begingroup$ @gabgoh: I guess the prior makes things more complicated. If $k$ is small, I guess you need to "overshoot" a bit to convince $B$ that some elements are really very frequent or very rare, contrary to your prior? $\endgroup$ – Jukka Suomela Nov 4 '10 at 12:10
  • $\begingroup$ You are right. Any ideas or any suggestions on related work? $\endgroup$ – Mike Nov 4 '10 at 18:58
  • $\begingroup$ The worst case is that B's prior focuses all probability on, say, 0. This prior will never change in response to any finite input. $\endgroup$ – whuber Nov 5 '10 at 2:50
  • $\begingroup$ The distribution $p$ is fixed. Only consider the worest $p'$. $\endgroup$ – Mike Nov 5 '10 at 4:33
5
$\begingroup$

For observing consecutive elements: pick up the best sequence of $k$ elements (depending on your proximity measure), and repeat it. Then B will always observe the same sequence (I assume that cyclical permutation doesn't affect B).

For observing random elements: how would you pick them randomly? Do you want a deterministic sequence?

$\endgroup$
  • $\begingroup$ Thanks. Note that I don't know how B will choose the k numbers. Let's consider the worst case. $\endgroup$ – Mike Nov 3 '10 at 23:42
  • 1
    $\begingroup$ If B chooses the k numbers adversarially, then (depending on the metric) she's probably going to choose the same digit over and over again, so your best bet is probably to just use the most probable digit in a constant sequence. $\endgroup$ – Yuval Filmus Nov 4 '10 at 0:47
  • $\begingroup$ You are right. Let's say that B will choose $k$ consecutive elements. Any ideas or any suggestions on related work? $\endgroup$ – Mike Nov 4 '10 at 19:00
  • $\begingroup$ You should pose your problem more fully before it can be discussed further. How do you measure distance between distributions? What is B's estimation algorithm? $\endgroup$ – Yuval Filmus Nov 5 '10 at 2:38
  • $\begingroup$ I just revised the formulation. Let the belief update rule be a simple frequentist. There is a distance function. $\endgroup$ – Mike Nov 5 '10 at 4:31
1
$\begingroup$

To optimize for sequences of $k$ consecutive numbers, you can use a greedy algorithm.

You generate each element successively. You do this by working with a (modifiable) copy of the $p_i$'s, which I'll refer to as $q_i$'s. For the first element, pick the $i$ with the greatest $q_i$, and I'll call the result $r$. Then set $q_r = q_r - 1$. Next, for all $q_i$, including the one you just picked, set $q_i = q_i + p_i$. Now you can repeat this procedure over and over, each time picking the greatest $q_i$.

This algorithm distributes the $i$'s evenly throughout the series. Any subset of consecutive numbers will be about as close as is possible to representing the distribution of the entire series. It also turns your series into repeating cycles of digits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy