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\).