¿Existe la posibilidad de elegir equitativamente entre tres elementos cuando cada elección sólo puede tener 2 opciones?

Question

Mi mujer y yo a menudo no sabemos qué DVD ver. Si tenemos dos opciones tenemos una solución sencilla, pongo un DVD en una mano detrás de mi espalda y el otro DVD en la otra mano. Ella elegirá una mano al azar y el DVD que tengo en esa mano será el que hay que ver.

Este procedimiento es fácil de ampliar a cualquier potencia de 2. Si tenemos 4 DVD, sostengo 2 en una mano y 2 en la otra. Cuando se elige un par de DVD, los reparto a dos manos y ella vuelve a elegir.

La cuestión es qué podemos hacer cuando tenemos 3 DVD. Las suposiciones que hacemos son:

• No soy imparcial. Si puedo influir de algún modo en el resultado, lo intentaré.
• En realidad, mi mujer elige cada vez un lado al azar, independientemente de lo que haya elegido antes.
• No tengo otro sitio donde esconder los DVD, así que todos están a la vista o en una de las dos manos.

Como requisito tenemos que debe ser un procedimiento con un número predeterminado de pasos. Ni más, ni menos. Si esto no es posible, una solución que garantice terminar con un upperbound, esta es una buena segunda opción. Por supuesto, ¡el DVD que elijamos debe ser realmente aleatorio!

Answer 1

Buena pregunta. En primer lugar, no hay ninguna solución que siempre tome un número fijo de pasos cada vez: después de n ensayos aleatorios independientes (elegir una mano), hay 2 n opciones posibles, y 2 n nunca es divisible por 3. (Equivalentemente: 1/3 no tiene una representación terminal en base 2.)

Pero se puede llegar a soluciones que terminen dentro de un número fijo de pasos con alta probabilidad. Tenga en cuenta que necesita al menos 2 ensayos, ya que log ₂ (3) > 1. He aquí un método sencillo:

1. Sujeta 2 DVD en una mano y 1 DVD en la otra (tu mujer no sabe cuál es cuál).

2. Si se elige la mano con 2 DVD: jugarlos uno contra otro.
   Si se elige el DVD 1, se juega contra una mano vacía.

Cada uno de los 3 DVD tiene la misma probabilidad 1/4 de ser elegido, y con probabilidad 1/4, hay que repetir desde cero. Esta solución requiere 2 intentos con probabilidad 3/4, 4 intentos con probabilidad (1/4)(3/4), 6 intentos con probabilidad (1/4) 2 (3/4) y así sucesivamente, por lo que toma un número esperado de 8/3 (≈ 2,66) ensayos. (Véase distribución geométrica .)

Creo que esto es óptimo (¿famosas últimas palabras?) si sólo tienes que elegir entre 3 DVD una vez. Probablemente, si va a elegir entre 3 DVD muchas veces, puede hacerlo mejor a largo plazo (amortizado) y alcanzar el límite inferior de log ₂ 3 ≈ 1,58 pruebas de media, "almacenando en caché" algunas elecciones aleatorias de la última vez. (¿Pero las recordarás? :-)) Al menos se puede hacer algo parecido al generar números aleatorios (véase también este hilo de Stack Overflow ligeramente relacionado ), pero en este caso con complicaciones de equidad teóricas del juego no estoy tan seguro.

Answer 2

En 1976, Knuth y Yao (No he podido encontrar una buena referencia en Internet.) Considera el siguiente problema: Tienes una moneda justa y debes escribir un algoritmo que dé como resultado 1 con probabilidad p1, dé como resultado 2 con probabilidad p2, ..., y dé como resultado n con probabilidad pn. (p1+p2+...+pn=1) Observe que cualquier posible algoritmo puede describirse en términos de ciertos árboles binarios (posiblemente infinitos): Un nodo que tiene dos hijos significa "lanza una moneda y elige uno de los hijos según el resultado"; una hoja está etiquetada con uno de los números 1, 2, ..., n y significa "da salida a ese número".

Un árbol óptimo que resuelve el problema tiene una hoja k en el nivel m si y sólo si el bit m-ésimo de pk es 1. En caso contrario hay cero hojas de este tipo.

"Óptimo" significa aquí no sólo que el tiempo medio de ejecución es el mejor posible, sino la garantía más sólida de que la probabilidad de ejecutar más de m pasos no es peor que la de cualquier otro algoritmo que resuelva el problema correctamente.

En tu caso, p1=p2=p3=0,01010101... El dígito justo antes del punto corresponde a la raíz (nivel 0) y los dígitos siguientes a los niveles siguientes. Por tanto, un árbol que no tiene hojas en los niveles 0 y 1, tiene hojas (1, 2 y 3) en el nivel 2, no tiene hojas en el nivel 3, ... es óptimo. Esta es exactamente la solución dada por ShreevatsaR. Un árbol así es bastante fácil de encontrar una vez que se sabe qué hojas hay que poner en cada nivel.

Como otro ejemplo, si p1=...=p6=1/6=0,00101010101..., entonces deberías tener hojas (una de cada 1, 2, 3, 4, 5, 6) en los niveles 3, 5, 7, y así sucesivamente. Si dibujas un árbol simétrico que obedezca esto encontrarás cómo elegir un DVD de 6: Primero coge tres con cada mano, luego haz lo que dijo ShreevatsaR para tres. También tienes garantizado que es óptimo.

Ahora puedes burlarte de mí y de mis amigos por utilizar un algoritmo subóptimo para asignar habitaciones de hotel .

Answer 3

No existe ningún procedimiento que limite el número de pasos. Aquí está la prueba. Supongamos que existe un procedimiento con no más de $N$ pasos. En cada paso se generan básicamente enteros aleatorios entre $1$ y $2$ . Considere todas las secuencias posibles de no más de $N$ números generados. Cada una de estas secuencias tiene una probabilidad de la forma $\frac{x}{2^N}$ .

Consideremos las secuencias para las que el procedimiento dice "1" (el resultado es igual a $1$ ). La suma de sus probabilidades es $\frac{x_1}{2_N}$ . También debe ser igual a $\frac{1}{3}$ . Pero $\frac{x_1}{2_N}$ no puede ser igual a $\frac{1}{3}$ .

Answer 4

Responderé al pie de la letra a su pregunta. DVDs A, B, C.

1. Mantén A y B detrás de la espalda. Esposa elige (diga A). Suelta B.
2. Mantenga elegido (A) y C detrás de la espalda. Esposa elige.
3. Si es la otra (C), a) entonces sujeta a C y B por detrás. La mujer elige (como siempre): Voilà. b) si no, a la cama.

Se cumplen todas las condiciones. 3 pasos.

Answer 5

Aquí hay una tabla de n 2^n m 3^m y p(fail) donde 3^m es el mayor valor < 2^m. La primera fila representa el algoritmo estándar.

Si te interesa el rendimiento en el peor de los casos, la fila n=65 sugiere una posibilidad interesante: tomar un número aleatorio de 65 bits, rechazarlo si es demasiado grande (1,14% de los casos) y, a continuación, utilizar div/mod repetidamente para obtener 41 opciones de 1 en 3. Este algoritmo es un 99% eficiente con la entropía de entrada frente al 59% del algoritmo estándar.

En hardware de 64 bits se pueden dar dos casos dependiendo de que el bit 65 sea 0 o 1.

2 4 1 3 25.00
3 8 1 3 62.50
4 16 2 9 43.75
5 32 3 27 15.62
6 64 3 27 57.81
7 128 4 81 36.72
8 256 5 243 5.08
9 512 5 243 52.54
10 1024 6 729 28.81
11 2048 6 729 64.40
12 4096 7 2187 46.61
13 8192 8 6561 19.91
14 16384 8 6561 59.95
15 32768 9 19683 39.93
16 65536 10 59049 9.90
17 131072 10 59049 54.95
18 262144 11 177147 32.42
19 524288 11 177147 66.21
20 1048576 12 531441 49.32
21 2097152 13 1594323 23.98
22 4194304 13 1594323 61.99
23 8388608 14 4782969 42.98
24 16777216 15 14348907 14.47
25 33554432 15 14348907 57.24
26 67108864 16 43046721 35.86
27 134217728 17 129140163 3.78
28 268435456 17 129140163 51.89
29 536870912 18 387420489 27.84
30 1073741824 18 387420489 63.92
31 2147483648 19 1162261467 45.88
32 4294967296 20 3486784401 18.82
33 8589934592 20 3486784401 59.41
34 17179869184 21 10460353203 39.11
35 34359738368 22 31381059609 8.67
36 68719476736 22 31381059609 54.33
37 137438953472 23 94143178827 31.50
38 274877906944 23 94143178827 65.75
39 549755813888 24 282429536481 48.63
40 1099511627776 25 847288609443 22.94
41 2199023255552 25 847288609443 61.47
42 4398046511104 26 2541865828329 42.20
43 8796093022208 27 7625597484987 13.31
44 17592186044416 27 7625597484987 56.65
45 35184372088832 28 22876792454961 34.98
46 70368744177664 29 68630377364883 2.47
47 140737488355328 29 68630377364883 51.24
48 281474976710656 30 205891132094649 26.85
49 562949953421312 30 205891132094649 63.43
50 1125899906842624 31 617673396283947 45.14
51 2251799813685248 32 1853020188851841 17.71
52 4503599627370496 32 1853020188851841 58.85
53 9007199254740992 33 5559060566555523 38.28
54 18014398509481984 34 16677181699666569 7.42
55 36028797018963968 34 16677181699666569 53.71
56 72057594037927936 35 50031545098999707 30.57
57 144115188075855872 35 50031545098999707 65.28
58 288230376151711744 36 150094635296999121 47.93
59 576460752303423488 37 450283905890997363 21.89
60 1152921504606846976 37 450283905890997363 60.94
61 2305843009213693952 38 1350851717672992089 41.42
62 4611686018427387904 39 4052555153018976267 12.12
63 9223372036854775808 39 4052555153018976267 56.06
64 18446744073709551616 40 12157665459056928801 34.09
65 36893488147419103232 41 36472996377170786403 1.14 ***
66 73786976294838206464 41 36472996377170786403 50.57
67 147573952589676412928 42 109418989131512359209 25.85
68 295147905179352825856 42 109418989131512359209 62.93
69 590295810358705651712 43 328256967394537077627 44.39
70 1180591620717411303424 44 984770902183611232881 16.59
71 2361183241434822606848 44 984770902183611232881 58.29
72 4722366482869645213696 45 2954312706550833698643 37.44
73 9444732965739290427392 46 8862938119652501095929 6.16
74 18889465931478580854784 46 8862938119652501095929 53.08
75 37778931862957161709568 47 26588814358957503287787 29.62
76 75557863725914323419136 47 26588814358957503287787 64.81
77 151115727451828646838272 48 79766443076872509863361 47.21
78 302231454903657293676544 49 239299329230617529590083 20.82
79 604462909807314587353088 49 239299329230617529590083 60.41
80 1208925819614629174706176 50 717897987691852588770249 40.62
81 2417851639229258349412352 51 2153693963075557766310747 10.93
82 4835703278458516698824704 51 2153693963075557766310747 55.46
83 9671406556917033397649408 52 6461081889226673298932241 33.19
84 19342813113834066795298816 52 6461081889226673298932241 66.60
85 38685626227668133590597632 53 19383245667680019896796723 49.90
86 77371252455336267181195264 54 58149737003040059690390169 24.84
87 154742504910672534362390528 54 58149737003040059690390169 62.42
88 309485009821345068724781056 55 174449211009120179071170507 43.63
89 618970019642690137449562112 56 523347633027360537213511521 15.45
90 1237940039285380274899124224 56 523347633027360537213511521 57.72
91 2475880078570760549798248448 57 1570042899082081611640534563 36.59
92 4951760157141521099596496896 58 4710128697246244834921603689 4.88
93 9903520314283042199192993792 58 4710128697246244834921603689 52.44
94 19807040628566084398385987584 59 14130386091738734504764811067 28.66
95 39614081257132168796771975168 59 14130386091738734504764811067 64.33
96 79228162514264337593543950336 60 42391158275216203514294433201 46.49
97 158456325028528675187087900672 61 127173474825648610542883299603 19.74
98 316912650057057350374175801344 61 127173474825648610542883299603 59.87
99 633825300114114700748351602688 62 381520424476945831628649898809 39.81
100 1267650600228229401496703205376 63 1144561273430837494885949696427 9.71
101 2535301200456458802993406410752 63 1144561273430837494885949696427 54.86
102 5070602400912917605986812821504 64 3433683820292512484657849089281 32.28
103 10141204801825835211973625643008 64 3433683820292512484657849089281 66.14
104 20282409603651670423947251286016 65 10301051460877537453973547267843 49.21
105 40564819207303340847894502572032 66 30903154382632612361920641803529 23.82
106 81129638414606681695789005144064 66 30903154382632612361920641803529 61.91
107 162259276829213363391578010288128 67 92709463147897837085761925410587 42.86
108 324518553658426726783156020576256 68 278128389443693511257285776231761 14.30
109 649037107316853453566312041152512 68 278128389443693511257285776231761 57.15
110 1298074214633706907132624082305024 69 834385168331080533771857328695283 35.72
111 2596148429267413814265248164610048 70 2503155504993241601315571986085849 3.58
112 5192296858534827628530496329220096 70 2503155504993241601315571986085849 51.79
113 10384593717069655257060992658440192 71 7509466514979724803946715958257547 27.69
114 20769187434139310514121985316880384 71 7509466514979724803946715958257547 63.84
115 41538374868278621028243970633760768 72 22528399544939174411840147874772641 45.76
116 83076749736557242056487941267521536 73 67585198634817523235520443624317923 18.65
117 166153499473114484112975882535043072 73 67585198634817523235520443624317923 59.32
118 332306998946228968225951765070086144 74 202755595904452569706561330872953769 38.99
119 664613997892457936451903530140172288 75 608266787713357709119683992618861307 8.48
120 1329227995784915872903807060280344576 75 608266787713357709119683992618861307 54.24
121 2658455991569831745807614120560689152 76 1824800363140073127359051977856583921 31.36
122 5316911983139663491615228241121378304 76 1824800363140073127359051977856583921 65.68
123 10633823966279326983230456482242756608 77 5474401089420219382077155933569751763 48.52
124 21267647932558653966460912964485513216 78 16423203268260658146231467800709255289 22.78
125 42535295865117307932921825928971026432 78 16423203268260658146231467800709255289 61.39
126 85070591730234615865843651857942052864 79 49269609804781974438694403402127765867 42.08
127 170141183460469231731687303715884105728 80 147808829414345923316083210206383297601 13.13