pregunta de probabilidad relacionada con el patrón de lanzamiento de monedas

Question

Si lanzo una moneda justa $n$ veces, calcula la probabilidad de que no se produzca un patrón HHTHTHH.

Answer 1

Construye un autómata finito determinístico que detecta la expresión regular $.*(HHTHTHH).*$ de tal manera que el único estado de aceptación $A$ siempre transiciones a un estado $B$ que siempre se transforma en sí mismo. El estado inicial es $S$ .

Esto es básicamente un gráfico dirigido y podemos encontrar la matriz de transición $P$ cuya fila da las probabilidades de pasar de un estado (es decir, vértice) correspondiente a esa fila, a los siguientes estados (un vértice correspondiente a cada columna).

Básicamente necesitas las entradas correspondientes al estado inicial $S$ y estado final $A$ de cada uno de los $P, P^2, P^3, \dots , P^n$ y sumarlos para obtener la probabilidad de que el patrón $HHTHTHH$ ocurre (o más simplemente el $(S,B)$ la entrada de $P^{n+1}$ será suficiente). Réstale eso a $1$ y ya has terminado.

El $(S,A)$ la entrada de $P^k$ da la probabilidad de que encontremos el patrón exactamente al final de $k$ y nada de tiros antes de eso.

Answer 2

No sé sobre la solución exacta, pero la aproximación numérica es $P(n)=1-e^{- \frac {n}{125}}$ .

Matlab \Octave Código

function test_script_1()
x=7:30:600;
y=tsh([],5000,7:30:600);
er=@(p)sum(((p(1)+p(2)*exp(p(3)*x/500))-y).^2);
an=fminsearch(er,[0,0,0]);
anr=round(an);
disp(anr);
plot(x,y,x,anr(1)+anr(2)*exp(anr(3)*x));
legend('calculated','1-e^{-x/125}',4)
end
function result=tsh(a,b,n)
% HHTHTHH (H -> 1 , T -> 0)
if isempty(a)
    a=logical([1 1 0 1 0 1 1]);
end
if isempty(b)
    b=1000;
end
if isempty(n)
    n=100;
end
if any(size(n)>1)
    result=zeros(size(n));
    for pa=1:length(n)
        result(pa)=test_script_1(a,b,n(pa));        
    end
    return
end
la=length(a);
t=false(1,b);
for i=1:b
    v=raspr(0,1,n);
    for j=1:n
        if all(a==v(j:j+la-1))
            t(i)=true;
            break
        end
    end
end
result=nnz(t)/b;
end
function resu=raspr(a1,b1,s)
resu=round((b1-a1+1)*rand(1,s)+a1-0.5);
end

¿Alguien sabe por qué?

Answer 3

Terminé haciendo algo muy similar a Moron.

Define una cadena de Markov con estados i=0..7 de la siguiente manera. Dada una secuencia completa de n monedas, si el patrón aún no ha aparecido, encontrar la longitud máxima de los últimos lanzamientos (sufijo de la secuencia) que coinciden con el inicio del patrón esperado, de modo que

   i =  length of matching suffix , if pattern has not appeared
   i = 7 otherwise

Por ejemplo: HTTHTTTTHT : i=0 , HTTTTHHT i=3

Es fácil anotar las probabilidades de transición. (i=7 sería un estado absorbente), y la probabilidad de estar en el estado 7 en el paso n .

Así que tu respuesta sería $ P(n) = 1- p_7[n]$ donde $p[n] = M^n p[0]$ donde $M$ es la matriz de transición de 8x8 y $p[0] = (1,0,0,0,0,0,0,0)$ es el estado inicial. Dudo que consiga una respuesta más simple en forma cerrada.

Uno podría obtener una solución aproximada muy gruesa asumiendo que los patrones que empiezan en cada posición son independientes (obviamente un falso supuesto), y obtener $ P(n) \approx (1-2^{-7})^{n-6}$ ( $n \ge 7$ )

ACTUALIZACIÓN: algún código de Octava/Matlab para probar la aproximación (parece funcionar mejor de lo que esperaba)

N=200;
% approximation
pa = (1-1/128).^((1:N)-6);
pa(pa>1)=1;
% transition matrix:
M = [ 1,1,0,0,0,0,0,0 ;
      1,0,1,0,0,0,0,0 ;
      0,0,1,1,0,0,0,0 ;
      1,0,0,0,1,0,0,0 ;
      0,0,1,0,0,1,0,0 ;
      1,0,0,0,0,0,1,0 ;
      1,0,0,0,0,0,0,1 ;
      0,0,0,0,0,0,0,2 ]/2;
p=[1,0,0,0,0,0,0,0];
p7=zeros(1,N);
p7(1)=1;
for n = 1:N
 p = p * M;
 p7(n) = 1 - p(8);
endfor
plot(7:N,p7(7:N),7:N,pa(7:N));

>>> pa(5:9)
ans =

   1.00000   1.00000   0.99219   0.98444   0.97675

>>> p7(5:9)
ans =

   1.00000   1.00000   0.99219   0.98438   0.97656

>>> pa(N-5:N)
ans =

   0.22710   0.22533   0.22357   0.22182   0.22009   0.21837

>>> p7(N-5:N)
ans =
   0.22717   0.22540   0.22364   0.22189   0.22016   0.21844