Full transcript
0:02Buenos días, bienvenidos a la clase. Eh,
0:06hoy día vamos a aprovechar lo que hemos
0:08aprendido de funciones generatrices y
0:10funciones generatrices de probabilidad
0:13para volver a darle una mirada a un
0:15problema que fue uno de los primeros que
0:18vimos en el curso que tiene que ver con
0:22eh encontrar el máximo recorriendo una
0:25lista de izquierda a derecha.
0:28Entonces, eh
0:32volvamos al problema
0:37de recorrer una lista de izquierda a
0:39derecha
0:55buscando el máximo.
1:02Ya. y contando
1:08el número
1:10de máximos locales de izquierda a
1:12derecha que vayamos encontrando.
1:35Ya, ya sabemos nosotros cuál es la
1:38respuesta.
1:40La respuesta es H subn. Eh, la pregunta
1:43es, ¿cuál es el número esperado de
1:45máximos locales que que uno encuentra,
1:48¿no es cierto? O sea, ya sabemos que eh
1:51si tengo una lista de largo n eh de
1:54números que vienen de un orden
1:56aleatorio, eh todos distintos.
1:59Eh,
2:01el número esperado de máximos locales de
2:03izquierda derecha que vamos a encontrar
2:04es H subn, el número armónico. Eh, así
2:08que, ¿cuál es la diferencia ahora? La
2:10diferencia es que vamos a estudiar no
2:12solamente el valor esperado, queremos
2:14conocer cuál es la distribución, cuál es
2:16la función generatriz de la variable
2:17aleatoria, número de máximos locales de
2:19izquierda derecha.
2:21Entonces,
2:23eh ahora
2:28queremos estudiar
2:35la distribución
2:42de esta variable aleatoria. Ya.
2:46Eh, esto es [suspiro]
2:51eh encontrar su función generatriz,
2:56su función generatriz de probabilidad,
2:59¿no es cierto? Porque encontrando la
3:00función generatriz de probabilidad
3:02podemos extraer los coeficientes y esos
3:04coeficientes son los que nos dan el
3:07los que nos dan eh la distribución.
3:10¿Okay? Entonces, eh, pongamos un
3:13ejemplo. Ah, supongamos que tengo esta
3:15lista. 3 1
3:195 2 4
3:238
3:257 9 6 y la voy a recorrer de izquierda a
3:30derecha, ¿no es cierto?
3:32Y esta es una lista de largo N.
3:35Entonces, lo que voy a hacer es que voy
3:37a ir recorriendo esta lista y voy a ir
3:40marcando cada vez que encuentro un
3:42número que es mayor que todos los
3:44anteriores. Entonces, el primero siempre
3:47eh se va a contar porque eh el primero
3:51que aparece, por lo tanto es mayor que
3:52todos los anteriores.
3:55E después el uno, no. El cinco, sí. El
3:58dos no, el cuatro no. El ocho sí, el
4:01siete no. El nueve, sí.
4:05el seis, ¿no? Ya. Eh, por lo tanto, en
4:08este caso, la variable aleatoria toma el
4:11valor 1 2 3 4, ¿no es cierto? El,
4:16¿cuál es el valor mínimo de que puede
4:18tomar esta variable aleatoria? Eh, uno,
4:22¿no es cierto? que sería cuando el
4:25primero que aparece es mayor que todos
4:27los que vienen a continuación, o sea,
4:29cuando el primero que aparece es el
4:30máximo, entonces nadie después le quita
4:33su lugar como campeón, digamos. Eh, y
4:37finalmente hubo solo un máximo local que
4:39terminó siendo el máximo global.
4:42Ese el valor mínimo, ¿no es cierto? ¿Y
4:44cuál es el valor eh máximo que puede
4:46tomar? sería n, en donde cada uno de los
4:50que aparece es mayor que todos los
4:53anteriores, ¿ya? Eh, cada uno que
4:55aparece es un máximo local. Y eso ocurre
4:57cuando la secuencia, la lista viene en
5:00orden creciente, ¿no es cierto? Hay cada
5:03un número que parece es mayor que todos
5:05los anteriores, pero esos son los
5:06extremos 1 N. Y lo que queremos ver es
5:09cuál es la distribución, ¿ya? Eh, y para
5:13eso vamos a definir entonces la función
5:16generátriz de probabilidad.
5:19Vamos a llamar G sub N de Z,
5:24la función generatriz de probabilidad
5:28del número
5:30de máximos locales
5:38izquierda a derecha.
5:45en una
5:47permutación aleatoria
5:58de los números
6:00del uno hasta el n. Okay.
6:05Como lo que lo único que interesa es la
6:08relación de orden que hay entre los
6:10elementos, eh los valores eh concretos
6:14que que tomen, no no son lo importantes,
6:16lo importante es la relación de orden.
6:18Esos números que estamos viendo en la
6:19pantalla [carraspeo]
6:21eh 3 5, etcétera, perfectamente podrían
6:23haber sido 30, 10, 50, 20, etcétera. y y
6:28la permutación, o sea, la secuencia
6:30tendría el mismo comportamiento, tendría
6:33el mismo número de máximos locales de
6:34izquierda a derecha, ¿no es cierto? Eh,
6:37así es que sin perder generalidad
6:38podemos suponer que los números son los
6:40números de un al n cualquier otra
6:42secuencia yo la puedo
6:45reetiquetar
6:47de modo que al al menor de todos los
6:48números le pongo uno, al segundo le
6:50pongo dos y así sucesivamente y tengo
6:53finalmente una permutación, ¿ya? Así que
6:55no estamos perdiendo generalidad. al
6:57suponer que se trata de una permutación.
7:00Entonces, lo que vamos a a ver es cómo
7:04podemos escribir una recurrencia para
7:05esta función generatriz de probabilidad.
7:07Y la idea es la siguiente. Supongamos
7:10que yo ya conozco la función generatriz
7:13de probabilidad para los n primeros
7:17números, ¿ya? Entonces tomo los n -1
7:20primeros números de la secuencia y veo
7:23cuál eh y tengo la función generatriz g
7:26sub n -1 de z. La supongo conocida. Ya
7:30estoy pensando inductivamente.
7:33Entonces si conozco la solución para n -
7:351, ¿cómo puedo partir de ahí obtener una
7:38solución para para n? Okay. Eh, entonces
7:42tengo que mirar qué efecto tiene el
7:44último número que aparece respecto del
7:47número de máximo locales de izquierda a
7:49derecha.
7:50Eh, ese último número eh puede ser mayor
7:54que todos los anteriores, ¿no es cierto?
7:57Y en ese caso su aparición haría que el
8:00contador de máximos locales se
8:01incrementara en uno
8:04o podría ser eh no ser mayor que todos
8:08los anteriores, como son todos
8:09distintos, entonces sería menor que el
8:11máximo a la fecha, ¿no es cierto? Que
8:15son todos los otros casos. Eh, y en ese
8:17caso no le suma nada al contador de de
8:21máximos locales, o sea, o le suma uno o
8:23le suma cero. Ya. Eh, ¿con qué
8:26probabilidad le suma uno? Bueno, que el
8:29último que aparezca sea el el máximo,
8:33sea mayor que todo lo anteriores, quiere
8:34decir que es el máximo de todos, ¿no es
8:36cierto? Y y entre los n elementos hay
8:39uno solo que es el máximo de todos. Por
8:41lo tanto, la probabilidad de que el
8:42último que aparezca sea el máximo de
8:43todos es 1 par por n.
8:45Ya, con probabilidad 1 partido por n se
8:48le suma uno al contador de máximos
8:50locales y con la probabilidad
8:52complementaria, o sea, 1 - 1 par n, no
8:55se le suma nada, o sea, se le suma cero.
8:58Ya, ¿cómo se le suma en una función
9:01generatriz? ¿Cómo uno le suma algo al a
9:04la variable aleatoria, al contador, ya?
9:07Multiplicando por Z, porque el contador
9:10va en el exponente de los zas. Entonces,
9:13yo quiero sumarle uno, tengo que
9:14multiplicar por Z. Si quiero eh sumarle
9:17CER, tengo que multiplicar por uno. Ah,
9:20por z a la 0.
9:23Entonces, con todas esas
9:24consideraciones, lo que tengo es que
9:28G sub n de Z,
9:33¿okay?, va a ser igual a g sub n - 1 de
9:37z. Entonces, esa es la solución que yo
9:39supongo conocida. Supongo ya yo conozco
9:43la distribución, la función generatriz
9:45para los n- primeros números y veo qué
9:48pasa cuando aparece el último. Lo que va
9:50a pasar es que
9:54con probabilidad,
9:56pongám 1 parido por n
10:00eh hay que sumarle uno al contador, por
10:02lo tanto multiplico por Z. Y con la
10:05probabilidad complementaria, o sea, n -
10:081/ido por n, no hay que sumarle nada,
10:11¿ya? Eh,
10:14si quieren, si queremos ser bien
10:16específico, hay que multiplicar por z a
10:18la cer, ¿no es cierto? En este caso
10:20habría que multiplicar por Z a la 1.
10:24Después ya no lo vamos a escribir así de
10:26esa manera, pero para que quede
10:27clarísimo.
10:29Y y ¿cuál es el punto de partida?
10:33Eh, si yo tengo eh una secuencia de
10:37largo cero,
10:41¿ya? ¿Cuántos máximos locales tiene?
10:46Cero, ¿no es cierto? porque no aparece
10:48ningún elemento, nadie podría ser máximo
10:50local. Eh, por lo tanto, su función
10:52general es z a la 0, ¿ya? Con
10:55probabilidad 1 es z a la 0, por lo tanto
10:58es 1. Ya, z a la 0. Esa es la
11:05esa es la función generatriz. Entonces,
11:09e si yo desenrollo esto,
11:14eh, ¿qué es lo que obtengo?
11:19obtengo que e sub n de z.
11:24Ya, si lo si lo voy de atrás para
11:27adelante, ¿no es cierto? El último sería
11:29el que acabo de escribir ahí, sería n -
11:321 parido por n
11:35más zido por n.
11:39Ya, el anterior habría sido
11:44n - 2
11:47partido por
11:50n - 1
11:53+ z parido por n- 1, ¿cierto? Lo mismo
11:57pero para n- 1 y así hacia atrás. Y si
12:00yo voy al al principio, eh
12:05tengo
12:08para el caso n = 1, tengo
12:120 parido por 1 + zido por 1
12:18y el siguiente sería 1/ 2 + z/ 2
12:25y así sucesivamente. Ese ese sería el
12:27producto.
12:30Eh,
12:31entonces e
12:37esto sería
12:41z parido por 1, ¿no es cierto?
12:44Esto sería z + 1/ 2.
12:52Ya. El siguiente, si adivinamos cuál
12:54sería. Sería z + 2/ por 3.
12:59Ah, y el último sería
13:03z + n - 1 parido por n.
13:09O sea,
13:12yo lo puedo escribir esto como la
13:13pitatoria
13:16para 1 menor o igual que k men igual que
13:19n
13:23de z
13:28+ k - 1 parido por k,
13:33¿cierto?
13:34Ahí tengo exactamente esa pitatoria me
13:36representa exactamente el producto que
13:38escribí allí arriba y
13:45y de hecho esto se puede
13:52yo lo puedo
13:55separar entre el numerador y el
13:56denominador, ¿no es cierto? El
13:58denominador es fácil,
14:00el denominador es n factorial.
14:05Y el numerador,
14:06escribámoslo, eh eh desenrollémoslo,
14:10sería z * z + 1
14:15hasta z + n - 1.
14:18Si ustedes se acuerdan, eso es lo que
14:20llamamos una potencia
14:22factorial ascendente.
14:25Así que eso yo lo puedo escribir como
14:29eh z
14:32a la n ascendente
14:35partido por n factorial, ¿ya? Z a la n
14:39ascendente por partido por n factorial.
14:43Eh, ¿cierto? Entonces, tenemos las
14:45potencias normales. Z a la n es z * z *
14:48z n veces. Y tengo las potencias
14:50factoriales que pueden ser ascendentes.
14:53Z * Z + 1 * Z + 2 * Z + 3 N factores o
14:57pueden ser descendentes. Z * Z - 1, Z -
15:002, también n factores. Ya. Cuando es
15:02ascendente le pongo la rayita encima del
15:05exponente. Cuando es descendente le
15:06pongo la rayita debajo del del
15:08exponente. Y la otra manera que yo tengo
15:11de representar esto es mediante
15:13coeficientes binomiales.
15:15este caso, específicamente el
15:17coeficiente binomial simétrico, el
15:21coeficiente binomial simétrico
15:22respectivo sería z - 1 n.
15:36Ya. Eso, ¿cómo lo puedo saber? Porque eh
15:40z - 1, n
15:44podemos escribirlo también en su versión
15:46de coeficiente binomal normal, ¿no es
15:48cierto? El que escribí recién es el
15:50simétrico. El normal sería la suma de
15:52los dos eh z
15:57n - 1 sobre n. Ya. Y
16:04porque el el la correspondencia entre
16:09coeficientes binomiales simétricos y
16:10normales es que eh a partir del
16:13coeficiente binomial simétrico,
16:16lo que va arriba es la suma de los dos.
16:18Z - 1 + n. Que es eso. Y abajo va
16:21cualquiera de los dos. En este caso lo
16:23que me conviene es que vaya que yo sé
16:24que es entero el n, ¿ya? Y va ahí.
16:28Y si yo lo tengo así, ustedes se
16:29acuerdan que una manera de expresar un
16:31coeficienteal
16:33es partiendo el de arriba irle restando
16:35uno cada vez en el producto. Así que
16:37sería z + n - 1 por z + n - 2, etcétera,
16:41dividido por n factorial, que es
16:42exactamente este producto que tengo si
16:44lo leo derecha a izquierda. Así que esa
16:47esa es la razón. Entonces aquí tengo la
16:50solución y la y la forma que nos va
16:53resultar más útil.
16:55Bueno, varias de estas van a resultar
16:56útiles, pero la que nos va a resultar
16:58más útil es la que me dice que G subn
17:02es coeficiente minimal simétrico. ¿Ya?
17:07Okay. Ahora, antes de
17:11seguir adelante,
17:13déjenme hacer una pequeña observación
17:18que va a enlazar esto con lo que hemos
17:20estado viendo antes,
17:22que es que
17:24esta
17:26la función
17:36cambi de color
17:40Ya. Ah, bueno, borrémoslo mejor porque
17:43está está quedando
17:48está quedando distinto el resto. Lo que
17:50yo quería haber puesto era esta ya la
17:52función. Ahí está mejor.
17:57G sub n z
18:00es de la siguiente forma.
18:06Miren, miren ustedes lo que yo tengo
18:08aquí arriba.
18:10Tengo
18:13algo más zir por algo. Algo má Z partir
18:17por algo, algo más ZTI por algo. Es un
18:19producto de
18:22eh de distribuciones. Cada una de estas
18:27es una pequeña distribución que
18:28corresponde al lanzamiento de una
18:30moneda. Ah. Eh, por ejemplo, aquí tengo
18:33una moneda en que con probabilidad medio
18:36sale sello, con probabilidad en medio
18:38sale cara y yo estoy contando cuántas
18:40caras salieron. Ya. Eh, acá esta es una
18:44moneda, al final es una moneda super
18:46sesgada porque la probabilidad de que
18:48salga cara es 1/ido por nilidad de que
18:51salga sello es la el complemento n - 1/
18:55por n. Ah, así es que eh esto se puede
18:58ver como que yo estoy lanzando eh
19:01monedas eh
19:05lanzo NBCs, pero cada vez estoy lanzando
19:06una moneda distinta, ah porque las
19:09probabilidades van cambiando,
19:11eh, y voy contando el número de caras
19:12que salen. O sea, eso es un problema
19:14apareció al que hemos visto antes, ¿no
19:15es cierto? Pero antes suponíamos que la
19:17probabilidad se mantenía fija, que la
19:20probabilidad de cara era P y la
19:22probabilidad de sello era Q. Pero aquí
19:24las probabilidades de car y de sello van
19:25cambiando. Entonces me sale algo más más
19:28general, algo de la forma
19:33G sub
19:36de Z
19:40igual un Q1 + P1 Z * Z.
19:47Q2 + P2* Z
19:51hasta un QN.
19:53más p * z.
19:57Ah, entonces
19:59este
20:04el Q1 es 0, P1 es 1. Acá el Q2 es 1/2,
20:13el P2 es 1/2 y así sucesivamente. Al
20:17final el Q sub n es n - 1 parido por N.
20:22El P sub n es 1/ por N. Entonces van
20:25cambiando la las probabilidades a medida
20:28que yo lanzo la moneda. Hal
20:32que el que habíamos estudiado hasta
20:34ahora.
20:35Entonces, donde
20:40P sub K + Q sub K siempre es igual a 1,
20:44¿no es cierto?
20:46Y esto
20:48se puede
20:50interpretar
20:56como el lanzamiento
21:05de n
21:09monedas distintas.
21:17[suspiro]
21:20contando
21:24el número total
21:27de caras que aparecen.
21:35Ya. Entonces
21:37ahí e tenemos un un modelo más general
21:41que el que habíamos visto hasta ahora.
21:44Eh para esto nosotros eh conocemos eh
21:49cómo calcular la
21:52media, ¿no es cierto? Porque esto es un
21:55producto de funciones generatrices.
21:58Nosotros sabemos que el valor esperado
22:01de un producto funciones generatrices es
22:03la suma de los valores esperados.
22:06Y así que yo basta que yo calcule el
22:09valor esperado de de cada uno de estos
22:12de estas pequeñas funciones generatrices
22:14y lo sume. Entonces, por ejemplo,
22:18el
22:20valor esperado en la primera es PU1,
22:22porque yo deberío respecto de Z, evalua,
22:26eso ya es innecesario porque ya
22:28desapareció el Z y lo que quedó fue P1.
22:31De si hago lo mismo en la segunda lo que
22:32queda es P2, en la última lo que queda
22:34es PU N.
22:35Y el valor esperado del muo
22:39eso. Así que esa parte la tengo. Ya.
22:43Esto implica que el mu es P1 + P2 hasta
22:49más p sub.
22:52Ya, en nuestro caso, en nuestro ejemplo,
22:57el ejemplo de ir buscando el máximo,
23:03tenemos que
23:05p sub k
23:08es 1 parido por k, ¿no es cierto? Ya,
23:11eso es lo que teníamos aquí arriba. Ya,
23:14el primero es 1 parido por 1, el segundo
23:15es 1/ido por 2, el último es 1 parido
23:17por n. Así que el P sub K, ya. Bueno,
23:21esta sería entonces la sumatoria de los
23:23P sub K 1 menor o igual que K menor o
23:26igual que N. Y por lo tanto, eh
23:30si si los presupu cas son 1 par por k,
23:33el mu es la sumatoria de 1/ido por k
23:37para 1 menor o igual que k menor igual
23:39que n y eso ustedes ya saben es h sub n,
23:42lo cual confirma
23:45el
23:48confirma lo que ya sabíamos, ¿no es
23:49cierto?
23:52¿Qué pasa con la varianza? Eh, lo mismo,
23:56la varianza es la suma de las varianzas.
23:59Entonces, tengo que ver cuál es la
24:00varianza de cada uno de esas pequeñas
24:03funciones generatrices. Para eso tengo
24:05que derivar eh dos veces. Ya
24:15la idea es cuál es el bar de p subk,
24:19perdón, al revés.
24:28Q sub K + P sub K Z.
24:33¿Cuál es la varianza de eso? ¿No es
24:34cierto? Para eso tengo que derivar dos
24:36veces y poner Z = 1, pero derivar dos
24:40veces quedó cero, así que es cer0. Ya.
24:43Eh, más la media, que es p sub k,
24:49menos la media al cuadrado, que es p sub
24:51k²
24:53y esto es p sub k factor de 1 - p sub k,
24:57o sea, esto es p sub k * q sub k,
25:01¿cierto?
25:03Esa es la varianza.
25:05Entonces, eh eso implica que el sigma
25:07cuadrado para nuestra para nuestro
25:10ejemplo va a ser la sumatoria
25:13de PK K por q para 1 menor o igual que
25:18K, menor o igual que N. Para nuestro en
25:20el caso general, ¿no es cierto?
25:22Y y ahora sí, en nuestro caso,
25:29sigma cuadrado va a ser entonces la
25:32sumatoria
25:33de 1 menor o igual que k men igual que n
25:37de p sub k que es 1/ido por k por q sub
25:40k que es 1 - 1/ por k
25:44y eso va a dar la sumatoria para 1 menor
25:48o igual que k men o igual que n de 1/
25:50por K
25:52menos la sumatoria 1 menor o igual que K
25:55men o igual que n de 1/ k².
26:00Okay.
26:02¿Qué es esto? El primero lo conocemos,
26:04es H sub n.
26:07Ya.
26:09El segundo,
26:11eh, creo que no lo habíamos visto hasta
26:13ahora o quizás sí.
26:15es como un número armónico, pero donde
26:16los denominadores no no van con
26:19exponente uno, sino que van con
26:20exponente dos, ¿ya? Eh, eso lo vamos a
26:26llamar H sub de segundo orden,
26:30¿ya?
26:32Entonces, donde
26:34H sub n de orden S, por así decirlo, es
26:39la sumatoria para 1 menor o igual que K
26:42men o igual que n de 1 parido por k a la
26:46s.
26:48Ya. Ahora, eh sabemos
26:58que H su
27:00es asintótico al logaritmo natural de n
27:04+ gama, ¿no es cierto?
27:07cuando n tiende a infinito.
27:12Eh,
27:14y
27:15eh un resultado bien conocido es que HN
27:20de segundo orden
27:24eh converge. Ah, HSUn no converge. Hn
27:28tiende a infinito cuando n tiende a
27:30infinito y la manera como tiende
27:31infinito es logarítmicamente.
27:34HN de segundo orden en cambio converge y
27:36ustedes si se acuerdan de las
27:38matemáticas de Plan Común se van a
27:40acordar del que para sumatorias de esa
27:43de esa forma eh cualquier exponente
27:46mayor que uno en el denominador hace que
27:48la serie converja, ¿ya? Y esta en
27:51particular converge a pi cuadrado sexto.
28:04Okay,
28:07vamos bien hasta aquí.
28:09Eh, así es que el número de máximos
28:14locales de izquierda a derecha, esa
28:16variable aleatoria tiene un valor
28:18esperado que es logarítmico, pero tiene
28:22una varianza que es constante. Ah, y eso
28:25quiere decir que la variabilidad que hay
28:28en torno a la media es muy pequeña, ¿ya?
28:32Y eso a partir de Chevichev, ¿okay? Así
28:35es que el la media en este caso es un
28:38muy buen predictor de lo que va a
28:40ocurrir en en la práctica. Es es
28:43sospechamos que la distribución va a ser
28:44muy concentrada en torno al mu
28:48esparcida porque si estuviera muy
28:50esparcida entonces la varianza podría a
28:52lo mejor también tender a infinito
28:54cuando cuando n tiende a infinito, pero
28:56no. Ya, a pesar de que el número largo
28:59de la lista tienda infinito,
29:02el la la campana que sospechamos que va
29:05a ser una forma de campana, no no lo
29:06hemos demostrado, ¿no es cierto? Pero
29:08sospechamos que sería alg forma como
29:09campana, eh va a ser va permanecer muy
29:13concentrado en torno mu. Ya es lo que
29:16estamos suponiendo, pero eso ya veremos
29:19si si es cierto o no. Eh, una
29:22observación,
29:26la serie
29:28sumatoria, la serie infinita sumatoria
29:30para K mayor o igual que 1
29:34eh de 1 partido por K a la S
29:49de Riman.
29:56la z griega
29:58z de s como función de soria
30:02de 1/ido por k a la s para k mayor o
30:06igual que 1.
30:09es una función que tiene una tremenda
30:11importancia en el análisis, en teoría de
30:14números y que está al centro de uno de
30:18los problemas abiertos de matemáticas
30:19más importantes, que es la hipótesis de
30:23de RAN, que tiene que ver con la
30:25ubicación de los ceros de esta de esta
30:27función tomado como una función compleja
30:30de S.
30:33Eh,
30:34pero eso se los dejo para que ustedes lo
30:36investiguen sin por si que les interesa
30:38saber más al respecto. Ah, pero nosotros
30:41vamos a seguir adelante aquí
30:43porque eh
30:47queremos ver la, como les dije,
30:48queríamos estudiar la distribución.
30:49Entonces, tenemos que ver qué pasa con
30:51los coeficientes de esta función
30:53generatriz que acabamos de de encontrar.
30:55Ah, entonces eh queremos
31:04estudiar
31:09eh la distribución
31:17representada
31:22por la función generatriz de
31:23probabilidad.
31:25Jesu n de z.
31:28Okay.
31:30Eh, tenemos que jesu n z.
31:36Bueno, yo les dije que Jesú z que la
31:38forma que más nos iba a servir era la
31:41que marqué ahí, pero en realidad estaba
31:43mintiendo un poco porque esta de acá
31:46también va a ser útil y es la que voy a
31:48usar en este momento. Z la ncendente
31:51partido por n factorial.
31:56Entonces es z la n ascendente.
32:07Okay.
32:09Entonces, necesitamos
32:12[suspiro]
32:17calcular lo que sería el coeficiente que
32:20multiplica z a la n
32:27o de, bueno, a ver,
32:31dentro de Jesú NZ,
32:34ya ese coeficiente, porque esto es esto
32:39que es esto va a ser la probabilidad
32:43de que haya
32:46A ver, eh, aquí tengo un pequeño error.
32:52Por los tiros antes que nadie se dé
32:54cuenta. Ahí este.
32:57Eh, bueno, pues
33:04ya eh lo que quiero es Z a la K, ¿no es
33:08cierto? No z a la N. E porque eso sería
33:12la probabilidad que haya K máximos
33:15locales
33:22de izquierda a derecha.
33:27cierto, el coeficiente. Entonces, yo
33:29tengo gn, quiero extraer el coeficiente
33:32que multiplica z la k y eso va a ser la
33:34probabilidad de que haya exactamente k
33:38máximos locales. Okay. Eh, el n
33:41factorial no es ningún problema.
33:44Así que lo la solución a esto está en
33:47los coeficientes de z elevado a n
33:49ascendente, ¿no es cierto? Yo quiero ver
33:52cuál es el coeficiente que multipliica a
33:54z
33:57la n ascendente, para lo cual tengo que
33:58expandir el z a la n ascendente.
34:01Entonces, vamos.
34:04Entonces, para esto
34:11necesitamos
34:15expandir
34:19Z a la N. ascendente. Entonces, vamos.
34:23¿Qué es Z a la 0 ascendente? Z a la 0
34:26ascendente es 1.
34:30Es, digamos, Z a la 0 es 1, ¿no es
34:33cierto?
34:34Eh, ¿qué es Z a la 1 ascendente?
34:38Eso sería z * z + 1, etcétera, pero en
34:41realidad eso es solo un factor, así es
34:43que va a ser z a la 1.
34:46Digamos z a la 1.
34:50Eh, ¿qué es z la 2 ascendente?
34:54Ese ya se más interesante. Eso es z por
34:57z + 1, ¿no es cierto?
35:01Y eso va a ser igual a Z + Z².
35:11Ya, ¿qué sería Z a la tres ascendentes?
35:13Ahí estamos llegando ya a las cosas que
35:15más vale la pena no hacer a mano, ¿no es
35:17cierto? Pero tratemos de hacerlo. Va a
35:19ser z * z + 1
35:23por z + 2, ¿no es cierto?
35:26Y eso va a ser Z por el producto de Z +
35:291* 0 + 2. ¿Se acuerdan cómo calcular
35:31esos productos mentalmente? Sería eh
35:36puedo escribirlo derecha izquierda z²
35:40más eh 3z
35:46más eh 2, ¿no es cierto?
35:49Eso.
35:51Entonces sería 2z
35:55+ 3z²
36:00+ Z c
36:03y así sucesivamente.
36:05Eh,
36:09usemos un poco nuestra calculadora
36:11simbólica
36:14para calcular un par de de expansiones
36:17más. Ya demasiado riesgoso seguir
36:20tratando de hacerla a mano. Así que
36:24vamos aquí vamos a ir share
36:27y
36:51entonces vamos a decir que vamos a usar
36:53variables
36:55Z y N como variables, perdón,
37:01Z y N como variables formales.
37:14Ya. y vamos a definir una función
37:27que retorna
37:30el resultado de expandir.
37:35Expandir qué cosa? Expandir el producto.
37:43¿Qué producto? el producto de Z + J,
37:46digamos,
37:50para J
37:54en el rango
37:56de eh 0 N. Claro,
38:020 n. Ya.
38:05Eso.
38:09¿Y qué me faltó?
38:12Producto
38:14hace falta un
38:17Eso sira paréntesis. Ya. Entonces, esto
38:20va a ser z + 0 * z + 1 * z + 2. ¿ya? O
38:24sea, z * z + 1, z + 2, z + n - 1, que
38:29porque recuerden que el el intervalo es
38:32abierto por la derecha, eh, así que ese
38:34es. Entonces, aquí ahora yo puedo venir
38:37y preguntar cuánto era g de cer, ¿no es
38:39cierto? Que sabemos que tiene que ser
38:41uno.
38:45Sí, afortunadamente lo vio bien. Eh,
38:48¿cuánto es G de 1
38:52Z? Ya.
38:54G de 2 [suspiro]
38:58Z +² sería
39:02eh G de 3,
39:07el que calculamos a mano, ¿no es cierto?
39:092 Z, lo estoy leyendo derecha,
39:10izquierda, así lo tenía en el apunte. 2z
39:14+ 3z² + Z³.
39:17Y hagamos un par más de 4
39:22sería 6z + 11z² + 6z³ + z a la cu y uno
39:28más para determinar g5
39:32sería 24z + 50 z² 35z³ 10 z a la cu
39:38un z a la qua h Entonces con eso podemos
39:43completar un poco nuestra tabla de
39:44expansiones. Así es que voy a volver a
40:03el Z a la cu ascendente
40:08ya de memoria
40:11lo tengo en una punta que no es de
40:12memoria sería 6z z + 11 z²
40:18+ 6z
40:20cu c + 1 z a la cu
40:24y el otro que calculé sería z a la 5
40:27ascendente que sería 29
40:31z + 50 z cu
40:37+ 35 z³
40:41+ 10 z la Cuarta
40:46la Z a la quinta.
40:48Okay.
40:55A ver, ya vemos
41:01s sub n k al coeficiente que multiplica
41:06a z a la k dentro de z a la n
41:10ascendente. ¿Ya? O sea, esos números que
41:13ustedes están viendo ahí como
41:14coeficientes son los s sub n como k.
41:17Entonces, con esos se suene como acá
41:22yo puedo construir una pequeña tabla
41:24aquí. Ah, entonces voy a tener una tabla
41:27aquí y una tabla acá, ¿no es cierto?
41:32Entonces,
41:34a ver, digamos que esto sería 0 1 2 3 4
41:425 Aquí
41:450 1
41:483 cu
41:51voy a necesitar más cinco por aquí.
41:57Ya. Entonces, aquí puedo poner el N.
42:00Aquí puedo poner el K.
42:01El sería 0 1 2 3 4 5 0 1 2 3 4 5. Ya.
42:11Entonces, si miramos nuestra tabula, Z a
42:15la 0 se expande como Z. Z a la 0
42:17ascendente se expande como Z a la 0. O
42:19sea, aquí el y el coeficiente es uno.
42:22Ya. El z a la 1 se expande como z a la
42:261. Ascendente se expanda como z a la 1.
42:28O sea, el coeficiente es un uno pero va
42:30acá.
42:32Z a la 2. El primero que ya más
42:33interesante es z + z², o sea, z a la 1 +
42:38z². Z a la 1 va aquí, z cuad va acá.
42:44Después el Z a la 3 ascendente,
42:49los coeficientes serían 2 3 1.
42:58Pues el siguiente eh sería
43:0261 6
43:10y el siguiente sería 29.
43:1529. No me equivoqué, creo. Creo copié
43:18mal.
43:21Era 24. Siguiente. A ver, déjame chear.
43:24Claro, 24. ¿Y dónde puse 29? Aquí no más
43:27parece. La única parte donde está malo.
43:29Vamos.
43:3424.
43:36Sí, lo chequé en la otra pantalla.
43:39Es 24.
43:4550
43:4835
43:5110
43:54y uno.
43:57Fíjense que la diagonal siempre es uno
44:00y tiene que ser.
44:04Bueno, estos números que están
44:06apareciendo aquí
44:08eh son conocidos en matemática.
44:12Eh,
44:14los números
44:21S sub n como K
44:24se llaman
44:27los
44:29números
44:31de Stirl
44:37del primer tipo.
44:53Tien varios nombres, además también se
44:54llaman Sterling. En inglés Sterling
44:58Cycle Numbers.
45:02Ahora, si hay del primer tipo, ustedes
45:04sospecharán que hay también del segundo
45:05tipo, ¿no es cierto? Bueno, eso ya van a
45:07aparecer en unos minutos más.
45:09¿Por qué se llaman sterling cycle
45:11numbers? Porque si ustedes se acuerdan,
45:13el número de máximos locales de
45:15izquierda a derecha era igual como
45:18variable aleatoria al número de ciclos
45:21que hay en una permutación aleatoria de
45:23largo n. ¿Ya? Entonces, estos números de
45:26stecuentan eh o nos entregan la
45:29probabilidad de que una permutación
45:30tenga k ciclos
45:33una vez que yo lo divido por n
45:34factorial, por supuesto. Ya, todos estos
45:36números hay que dividirlos por n
45:38factorial para que sean probabilidades.
45:41¿Okay?
45:43Eh, entonces,
45:45eh, ah, y bueno, y tiene una anotación
45:49y y se denotan
45:55como n sobre K, pero con paréntesis
45:58cuadrado.
45:59SAT una notación similar a los a los
46:02coeficientes binomiales, pero los
46:04coeficientes binomiales se escriben con
46:05paréntesis redondo. Los números de
46:07stling de primer tipo se escriben con
46:09paréntesis cuadrados.
46:12Y bueno, para anticiparnos un poco, los
46:14números de estil segundo tipo se
46:15escriben con con llave, paréntesis de
46:17llave, ¿no?
46:20Eh, entonces como estos son los
46:22coeficientes que aparecen en la
46:23expansión, entonces su su definición
46:27viene de que z a la n ascendente se
46:33expande como la sumatoria sobre K de N
46:37sobre K, números de steel ring de primer
46:39tipo por Z a la K.
46:42Ya. Y el rango eh del K no necesitamos
46:46en realidad indicarlo porque eh se
46:52limita naturalmente los números Steing
46:54son cero fuera del del rango que ustedes
46:57ven ahí hacia la izquierda, hacia la
46:59derecha son cero.
47:02Y ustedes conocen la la la fórmula de
47:06recurrencia para los coeficientes
47:08binomiales, ¿no es cierto? que n sobre k
47:11es eh n - 1 sobre k - 1 eh + n - 1 sobre
47:18k h la que da el triángulo de pascal.
47:21Esto que ustedes están viendo ahí es lo
47:22que vendría a ser el triángulo de
47:23Pascal, pero para números de sterling,
47:26¿ya? Y la propiedad que define a este
47:29triángulo, esta especie de triángulo
47:31pascal es la siguiente.
47:34La propiedad
47:36que tienen es que n sobre k
47:42es n - 1 sobre k - 1
47:48+ n - 1 m* n - 1 sobre k.
47:56Ya.
47:58Eh, en los coeficientes binomiales la la
48:01recurrencia es muy parecida. Lo único
48:05que este factor n -1 en ese caso no
48:07aparece. Ya. Y en este caso sí, en el
48:10caso de los números aparece ese factor
48:12n-1 que ustedes están viendo aquí. ¿Ya?
48:18Y y el caso de los de los de los
48:20coeficientes manuales, este factor n -1
48:22no existe.
48:25Así que eso
48:29sobre
48:31números de sterling. Ya. Ahora,
48:35esta expansión que yo que ustedes están
48:37viendo aquí, ya la que
48:43esta espacio que está aquí
48:46me dice que para cualquier n eh yo puedo
48:51expandir el z a la n ascendente como una
48:54combinación lineal de potencias normales
48:58Z la K, ¿no es cierto? Estas no son
49:00potencias ascendentes, son las potencias
49:01normales
49:03y estos son los coeficientes de esa
49:05combinación lineal.
49:07Entonces, y si eso yo lo escribo línea
49:10por línea, como la que estaba aquí,
49:14ya esto, esto que estoy viendo aquí,
49:18todo esto que estoy viendo aquí, yo lo
49:20puedo escribir de manera matricial,
49:23si es que pongo un vector de todos los
49:24zas elevados a potencia ascendente y acá
49:28este otro lado tengo un vector de todas
49:29las potencias normales y aquí están los
49:31coeficientes que permiten transformar de
49:33uno en otro. Ya. Entonces
49:38esto
49:44se puede
49:48escribir
49:51de manera matricial.
49:59Mire, aquí yo tengo un vector
50:05que son todas las potencias ascendentes.
50:08Z a la 0 ascendente, Z a la 1
50:11ascendente, Z a la 2 ascendente, Z a la
50:153 ascendente y así sucesivamente, ¿no es
50:17cierto?
50:19Z a la 4 ascendente, Z a la 5
50:22ascendente. Esto es un vector infinito.
50:24Ah,
50:25y aquí hay una matriz
50:28también infinita.
50:31En están los coeficientes que acabamos
50:32de ver. El coeficiente uno, todo lo que
50:35yo no ponga son ceros, ¿no es cierto?
50:37Entonces, está el uno, acá está el 1,
50:42acá está el 2 3 1, acá está el 6
50:50y así sucesivamente.
50:52Esto es una matrizangular inferior, o
50:54sea, es puro cero. Ya. Y acá está el
50:57vector de potencias normales.
51:02Z a la 0, Z a la 1, Z a la 2, Z a la 3,
51:08Z a la 4 y así.
51:16Sí, aquí tengo una ecuación matricial.
51:21En realidad no es una ecuación porque no
51:22hay incógnita, si no me fino una
51:24identidad matricial de matrices y
51:27vectores infinitos, está pero no es
51:29problema porque no es problema que sean
51:31infinitos porque cada línea contiene
51:34solamente un número finito de términos
51:36no ceros. Así es que no tengo problema
51:38en hacer el cálculo. Ya. Eh, pero eh
51:43escrito de esta manera. Bueno, y esta
51:45matriz la podemos llamar S. Hm.
51:50mayúscula es la matriz de los números de
51:52sterling de de primer tipo, ¿ya?
51:57Pero escrito de esta manera, esto
51:59sugiere
52:01de inmediato que yo puedo despejar
52:06podemos despejar el vector de la derecha
52:08de potencias normales en función del
52:11vector de la izquierda de potencias
52:13ascendentes. Entonces, eh
52:20despejando
52:23yo puedo expresar mi vector de la
52:25derecha, que sería z a la 0, z a la 1, z
52:30a la dos y así sucesivamente
52:42como una cierta matriz.
52:45que va a ser S a la men-1, ¿no es
52:49cierto?
52:50Si es que es la de arriba era S, esta es
52:52S a la men1
52:54que va a estar multiplicando a vector de
52:57potencia
52:59ascendente Z a la 0 ascendente, Z a la 1
53:04ascendente Z a la 2 ascendente y así
53:06sucesivamente.
53:17Y estos que están aquí,
53:20los coeficientes que aparecen en esta
53:21matriz inversa,
53:24son
53:26se anotan n sobre k con paréntesis
53:29de llave, paréntesis crespo y se llaman
53:32los números de steerling del segundo
53:34tipo.
53:41Ya. Entonces, los números de estilen de
53:43primer tipo permiten pasar de potencias
53:46ascendentes a potencias normales y los
53:48números estiles de segundo tipo permiten
53:50pasar de potencias normales a potencia
53:53a potencia ascendente. Ah, entonces eh
53:58cómo
54:00sin invertir esta matriz infinita, ¿cómo
54:02podríamos encontrar lo que son esos esos
54:05números? Bueno, el Z
54:09z a la 0 claramente es Z a la 0
54:12ascendente, lo mismo, ¿cierto? Y Z a la
54:141 es z a la 1 ascendente. Así que esos
54:18dos no tienen misterio. Eh, pero ¿cómo
54:21se escribiría Z cuado
54:24en función
54:26de potencias ascendentes? Ya. Bueno, eh,
54:29si va a haber un z², eso necesariamente
54:33quiere decir que tiene que haber un z a
54:35la dos ascendentes. El único que aporta
54:37un cuadrado. ¿Ya? Eh, entonces, ¿qué es
54:40Z a la do ascendente? A ver, déjeme un
54:42espacio ahí. Z a la 2 ascendente sería Z
54:47* Z + 1, ¿no es cierto?
54:50Eh, y eso sería z²
54:54+ Z.
54:56Si yo lo dejara hasta ahí no más, ya
55:00esto no sería z² porque sería z² + z.
55:03Así que para que sea realmente z² tengo
55:06que restar el z que sobra. Y el z que
55:09sobra lo puedo restar como un z a la 1
55:11ascendente,
55:16que sería restar z. Sería restar z, con
55:19lo cual esto se va y queda z². Entonces,
55:22fíjese los coeficientes que aparecieron
55:24aquí.
55:25apareció un -1 y un +1. Ya. Y
55:32si intentamos hacer un
55:36un
55:38el siguiente.
55:41A ver, eh, ¿cómo cómo yo podría hacer un
55:43Z cubo, ya? Z cubo tiene que comenzar
55:48con un Z a la 3 ascendente. ¿Ya? ¿Y qué
55:52es Z a la 3 ascendente? Eso yo lo sé por
55:55los números de Stirling, ¿no es cierto?
55:57Z a la 3 ascendente va a ser, no tengo
56:01más que hacerlo. Yo ya lo tengo, ya lo
56:03hice, de hecho. Z³ + 3z²
56:09+ 2z.
56:11Okay. Entonces,
56:14eh, bueno, ahí el z³ está bien, pero el
56:173 cu
56:20+ 2z eh sobra, ¿no es cierto? Entonces,
56:22tengo que restar 3 z². Para eso voy a
56:25restar 3 Z a la 2 ascendente.
56:30Entonces, yo le resto 3 z a la dos
56:32ascendentes
56:34y y 3z a la 2 ascendente
56:39eh es eh
56:42-3z
56:44- 3z²,
56:48lo cual está bien porque me cancela el 3
56:51z²,
56:53pero me quedó un - z,
56:56que para compensar yo tengo entonces que
56:59sumar un + z a la 1 ascendente y eso me
57:03agregaría un + z que hace que todo se
57:05cancele y queda perfecto. ¿Ya? Entonces,
57:08fíjense ustedes los coeficientes que han
57:10ido apareciendo. Aquí aparece un 1, un
57:11-3 y un +1. Entonces, yo puedo armar una
57:16mi yo puedo armar mi tabla aquí
57:22de coeficiente de stil de segundo tipo,
57:24¿ya?
57:26Eh,
57:44aquí está el N. Aquí está el K y lo que
57:46estaría aquí sería el N sobre K. Aquí 0
57:511 2 3 4 5 0 1 2 3 4 5 y los números
57:59entonces sería uno aquí, aquí sería uno
58:02acá sería -1 porque me salió un menos z
58:08a la 1 ascendente y un + z la 2
58:11ascendente. Y acá sería 1 - 3 1.
58:18Y acá sería menos si siguiéramos sería
58:21esto.
58:23Y el siguiente sería 1 - 15
58:2825
58:30- 10
58:321. ¿Ya? Y así sucesivamente. Entonces
58:35sigue, por supuesto. Ya. Estos son los
58:38coeficientes de segundo tipo. Ahora,
58:41fíjense ustedes que hay signos
58:42alternados. Ah, entonces eh los
58:46[suspiro]
58:48n sobre k
58:55se definen
58:59como los valores absolutos
59:07y los signos alternados.
59:14se se incorporan
59:20en la fórmula de expansión.
59:30Okay.
59:38A ver.
59:47Okay.
59:49Así que
59:52con esto ustedes ya, pero algunos de
59:55ustedes quizás los conocían ya, si no
59:56los otros les he presentado dos números
1:00:01eh de importancia en combinatoria y en
1:00:05análisis de algoritmo que son los
1:00:07números de sterling de primer y de
1:00:09segundo tipo. Ahora, veamos,
1:00:13acerquémonos a a nuestros temas de más
1:00:16de computación, computer science, ¿no?
1:00:19En particular, eh, veamos cuál es la
1:00:22relación con los árboles de búsqueda
1:00:23binaria.
1:00:38Supongamos que yo
1:00:41construí un árbol con las con esta
1:00:43secuencia de números, consideráolo
1:00:45inserciones.
1:00:54Ya. Entonces, eh
1:00:57aparece el tres, ¿no es cierto? Después
1:00:59a la izquierda el uno.
1:01:02Después aparece el cinco que está por
1:01:04acá.
1:01:05El dos vendría por acá.
1:01:08El cuatro aquí.
1:01:11El ocho vendría acá.
1:01:14El siete acá
1:01:17el nueve acá
1:01:20y el seis acá. Esa sería.
1:01:25Entonces, lo que habíamos visto, eh, por
1:01:28ejemplo, el largo de la rama derecha, si
1:01:30yo marco
1:01:34lo que hay en la rama derecha, eso
1:01:36corresponde a los máximos locales de
1:01:39izquierda a derecha
1:01:42en la permutación, ¿no es cierto? Eso ya
1:01:45lo lo sabíamos. Entonces,
1:01:52el largo de la rama derecha
1:02:03es igual al número de máximos locales
1:02:12de izquierda a derecha.
1:02:17Por lo tanto, ahora yo sé que su
1:02:21distribución
1:02:27es z la n ascendente partido por n
1:02:30factorial o lo que es lo mismo z - 1 n,
1:02:35¿cierto? Ese ese esa es la función
1:02:38generatriz que me da la probabilidad que
1:02:40la rama derecha tenga largo K.
1:02:44Entonces, pero es el largo de la rama
1:02:46derecha. Supongamos ahora que yo quiero
1:02:48hacer una búsqueda infructuosa. Ya. Si
1:02:51quiero hacer una búsqueda infructuosa.
1:03:01Entonces, supongamos que copiamos de
1:03:04nuevo el arbolito.
1:03:06tres.
1:03:09Un, dos,
1:03:13cinco.
1:03:27Ya.
1:03:30Y supongamos que yo busco el,
1:03:35supongamos que buscamos
1:03:38tengo que buscar un número que no esté,
1:03:40¿no es cierto? Por ejemplo, supong
1:03:42buscamos 6.5. Ah, un número que no está
1:03:45en en el árbol. Entonces, eh, en este
1:03:49árbol yo voy a terminar aquí, ¿no es
1:03:52cierto? Aquí en esta hoja que hasta
1:03:55ahora no había dibujado las hojas, pero
1:03:57si dibujo las hojas en esa hoja es donde
1:03:59yo termino. Ahí ahí estaría el espacio
1:04:01para el 6.5, ¿no es cierto? Entonces
1:04:06si si
1:04:08yo veo el camino que seguí para llegar
1:04:10ahí, ¿no es cierto? Obviamente
1:04:12el camino que seguí para llegar aquí fue
1:04:15este. Voy aquí y acá. Ya. Eh, en este
1:04:18camino yo me encontré en números que
1:04:21eran menores que el 6,5, por ejemplo, el
1:04:233, el 5, el seis y números que eran
1:04:27mayores, el ocho, el siete. Ya el lo
1:04:32puedo marcar de distintos colores,
1:04:35ya el tres, el cinco, el seis fueron
1:04:39números que me encontré por el camino
1:04:41que eran menores que el 6,5.
1:04:45Y por otro lado me encontré números como
1:04:47el 8 y el 7 que eran mayores que el 6,5,
1:04:51¿cierto?
1:04:54Entonces, ¿qué relación tiene eso con
1:04:57máximos y mínimos? La relación que hay
1:04:59es la siguiente. Si yo tengo aquí mi
1:05:01lista de números, que serían el tres, el
1:05:041, el 5, el dos, el 4, el 8, el 7, el 9,
1:05:11el 6,
1:05:14yo la puedo separar entre los que son
1:05:17menores que 6.5
1:05:19y los que son mayores que 6.5.
1:05:23Okay. Entonces, en los menores,
1:05:26¿cuáles serían menores? serían el tres,
1:05:30el uno, el cco,
1:05:35el dos,
1:05:37el cuatro,
1:05:41el seis
1:05:45y mayores que 6.5, ¿cuáles serían?
1:05:48El 8o,
1:05:51el 7,
1:05:53el nueve.
1:05:55Okay. Entonces, si ahora yo voy
1:06:01y marco en la primera de las listas,
1:06:04¿cuál es el cuáles son los que yo me
1:06:06encontré por el camino?
1:06:08Yo me encontré con el tres, el cinco y
1:06:12el seis, que son exactamente
1:06:15los máximos locales de izquierda a
1:06:17derecha dentro de los que son menores.
1:06:21Y si yo marco los que me encontré
1:06:24que eran mayores, serían el ocho y el
1:06:27siete,
1:06:29que son exactamente los mínimos locales
1:06:32de izquierda a derecha dentro de los que
1:06:34son mayores. Ya. Ahora, máximos y
1:06:38mínimos son simétricos, así que la
1:06:39distribución es la misma. Entonces, eh
1:06:42si si yo digo que hay eh
1:06:47ahí no me quedó mucho espacio, pero si
1:06:50yo digo que aquí hay k menores ah y acá
1:06:55entonces hay n- k mayores.
1:07:01Para buscar fijo,
1:07:06el costo de la búsqueda
1:07:14es la suma
1:07:20de
1:07:23los máximos locales
1:07:29de izquierda a derecha.
1:07:35en una lista de largo K,
1:07:40¿cierto? Lo que está marcado en naranja
1:07:44y más los mínimos
1:07:49locales
1:07:52de izquierda a derecha
1:07:56en una lista de largo N- K.
1:08:05Eh,
1:08:08y ambos son independientes
1:08:22y por lo tanto
1:08:27su función general de probabilidad es el
1:08:31producto,
1:08:38el producto
1:08:41de ambas
1:08:45funciones generatriz de probabilidad.
1:08:47Entonces, yo tengo la función generatriz
1:08:49de probabilidad.
1:08:51Yo conozco la función generatriz de
1:08:54probabilidad del número de máximos
1:08:55locales en una lista de largo K.
1:08:58Y yo conozco la función generatriz de
1:09:00probabilidad en una lista de de largo n
1:09:05- k y lo que tengo que hacer es hacer el
1:09:07producto. Así es que el producto de
1:09:10estas dos funciones generatrices de
1:09:11probabilidad va a ser la primera que es
1:09:15z - 1, k, ¿cierto? Pues ustedes se
1:09:19acuerdan que la distribución la la
1:09:23función generatriz era z - 1, n cuando
1:09:25la lista era largo n. Así es que esto va
1:09:28a ser z - 1 - k men como k multiplicado
1:09:31por z - 1
1:09:35coma n - k.
1:09:39Ya, pero eso es cuando hay un k fijo.
1:09:45Pero el K no es fijo, ¿ya? El K es el
1:09:49número de elementos que quedan a la
1:09:52izquierda del que yo estoy buscando.
1:09:56¿Cuántos si hago una búsqueda
1:09:59en un árbol de búsqueda binaria con n
1:10:01elementos con n llaves de un elemento
1:10:04que no está?
1:10:06¿Cuántos elementos quedan a la
1:10:07izquierda? Bueno, eso varía. Puede que
1:10:09no quede ninguno a la izquierda si es
1:10:11que yo estoy buscando uno que es menor
1:10:12que todos los que están presentes, ¿no
1:10:13es cierto?
1:10:15Y el otro extremo es que queden todos a
1:10:17la izquierda. Si estoy buscando uno que
1:10:18es mayor que todos los que están
1:10:19presentes, o sea, tengo n más un
1:10:22posibilidades, que no quede nadie, cero
1:10:25hasta que hasta que queden todos n. De
1:10:27er hasta n hay n más n más un
1:10:29posibilidades y son todas aquí
1:10:31probables. Ya el elemento que yo estoy
1:10:33buscando puede caer en cualquiera de los
1:10:35n más lugares de con la misma
1:10:37probabilidad. Por lo tanto, para obtener
1:10:40la función generatriz de probabilidad,
1:10:44cuando buscamos un elemento aleatorio,
1:10:48si buscamos
1:10:50infructuosamente
1:10:59un elemento
1:11:02aleatorio,
1:11:09Ya. Entonces,
1:11:18la función generatriz de probabilidad
1:11:22para el costo de búsqueda,
1:11:32digamos,
1:11:36Punz.
1:11:40[suspiro]
1:11:40es
1:11:42pes de z igual al promedio.
1:12:12Ya, a ese promedio.
1:12:15Porque lo que tengo aquí,
1:12:21este es el la función generatriz del
1:12:23costo de búsqueda cuando yo busco el
1:12:24K1o,
1:12:26o sea, está condicionado a que yo busco
1:12:28el K1 y para remover la condicionalidad
1:12:30lo que tengo que hacer es ponderar por
1:12:33la probabilidad de que yo busque el K1
1:12:35que es 1/ido por n + 1 y sumar sobre
1:12:37todos esos sobre todos los valores de K
1:12:40y me queda este promedio.
1:12:43Esa es la función generatriz de
1:12:44probabilidad del costo de búsqueda
1:12:48de un elemento aleatorio. Ya. Ahora,
1:12:51¿esta sumatoria se puede simplificar? En
1:12:54realidad sí. Ah, se puede simplificar
1:12:57porque eh olvidémonos por un momento del
1:13:02del
1:13:051 parido por n + 1. Ya.
1:13:10Después dividimos por n
1:13:16suma
1:13:19sumatoria 0 menor igual que k men igual
1:13:22que n de z - 1
1:13:25k por z - 1
1:13:29n - k
1:13:32es una convolución.
1:13:39Okay.
1:13:41Entonces,
1:13:44si yo le aplico función generatriz
1:13:48a a esto,
1:13:50ya
1:13:52si yo le aplico
1:13:55función generatriz en Z a esto, la
1:13:58generatriz de una convolución es el
1:13:59producto de las generatrices, ¿no es
1:14:01cierto? Entonces, ¿cuál es la generatriz
1:14:04de z - 1, k?
1:14:06Eso es 1/ido por 1 - z.
1:14:12Eh, no, en realidad la variable z ya
1:14:14está ocupada. Usemos otra, usemos x. Ya,
1:14:20Z ya está usada, así que llamémosla,
1:14:25llamamos X.
1:14:271 - x elevado a Z.
1:14:31¿Se
1:14:33acuerdan ustedes que la generatriz del
1:14:36coeficiente binomial simétrico alfa n
1:14:40era 1/ido por 1 + z elevado alfa + 1?
1:14:43Ah, alfa + 1. Así que hay que sumarle 1
1:14:46al z - 1 me queda z.
1:14:48Y el la otra es la misma, es 1/ido por 1
1:14:53- x, digamos, a la z también es la misma
1:14:58en la convolución, por lo tanto es es 1
1:15:02par 1 - x
1:15:05a la 2z.
1:15:09Y si ahora yo extraigo el coeficiente,
1:15:13ya,
1:15:14eh
1:15:16lo que me queda es eh un coeficiente
1:15:20minimal simétrico
1:15:24en que en vez de ser z- 1 ahora es 2 z -
1:15:281. Eso es todo. Simple.
1:15:35Por lo tanto, la suma
1:15:40es igual a
1:15:46eh al coeficiente binomial simétrico
1:15:502 z - 1, n.
1:15:54Ya, esta
1:15:59esto es igual a eso.
1:16:02suma de coeficientes binomiales se
1:16:04simplifica
1:16:05a esta a este coeficiente binomial
1:16:10con esto de que es una convolución y por
1:16:13lo tanto [carraspeo]
1:16:15el p sub n
1:16:18de z
1:16:25- 1 n parido por n + 1.
1:16:32Esa es la función generatriz de
1:16:34probabilidad del costo
1:16:37de búsqueda infructosa en un árbol de
1:16:40búsqueda
1:16:42binaria construido al azar. Ah, este es
1:16:45la función generatriz de probabilidad
1:16:49del costo de búsqueda
1:16:56y fructuosa.
1:17:02Ya.
1:17:04Ahora, eh nos quedan unos minutos, así
1:17:06que podemos trabajar un poquito con esta
1:17:09fórmula.
1:17:10Esto es lo mismo que 2 z a la n
1:17:15ascendente partido por n
1:17:18+ 1 factorial porque partido por n
1:17:20factorial, pero hay un n + 1 además, así
1:17:23que es un n + 1 factorial,
1:17:26¿ya?
1:17:27Y esto expandido sería, ¿cuánto? sería
1:17:302z
1:17:332z + 1
1:17:36hasta 2z + n - 1
1:17:42divido por 1 * 2 * 3 hasta n + 1.
1:17:44Olvidémonos del 1, pongámosle 2 3 hasta
1:17:48n + 1.
1:17:50Ya. Y esto es la pitatoria
1:17:57para cer menor o igual que k menor o
1:17:59igual que n - 1
1:18:03de 2z + k,
1:18:07¿cierto?
1:18:10Partido por eh K + 2.
1:18:17Sí.
1:18:20Y esto yo lo puedo escribir como la
1:18:21pitatoria
1:18:23para 0 menor igual que k men igual que n
1:18:26- 1
1:18:28de k paro por k + 2
1:18:33+ 2 parido por k + 2z.
1:18:39¿Y para qué me doy el trabajo de
1:18:40escribirlo de esta manera? Porque ahora
1:18:42puedo identificar y decir, "Mire, esto
1:18:44es un q sub k.
1:18:48¿Qué pasó? Ah,
1:18:53esto es un Q sub K y esto de acá, este
1:18:57de aquí y este de acá es un P sub K.
1:19:01Por lo tanto,
1:19:04a lo que quería llegar es que
1:19:07esto
1:19:08también corresponde
1:19:13[suspiro]
1:19:14corresponde
1:19:20a un proceso
1:19:25de lanzamiento de monedas distintas.
1:19:37O sea, el largo de la rama derecha es un
1:19:39proceso de lanzamiento de monedas
1:19:41distintas. El costo de búsqueda
1:19:43infructuoso también se puede representar
1:19:45como un
1:19:48como un proceso de lanzamiento de
1:19:51monedas distintas. Ah, y si decimos
1:19:59que el largo de la rama derecha
1:20:17tiene distribución.
1:20:23fz
1:20:25= a z - 1 n
1:20:29= z * z + 1
1:20:35hasta z + n - 1
1:20:39divido por n factorial, ¿no es cierto?
1:20:43y
1:20:45que el costo de búsqueda
1:20:59tiene
1:21:02la distribución que acabamos de ver,
1:21:06llamémosla G g
1:21:10de Z igual
1:21:132 z - 1 n divido por n + 1
1:21:19que sería
1:21:202z
1:21:232z + 1
1:21:26hasta 2z + n - 1 dividido todo eso por n
1:21:31+ 1 factorial.
1:21:36Entonces
1:21:40se puede
1:21:43escribir
1:21:46G de Z
1:21:49como G de Z
1:21:53igual a F de 2 z.
1:21:59¿Qué pasa si yo pongo f de 2 z y voy
1:22:02acá? Ah.
1:22:04Si la si en el en el f en vez de poner z
1:22:09yo pongo 2 z, me va a quedar 2 zz + 1,
1:22:15ya hasta 2z + n - 1 que corresponde
1:22:17exactamente al numerador de acá, ¿ya?
1:22:20Quedaría dividido por n factorial. Pero
1:22:22el problema es que si yo lo dejo así,
1:22:25eso no es una función generativa de
1:22:26probabilidad porque f si pongo en una
1:22:31función generativa de probabilidad al
1:22:33poner z = 1 tiene que valer 1. Eso
1:22:35caracteriza una función generatriz de
1:22:37probabilidad. En este caso no sería
1:22:38cierto [carraspeo]
1:22:41porque f1
1:22:43ya eh sería, perdón, g de1 sería f2 y f2
1:22:50no tiene por qué valer 1. Pero yo puedo
1:22:53normalizar
1:22:55si yo divido
1:22:58por f de2,
1:23:01en ese caso el resultado sí es una
1:23:03función general de probabilidad. Ya. Eh,
1:23:07porque ahora sí el cociente vale vale
1:23:10uno. Ah, ¿y qué eh significa poner f
1:23:14de2?
1:23:16F de2.
1:23:21En nuestro ejemplo,
1:23:25f2 sería poner eh n1
1:23:30y n1 es n + 1, ¿ya? que es exactamente
1:23:34el n + 1 por el cual tengo que dividir
1:23:36ahí. Ya. Eh,
1:23:40otra manera de
1:23:45Sí, está bien. Eh, eso yo lo puedo ver
1:23:48aquí también. ¿Cuánto es f de
1:23:51para n = 2? Ah, es eh
1:23:58a ver, eh, no no no no no. Eh, para z =
1:24:012, o sea, para z - 1 = 1, para z = 2,
1:24:05sería
1:24:07y no, acá es más difícil de ver, eh,
1:24:10pero
1:24:12pero si acá esto lo escribo como,
1:24:16¿cuánto es n1? Eso es n + 1 sobre 1 y n
1:24:19+ 1 sobre 1 es n + 1. Ahí está, ahí es
1:24:21más fácil. Ya. Y ese es el n + 1 que
1:24:23aparece ahí. Ese n + 1 es el f de2
1:24:27necesario para para normalizar. Así que
1:24:32eh eh en realidad eh todo esto se puede
1:24:35representar como procesos de lanzamiento
1:24:37de monedas distintas. Y eso manténgalo
1:24:40en mente porque ahí voy a ver que eh
1:24:46porque hay una pregunta que todavía no
1:24:47hemos respondido ah que es qué forma
1:24:50tiene la
1:24:52distribución. Si nosotros volvemos a
1:24:56nuestras tablas, lo que vemos es que eh
1:25:00acá
1:25:03esta en cada línea los números van
1:25:06creciendo hasta un cierto punto y luego
1:25:08decrecen. 2450 35 10 1 son estrictamente
1:25:12ascendentes hasta un cierto punto son
1:25:14estrictamente descendentes a partir de
1:25:15ahí. ¿Y cuál es el punto donde está el
1:25:18máximo? Mm, vaya uno a saber. Así que
1:25:22ese punto todavía lo tenemos pendiente.
1:25:24Vamos a ver si lo si lo abordamos en la
1:25:27casa que viene. Ya, pero eso sería todo
1:25:30por hoy. Muchas gracias a todos los que
1:25:34vinieron y espero que hayan descansado
1:25:37el receso y nos volveremos a ver en la
1:25:41clase del viernes. Hasta luego.
1:25:44Chao, profe. Gracias.
1:25:46Chao, profe. Gracias. Hasta luego.
1:25:48Hasta luego.