Kopplingar är ett kraftfullt matematiskt verktyg för att resonera om par av probabilistiska processer. Den senaste utvecklingen inom formell verifiering identifierar ett nära samband mellan kopplingar och pRHL, en relationell programlogik som motiveras av tillämpningar för påvisbar säkerhet, vilket möjliggör formell konstruktion av kopplingar från sannolikhetsteori litteratur. Befintligt arbete med pRHL visar dock endast förekomsten av en koppling och ger inte ett sätt att bevisa kvantitativa egenskaper om kopplingen, som behövs för att resonera om blandning och konvergens av probabilistiska processer. Dessutom är pRHL till sin natur ofullständigt och kan inte fånga upp några avancerade typer av kopplingar, t.ex. växelkopplingar. Vi tar itu med båda problemen enligt följande. För det första definierar vi en förlängning av pRHL, kallad ×pRHL, som uttryckligen konstruerar kopplingen i en pRHL härledning i form av ett probabilistiskt produktprogram som simulerar två korrelerade körningar av det ursprungliga programmet. Befintliga verifikationsverktyg för probabilistiska program kan sedan användas direkt på den probabilistiska produkten för att bevisa kopplingens kvantitativa egenskaper. För det andra utrustar vi ×pRHL med en ny regel för medan slingor, där resonemang kan fritt blanda synkroniserade och osynkroniserade slingor iterationer. Vår bevisregel kan fånga exempel på skiftkopplingar, och logiken är relativt komplett för deterministiska program. Vi visar sundhet i ×pRHL och använder det för att analysera två klasser av exempel. För det första verifierar vi snabb blandning med hjälp av olika verktyg från koppling: standardkoppling, skiftkoppling och spårkoppling, en kompositionsprincip för att kombinera lokala kopplingar till en global koppling. För det andra verifierar vi (ungefär) likvärdighet mellan en källa och ett optimerat program för flera fall av loopopoptimering från litteraturen.
Slutligen, REF use ×pRHL, en korrekturrelevant variant av pRHL, för att extrahera ett produktprogram för Glauber dynamik.
Coupling proofs are probabilistic product programs
{'venue': 'POPL 2017', 'journal': None, 'mag_field_of_study': ['Computer Science']}