¿Cuál es el número esperado de dados que uno necesita para rodar a obtener cualquier monótonamente creciente de la serie de la 1 a la 6?

Question

Similar a: "Lo que se espera que el número de dados que uno necesita para rodar a obtener 1,2,3,4,5,6 en orden?" pero permitimos que se repite de manera 1,1,2,2,3,4,4,4,4,5,5,6 cuenta.

Mi respuesta (o simulación) es errónea, ya que no puedo conseguir un acuerdo razonable.

Mi C++11 de simulación de código a continuación. Me temo que el 'error' es más probable que sea en mi álgebra

#include <iostream>
#include <random>

int main(int argc, char* argv[])
{
  int seed = 101;
  if ( argc>1 )
    seed = atoi(argv[1]);

  std::uniform_int_distribution<int> distribution(1,6);
  std::mt19937 engine(seed);
  auto generator = std::bind(distribution,engine);

  int rollForSequenceSum = 0;
  int multiples = 1000;
  for ( int i=0; i<multiples; ++i )
  {
    int rollCount = 0;
    int nextInSequence = 1;

    while ( nextInSequence <= 6 )
    {
      ++rollCount;
      int random = generator();
      if ( random == nextInSequence )
      {
        ++nextInSequence;
      } 
      else if ( random == (nextInSequence-1) )
      {
        //Do nothing
      } 
      else if ( random == 1 )
      {
        nextInSequence = 2;
      }
      else
      {
        nextInSequence = 1;
      }
    }
    rollForSequenceSum += rollCount;
  }
  double mean = (double) rollForSequenceSum / (double) multiples;
  std::cout << mean << std::endl;
}

Answer 1

Esto no es malo si se configura como una discreta de la cadena de Markov. Deje que los diferentes estados posibles del juego de ser "S" (para empezar), y luego 1, 2, 3, 4, 5, "6/" (para aceptar). Inicio significa que no se pudo obtener la monotonía de ejecución de los números y tuvo que empezar desde cero en el comienzo del juego. Aceptar significa que usted tiene un 6 sólo después de una monótona secuencia de los otros números.

Quieres saber el largo plazo, la probabilidad de estar en estado 6/A, y a partir de esto, usted puede fácilmente averiguar cuál es el número esperado de morir rollos sería (se los dejo a usted porque es satisfactoria.)

Pero para empezar, usted puede escribir una matriz de transición para este juego:

$$\begin{array}{| c || c | c | c | c | c | c | c |} \hline & S & 1 & 2 & 3 & 4 & 5 & 6/A \\ \hline S & 5/6 & 1/6 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 4/6 & 1/6 & 1/6 & 0 & 0 & 0 & 0 \\ \hline 2 & 1/2 & 1/6 & 1/6 & 1/6 & 0 & 0 & 0 \\ \hline 3 & 1/2 & 1/6 & 0 & 1/6 & 1/6 & 0 & 0 \\ \hline 4 & 1/2 & 1/6 & 0 & 0 & 1/6 & 1/6 & 0 \\ \hline 5 & 1/2 & 1/6 & 0 & 0 & 0 & 1/6 & 1/6 \\ \hline 6/A & 5/6 & 1/6 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}$$

Ahora es una cuestión de obtener el derecho de vector propio de la matriz, para decirle a largo plazo de las probabilidades, y, a continuación, averiguar cómo activar que a largo plazo la probabilidad en un número esperado de rollos. Tenga en cuenta que la mayoría numérica autovector rutinas sólo calcular "derecho vectores propios", que se producen en el lado derecho de la matriz en cuestión. Para un típico estocástico de la matriz, se desea calcular la izquierda autovector correspondiente al autovalor 1. Así que para conseguir esto, numéricamente, primero necesita para tomar la transpuesta de la matriz de transición y después de alimentar a su linear algebra package.

Agregó

Después de la fijación de los errores que yo había hecho en la anterior matriz de transición (que ahora está correcto), he utilizado el siguiente código en Python para comprobar lo que el vector propio método produjo como una solución, y he traducido su simulación de Monte Carlo en Python para comprobar numéricamente.

El resultado que obtuve para el largo plazo de la distribución estacionaria del juego es $$[ 0.79168, 0.16667, 0.03333, 0.00667, 0.00133, 0.000267, 0.0000444],$$

y así los recíprocos de estos elementos da el número esperado de rollos para llegar a cada estado: $$[1.26, 6.0, 30, 150, 750, 3750, 22500]$$ (podría haber algún error de redondeo dependiendo de lo bien que NumPy del paquete linalg es, yo no soy el uno para preguntar acerca de eso). Tenga en cuenta que la segunda entrada, 6 rollos para obtener el primer 1, encaja con la intuición de un uniforme de 6 caras morir, así que eso es reconfortante.

Así que de acuerdo a esto, la "analítica" de la solución es que se debe tomar alrededor de 22500 rollos para llegar a una monótona secuencia que termina con un 6. Mi simulaciones de Monte Carlo de acuerdo con esto, como he obtenido un número esperado de rollos de 22609.618 en una simulación de 10.000 vueltas (un poco lento en Python, pero no debería ser un problema en C++).

Aquí está el código para mi solución:

import numpy as np

# Set up the transition matrix.
tmat = np.asarray([ [5.0/6.0, 1.0/6.0, 0, 0, 0, 0, 0], 
                    [4.0/6.0, 1.0/6.0, 1.0/6.0, 0, 0, 0, 0],
                    [3.0/6.0, 1.0/6.0, 1.0/6.0, 1.0/6.0, 0, 0, 0],
                    [1.0/2.0, 1.0/6.0, 0, 1.0/6.0, 1.0/6.0, 0, 0],
                    [1.0/2.0, 1.0/6.0, 0, 0, 1.0/6.0, 1.0/6.0, 0],
                    [1.0/2.0, 1.0/6.0, 0, 0, 0, 1.0/6.0, 1.0/6.0],
                    [5.0/6.0, 1.0/6.0, 0, 0, 0, 0, 0]]).astype('float64')


# Compute long-run probability and expected rolls
# with eigenvalue method.
w,v = np.linalg.eig(np.transpose(tmat))

# Get stationary distribution as eigenvector
# corresponding to eigenvalue 1.
# Take real part to get rid of Python's
# complex notation, and divide by vector sum
# just in case round off error makes it not
# quite sum up to 1.0

stationary_probs = np.real(v[:,0])
print stationary_probs/sum(stationary_probs)

# Print the element-wise reciprocals which are
# the expected number of rolls to each state.
print 1/(stationary_probs/sum(stationary_probs))

# Monte Carlo simulation to compare results.

total_rolls = 0; num_repeats = 10000;
iter_rolls = np.zeros((1,num_repeats))
for ii in range(num_repeats):

    cur_roll = np.random.randint(1,7)
    num_rolls = 1

    if cur_roll == 1:
        next_val = 2
    else:
        next_val = 1

    while( next_val <= 6 ):
        prev_roll = np.copy(cur_roll)
        cur_roll = np.random.randint(1,7)
        num_rolls =  num_rolls + 1

        if(cur_roll == next_val):
            next_val = next_val + 1
        elif(cur_roll == prev_roll):
            pass
        elif(cur_roll == 1):
            next_val = 2
        else:
            next_val = 1

    iter_rolls[0,ii] = num_rolls
    total_rolls = total_rolls + num_rolls
    print "Finished iteration %d of %d"%(ii,num_repeats)

print "Monte Carlo mean: %f"%(np.mean(iter_rolls[0,:]))

Como un aparte, esta vinculado capítulo de libro hace un mejor trabajo de explicar lo que está pasando en la que casi cualquier otra referencia que yo era capaz de Google. En particular, la sección donde se define el "significa el tiempo paso", y resulta que estos son los recíprocos de la distribución estacionaria de las entradas es exactamente la información de antecedentes relevantes para problemas como estos.

De Wikipedia, el tratamiento de este tipo de discreta de la cadena de Markov problema es ínfimo y decepcionante. Si usted quiere "pagar" esta respuesta, considere la posibilidad de editar la entrada de la Wikipedia sobre la Matriz Estocástica para incluir este ejemplo. El único ejemplo en la actualidad hay una con un trivial estado de absorción, lo cual es totalmente ineficiente para alguien que está aprendiendo, especialmente con alguien tratando de aprender a problemas del modelo con las cadenas de Markov en lugar de sólo a resolver pedagógica de las cadenas de Markov dada por los maestros.

Answer 2

Considere el siguiente diagrama. La fila superior representa el número esperado de rollos hasta que la caja número es hecho rodar la secuencia. La segunda fila es el número esperado de rollos hasta que otro número es hecho rodar. $\boxed{0}$ representa el estado antes de la $1$ es la primera laminado. Los números por las flechas, son probabilidades.

$\hskip{3mm}$

Puesto que hay un $\frac16$ de probabilidad de sacar un $1$, se requieren, en promedio, $6$ rollos para obtener de$\boxed{0}$$\boxed{1}$.

Una vez que un número es hecho rodar, va a tomar, en promedio, $\frac65$ rollos para rodar algo más.

Para llegar desde $\boxed{1}$$\boxed{2}$, hay un $\frac15$ de probabilidades de que se tome $\frac65$ rollos. Hay un $\frac45\cdot\frac15$ de probabilidades de que se tome $6+2\cdot\frac65$ rollos, y un $\left(\frac45\right)^2\cdot\frac15$ de probabilidades de que se tome $2\cdot6+3\cdot\frac65$, etc. Por lo tanto, se necesita, en promedio, $$ \begin{align} \sum_{k=0}^\infty\frac15\left(\frac45\right)^k\left(6k+\frac65(k+1)\right) &=4\cdot6+5\cdot\frac65\\ &=30\tag{1} \end{align} $$ rollos para obtener de$\boxed{1}$$\boxed{2}$.

Llegar de $\boxed{2}$ $\boxed{3}$es el caso común. Si un rollo pierde su marca, hay un $\frac14$ de probabilidad de que un $1$ fue rodada y volvemos a $\boxed{1}$, ahorrando un promedio de $6$ rollos; de lo contrario, volvemos a $\boxed{0}$. Por lo tanto, la falta de la marca significa un extra de $$ \frac14\cdot(36-6)+\frac34\cdot36=36-\frac32\etiqueta{2} $$ rollos, en promedio, para volver a $\boxed{2}$. Utilizando el mismo razonamiento que en $(1)$, para obtener de $\boxed{2}$$\boxed{3}$, lleva a $$ \begin{align} \sum_{k=0}^\infty\frac15\left(\frac45\right)^k\left(\left(36-\frac32\right)k+\frac65(k+1)\right) &=4\cdot\left(36-\frac32\right)+5\cdot\frac65\\ &=4\cdot36-6+6\\ &=4\cdot36\tag{3} \end{align} $$ Por lo tanto, llegar a $\boxed{3}$ es de $5$ veces tan largo como llegar a $\boxed{2}$.

La cosa idéntica que pasa por $\boxed{3}$, $\boxed{4}$, $\boxed{5}$, y $\boxed{6}$. Esto nos deja con un promedio de $22500$ rollos hasta que llegamos a $\boxed{6}$.

---

Representación de la matriz para el Diagrama de

Como alternativa, considere el siguiente Estado de la Matriz de Transición $$ M_7=\frac{1}{6} \begin{bmatrix} 5 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 1 & 1 & 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 1 & 1 & 0 & 0 \\ 3 & 1 & 0 & 0 & 1 & 1 & 0 \\ 3 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 6 \end{bmatrix}\etiqueta{4} $$ y el Estado inicial del Vector $$ S=\begin{bmatrix}1&0&0&0&0&0&0\end{bmatrix}\etiqueta{5} $$ El estado de vectores $SM_7^n$ representa la distribución esperada de los estados $\boxed{0}-\boxed{6}$ después $n$ rollos.

Para el cálculo de la duración prevista para rodar una $6$, en secuencia, vamos a $M_6$ $M_7$ fila $7$$0$. A continuación, $SM_6^n$ representa los mismos estados como $SM_7^n$, excepto que cuando el estado de $\boxed{6}$ es alcanzado, está vacante en la siguiente tirada. Por lo tanto, el elemento $7$ $SM_6^n$ es la probabilidad de que un $6$ es la primera laminados, en secuencia, en el rollo de $n$. Por lo tanto, el elemento $7$ de $$ \sum_{n=1}^\infty nSM_6^n\etiqueta{6} $$ es la duración prevista hasta un $6$ se rodó, en la secuencia. De hecho, Mathematica dice que $$ SM_6(I-M_6)^{-2}=\begin{bmatrix}400687782 & 84353250 & 16871550 & 3374490 & 674934 & 134994 & \color{red}{22500}\end{bmatrix} $$ Podemos realizar el mismo cálculo con $M_k$, $M_7$ con todos, pero el primer $k$ filas conjunto de a $0$: $$ \begin{align} SM_5(I-M_5)^{-2}&=\begin{bmatrix}16016832 & 3371550 & 674490 & 134934 & 26994 & \color{red}{4500} & 0\end{bmatrix}\\ SM_4(I-M_4)^{-2}&=\begin{bmatrix}639222 & 134490 & 26934 & 5394 & \color{red}{900} & 0 & 0\end{bmatrix}\\ SM_3(I-M_3)^{-2}&=\begin{bmatrix}25416 & 5334 & 1074 & \color{red}{180} & 0 & 0 & 0\end{bmatrix}\\ SM_2(I-M_2)^{-2}&=\begin{bmatrix}1014 & 210 & \color{red}{36} & 0 & 0 & 0 & 0\end{bmatrix}\\ SM_1(I-M_1)^{-2}&=\begin{bmatrix}30 & \color{red}{6} & 0 & 0 & 0 & 0 & 0\end{bmatrix}\\ SM_0(I-M_0)^{-2}&=\begin{bmatrix}\color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix} \end{align} $$ todo lo cual está de acuerdo con el diagrama de arriba.

Answer 3

Voy a postear mi álgebra y el razonamiento a continuación. Gracias a robjohn y EMS para el independiente de llegar a una respuesta en la que está de acuerdo con mi simulación y corregido álgebra.

Deje $N_i$ ser el número esperado de lanzamientos llevados a tiene $i$ en la secuencia.

$N_6$ es el número esperado de lanza para que el juego final.

$N_1 = \frac{1}{6}.1 + \frac{5}{6}(1+N_1)$

como hay un 1 en 6 posibilidad de llegar a $N_1$ en un solo tiro y un $\frac{5}{6}$ de probabilidad de perder un tiro y la necesidad de lanzar los dados de otro $N_1$ veces.

$N_2 = N_1 + \frac{1}{6}.1 + \frac{1}{6}(1+N_2-N_1) + \frac{4}{6}(1+N_2)$

como uno debe estar en 1 ya que tarda $N_1$ lanza y una que tiene un 1 en 6 probabilidad de sacar un 2, un 1 en 6 posibilidad de sacar un 1 desperdiciando así un tiro, pero sólo tener que empezar a partir de 1, y un 4 en 6 posibilidad de rodar otra cosa de 1 o 2 en caso de que un tiro se pierde, y uno tiene que empezar de nuevo desde cero.

$N_3 = N_2 +\frac{1}{6}.1 + \frac{1}{6}(1+N_3-N_1) + \frac{1}{6}(1+N_3-N_2) + \frac{3}{6}(1+N_3)$

como uno debe de estar en 2 ya que tarda $N_2$ lanza y una que tiene un 1 en 6 probabilidad de sacar un 3, 1 en 6 posibilidad de sacar un 1 desperdiciando así un tiro, pero sólo tener que empezar desde 1 de 1 en 6 probabilidad de sacar un 2 desperdiciando así un tiro, pero sólo tener que empezar de 2 y de 3 en 6 posibilidad de rodar algo distinto de 1, 2 o 3 en el que caso de que un tiro se pierde, y uno tiene que empezar de nuevo desde cero.

Del mismo modo

$N_4 = N_3+\frac{1}{6}.1 + \frac{1}{6}(1+N_4-N_1) + \frac{1}{6}(1+N_4-N_3) + \frac{3}{6}(1+N_4),$

$N_5 = N_4 +\frac{1}{6}.1 + \frac{1}{6}(1+N_5-N_1) + \frac{1}{6}(1+N_5-N_4) + \frac{3}{6}(1+N_5),$

$N_6 = N_5 +\frac{1}{6}.1 + \frac{1}{6}(1+N_6-N_1) + \frac{1}{6}(1+N_6-N_5) + \frac{3}{6}(1+N_6).$

Estos son lineales ecuaciones simultáneas que uno puede resolver para obtener:

$N_1 = 6$

$N_2 = 5.N_1 + 6$

$N_3 = 5.N_2$

$N_4 = 5.N_3$

$N_5 = 5.N_4$

$N_6 = 5.N_5$

o

$N_1 = 6$

$N_2 = 36$

$N_3 = 180$

$N_4 = 900$

$N_5 = 4500$

$N_6 = 22500$