Comprendre la dérivation dans Robbins (1952)

Question

J'essayais de lire l'article de 1952 d'Herbert Robbins "Some Aspects of the Sequential Design of Experiments" ( ici ) et je suis vraiment, de manière agaçante, bloqué sur la formule (2). Je ne peux pas, pour la vie de moi, comprendre comment on montre dans le cadre décrit que$$ p_{i+1} = (\alpha + \beta - 1)p_i + (\alpha + \beta - 2\alpha\beta). $$La section environnante est très lisible, mais pour économiser l'effort du lecteur :$\alpha$et$\beta$sont les probabilités de deux pièces$A$et$B$, respectivement, à venir en tête ;$p_i$est la probabilité de retourner face sur flip$i$. Il y a une récompense d'un dollar pour chaque tête, donc l'objectif est d'équilibrer l'échantillonnage de$\alpha$et$\beta$avec l'exploitation de la monnaie correspondant à$\max(\alpha, \beta)$. Robbins discute d'une "règle"$R_1$(politique, dans le langage de la littérature sur les bandits d'aujourd'hui) qui stipule de changer de pièces lorsque la pièce actuelle sort sur pile et de s'en tenir à la pièce actuelle lorsqu'elle tombe sur face. Dans ce contexte, je pense comprendre le deuxième terme :$$\alpha + \beta - 2\alpha\beta = (1-\alpha)\beta + (1-\beta)\alpha. $$C'est la probabilité d'avoir pile au flip$i$, échangeant des pièces comme la règle l'exige et obtenant une tête sur la pièce opposée à la fois$i+1$. Mais je ne peux tout simplement pas comprendre le premier mandat. Robbins contraint que$0 < \alpha, \beta < 1$, pour que$|\alpha + \beta - 1| < 1$, cependant le premier terme ne contient pas la valeur absolue. Je ne comprends pas comment nous nous assurons que$p_{i+1}$est une probabilité si le premier terme peut être négatif. Plus important encore, je ne peux tout simplement pas comprendre quel événement$(\alpha + \beta - 1)$est censé représenter. Je n'ai pas été en mesure de produire une dérivation qui l'explique de manière satisfaisante. Une explication intuitive ou une dérivation serait très utile (je ne soupçonne pas que la dérivation soit longue, il me manque clairement quelque chose).

Merci beaucoup!

Answer 1

J'ai eu du mal avec l'expression ces derniers jours, très frustrant mais finalement gratifiant car je pense que la dérivation ci-dessous montre comment obtenir la récursivité. Malheureusement, je n'ai pas d'explication intuitive pour la récursivité...

Définir les événements$H_i := \text{"heads in flip } i$",$A_i := \text{"coin $UN$ is used in flip $je$"}$et$B_i := \text{"coin $B$ is used in flip $je$"}$. Ensuite, vous obtenez ce qui suit :\begin{align*} p_{i+1} &= \mathbb{P}(H_{i+1}) \\ &= \mathbb{P}(H_{i+1} | H_i, A_i)\mathbb{P}(H_i|A_i)\mathbb{P}(A_i) + \mathbb{P}(H_{i+1} | H_i^c, A_i)\mathbb{P}(H_i^c|A_i)\mathbb{P}(A_i)\\ & \enspace \enspace \enspace \enspace + \mathbb{P}(H_{i+1} | H_i, B_i)\mathbb{P}(H_i|B_i)\mathbb{P}(B_i) + \mathbb{P}(H_{i+1} | H_i^c, B_i)\mathbb{P}(H_i^c|B_i)\mathbb{P}(B_i) \\ &= \alpha^2\mathbb{P}(A_i) + \beta (1-\alpha)\mathbb{P}(A_i) + \beta^2\mathbb{P}(B_i) + \alpha(1-\beta)\mathbb{P}(B_i) \\ &= \alpha^2\mathbb{P}(A_i) + \beta^2\mathbb{P}(B_i) + \beta(1-\alpha) + \alpha(1-\beta) -\mathbb{P}(B_i)\beta(1-\alpha) - \mathbb{P}(A_i)\alpha(1-\beta)\\ &= \alpha\mathbb{P}(A_i)(\alpha + \beta - 1) + \beta\mathbb{P}(B_i)(\alpha + \beta - 1) + \beta(1-\alpha) + \alpha(1-\beta) \\ &= (\alpha + \beta - 1)(\alpha \mathbb{P}(A_i) + \beta \mathbb{P}(B_i)) + \beta(1-\alpha) + \alpha(1-\beta) \\ &= (\alpha + \beta - 1)p_i + \beta(1-\alpha) + \alpha(1-\beta) \end{align*}

Answer 2

delivery101 a merveilleusement répondu à la question initiale. Je voulais également contribuer à l'explication de l'équation suivante dans l'article, car bien que l'on puisse l'accepter comme la conséquence de l'algèbre comme Eq. (2), la justification est utile et j'ai déjà fait le travail fastidieux.

L'équation suivante indique sans démontrer pourquoi la relation de récursivité justifiée dans la réponse acceptée implique ce qui suit :$$ p_i = (\alpha + \beta - 1)^{i-1}\Big[p_1 - \frac{\alpha + \beta - 2\alpha\beta}{2 - (\alpha + \beta)}\Big] + \frac{\alpha + \beta - 2\alpha\beta}{2 - (\alpha + \beta)}.$$

En assimilant cela à l'Eq. (2) de l'article, j'ai observé que

$$ (\alpha + \beta - 1)p_1 - \frac{(\alpha + \beta - 1)(\alpha + \beta - 2\alpha\beta)}{2 - (\alpha + \beta)} + \frac{(\alpha + \beta - 2\alpha\beta)}{2-(\alpha + \beta)} = (\alpha + \beta - 1)p_1 + (\alpha + \beta - 2\alpha\beta)$$ $$\implies \frac{1-(\alpha + \beta - 1)}{2 - (\alpha + \beta)}(\alpha + \beta - 2\alpha\beta) = \frac{2 - (\alpha + \beta)}{2 - (\alpha + \beta)}(\alpha + \beta - 2\alpha\beta) = \alpha + \beta - 2\alpha\beta$$

qui démontre la substitution de clé.

Laisser$\pi = \alpha + \beta - 2\alpha\beta$, laisser$\lambda = \alpha + \beta - 1$, et laissez$\phi = \frac{\alpha + \beta - 2\alpha\beta}{2 - (\alpha + \beta)}$. Essayons de dévoiler$p_3$selon l'équation (2). On voit ça

\begin{align} p_4 &= \lambda[\lambda[\lambda p_1 + \pi] + \pi] + \pi \\ &= \lambda[\lambda[\lambda p_1 + \phi - \lambda\phi] + \pi] + \pi \\ &= \lambda[\lambda[\lambda p_1 + \phi - \lambda\phi] + \phi - \lambda\phi] + \pi \\ &= \lambda[\lambda[\lambda p_1 + \phi - \lambda\phi] + \phi - \lambda\phi] + \phi - \lambda\phi \\ &= \lambda[\lambda^2[p_1 - \phi] + \lambda\phi + \phi - \lambda\phi] + \phi - \lambda\phi \\ &= \lambda[\lambda^2[p_1 - \phi] + \phi] + \phi - \lambda\phi \\ &= \lambda^3[p_1 - \phi] + \lambda\phi + \phi - \lambda\phi \\ &= \lambda^3[p_1 - \phi] + \phi \end{align}

qui se généralise à l'équation (3) comme prévu.