Suppose $\{ p_{k} \}$ is a collection of real numbers with the following properties:

1) $p_k \in (0,1)$ $~~~~$(i.e. $0$ and $1$ are not allowed values)

2) $\sum_{k=1}^{\infty} p_k =1$

An example of such a collection is $p_k := \frac{6}{\pi^2 k^2}$. You are free to choose any such collection in order to answer the following question:

Can you generate a sequence of natural numbers $\{x_n\}$ with the following property: $$ \lim_{N \rightarrow \infty}\frac{\#\{n \in [1,N]: x_n = k \}}{N} = p_k \qquad \forall k.$$

My criteria for "generating" a sequence means I should actually be able write a program to generate these $\{x_n\}$. I am not looking for an abstract existential result; ideally the $x_n$ should be given by an explicit formula.

To clarify my question; you can choose whatever $p_k$ you want to answer my question, as long as it satisfies conditions $1)$ and $2)$. You can take the specific example $p_k := \frac{6}{\pi^2 k^2}$ I gave, but that is not necessary. Again, the only condition is that given $k$ I should actually be able to evaluate $p_k$; it should not be something that is given indirectly or which is merely shown to exist theoretically. Ideally, $p_k$ should be a formula in terms of $k$.


migrated from mathoverflow.net Jan 19 '15 at 3:16

This question came from our site for professional mathematicians.

  • 4
    $\begingroup$ This really isn't research level, but you can get a very elegant solution by splitting $[0,1]$ into intervals of length $p_k$ and taking multiples of any irrational number mod 1. $\endgroup$ – Eric Wofsey Jan 18 '15 at 19:13
  • $\begingroup$ @Eric: Can you explain a bit more? I split [0,1] into those intervals and choose any irrational number $\alpha$. After that what is x_n? $\endgroup$ – Ritwik Jan 18 '15 at 20:39
  • $\begingroup$ Eric means the following: let $(I_k)_{k=1}^\infty$ be a sequence of pairwise disjoint intervals whose union is equal to $[0,1]$, and such that each interval $I_k$ has length $p_k$. Let $\alpha \in \mathbb{R}\setminus \mathbb{Q}$. Define $x_k:=p_n$ if and only if the fractional part of $k\alpha $ belongs to $I_n$. The property which you require then follows from Weyl's Criterion on equidistributed sequences. $\endgroup$ – Ian Morris Jan 18 '15 at 22:05
  • $\begingroup$ @Ian: Thank you, thats clear now. This is actually the sort of answer I was looking for (i.e. there is some starting seed and then the rest of the numbers are generated from the seed). $\endgroup$ – Ritwik Jan 19 '15 at 3:39

Let $p_k = 1/2^k$ and $x_k = n$ if $k = 2^{n-1}(2m - 1)$ for some integer $m>0$. I believe this works.

  • $\begingroup$ I don't think this is what OP wants, because you only gave an example for single specific choice of $p_k$. $\endgroup$ – Wojowu Jan 18 '15 at 10:21
  • $\begingroup$ When Ritwik wrote "you can choose whatever $p_k$ you want" I took that to mean that all that was wanted was a solution for a particular $p_k$, not for a general $p_k$, but I could be wrong. $\endgroup$ – user24142 Jan 18 '15 at 10:24
  • $\begingroup$ Ah, okay, I didn't read the last part of a question. $\endgroup$ – Wojowu Jan 18 '15 at 10:25
  • $\begingroup$ @Wojowu: Bill is correct; I wanted the answer for a specific $p_k$. $\endgroup$ – Ritwik Jan 18 '15 at 11:41

Let me provide an algorithm for arbitrary $\ (p_k)$.

Let $\ (p_k: k=1\ 2\ \ldots)\ $ be an arbitrary sequence of positive real numbers $\ p_k>0\ $ such that $\ \sum_{k=1}^\infty p_k=1.\ $ Then define $\ x_n\ $ as the smallest natural number $\ x_n=k\ $ such that:

$$\frac 1n\cdot \left|\{m<n:x_m=k\}\right|\ \ <\ \ p_k$$

(This indeed is an algorithm rather than a closed formula).

REMARK   This would work even for a little more general (weaker) assumption $\ p_k\ge 0$.


Bill J's example from above admits a simple generalization. Consider an arbitrary integer $\ a>1.\ $ Let

  • $\ \forall_{k=1\ 2\ \dots}\ \ p_k := \frac{a-1}{a^k}$
  • $\ \forall_{k\ n=1\ 2\ \ldots}\ \ \left(x_n:=k\quad\Leftarrow:\Rightarrow\quad a^{k-1}\, |\, n\not\equiv 0 \mod a^k\right)$

REMARK   The above example, including the one by Bill J, is a special case of my general algorithm above.


Another example is the following:
Let $p_k=\frac{1}{s_k}$ where $s_k$ denotes the $k$-th term of the Sylvester sequence.

It is well known that the sum of its reciprocals converges to $1$, and of course $p_k=\frac{1}{s_k}\in (0,1)$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.