1
$\begingroup$

In this Code Golf question, programmers were challenged to write a function with an interesting property:

Your task here will be to implement a function that forms a permutation on the positive integers (A bijection from the positive integers onto themselves). This means that each positive integer should appear exactly once in the permutation. The catch is your function should have a larger probability of outputting an odd number than an even number.

To avoid confusion or ambiguity I am going to clearly lay out what is meant by probability in this question.

Let us say we have a function $f$. The probability of a number being odd will be defined as the limit of ratio odd members of the set to the size of the set $f(1 \ldots n)$ as $n$ tends towards infinity.

As an extra challenge, the question suggested trying to:

Write a permutation that has no defined probability (that is there is no limit).

In this response to the challenge, a user suggested this sequence:

It [= the supplied solution] indexes a sequence that [first] contains $2^{0}$ odd numbers, then $2^{1}$ even, then $2^{2}$ odd, then $2^{3}$ even, and so on.

Correct me if I'm wrong, but I believe this sequence is:

$S(n) =$

  • the smallest odd number greater than the previous odd number in the sequence if $\lfloor log_{2}(n) \rfloor$ is even
  • the smallest even number greater than the previous even number in the sequence if $\lfloor log_{2}(n) \rfloor$ is odd

With $S(1)=1$ and $S(2)=2$.

The user who posted this solution said that they believed this sequence did not have the described limit, as desired, but admitted that they did not know for sure.

Is the user who posted this sequence correct? If not, what is the desired limit?

$\endgroup$
1
  • $\begingroup$ My calculus and understanding of sequences are a bit rusty, so I apologize if any of the notation or descriptions in my question are incorrect. Feel free to edit my question to correct me or tell me what I did wrong, even if it somewhat changes the meaning of the question. $\endgroup$
    – Kevin
    Commented Sep 4, 2017 at 5:06

3 Answers 3

2
$\begingroup$

Let us talk of block $k$ as the set of $2^k$ numbers of the same parity. For example, block $2$ is the block of $2^2$ odd numbers. If $k$ is even, at the end of block $k$ we have $1+4+16+\ldots 2^k=\frac {4^{\frac k2+1}}3\approx \frac 23\cdot 2^{k+1}$ odd numbers out of $2^{k+1}-1$ total numbers for a density of about $\frac 23$. If $k$ is odd we have twice as many evens as odds for an odd density of $\frac 13$. The density will oscillate between $\frac 23^-$ and $\frac 13$ forever, so there is no limit. The user is correct.

$\endgroup$
1
$\begingroup$

Just try to track the ratio.

  • After the $2^0$ odd numbers, the ratio is $1$.
  • After the $2^1$ even numbers, the ratio decreases to $1/3$.
  • After the $2^2$ odd numbers, the ratio increases to $5/7$.
  • After the $2^3$ even numbers, the ratio decreases to $5/15$.

More succinctly, the ratio oscillates between decreasing to $\frac{(2^{k+1}-1)/(4-1)}{(2^{k+1}-1)/(2-1)} = \frac{1}{3}$ after adding $2^k$ even numbers, and increasing to $\frac{(2^{k+1}-1)/(4-1) + 2^{k+1}}{(2^{k+1}-1)/(2-1) + 2^{k+1}} = \frac{\frac{1}{3} (1 - 2^{-(k+1)}) + 1}{(1 - 2^{-(k+1)}) + 1} \approx \frac{2}{3}$ after adding $2^{k+1}$ odd numbers.

So in the limit the ratio will oscillate between $1/3$ and $\approx 2/3$ (while approaching $2/3$ from below).

$\endgroup$
1
$\begingroup$

As the user whose sequence started this question, I'd like to supply the proof I was at first too lazy to do :—). The both other answers are great for getting the intuition, but here's (an attempt for) a solid proof I was whining about not having.

We want to prove that the sequence $a_n = \frac{\text{# of odd numbers in $\{S(k) | 1 \leq k \leq n\}$}}{n}$, with $S(k)$ defined as in the OP, has no limit. From the definition, we know that a sequence $a_n$ has the limit $L$ if and only if $$ \forall\ \varepsilon > 0\ \exists\ N \in \mathbb N\ \forall\ n > N: |a_n - L| < \varepsilon. $$ Negating, we see that $L$ is not the limit of $a_n$ if and only if $$ \exists\ \varepsilon > 0\ \forall\ N \in \mathbb N\ \exists\ n > N: |a_n - L| \geq \varepsilon. $$ If this holds for any $L$, there's no limit at all. So we want to prove $$ \forall\ L \in \mathbb R\ \exists\ \varepsilon > 0\ \forall\ N \in \mathbb N\ \exists\ n > N: |a_n - L| \geq \varepsilon. $$

We see that $\frac 1 3 \leq a_n \leq 1$. Because of that, we can already say that if $L < \frac 1 3$, we choose $\varepsilon < \left|\frac 1 3 - L\right|$ and the condition is OK. Similarly, if $L > 1$, we choose $\varepsilon < |1-L|$.

Now we have the luck of knowing that all $a_{4^k-1} = \frac 1 3$ (for $k \in \mathbb N$). So if $\frac 1 3 < L \leq 1$, we can just choose $\varepsilon < \left|\frac 1 3 - L\right|$. Then, for any $N$, we can take $n$ to be the next higher number of the form $4^k-1$. The condition is then trivially fulfilled.

So there is only one possible $L$ left, and that's $\frac 1 3$. Fortunately we know that all $a_{2^{2k+1}-1} > \frac 2 3$, so we can safely choose $\varepsilon = \text{(say)} \frac 1 6$. Then, for any $N$, we can take $n$ to be next higher integer of the form $2^{2k+1}-1$ and we're done.

With this, the clause "$L$ is not a limit" is seen to hold for all real $L$; hence, the sequence has no limit.

Edit: I'd like to point out that the $a_{2^{2k+1}-1}$'s close on to the limit of $\frac 2 3$ from above, not below (which is what the other answers state). It's best seen when we expand the numerator and denominator as a sum of some powers of 2: $$ a_{2^{2k+1}-1} = \frac 1 3 \frac{2^{2k+2}-1}{2^{2k+1}-1} = \frac 1 3 \frac{1 + 2 + 2^2 + \ldots + 2^{2k+1}}{1 + 2 + 2^2 + \ldots + 2^{2k}} = \\ = \frac 1 3 \left[ 1 + \frac{2^{2k+1}}{1 + 2 + 2^2 + \ldots + 2^{2k}} \right] = \frac 1 3 \left[ 1 + \frac{2^{2k+1}}{2^{2k+1}-1} \right] = \frac 1 3 \left[ 1 + \frac{1}{1 - 2^{-2k-1}} \right].$$

The second fraction is always a little larger than 1, because the denominator is always somewhat smaller than 1. Hence the 2/3 is approached from above.

$\endgroup$

You must log in to answer this question.

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