2
$\begingroup$

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$.

$\endgroup$
4
  • 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$ Jan 18, 2015 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, 2015 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, 2015 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, 2015 at 3:39

4 Answers 4

9
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2015 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, 2015 at 10:24
  • $\begingroup$ Ah, okay, I didn't read the last part of a question. $\endgroup$
    – Wojowu
    Jan 18, 2015 at 10:25
  • $\begingroup$ @Wojowu: Bill is correct; I wanted the answer for a specific $p_k$. $\endgroup$
    – Ritwik
    Jan 18, 2015 at 11:41
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)$

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .