Zufällig eine Quadratzahl erwischen, die II.

12.12.2021, 14:18

Malcang

Zufällig eine Quadratzahl erwischen, die II.

Guten Tag zusammen, schönen Sonntag smile

Ich hatte vor einiger Zeit bereits einen ähnlichen Thread eröffnet, aber neue Erkenntnisse gewonnen. Bitte sehr es mir daher nach, dass ich einen weiteren Thread eröffne.
Die Aufgabe mutet vielleicht etwas seltsam an. Ich benötige dies für eine Ausarbeitung, daher kann ich einige Voraussetzungen angeben. Hier erstmal das "Spiel"

Gegeben sei eine natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ . Es wird nun eine zufällige Zahl $\begin{eqnarray*} m \end{eqnarray*}$ zwischen $\begin{eqnarray*} 1 \end{eqnarray*}$ und $\begin{eqnarray*} 2\cdot\sqrt{n} \end{eqnarray*}$ gewählt. Wenn diese eine Quadraztahl ist, stoppe. Wenn nicht, wähle $\begin{eqnarray*} m \end{eqnarray*}$ zufällig aus dem Intervall $\begin{eqnarray*} 2\cdot\sqrt{2n} \end{eqnarray*}$ und so weiter.
Das "Spiel" ist verloren, wenn in $\begin{eqnarray*} \lfloor\sqrt[3]{n}\rfloor \end{eqnarray*}$ Durchgängen kein Quadrat gefunden werden konnte.
Wie groß ist die Wahrscheinlichkeit zu gewinnen?

Weitere Voraussetzung:
Sei $\begin{eqnarray*} i \end{eqnarray*}$ der aktuell durchlaufene Durchgang. Gehe davon aus, dass $\begin{eqnarray*} i\cdot n \end{eqnarray*}$ keine Quadratzahl ist.
Außerdem ist die Wahl der zufälligen Zahlen jeweils unabhängig und gleichverteilt.

Mein Ansatz:
Es wird eine zufällige Zahl im Intervall $\begin{eqnarray*} [1, 2\sqrt{i\cdot n}) \end{eqnarray*}$ gewählt. Da $\begin{eqnarray*} i\cdot n \end{eqnarray*}$ kein Quadrat ist, gilt $\begin{eqnarray*} [1, 2\sqrt{i\cdot n}) = [1, \lfloor 2\sqrt{i\cdot n}\rfloor ] \end{eqnarray*}$ (Man beachte die Abrundungsklammer).
In diesem Intervall gibt es $\begin{eqnarray*} \lfloor \sqrt{\lfloor 2\sqrt{i\cdot n}\rfloor }\rfloor -1 \end{eqnarray*}$ Quadratzahlen. Die Gesamtanzahl der natürlichen Zahlen in diesem Intervall ist $\begin{eqnarray*} \lfloor 2\sqrt{i\cdot n} \rfloor \end{eqnarray*}$
Damit berechne ich nun die Wahrscheinlichkeit $\begin{eqnarray*} p(i) \end{eqnarray*}$ , im i-ten Durchgang eine Quadratzahl zu erhalten :
$\begin{eqnarray*} p(i) = \frac{\lfloor \sqrt{\lfloor 2\sqrt{i\cdot n}\rfloor }\rfloor -1 }{\lfloor 2\sqrt{i\cdot n} \rfloor } \end{eqnarray*}$

Betrachten wir einige Wahrscheinlichkeiten:
$\begin{eqnarray*} P (\text{ Treffer im i-ten Durchgang }) = p(i) \end{eqnarray*}$
$\begin{eqnarray*} P (\text{ kein Treffer im i-ten Durchgang }) = 1-p(i) \end{eqnarray*}$
$\begin{eqnarray*} P (\text{ Kein einziger Treffer in l Durchgängen }) = (1-p(1))\cdot (1-p(2))\cdots (1-p(l)) \end{eqnarray*}$ , wobei $\begin{eqnarray*} l = \lfloor \sqrt{3}[n]\rfloor \end{eqnarray*}$

Ich suche also: $\begin{eqnarray*} P (\text{ Erfolg }) = 1- (1-p(1))\cdot (1-p(2))\cdots (1-p(l)) \end{eqnarray*}$

Dies möchte ich ja nun nach unten abschätzen, also muss ich das Produkt ja nach oben abschätzen.
Daran scheitere ich aktuell leider.
Unter der Annahme, dass $\begin{eqnarray*} p(i) \geq p(i+1) \end{eqnarray*}$ habe ich das mal nach oben abgeschätzt, aber viel zu grob, ich komme dort auf $\begin{eqnarray*} \frac{\sqrt{2}}{2} \end{eqnarray*}$ und erhielte für größer werdendes $\begin{eqnarray*} n \end{eqnarray*}$ dann die Abschätzung $\begin{eqnarray*} P(\text{Erfolg}) \geq 1 \end{eqnarray*}$ was mir ja nur sagt, dass die Wahrscheinlichkeit für stiegendes $\begin{eqnarray*} n \end{eqnarray*}$ immer größer wird. Ein python-Skript sagt mir aber, dass die Wahrscheinlichkeit bereits für sehr kleine n mindestens 40% beträgt. Leider komme ich nicht in diese Nähe.

Habt ihr einen Ansatz für mich?

Danke für's Lesen und viele Grüße smile

13.12.2021, 12:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
In diesem Intervall gibt es $\begin{eqnarray*} \lfloor \sqrt{\lfloor 2\sqrt{i\cdot n}\rfloor }\rfloor -1 \end{eqnarray*}$ Quadratzahlen.

Die Subtraktion -1 bei der Anzahl gehört m.E. entfernt. Oder zählst du $\begin{eqnarray*} 1=1^2 \end{eqnarray*}$ nicht mit zu den Quadratzahlen? Erstaunt1

P.S.: Die Verkopplung von Wurzeln/Logarithmen ganzer Zahlen mit der Gaußklammerfunktion, auch gern mehrfach ineinander geschachtelt, scheint ja dein besonderes Steckenpferd zu sein. Ich kann die Threads schon gar nicht mehr zählen, wo das (in Variationen) immer wieder Thema ist. Augenzwinkern

13.12.2021, 17:44

Malcang

Auf diesen Beitrag antworten »

Grüß dich, HAL 9000 Wink

Zitat:

Original von HAL 9000
P.S.: Die Verkopplung von Wurzeln/Logarithmen ganzer Zahlen mit der Gaußklammerfunktion, auch gern mehrfach ineinander geschachtelt, scheint ja dein besonderes Steckenpferd zu sein. Ich kann die Threads schon gar nicht mehr zählen, wo das (in Variationen) immer wieder Thema ist. Augenzwinkern

Ich schreibe eine Ausarbeitung in der Zahlentheorie. Da kommt, wie Elvis (unser Nutzer) schon bemerkte aus allen Bereichen etwas zusammen Big Laugh

Zitat:

Die Subtraktion -1 bei der Anzahl gehört m.E. entfernt

Das war ein Fehler da hast du Recht, vielen Dank für den Hinweis.
Ich bin damit einen großen Schritt weitergekommen. Vielleicht hast du und gerne auch andere Helfer Zeit und Lust, sich den weiteren Hergang anzusehen. Es wird jetzt analytisch, falls ein Moderator das eventuell verschieben möchte.

Ich konnte abschätzen: $\begin{eqnarray*} \frac{\lfloor \sqrt{\lfloor 2\sqrt{n\cdot i}\rfloor}\rfloor}{\lfloor 2\sqrt{n\cdot i}\rfloor} \geq \frac{1}{\sqrt{2\sqrt{n\cdot i}}} - \frac{1}{\sqrt{n\cdot i}} \end{eqnarray*}$ .

Dies liefert mir auch eine sehr gute Näherung.
Ich habe mal ein python-Skript laufen lassen.
Mit der korrekten Formel sieht die Erfolgswahrscheinlichkeit bei steigendem n so aus:
[attach]54133[/attach]
Mit der oben getroffenen Abschätzung sieht es so aus:
[attach]54134[/attach]

Nun habe ich mal sehr grob abgeschätzt, indem ich $\begin{eqnarray*} i = \lfloor\sqrt[3]{n}\rfloor \end{eqnarray*}$ gesetzt habe:
$\begin{eqnarray*} \frac{\lfloor \sqrt{\lfloor 2\sqrt{n\cdot i}\rfloor}\rfloor}{\lfloor 2\sqrt{n\cdot i}\rfloor} \geq \frac{1}{\sqrt{2\sqrt{n\cdot i}}} - \frac{1}{\sqrt{n\cdot i}} > \frac{1}{\sqrt{2}\cdot n^{\frac{1}{3}}} - \frac{1}{\sqrt{n}} \end{eqnarray*}$ .

Mit dieser Abschätzung sieht es dann so aus:
[attach]54135[/attach]

Ich denke das würde mir reichen. Aber wie zeige ich nun die Konvergenz von $\begin{eqnarray*} 1-(1-\frac{1}{\sqrt{2}\cdot n^{\frac{1}{3}}} - \frac{1}{\sqrt{n}})^l \end{eqnarray*}$ für steigendes n? (Wobei hier $\begin{eqnarray*} l:=\lfloor \sqrt[3]{n}\rfloor \end{eqnarray*}$ aus Gründen der Lesbarkeit). verwirrt

Edit: Konvergenz ist hier wahrscheinlich das falsche Wort. Nach den Werten in Python scheint das ganze zu alternieren. Daher würde mir ja Beschränktheit nach unten bereits genügen.

14.12.2021, 16:51

IfindU

Auf diesen Beitrag antworten »

Ich habe mir nicht alles durch gelesen, aber hierzu:

Zitat:

Ich denke das würde mir reichen. Aber wie zeige ich nun die Konvergenz von $\begin{eqnarray*} 1-(1-\frac{1}{\sqrt{2}\cdot n^{\frac{1}{3}}} - \frac{1}{\sqrt{n}})^l \end{eqnarray*}$ für steigendes n? (Wobei hier $\begin{eqnarray*} l:=\lfloor \sqrt[3]{n}\rfloor \end{eqnarray*}$ aus Gründen der Lesbarkeit). verwirrt

Edit: Konvergenz ist hier wahrscheinlich das falsche Wort. Nach den Werten in Python scheint das ganze zu alternieren. Daher würde mir ja Beschränktheit nach unten bereits genügen.

Wenn du statt $\begin{eqnarray*} l = \sqrt[3]{n} \end{eqnarray*}$ hast, kannst du zeigen, dass es gegen $\begin{eqnarray*} 1 - e^{-\frac 1 {\sqrt 2}} \end{eqnarray*}$ konvergiert. Damit erkennst du vermutlich auch wie man es zeigen kann. Dann kannst du noch gucken wie sehr sich das ändert, wenn man $\begin{eqnarray*} l \end{eqnarray*}$ abrundet.

14.12.2021, 17:41

Malcang

Auf diesen Beitrag antworten »

Hallo IfindU,

ich danke dir vielmals für diesen Hinweis.
Leider habe ich einen Vorzeichenfehler gemacht. Der abgeschätzte Ausdruck müsste ja in Klammern stehen, sodass ich eigentlich die Konvergenz von
$\begin{eqnarray*} 1-(1-\frac{1}{\sqrt{2}n^{\frac{1}{3}}}+\frac{1}{\sqrt{n}})^l \end{eqnarray*}$
suche.
So ein Mist geschockt

Trotzdem werde ich aber mit deinem Hinweis das ganze erstmal einklemmen, indem ich den Exponenten abschätze.
Der Hinweis mit dem Grenzwert sollte ja mir ja eigentlich bei der weiteren Überlegung ebenfalls weiterhelfen. Ich setze mich gleich zuhause wieder daran und würde mich dann nochmal melden smile

Vielen Dank für all eure Hilfe!

14.12.2021, 17:55

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
$\begin{eqnarray*} 1-(1-\frac{1}{\sqrt{2}n^{\frac{1}{3}}}+\frac{1}{\sqrt{n}})^l \end{eqnarray*}$
suche.
So ein Mist geschockt

Der Grenzwert ist der gleiche Augenzwinkern

14.12.2021, 19:47

Malcang

Auf diesen Beitrag antworten »

Damit hab ich es raus. Wahnsinn!
Ich danke euch ganz vielmals! smile

Neue Frage »

Antworten »

Zufällig eine Quadratzahl erwischen, die II.

Verwandte Themen