Ya no tienes que indagar más por todo internet ya que llegaste al sitio indicado, tenemos la respuesta que buscas sin complicarte.
Solución:
Proporcionamos una respuesta y la vinculamos con las respuestas ya dadas que pueden ayudar a ver las conexiones.
Algunas observaciones:
-
Podemos reducir el problema a uno combinatorio contando todos los caminos a partir de $ (0, k) $ para $ (m-1, n-1) $ usando pasos $ (1,1) $ y $ (1, -1) $ que no llegan a las lineas $ y = 0 $ y $ y = n $.
-
El punto de partida representa el $ k $ monedas del jugador que tiene desde el principio. Ganar una ronda aumenta sus monedas en una, lo que está representado por un paso. $ (1,1) $ y perder una ronda también significa entrar $ x $-dirección en uno, pero disminuyendo $ y $ por uno, así que damos un paso $ (1, -1) $.
-
Cada ruta válida desde $ (0, k) $ para $ (m-1, n-1) $ tiene longitud $ m-1 $ y se realiza con probabilidad $ frac 1 2 ^ m-1 $. Con el fin de alcanzar $ (m, n) $ esto solo se puede hacer en un paso desde $ (m-1, n-1) $ para $ (m, n) $ con probabilidad $ frac 1 2 $, de modo que el número de rutas válidas desde $ (0, k) $ para $ (m-1, n-1) $ finalmente tiene que ser dividido por $ 2 ^ m $ para encontrar la probabilidad deseada.
Comenzamos con un ejemplo que confirma el enfoque de @GCab.
Ejemplo (parte 1): k = 2, m = 14, n = 6
Contamos el número de rutas válidas desde $ (0,2) $ para $ (14,6) $, que es el número de rutas de celosía desde $ (0,2) $ para $ (13,5) $ que no tocan las lineas $ y = 0 $ y $ y = 6 $, seguido de un $ m $-th paso desde $ (13,5) $ para $ (14,6) $.
Vemos de acuerdo con la tabla presentada por @GCab que tenemos $ color rojo 364 $ rutas válidas que están marcadas en rojo en el gráfico siguiente.
We can normalise the situation by shifting $(0,k)$ to $(0,0)$ and consider the equivalent problem to count the number of lattice paths from $(0,0)$ to $(m-1,n-1-k)$ using steps $(1,1)$ and $(1,-1)$ without reaching the boundaries $y=n-k$ and $y=-k$. We denote this number of valid paths by
beginalign*
L_m-1,n-1-k;n-k,k
endalign*
Formula:
The formula above in the form $L_m,n;r,s$ counting valid paths from $(0,0)$ to $(m,n)$ which do not reach the boundaries $y=r$ and $y=-s$ is established in this post. It can be written as
beginalign*
L_m,n;r,s&=binommfracm+n2-sum_jgeq1left[binommfracm+n2-r+j(r+s)
+binommfracm+n2+s-j(r+s)right]\ & qquad qquad qquad + sum_ j geq1 left[binommfracm+n2+j(r+s)
+binommfracm+n2-j(r+s)right] etiqueta 1 \ end align *
En la situación actual obtenemos de (1) el número de caminos válidos para el problema de OP:
begin align * & color blue L_ m-1, n-1-k; nk, k = binom m-1 frac m + nk 2 – 1 \ & quad qquad- sum_ j geq1 left[binomm-1fracm+n-k2-1-n+k+jn+binomm-1fracm+n-k2-1+k-jnright]\ & quad qquad + sum_ j geq1 left[binomm-1fracm+n-k2-1+jn+binomm-1fracm+n-k2-1-jnright] etiqueta 2 \ & quad = – sum_ j geq0 binom m-1 frac m + nk 2 -1 + k + jn – sum_ j geq1 binom m-1 frac m + nk 2 -1 + k-jn \ & quad qquad + sum_ j geq0 binom m-1 frac m + nk 2 -1 + jn + sum_ j geq1 binom m-1 frac m + nk 2 -1-jn etiqueta 3 \ & quad , , color azul = sum_ j = – infty ^ infty left[binomm-1fracm+n-k2-1+jn-binomm-1fracm+n+k2-1+jnright] etiqueta 4 end align *
Comentario:
-
En (3) cambiamos en la serie más a la izquierda el índice en uno para comenzar con $ j = 0 $. En la tercera serie fusionamos el término más a la izquierda de (2).
-
En (4) combinamos las dos series más a la derecha así como las dos series más a la izquierda.
La probabilidad resultante es
begin align * color blue frac 1 2 ^ m L_ m-1, n-1-k; nk, k end align *Las sumas en (2) son una consecuencia de la aplicación del principio de inclusión-exclusión a las rutas reflejadas. Esto es necesario para compensar el conteo doble como se indica en la respuesta de @Hans.
.
Ejemplo (parte 2): k = 2, m = 14, n = 6
Para verificar (2) calculamos el número de rutas válidas del ejemplo anterior.
Obtenemos
begin align * color blue L_ 13,3; 4,2 & = binom 13 8 – left[binom1310+binom134right]+ izquierda[binom132right] etiqueta 3 \ & = 1 , 287- (286 + 715) +78 \ & , , color azul = 364 end align *
de acuerdo con la primera parte del ejemplo. Tenga en cuenta que el número de trayectorias reflejadas entre paréntesis en (3) se indica en el gráfico mediante $ A_1, B_1 $ y $ B_2 $.
Esto se resuelve mediante la aplicación repetida del principio de reflexión.
Solo necesitamos enumerar el número de trayectorias de pérdidas y ganancias que satisfacen la condición que luego se divide por $ 2 ^ m $ para obtener la probabilidad. El número de caminos a partir de $ 0 $ monedas y terminando en $ y $ monedas en el $ x $la ronda es
$$ y elija l tag1 $$
dónde $ l = frac xy 2 $ es el número de pérdidas en este camino.
Primero resolvemos el problema parcial de partir de $ k $ monedas y terminando en $ n $ monedas en ronda $ m $ por primera vez (así que cayendo debajo $ 0 $ se permite la moneda). Cada ruta admisible da una ruta única de $ m-1 $ rondas que alcanza $ n-1 $ monedas en ronda $ m-1 $ sin poseer nunca $ n $ monedas antes. Cada uno de esos caminos de $ m-1 $ rondas genera una única requerida $ m $ redondea el camino ganando una ronda más. Debido a esta correspondencia uno-uno, solo necesitamos calcular el número de tales $ m-1 $ caminos redondos $ N_1 (m, k, n) $. Por el principio de reflexión aplicado a la línea reflectante de $ n $ monedas y ecuación $ (1) $$$ f_1 (n, k, m) = m-1 elija frac m-n + k 2 – m-1 elija frac mn-2 + k 2. $$
Ahora agregamos la condición de que el camino nunca debe tocar el $ 0 $ línea de monedas. Por el principio de reflexión aplicado a la línea de monedas. $ 0 $, los caminos que satisfacen la condición del párrafo anterior pero no tocan el $ 0 $ línea de moneda uno a uno corresponde a
$$ f_2 (n, k, m) = m-1 elija frac m-n + k 2 – m-1 elija frac mn-2 + k 2 – m- 1 elija frac m + n-2 + k 2 + m-1 elija frac m + n + k 2. $$
Necesitamos reflejar el camino ad infinitum alrededor de las líneas. $ ni _ i = 0 ^ infty $ hasta que se agote la longitud del camino para tal reflexión. Por inducción matemática, podemos obtener la enumeración final deseada.
$$ f (n, k, m) = sum_ i = – infty ^ infty Bigg (m-1 choose frac m- (2i + 1) n + k 2 – m-1 elige frac m- (2i + 1) n-2 + k 2 Bigg) $$
dónde $ a elija b: = 0, , forall b not in[0,a]PSo entero $ i in big[-frac12big(fracm-kn+1big),,frac12big(fracm+kn-1big)big]PS. La probabilidad buscada es simplemente $ frac f (n, k, m) 2 ^ m $.
El enfoque estándar sería a través de la matriz de Markov.
La matriz de transición, que denota la probabilidad de cambios en el capital en cada corrida, es simple. Para $ n = 4 $ por ejemplo, es
$$ bf T (4) = left ( matrix 1 & 0 & 0 & 0 & 0 cr 1/2 & 0 & 1/2 & 0 & 0 cr 0 & 1/2 & 0 & 1/2 & 0 cr 0 & 0 & 1/2 & 0 & 1/2 cr 0 & 0 & 0 & 0 & 1 cr derecha) $$
y computacionalmente funciona bastante bien. Tomando los diversos poderes de la matriz ($ bf T ^ m $) los $ k $-th fila dará la probabilidad de obtener el capital correspondiente al índice de la columna.
Ya que en $ 0 $ y $ n $ tenemos una barrera absorbente, esas columnas darán la probabilidad acumulativa de perder o ganar.
De esta forma obtenemos por ejemplo, para $ n = 5,6 $, las siguientes tablas para $ f (n, k, m) $
que se corresponden con el tuyo. Sin embargo, los resultados son difíciles de representar en términos analíticos, porque la forma canónica de Jordan es complicada y la posible división en componentes más simples conduce a términos no conmutativos.
Así que adoptamos un enfoque diferente.
Si llegamos a redondear $ q $ con mayúscula $ 1 le c le n-1 $, luego el número de formas de proceder desde aquí y ganar en la ronda $ m $ ($ w_n (q, m, c) $) es claramente igual al número de formas de alcanzar ese objetivo a partir de la ronda anterior ($ q-1 $) con mayúscula $ c-1 $
más los que tienen mayúscula $ c + 1 $, ya que la probabilidad de ganar y perder es la misma. Es decir
$$ w _ , n (q, m, c) = izquierda[ 1 le c le n – 1 right] left (w _ , n (q – 1, m, c – 1) + w _ , n (q – 1, m, c + 1) right) $$
dónde PS[P]PS denota el Soporte Iverson$$ left[ P right] = left { begin array * 20 c 1 & P = VERDADERO \ 0 & P = FALSO \ end array Derecha. $$
y la condición $ left[ 1 le k le n – 1 right]PS es asegurar que nos mantengamos en juego.
Yendo hacia atrás desde el punto $ (m, n) $ y complementando el capital, es fácil transformar lo anterior en una recursividad para $ f $, comenzando desde el punto$ (n, 0) $$$ bbox[lightyellow] eqalign & f_n (k, m) = cr & = left[ 1 le k le n – 1 right] left (f_n (k – 1, m – 1) + f_n (k + 1, m – 1) right) + left[ 0 = m right]izquierda[ n = k right] = cr & = left[ 0 le k – 1 le n – 2 right]f_n (k – 1, m – 1) + izquierda[ 2 le k + 1 le n right]f_n (k + 1, m – 1) + izquierda[ 0 = m right]izquierda[ n = k right] cr $$
esto se comprueba con las tablas anteriores y proporciona una herramienta de cálculo más eficaz.
Comentarios y valoraciones
Eres capaz de añadir valor a nuestra información colaborando tu experiencia en las notas.