Erwartete Anzahl von Münzwürfen, bis alle Autos ans Ende der Reihe fahren?

Stellen Sie sich vor, wir haben ein Array der Länge 2 N , wo die erste N Einträge sind a C (das ein Spielzeugauto darstellt) und der Rest N Einträge sind leer. Außerdem haben wir N faire Münzen beschriftet 1 durch N , wo Münze ich entspricht Auto C ich im Array.

Bei jedem Zeitschritt drehen wir alle um N Münzen. Wenn Münze ich kommt als Köpfe, dann Auto C ich bewegt sich in der Reihe um einen Platz nach vorne, aber nur, wenn es nicht von einem anderen Auto direkt in der Position davor blockiert wird. Sonst, wenn blockiert oder die Münze Zahl zeigt, Auto C ich tut nichts.

Die Frage besteht aus zwei Teilen:

  1. Was ist die erwartete Anzahl von Zeitschritten bis zum N - T H Auto erreicht das Ende des Arrays (erreicht Slot 2 N )?
  2. Was ist die erwartete Anzahl von Zeitschritten bis alle N Autos haben sich von Anfang an bewegt N Slots des Arrays bis zum letzten N Schlüssel?

Teil 1 habe ich wie folgt ausgearbeitet. Die erwartete Anzahl von Würfen für eine Münze, um als Kopf zu landen, ist 2 , und das N - T H Auto muss sich bewegen N Slots, um bis zum Ende zu gelangen (und wird niemals durch irgendetwas blockiert), also ist die erwartete Anzahl von Zeitschritten 2 N . Ich bin jedoch bei der Annäherung an Teil 2 verloren. Ich überlege, dass es auf der Bestellung stehen sollte Ö ( N Protokoll ⁡ N ) weiß aber nicht weiter. Ich stoße immer wieder auf eine lange Kette bedingter Wahrscheinlichkeiten und frage mich, ob es einen eleganteren Weg gibt, den ich übersehe.

Ich denke, es ist zumindest Ordnung N 2 denn das ist die Zeit, die das erste Auto braucht, um sich auch nur einen Schritt zu bewegen
Sehen Sie, wie lange es für das Auto dauert N − 1 um an sein Ziel zu gelangen und dann für das Auto an N − 2 und sehen, ob es ein Muster gibt.
@norfair: nein, es dauert 2 N für das erste Auto, das sich einmal bewegt. N nimmt 2 kippt dann N − 1 nimmt 2 Überschläge usw. Aber während Auto 1 wartet, bewegen sich die vorderen Autos weiter nach vorne. Ich glaube, es ist linear in N .
Ja, du hast recht. Aus irgendeinem Grund habe ich sie zusammengefasst, um das quadratische Wachstum zu erhalten.
Übrigens denke ich, dass dies mit dem Totally Asymmetric Simple Exclusion Process (oder TASEP) zusammenhängt.

Antworten (1)

Für den zweiten Teil habe ich keine schöne Antwort, aber wir können Grenzen setzen. Eine Obergrenze ist 2 N 2 . Stellen Sie sich vor, wir machen es schwerer, indem wir das sagen N T H Auto muss vor dem Ende ankommen N − 1 S T Auto bewegt sich überhaupt, dann die N − 1 S T muss vor dem Ende ankommen N − 2 N D bewegt sich überhaupt und so weiter. Durch den ersten Teil ist die erwartete Zeit für jedes Auto 2 N so ist die erwartete Gesamtzeit 2 N 2 . Da Autos nur schneller fertig werden können, wenn sie früher fahren dürfen, ist dies eine Obergrenze.

Betrachten wir für die Untergrenze nur Autos N Und N − 1 und frage nach der Zeit N − 1 beenden. Wir werden es einfacher machen, indem wir sagen, dass if N bekommt zwei leere Plätze zwischen den beiden Autos N − 1 kann sich frei bewegen, ohne sich Gedanken über das Aufholen machen zu müssen. Nun lass A ( k ) die erwartete Anzahl von Bewegungen sein, wenn Auto N − 1 hat k Platz zum Mitnehmen und Auto N steht direkt davor. Lassen B ( k ) die erwartete Anzahl von Bewegungen sein, wenn Auto N − 1 hat k Platz zum Mitnehmen und Auto N hat k − 1 Räume zu gehen. Wir können gekoppelte Wiederholungen schreiben

A ( k ) = 1 + 1 2 B ( k ) + 1 2 A ( k ) A ( k ) = 2 + B ( k )
denn wenn die autos nur auto zusammen sind N kann sich bewegen und es bewegt sich (mit einem Leerzeichen dazwischen), wenn es Kopf bekommt.
B ( k ) = 1 + 1 4 B ( k − 1 ) + 1 4 ( 2 k ) + 1 4 A ( k − 1 ) + 1 4 B ( k )
denn wenn sie beide Köpfe bekommen, sind wir drin B ( k − 1 ) , wenn nur die Front Köpfe bekommt stört es nicht mehr und Auto N − 1 wird das Ende erreichen in 2 k mehr Bewegungen, wenn nur das Heck Köpfe bekommt, sind wir drin A ( k − 1 ) und wenn keiner von beiden Köpfe bekommt, bleiben wir, wo wir sind. Das System konvergiert gegen A ( k ) = 2 k + 4 von unten. Die Zeit fürs Auto N − 2 muss mindestens 2 N + 8 weil das auto N − 1 begrenzt Auto N − 1 mindestens so viel wie Auto N begrenzt Auto N − 1 . Das sagt die Zeit fürs Auto 1 ist mindestens 2 N + 4 ( N − 1 ) = 6 N − 4 . Ich vermute, es ist nicht viel schlimmer als das.

Erwartete Anzahl von Münzwürfen, bis alle Autos ans Ende der Reihe fahren?
AntwortenHierDatenschutz-Bestimmungen1y, 0v