Wahrscheinlichkeit einer rationalen Nullstelle

Question

Seien $( \epsilon _{ 1} , \ldots , \epsilon _{ d - 1} )$ Bernoulli Variablen mit parameter $1 / 2$. Finden sie einen asymptotischen Ausdruck für
die Wahrscheinlichkeit $r _{ d}$, dass das Polynom
$\begin{aligned} X^{ d}+ \sum_{ i = 1}^{ d - 1} \epsilon _{ i} X^{ i}+ 1 \end{aligned}$
eine rationale Nullstelle hat. Sie sollen also eine Funktion $f( d)$ finden, mit
$\begin{aligned} f ( d)\sim p _{ d} \iff \lim_{d \to\infty} \frac{ f( d) }{ p _{ d} } = 1 .\end{aligned}$

Comments

Hinweis: Es gibt eine Bedingung, welche rationale Nullstellen eines Polynoms zu erfüllen haben. Das schränkt die Möglichkeiten ein.

Answer 1

$-1$ ist die einzige mögliche Nullstelle (vgl. Satz über ratinoale Nullstellen). Ist z.B. $d$ ungerade, so ist $-1$ eine Nullstelle von
$\begin{aligned} Q( X) = X ^{ d} + \sum_{ k = 1}^{ d - 1} \varepsilon _{ k} X^{ k}+ 1 \end{aligned}$
wenn genau gleich viele $\varepsilon _{ u}$ (für $u$ ungerade) wie $\varepsilon _{ g}$ (für $g$ gerade) der $\varepsilon _{ k}$ gleich eins sind.
Das ist also gleich der Anzahl an Bitstrings, die auf den geraden und ungeraden Positionen gleich viele Einsen haben, also
$\begin{aligned} \sum_{ k = 0}^{ ( d - 1) / 2} \binom{ ( d - 1) / 2}{ k} ^{ 2} = \binom{ d - 1}{ ( d - 1) /2} .\end{aligned}$
Ähnliches ergibt sich für $d$ gerade (asymptotisch wird es gleich sein).
Jetzt noch die Stirling-Approximation einsetzen, also
$\begin{aligned} \binom{ d - 1}{ ( d - 1) /2} = \frac{ ( d - 1)! }{ \left( \left( \frac{ d - 1}{ 2}\right)!\right)^{ 2} } \sim \frac{ \sqrt{ 2\pi ( d - 1) } \left( ( d - 1) / e\right)^{ d - 1}}{ \pi ( d - 1) ( ( d - 1) / ( 2 e) )^{ d - 1} } = 2^{ d - 1} \sqrt{ \frac{ 2}{ \pi ( d - 1) } } .\end{aligned}$
Nun ist also
$\begin{aligned} \mathbf{P}\left[ Q( -1) = 0\right] &= \sum_{ ( x_{ 1} , \ldots , x_{ d - 1} ) \in ( 0, 1)^{ d-1} } \mathbf{P}\left[ Q( -1) = 0 \mid \forall k\colon \varepsilon _{ k} = x_{ k} \right] \cdot \mathbf{P}\left[ \forall k\colon \varepsilon _{ k} = x_{ k} \right] \\ &\sim 2^{ d - 1} \sqrt{ \frac{ 2}{ \pi ( d - 1) } } \cdot \frac{1}{ 2^{ d - 1}} = \sqrt{ \frac{ 2}{ \pi ( d - 1) } } \end{aligned}$

Mit $(0, 1)^n$ meine ich hier die Menge aller Bitstrings der Länge $n$.