Tengo una bolsa que contiene N monedas. ¿Cuál es la probabilidad de tener un monto redondo en dólares?

Question

En mi país tenemos \$0.10, \$0.20, \$0.50, \$1, y \$2 monedas. Si yo fuera a verter una bolsa de monedas en la mesa ¿cuál sería la probabilidad de que yo podría comprar un montón de \$1 aperitivos sin necesidad de ningún cambio? ¿Este cambio, si la bolsa no contiene todo el valor en dólares de las monedas?

Estoy bastante seguro de que el que $P=0.1$ para valores muy grandes de $N$ (como hay 10 posibles ciento de los valores). Me gustaría ser capaz de probar esto y ser capaz de ver cómo la probabilidad de cambios con $N$, pero no puedo encontrar una regla para toda la serie y los mayores valores de $N$.

He escrito un poco de Python a la simulación de la prueba de $N$ valores $0$ a través de $50$ y voy a editar con el resultado de que cuando finalice.

EDIT: Resultados de mi guión, parecen confirmar mi pensamiento: http://pastebin.com/cD8PeuwT

Answer 1

Usted está en uno de los diez estados; es decir, el número de 10c.
Así que lo tratan como un diez-vector, inicialmente en estado $v=[1,0,0,0,0,0,0,0,0,0]$. La matriz de transición es este, para que no de oro:
$$A=\left[\begin{array}{cccccccccc} 0&1/3&1/3&0&0&1/3&0&0&0&0\\ 0&0&1/3&1/3&0&0&1/3&0&0&0\\ 0&0&0&1/3&1/3&0&0&1/3&0&0\\ 0&0&0&0&1/3&1/3&0&0&1/3&0\\ 0&0&0&0&0&1/3&1/3&0&0&1/3\\ 1/3&0&0&0&0&0&1/3&1/3&0&0\\ 0&1/3&0&0&0&0&0&1/3&1/3&0\\ 0&0&1/3&0&0&0&0&0&1/3&1/3\\ 1/3&0&0&1/3&0&0&0&0&0&1/3\\ 1/3&1/3&0&0&1/3&0&0&0&0&0\end{array}\right]$$ o algo similar con quintas partes si hay oro.
La distribución inicial, para no monedas es $v$; para una moneda es $vA$, para dos monedas es $vAA=vA^2$ $n$ monedas es $vA^n$.
Mira los autovalores de la matriz a ver cómo rápidamente el estado inicial de los enfoques $[1/10,1/10,...,1/10]$
Resulta que los valores propios son $(\omega+\omega^2+\omega^5)/3$ donde $\omega^{10}=1$ es uno de la décima raíces de la unidad. El mayor de estos, al$\omega=1$$1$. El próximo mayores valores propios tienen amplitud 0.71632, de manera que la distancia a partir de una distribución uniforme disminuye en proporción al $N$ se incrementa en 1.
Los autovalores con monedas de oro se $(2+\omega+\omega^2+\omega^5)/5$, el mayor de los cuales (excepto el 1) tiene valor absoluto 0.58713, por lo que se alcanza un equilibrio más rápidamente.

Answer 2

Estoy bastante seguro de que el que $P=0.1$ para valores muy grandes de $N$

Aquí es una prueba de esta afirmación.

Como $N$ tiende a infinito,

• La cantidad de dinero extra de 10 céntimos de euro tenderá hacia una homogénea distribución aleatoria en $\{0, .1, .2, .3, .4, .5, .6, .7, .8, .9\}$.

• La cantidad de dinero extra de 20 céntimos de euro tenderá hacia una homogénea distribución aleatoria en $\{0, .2, .4, .6, .8\}$.

• La cantidad de dinero extra de 50 céntimos tenderá hacia una homogénea distribución aleatoria de $\{0, .5\}$.

Para encontrar la probabilidad final de que el dinero total a ser un número entero, sólo tenemos que añadir estas tres distribuciones de mod $1$. Pero la distribución uniforme añadido a la distribución de cualquier mod 1 es de nuevo la distribución uniforme. Por lo que la distribución de la suma mod 1 es (como $N \to \infty$) uniforme en $\{0, .1, .2, .3, .4, .5, .6, .7, .8, .9\}$, como se conjeturó.