Número esperado de ensayos hasta el éxito

Considere el siguiente rompecabezas famoso. 
En un país, todas las familias quieren un niño. Siguen teniendo bebés hasta que nace un niño. ¿Cuál es la proporción esperada de niños y niñas en el país?  
Este acertijo se puede resolver fácilmente si conocemos el siguiente resultado interesante en probabilidad y expectativa. 
Si la probabilidad de éxito es p en cada intento, entonces el número esperado de intentos hasta el éxito es 1/p  
Prueba: Sea R una variable aleatoria que indica el número de intentos hasta el éxito. 
 

The expected value of R is sum of following infinite series
E[R] = 1*p + 2*(1-p)*p + 3*(1-p)2*p + 4*(1-p)3*p + ........ 

Taking 'p' out
E[R] = p[1 + 2*(1-p) + 3*(1-p)2 + 4*(1-p)3 + .......] ---->(1)

Multiplying both sides with '(1-p)' and subtracting 
(1-p)*E[R] = p[1*(1-p) + 2*(1-p)2 + 3*(1-p)3 + .......] --->(2)

Subtracting (2) from (1), we get

p*E[R] = p[1 + (1-p) + (1-p)2 + (1-p)3 + ........] 

Cancelling p from both sides
E[R] = [1 + (1-p) + (1-p)2 + (1-p)3 + ........] 

Above is an  infinite geometric  progression with ratio (1-p). 
Since (1-p) is less than, we can apply sum formula.
  E[R] = 1/[1 - (1-p)]
       = 1/p

Solución del acertijo de proporción de niños/niñas: 
usemos el resultado anterior para resolver el acertijo. En el acertijo dado, la probabilidad de éxito en cada prueba es 1/2 (suponiendo que las niñas y los niños tienen la misma probabilidad). 
 

Let p be probability of having a baby boy.
Number of kids until a baby boy is born = 1/p 
                                        = 1/(1/2)
                                        = 2 
Since expected number of kids in a family is 2,
ratio of boys and girls is 50:50. 

Analicemos otro problema que utiliza el resultado anterior. 
Coleccionista de cupones Problema 1: 
Suponga que hay n tipos de cupones en una lotería y cada lote contiene un cupón (con probabilidad 1 = n cada uno). Cuántos lotes hay que comprar (en expectativa) hasta que tengamos al menos un cupón de cada tipo.  
La solución de este problema también se basa en el resultado anterior. 
Sea X _i el número de lotes comprados antes de cobrar el nuevo cupón i. 
Tenga en cuenta que X ₁ es 1 ya que el primer cupón siempre es un cupón nuevo (no cobrado antes). 
Sea ‘p’ la probabilidad de que se recoja el segundo cupón en la próxima compra. El valor de p es (n-1)/n. Entonces, el número de intentos necesarios antes de elegir el segundo cupón nuevo es 1/p, lo que significa n/(n-1). [Aquí es donde usamos el resultado anterior] 
De manera similar, la cantidad de intentos necesarios antes de que se recopile el tercer cupón nuevo es n/(n-2) 
 

Using Linearity of expectation, 
we can say that the total number of expected trials = 
                  1 + n/(n-1) + n/(n-2) + n/(n-3) + .... + n/2 + n/1
               = n[1/n + 1/(n-1) + 1/(n-2) + 1/(n-3) + ....+ 1/2 + 1/1]
               = n * Hn
Here Hn is n-th Harmonic number

Since Logn <= Hn <= Logn + 1, we need to buy around 
nLogn lots to collect all n coupons. 

Coleccionista de cupones Problema 2 : (Enfoque e implementación con un ejemplo):

Hay  N  elementos en una array. Al principio, se elige un elemento aleatorio. Después de que algún elemento haya terminado, el siguiente se elige al azar e independientemente de lo que se haya seleccionado antes. Encuentre las selecciones mínimas que se deben hacer hasta que cada elemento se seleccione al menos una vez.

Nota: La respuesta se considerará correcta si tiene un error absoluto o relativo inferior a  10^(-1) . Más formalmente, si la salida esperada es  A  y su salida es  B , su salida se considerará correcta si y solo si |A − B| ≤ 10−1 * máx{|A|, |B|, 1} .

Ejemplos:

Entrada: 1 
Salida: 1.0
Explicación: Solo hay un elemento y debe seleccionarse para que todos los elementos estén seleccionados.

Entrada: 2
Salida: 3.0
Explicación: Después de seleccionar el primer elemento, hay 1/2 posibilidad de terminar la array cada vez que se selecciona un nuevo elemento. Entonces, el número esperado de elementos seleccionados es 2/2 + 3/4 + 4/8… = 3.

Entrada: 3
Salida: 5.5
Explicación: Los elementos seleccionados son 3/1+3/2+3/3=5.5
 

 

Siga los pasos para resolver el problema:

1. Inicialice ans (número de intentos) a 0.
2. Recorra de 1 a N por i.
3. Agregue valores consecutivos de N / i a ans.
4. Devuelve ans como respuesta final.

A continuación se muestra la implementación del enfoque anterior:

//C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum selections
double minSelections(int& n){
   double ans = 0;
   for(int i = 1; i <= n; i++)
       ans += 1.0 * n / i;
         
   return ans;
}
 
// Driver's code
int main() {
int N = 3;
cout << fixed << setprecision(8) << minSelections(N);
return 0;
}

// JAVA program of th above approach
import java.util.*;
class GFG
{
 
// Function to find minimum selections
static double minSelections(int n){
   double ans = 0;
   for(int i = 1; i <= n; i++)
       ans += 1.0 * n / i;
          
   return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
    System.out.print(String.format("%.8f", minSelections(N)));
}
}
 
// This code is contributed by code_hunt.

// C# program of the above approach
 
using System;
 
class GFG {
 
    // Function to find minimum selections
    static double minSelections(int n)
    {
        double ans = 0;
        for (int i = 1; i <= n; i++)
            ans += 1.0 * n / i;
 
        return ans;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 3;
        Console.WriteLine(
            minSelections(N).ToString("0.00000000"));
    }
}
 
// This code is contributed by  phasing17

// JavaScript code for the above approach:
 
// Function to find minimum selections
function minSelections(n){
   let ans = 0;
   for(let i = 1; i <= n; i++)
       ans += 1.0 * n / i;
         
   return ans;
}
 
// Driver's code
let N = 3;
console.log(minSelections(N).toFixed(8));
 
 
// This code is contributed by phasing17

5.50000000

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Ejercicio: 
1) Se lanza un dado justo de 6 caras hasta que se ve un ‘5’ como resultado del lanzamiento de dados. ¿Cuál es el número esperado de lanzamientos? 
2) ¿Cuál es la proporción de niños y niñas en el acertijo anterior si la probabilidad de un bebé es 1/3? 
Referencia:  
http://www.cse.iitd.ac.in/~mohanty/col106/Resources/linearity_expectation.pdf  
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6- 042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-22-expectation-i/ 
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.