Cap tulo 2

Procesos Estoc asticos

La teor a de la probabilidad es, junto con la teor a de se nales, uno de los dos pilares matem aticos sobre los que se asienta el an alisis de sistemas de comunicaciones digitales. En este cap tulo se presentan nociones b asicas de probabilidad y procesos aleatorios. Se revisan los conceptos de variable aleatoria y procesos estoc asticos y sus propiedades, en particular aquellas de inter es en comunicaciones digitales [5].

2.1

Probabilidad

El concepto de probabilidad est a ligado a realizaci on (f sica o mental) de un experimento aleatorio, entendi endose por tal un experimento cuyo resultado es desconocido (es decir, no predecible) por un observador. Suele ponerse el ejemplo de lanzamiento de un dado: el resultado puede ser cualquier n umero entre 1 y 6, pero es a priori impredecible ni siquiera por el lanzador. La probabilidad es una medida de la incertidumbre que, para un observador, tiene el resultado de un experimento, y es, por tanto, una medida subjetiva: as , por ejemplo, el contenido de un mensaje enviado a trav es de un canal de comunicaciones digitales es completamente desconocido por el receptor antes de iniciarse la comunicaci on, pero no por el transmisor, que puede predecirlo con exactitud en la medida que conoce el mensaje transmitido [5]. El desconocimiento puede ser total o parcial. Si consideramos el experimento lanzar dos dados y sumar sus puntos, cualquier resultado entre 2 (1 + 1) y 12 (6 + 6) es 17

18

Procesos Estoc asticos

posible, pero tambi en sabemos que el 7 es un resultado m as esperable que el 2. Lo sabemos por naturaleza del experimento o por informaci on estad stica. La probabilidad es pues esencialmente, una medida de incertidumbre sobre el resultado del experimento y es, por tanto, dependiente de la cantidad de informaci on disponible por el observador en cada momento. Para acercarnos a una denici on m as formal, se precisan varios elementos: Un espacio muestral, , que es el conjunto de todos los resultados posibles de un experimento aleatorio. Un conjunto de sucesos, = {S, S }. Un suceso es cualquier subconjunto de 1 . Ejemplos de sucesos en el ejemplo de los dados son que la suma sea: 2, un n umero impar, un n umero menor que 8, etc. En total hay 211 posibles sucesos. Denimos ahora una medida de probabilidad Pr como toda una funci on que, aplicada sobre cualquier suceso S , devuelve un n umero real Pr {S } que vericalas siguientes propiedades: 1. 0 < Pr {S } < 1 2. Pr {} = 0 3. Pr {} = 1 4. Dado un conjunto nito ( o innito numerable) de sucesos Si disjuntos Si Si = se verica

Pr
k=1

Si

=
k=1

Pr {Si }

(2.1)

2.1.1

Asignaci on de probabilidades a sucesos

Supongamos que el experimento aleatorio puede repetirse un n umero indenido de veces, y que el resultado de cada experimento es independiente de los dem as. Diremos que una probabilidad Pr es un buen modelo de incertidumbre para dicho experimento en la medida en que sea capaz de predecir con exactitud la frecuencia con la que se repiten los diferentes sucesos del experimento. Es decir, Pr es una buena medida de incertidumbre sobre el resultado del experimento si dado cualquier suceso S , tras N repeticiones del experimento, denominado Ns

2.2 Variables Aleatorias

19

al n umero de veces que se produce alg un resultado que est a en S, el cociente Ns /N converge a P {S } cuando N tiende a innito.[13]

2.2

Variables Aleatorias

Estrictamente hablando, variable aleatoria es toda aplicaci on de en la recta real, que asigna a cada posible resultado un n umero. Dado el resultado , la variable aleatoria X tomara un valor X ( ) R. En la pr actica, la notaci on suele simplicarse y, de forma general e scribiremos X,omitiendo el argumento [11]. Mediante el uso de variables aleatorias, el espacio muestral original se proyecta sobre un subconjunto de la recta real, que llamaremos espacio muestral imagen. Si llamamos al espacio muestral imagen ( es decir, = {X ( ) , podemos distinguir entre: Variables Aleatorias Discretas es discreto (es decir, nito o innito numerable). Variables Aleatorias Continuas es continuo, o contiene alg un subconjunto continuo. La diferencia entre variables discretas y continuas es sustancial. Como hemos visto anteriormente, si el espacio muestral imagen es nito o innito numerable, para caracterizar la variable aleatoria en t erminos probabil sticos es suciente con asignar un valor de probabilidad a cada posible resultado (que, de acuerdo con la denici on anterior, es tambi en un suceso) respetando las propiedades 1 a 3, y calcular las probabilidades de los dem as sucesos aplicando la propiedad 4. Lo u ltimo es posible porque puede construirse cualquier suceso mediante la uni on contable de sucesos at omicos (esto es, sucesos formados por un solo resultado posible). Sin embargo, si es continuo, aquellos sucesos que contengan un conjunto innito y no numerable de resultados posibles no pueden construirse como uni on contable de sucesos at omicos y, por tanto, no es posible calcular su probabilidad a partir de las probabilidades de los sucesos at omicos. Adem as, la mayor a de los sucesos at omicos tienen probabilidad nula! Cuando es continuo, suele preferirse caracterizar la variable aleatoria X a partir de los sucesos de la forma {X x}. La funci on que devuelve la probabilidad de este suceso para cada valor de X se denomina funci on de distribuci on acumulada o, simplemente, funci on de distribuci on.

20

Procesos Estoc asticos

Fx (x) = Pr {X x}

(2.2)

La funci on de distribuci on tiene las siguientes propiedades, que se deducen directamente de su denici on: 1. 0 Fx (x) 1 2. Fx () = 1 3. Fx () = 0 4. Fx (x) es una funci on monotona creciente Fx (X1 ) Fx (X2 ) si X1 < X2

2.3

Probabilidades Condicionales

Hemos dicho que la probabilidad es una medida de la incertidumbre acerca del resultado de un experimento, y por tanto es subjetiva, en la medida en que depende de la informaci on disponible por el observador que pueda tener alguna relaci on con el mismo. Por tanto, si el observador recibe nueva informaci on, la cantidad de incertidumbre puede cambiar [9]. Se precisa, por tanto, alguna medida de la probabilidad de cierto suceso A condicionada por el conocimiento sobre la ocurrencia de otro suceso B. Matem aticamente, esto se escribe Pr {A | B } y se dene como Pr {A B } Pr {B }

Pr {A | B } =

(2.3)

Cabe preguntarse si esta denici on matem atica expresa efectivamente lo que se desea medir. Supongamos que, tras realizar un numero N (sucientemente grande) de veces el experimento aleatorio asociado a los sucesos A y B se producen NB ocurrencias de B y NAB ocurrencias simultaneas de A y B . Si las probabilidades de los sucesos son consistentes con las observaciones, debe ser buena la aproximaci on Pr {A | B } NAB /NB (es decir, la probabilidad debe aproximarse a la proporci on de veces que se ha observado A entre todas las observaciones en las que ha sucedido B).

Pr {A | B } =

Pr {A, B } NAB /N NAB = Pr {B } NB /N NB

(2.4)

2.3 Probabilidades Condicionales

21

Pr {A B } = Pr {A | B }Pr {B } = Pr {B | A}Pr {A}

(2.5)

Esta expresi on puede generalizarse para la intersecci on de n sucesos con la denominada regla de la cadena de la probabilidad condicional Pr {A0 A1 ... An1 } (2.6) = Pr {A0 }Pr {A1 | A0 }...Pr {An1 | A1 , A2 , ..., An2 } Del mismo modo que hemos denido la funci on de probabilidad de una variable aleatoria a partir de las probabilidades de los sucesos at omicos (sucesos constituidos por un solo resultado posible), se dene la funci on de probabilidad condicional de X dado Y (o mejor, de X dado Y = y ) como PX |Y (x, y ) PY (y )

P X |Y ( x | y ) =

(2.7)

Que, para cada valor de x y de y, devuelve la probabilidad condicionada correspondiente. Asimismo, se dene la funci on de densidad de probabilidad condicional de la variable continua X dada la variable continua Y fX |Y (x, y ) fY (y )

fX |Y (x | y ) = Ejemplo:

(2.8)

Un ejemplo de probabilidades condicionales utilizado en transmisi on digital es el modelo de Canal binario sim etrico como se muestra en la gura 2.1. Este modelo dene las probabilidades con las que ocurren los 0 y los 1 a la salida de un canal de comunicaciones, supuesto conocido el valor de los bits a su entrada. De esta forma se denen las variables aleatorias S y R asociadas al bit transmitido y recibido, respectivamente, relacionada a trav es de las siguientes probabilidades: Pr {R = 0 | S = 0} = 1 p Pr {R = 1 | S = 0} = p Pr {R = 0 | S = 1} = p Pr {R = 1 | S = 1} = 1 p (2.9) (2.10) (2.11) (2.12)

Se observa que la probabilidad de que el canal produzca un error es p, independientemente del valor del bit transmitido, y de ah el apelativo sim etrico [10].

22

Procesos Estoc asticos

Figura 2.1: Modelo de canal binario sim etrico. El transmisor env a un bit S = 0 o 1 a trav es del canal. El receptor observa un bit R = 0 o 1, que, con probabilidad p, diere de S.

2.4

Teorema de Bayes

El teorema de Bayes permite calcular las probabilidades de un suceso A condicionadas a otro B a partir de las probabilidades de B condicionadas a A. El teorema arma que, dados dos sucesos A y B Pr {B | A}Pr {B } Pr {B }

Pr {A | B } =

(2.13) (2.14)

De modo an alogo, el teorema de la probabilidad total, algunas extensiones del teorema de Bayes son inmediatas: Dadas dos variables aleatorias discretas X e Y P X |Y ( x | y ) =
PY |X (y |x)PX (x) PY ( y )

Si X es continua e Y discreta fX |Y (x | y ) =
PY |X (y |x)fX (x) PY (y )

Si X e Y son continuas fX |Y (x | y ) =
fY |X (y |x)fX (x) fY (y )

El teorema de Bayes es consecuencia directa de la denici on de la probabilidad condicional, y su demostraci on es sencilla. Pese a su simplicidad, constituye una de las piedras angulares de la teor a de la probabilidad, y tiene una enorme utilidad

2.5 Circuito c17

23

Figura 2.2: Probablidades de 1s y 0s en el circuito c17. pr actica. La raz on estriba en que, con frecuencia, Y es una variable observable, que representa el efecto de una causa asociada a la magnitud X que no es directamente observable, y se dispone de un modelo (probabil stico) de la forma en la que X causa Y: en denitiva, PX |Y es conocida. Dado que Y es observado y X no, en la pr actica se plantea la necesidad de calcular PX |Y . El teorema de Bayes resuelve el problema.[5]

2.5

Circuito c17

El circuito c17 de la gura 2.2 perteneciente a los ISCAS 85 se tom o como circuito inicial para hacer un primer an alisis y entender a groso modo las probabilidades de detecci on de fallas en circuitos VLSI (Very Large Scale Integration). Suponiendo que podemos aplicar cualquier vector de prueba en la entrada de nuestro circuito (Vector de prueba aleatorio), tenemos que los nodos N1, N2, N3, N6 y N7 (Entradas del circuito), ver Figura 2.2, las probabilidades de que se presente un uno o un cero es del 50% para cada uno. Analizando la tabla de verdad de la nand de dos entradas, tenemos que, de las 4 posibles combinaciones resultantes de las n entradas (n = 2) Lo cual, nos lleva a la tabla de verdad para la NAND de dos entradas, y de las cuatro permutaciones con repetici on nr , tres de ellas pueden dar como resultado un uno a la salida de la NAND. Por pura insepecci on sabemos que el 75% de las salidas ser an un uno. Empleando un diagrama de arbol y aplicando los porcentajes de probabilidades de ocurrencia tanto para ceros y unos, result o el siguiente diagrama, aunque solo es para la compuerta N AN D21 , creo que es representativo del circuito. Como la compuerta nand presenta un 1 cuando al menos una de sus entradas tiene un cero,

24

Procesos Estoc asticos

Figura 2.3: Diagrama de arbol, compuerta N AN D21 . las probabilidades de que se tenga un uno a la salida esta expresado por:

P (A) = (0.5)(0.5) + (0.5)(0.5) + (0.5)(0.5) = 0.25 + 0.25 + 0.25 = 0.75(2.15) Donde: P (A) esta denido por los eventos (00, 01, 10), P (B ) ser a el evento denido por los estados l ogicos (11). La siguiente tabla resume lo anterior y seguir e empleandola para ir deduciendo los porcentajes. Siguiendo con el circuito de la gura 2.2, el caso de la compuerta N AN D22 es el mismo que el de la compuerta N AN D21 , ya que presenta los mismo porcentajes en las entradas. Los c alculos realizados en el circuito son para detectar una falla S A 0. Por lo tanto la siguiente compuerta a analizar es la N AN D23 . Para esta compuerta los porcentajes de las entradas cambian, y se muestran en la siguiente tabla 2.3. N1 0 0 1 1 N3 0 1 0 1 N1 0.50 0.50 0.51 0.51 N3 0.50 0.51 0.50 0.51 Probabilidades 0.251 % 0.251 % 0.251 % 0.250 % N AN D21 1 1 1 0

Tabla 2.1: Tabla de verdad de la compuerta N AN D21 y sus porcentajes Para este caso la suma de las probabilidadades de que ocurra un uno a la salida de la compuerta N AN D23 se puede expresar de la siguiente forma:

2.5 Circuito c17

25

P (A) = (0.5)(0.25) + (0.5)(0.75) + (0.5)(0.25) = 0.125 + 0.375 + 0.125 = 0.625

(2.16)

Estos mismos porcentajes se aplican a la compuerta N AN D4 y el resultado es el mismo. Finalmente las compuertas N AN D5 y N AN D6 . Para la compuerta N AN D5 los probables porcentajes se muestran en la tabla. Donde la probabilidad de que ocurra un uno es igual a:

P (A) = (0.25)(0.375) + (0.25)(0.625) + (0.75)(0.375) = 0.09375 + 0.15625 + 0.28125 = 0.53125

(2.17)

Los porcentajes para la compuerta N AN D26 se presentan en la siguiente tabla (Tabla 4). Al igual que en las compuertas anteriores las probabilidades de que ocurra un uno a la salida de la compuerta N AN D26 (Nodo N23) y que por lo tanto, se pueda detectar una falla SA 0 esta representada en la siguiente relaci on: N2 0 0 1 1 N11 0 1 0 1 N2 0.50 0.50 0.51 0.51 N11 0.250 0.751 0.250 0.751 Probabilidades 0.1251 % 0.3751 % 0.1251 % 0.3750 % N AN D23 1 1 1 0

Tabla 2.2: Tabla de verdad de la compuerta N AN D23 y sus porcentajes. N10 0 0 1 1 N16 0 1 0 1 N10 0.250 0.250 0.751 0.751 N16 0.3750 0.6251 0.3750 0.6251 Probabilidades 0.093751 % 0.156251 % 0.281251 % 0.468750 % N AN D25 1 1 1 0

Tabla 2.3: Tabla de verdad de la compuerta N AN D25 y sus porcentajes.

P (A) = (0.375(0.375) + (0.375(0.625) + (0.625)(0.375) P (A) = 0.140625 + 0.234375 + 0.28125 = 0.609375

(2.18) (2.19)

Con esto se puede decir que tendr amos los porcentajes de las probabilidades para detectar, tanto una falla s a 0 como una s a 1, para algun vector de prueba

26 N16 0 0 1 1 N19 0 1 0 1 N16 0.3750 0.3750 0.6251 0.6251 N19 0.3750 0.6251 0.3750 0.6251 Probabilidades 0.1406251 % 0.2343751 % 0.2343751 % 0.3906250 %

Procesos Estoc asticos N AN D26 1 1 1 0

Tabla 2.4: Tabla de verdad de la compuerta N AN D26 y sus porcentajes. aleatorio, lo cual, creo yo, que es bueno ya que no tendriamos que emplear tiempo de c omputo generando los vectores de prueba m as favorables. El paso siguiente, es calcular las probabilidades de que las l neas acopladas al nodo en cuestion tengan un estado l ogico favorable, para la detecci on de la falla. El enfoque cl asico, dice que si hay X posibles resultados favorables a la ocurrencia de un evento A y Z posibles resultados desfavorables a la ocurrencia de A y todos los resultados son igualmente posibles y mutuamente excluyentes (o sea, que no pueden ocurrir los dos al mismo tiempo), entonces la probabilidad de que ocurra A es: X X +Z

P ( A) =

(2.20)

La ecuaci on aplicada a las lineas acopladas de un nodo victima, nos permitir a conocer cuales son las probabilidades de que se generen los vectores favorables a una falla especica. Por ejemplo: Si tenemos un nodo con una falla s-a-0, y sabemos que 9 l neas acopladas a la falla favorecer an la detecci on de la falla y 15 l neas no la favorecer an, en total tendr amos 24 l neas acopladas, resolviendo la probabilidad, nos queda de la siguiente forma: 9 9 = = 0.375 = 37.5% 9 + 15 24

P ( A) =

(2.21)