Racionalidad distribuida uniformemente

Question

¿Existe algún algoritmo, función o fórmula $f(n)$ que es una biyección entre los enteros positivos y los racionales en $(0,1)$ con la condición de que para todos los números reales $a,b,x$ con $0<a<b<1<x$ si dejamos que $i(x)$ sea el número de enteros distintos $0<n_j<x$ que satisfacen $a<f(n_j)<b$ entonces tenemos $\lim_{x\rightarrow\infty}i(x)/x=b-a$ ?

Answer 1

Van der Corput es un poco exagerado. Da una secuencia con una discrepancia especialmente baja, pero eso es más de lo que se necesita para una distribución uniforme.

Hay un teorema de von Neumann que dice que cualquier conjunto contable de reales denso en $(0,1)$ puede ordenarse de forma que se convierta en una secuencia uniformemente distribuida. Una forma de hacerlo es enumerar el conjunto de cualquier manera, por ejemplo, $s_1,s_2,\dots$ y también anotar una lista de intervalos $I_1,I_2,\dots$ donde los dos primeros intervalos de partición $(0,1)$ en dos trozos iguales, las tres siguientes particiones $(0,1)$ en tres trozos iguales, etc. Luego, para cada $j$ , $j=1,2,\dots$ , dejemos que $u_j$ ser el primero no utilizado $s_j$ en $I_j$ . Entonces $u_1,u_2,\dots$ se puede demostrar que es un ordenamiento uniformemente distribuido de su conjunto denso.

Answer 2

Está buscando un equidistribuido secuencia de racionales que utiliza cada racional exactamente una vez. El Secuencia Van der Corput mencionada por GEdgar se aproxima, salvo que se le escapan algunos de los racionales. Pero puedes echar los números que faltan, siempre que los repartas.

Por ejemplo, la secuencia binaria de Van der Corput utiliza todos los racionales diádicos. Si se enumeran los racionales no diádicos y se inserta el $k$ a la secuencia en la posición $2^k$ , por ejemplo, se puede comprobar que la nueva secuencia sigue siendo equidistribuida. La clave es la del primer $N$ en la secuencia, sólo $o(N)$ han sido modificados.

Answer 3

Los racionales diádicos positivos menores que 1 son:

$$\large \frac{n+1/2}{2^{ \lfloor log_2 n \rfloor }} -1$$

Utilizando este formulario:

(x+1/2)/(2^floor(log(abs(x))/log(2)))-1

Yo grafico esto:

*El gráfico muestra un rango de 0..2, pero la fórmula en realidad tiene un rango de 0..1.

una progresión de numeradores Impares sobre potencias crecientes de dos denominadores en intervalos enteros positivos.

from math import log2,floor
from fractions import Fraction
def dyadics(n=Fraction(1,1)):
    while 1:
        yield (2*n+1)/2**floor(log2(n)+1)-1
        n += 1
in_sequence = dyadics()
for n in range(2**4):
    print(next(in_sequence))

1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, 1/16, 3/16, 5/16, 7/16, 9/16, 11/16, 13/16, 15/16, 1/32

Answer 4

(Puede que haya interpretado mal esta pregunta. Me encontré con esta pregunta mientras me preguntaba si es posible construir una variable aleatoria "uniforme" que genere racionales. Creo que es imposible).

Consideremos una variable aleatoria $X$ sobre los racionales en (0,1). Una forma de definir una distribución "uniforme" es la siguiente regla:

$$ \mathrm{P}(a < X < a+\epsilon) = \epsilon $$

para cualquier $0 < a < a+\epsilon <1$ . Esto dice que la probabilidad de que un número extraído de $X$ está en el intervalo $(a,a+\epsilon)$ es igual a $\epsilon$ y, en particular, la probabilidad es independiente de $a$ .

La probabilidad de que $X$ es igual a cualquier racional particular, $r$ debe ser cero. Una prueba por contradicción: Si existiera un $r$ tal que

$$ \mathrm{P}(X = r) = p_r > 0 $$

entonces se podría construir un intervalo alrededor de $r$ que es más estrecho que $p_r$ como por ejemplo $(r-\frac13 p_r, r+\frac13 p_r)$ . Por nuestra regla anterior, es debe sea el caso que

$$ \mathrm{P}(r-\frac13 p_r < X < r+\frac13 p_r) = \frac23 p_r $$

pero esto contradice la suposición de que ya existe un único elemento en ese intervalo que tiene probabilidad $p_r$ . No hay suficiente masa de probabilidad en el intervalo arbitrariamente pequeño para permitir que los racionales individuales tengan probabilidades distintas de cero.

Por lo tanto, la masa de probabilidad asociada a cualquier racional debe ser cero. (O quizás hiperreal .)

Ahora, es trivial construir una distribución (posiblemente no uniforme) sobre los racionales, que llamaré $Y$ . Dibuja el denominador, $d$ de una distribución entera adecuada (como Geometría ) y dibujar el numerador, $n$ de manera uniforme desde el rango $0<n<d$ . Para cada racional $r$ habrá una probabilidad no nula de que se genere a partir de ese esquema simple:

$$ \mathrm{P}(Y=r) > 0 $$

y, por supuesto, estos deben sumar 1 para ser una distribución de probabilidad adecuada:

$$ \sum_{r \in \mathcal{Q}} \mathrm{P}(Y=r) = 1 $$

Por último (y no estoy seguro de haberlo entendido bien...), las probabilidades de cada elemento de X (cero) son menores que las de cada elemento de Y (distinto de cero).

$$ \forall r \qquad \mathrm{P}(Y=r) > \mathrm{P}(X=r) $$

y por lo tanto la suma para X, $ \sum_{r \in \mathcal{Q}} \mathrm{P}(X=r) $ no puede sumar 1. Cada término de la suma de X es menor que el término correspondiente de Y. Por lo tanto, no puede existir tal distribución sobre los racionales.

(Esta respuesta probablemente no sea novedosa, no soy un especialista. Pero me interesa esta pregunta. Se agradece cualquier comentario).