]> A párosítási probléma
  1. Virtuális laboratóriumok
  2. 11. Véges mintavételi modellek
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6
  9. 7
  10. 8
  11. 9

5. Párosítási probléma

Definíciók és jelölés

Párosítási kísérlet

A párosítási kísérlet egy véletlen kísérlet, amít számos érdekes módon meg tudunk fogalmazni:

Ezek a kísérletek matematikai szempontból nyilvánvalóan ekvivalensek és megfelelnek egy, a D n 1 2 n populációból származó X X 1 X 2 X n vektor véletlen permutációjának a kiválasztásának.

Itt van a fenti példák interpretációja:

Modellünk feltevése természetesen az, hogy X egyenletes eloszlású D n permutációinak mintaterén. Az objektumok száma, n a kísérlet alapparamétere. Vizsgálni fogjuk a D n populációból vett visszatevéses mintavétel esetét is, mivel az elemzés sokkal könnyebb, de mindazonáltal betekintést ad erre a mintavételre is. Ebben az esetben X a D n halmazon független, azonos eloszlású valószínűségi változóknak egy sorozata.

Párosítások

Azt mondjuk, hogy a párosítás a j -edik pozicióban jött létre, ha X j j . Így N n , a párosítások száma valószínűségi változó, matematikailag a következőképpen definiálható:

N n i 1 n I j

ahol I j X j j indikátor változó a j -edik pozicióban létrejövő párosítás eseményére. A problémánk, hogy kiszámítsuk a párosítások számának eloszlását. Ez a valószínűségszámításban egy régi és ismert probléma, amit először Pierre-Remond Montmort vizsgált; ezért tiszteleti okokból néha, mint Montmort féle párosítási problémára hivatkozunk.

Visszatevéses mintavétel

Oldjuk meg előszőr a párosítási problémát a könnyű esetben, amikor a mintavétel visszatevéses.

Mutassuk meg, hogy az I 1 I 2 I n minta n Bernoulli kísérletnek egy sorozata, ahol 1 n a vizsgált esemény valószínűsége!

Következtessünk arra, hogy a párosítások száma, N n n és 1 n paraméterű binomiális eloszlású.

N n k n k 1 n k 1 1 .n n k ,  k 0 1 n

Felhasználva a binomiális eloszlás alaperedményeit mutassuk meg, hogy

  1. N n 1
  2. N n 1

Így, a párosítások számának várható értéke és szórásnégyzete 1, tekintet nélkül n -re, ami elsőre némileg meglepő eredmény.

Felhasználva az analízis egyik alapvető határértékét, mutassuk meg, hogy N n k 1 k ha n k esetén.

Mint k függvénye, ennek a kifejezésnek a jobboldala egy 1 paraméterű Poisson eloszlás sűrűségfüggvénye. Így a párosítások számának eloszlása 1 paraméterű Poisson eloszláshoz tart, ha n növekszik. Ez egy speciális esete a Binomiális eloszlás Poisson eloszláshoz való konvergenciájának.

Visszatevés nélküli mintavétel

Most vizsgáljuk azt a valódi jelentőségű esetet, amikor a mintavétel visszatevés nélküli úgy, hogy X D n elemeinek egy véletlen permutációja.

Permutációk számolása párosításokkal

Ahhoz, hogy meg tudjuk adni N n sűrűségfüggvényét, meg kell határoznunk D n permutációinak a számosságát párosítások egy meghatározott számával. Ezt könnyen elő tudjuk állítani, ha megszámoltuk a párosítás nélküli permutációk számát; ezeket D n működési zavarainak fogjuk nevezni. D n azon permutációinak a számát, amelyek pontosan k párosítást tartalmaznak

b n k N n k ,  k 0 1 n -val fogjuk jelölni.

Így b n 0 D n működési zavarainak a száma.

Mutassuk meg, hogy a működési zavarok száma

b n 0 n j 0 n 1 j j
  1. Felhasználva a mértékszámítási tulajdonságokat mutassuk meg, hogy b n 0 n i 1 n X i i
  2. Felhasználva a kombinatorika bennfoglalás-kizárás formuláját mutassuk meg, hogy b n 0 n j 1 n 1 j 1 K J j i J X i i
  3. Mutassuk meg, hogy ha J D n J j -vel, akkor i J X i i n j
  4. Emlékeztetünk arra, hogy D n J részhalmazainak a száma J j jelöléssel n j

Felhasználva a kombinatorika szorzási elvét mutassuk meg, hogy

b n k n k j 0 n k 1 j j ,  k 0 1 n
  1. Az összes permutációt egy kétlépéses eljárás generálja pontosan k párosítással.
  2. Válasszunk ki k egész számot, ahol párosítás lesz. A kiválasztások lehetséges száma n k .
  3. Válasszuk ki a maradék n k egész számnak egy permutációját, amely nincs párosítva. A kiválasztások lehetséges száma b n k 0 .

A sűrűségfüggvény

Felhasználva az előző gyakorlat eredményét, mutassuk meg, hogy N n -nek van sűrűségfüggvénye, melyet az alábbiakban megadunk. Hasonlítsuk össze a 2. gyakorlat eredményét azzal, amikor a mintavétel visszatevéses.

N n k 1 k j 0 n k 1 j j ,  k 0 1 n

A párosítási kísérletben változtassuk az n paramétert és figyeljük meg a sűrűségfüggvény helyét és alakját. n kiválasztott értékeire végezzük el a kísérletet 1000-szer, 10-esével frissítve. Figyeljük meg az empirikus sűrűségfüggvény nyilvánvaló konvergenciáját a valódi sűrűségfüggvényhez.

Mutassuk meg, hogy N n n 1 0 . Adjunk egy valószínűségszámítási bizonyítást, hogy a szóbanforgó esemény lehetetlen és egy algebrai bizonyítást ugyanerre az eseményre, a 7. gyakorlatban szereplő sűrűségfüggvényt használva.

Felhasználva az analízisből származó (végtelen) sorokkal kapcsolatos ismereteket mutassuk meg, hogy N n k 1 k ha n k esetén.

Valamint ahogy a visszatevéses mintavétel esetében, a párosítások számának az eloszlása az 1 paraméterű Poisson eloszláshoz konvergál, ahogy n növekszik. A konvergencia rendkivül gyors. Valóban a párosítások számának az eloszlása n 10 esetén lényegében ugyanaz, mint a párosítások számának az eloszlása n 1000000 esetén!

A párosítási kísérletben növeljük n értékét és figyeljük meg, milyen gyorsan stabilizálódik a sűrűségfüggvény. A kiválasztott n értékével végezzük el a kísérletet 1000-szer, 10-esével frissítve. Figyeljük meg, a relatív gyakoriság függvény sűrűségfüggvényhez való nyilvánvalóan látható konvergenciáját.

Momentumok

A párosítások számának várható értéke és szórásnégyzete közvetlenül számolható az eloszlásból. Továbbá sokkal jobb a reprezentációt használni az indikátor változóval kapcsolatban. Ebben a fejezetben a cserélhető tulajdonság egy nagyon fontos eszköz.

Mutassuk meg, hogy I j 1 n minden j 1 2 n -re.

Mutassuk meg, hogy N n 1 . Útmutatás: Használjuk a 12. gyakorlat eredményét és a várható érték alaptulajdonságait.

Így, a párosítások számának várható értéke 1, tekintet nélkül n -re, valaimnt arra, hogy a mintavétel visszatevéses.

Mutassuk meg, hogy I j n 1 n 2 minden j 1 2 n -re.

Ha van egy párosításunk, akkor úgy tűnik, hogy ez valószínűbbé teszi, hogy lesz még további párosításunk egy másik helyen is. Így feltételezhetjük, hogy az indikátor változók pozitívan korreláltak.

Mutassuk meg, hogy különböző j és k értékekre, melyek 1 2 n -ből vannak,

  1. I j I k 1 n 2 n 1
  2. I j I k 1 n 1 2

A 15. gyakorlatból, amikor n 2 , az az esemény, hogy egy párosítás az 1-es pozicióban van teljesen korrelált azzal az eseménnyel, hogy a párosítás a 2-es pozicióban van. Indokoltnak tűnik ez az eredmény?

Mutassuk meg, hogy N n 1 . Útmutatás: Használjuk fel az előző két gyakorlatot és a kovariancia alaptulajdonságait.

A párosítási kísérletben változtassuk az n paramétert és figyeljük meg a várható érték/standard szórás grafikonjának helyzetét és alakját. A paraméter kiválasztott értékeire végezzük el a kísérletet 1000-szer, 10-esével ismételve. Figyeljük meg a mintaátlagnak és a minta standard szórásának a nyilvánvaló konvergenciáját az eloszlás várható értékéhez és standard szórásához.

Mutassuk meg, hogy különböző j és k esetén, melyek 1 2 n halmazból vannak, I j I k 0 ha n .

Így az az esemény, hogy a párosítás a j -edik pozicióban van, közel független attól az eseménytől, hogy a párosítás a k -adik pozicióban van, ha n nagy. Nagy n -re az indikátorváltozó csaknem ugyanúgy viselkedik, mint n 1 n paraméterű Bernoulli kísérlet, amely természetesen akkor következik be, amikor a mintavétel visszatevéses.

Egy rekurzív kapcsolat

Ebben a részfejezetben a párosítások számának eloszlásfüggvényére egy másik levezetést fogunk adni abban az értelemben, hogy egy n paraméterű kísérletet beágyazunk egy n 1 paraméterű kísérletbe. Először vizsgáljuk meg D n 1 -nek az X 1 X 2 X n X n 1 véletlen permutációját.

Bizonyítsuk be, hogy X 1 X 2 X n D n -nek akkor és csak akkor véletlen permutációja, ha X n 1 n 1 és I n 1 1

Felhasználva az előző gyakorlat eredményét bizonyítsuk be, hogy

N n k N n 1 k 1 I n 1 1 ,  k 0 1 n

Felhasználva az előző gyakorlat eredményét és a feltételes valószínűségről tanultakat mutassuk meg, hogy

N n k N n 1 k 1 I n 1 1 N n 1 k 1 I n 1 1 ,  k 0 1 n

Bizonyítsuk be, hogy

  1. I n 1 1 1 n 1
  2. I n 1 1 N n 1 k 1 k 1 n 1

Végül, következtessünk arra, hogy N n k k 1 N n 1 k 1 k 0 1 n esetén.

Megjegyezzük azt is, hogy N 1 1 1 .

Az előző két gyakorlatnak az eredményei használhatók arra, hogy megkapjuk N n sűrűségfüggvényét minden n -re, rekurzív módon.

A generátor függvény

Emlékeztetünk arra, hogy N n generátorfüggvénye a következő:

G n t t N n j 0 n N n j t j ,  t

Felhasználva az utolsó részfejezet eredményeit és az analízist, meg tudjuk mutatni, hogy a generátorfüggvény kielégíti a következő differenciálegyenletet és a kiegészítő feltételeket:

t G n 1 t G n t ,  G n 1 1 1

Megjegyezzük, hogy G 1 t t t esetén. Ez a tény, az előző gyakorlatban szereplő differenciálegyetrendszerrel lehetővé teszi, hogy kiszámítsuk G n -t minden n -re

Mutassuk meg, hogy t esetén

  1. G 2 t 12 12 t 2
  2. G 3 t 13 12 t 16 t 3
  3. G 4 t 38 13 t 14 t 2 124 t 4

Felhasználva a 25. gyakorlatot mutassuk meg, hogy

t k G n t G n k t

Felhasználva az előző gyakorlat eredményét és a generátorfüggvény alaptulajdonságait következtessünk arra, hogy

N n k 1 k N n k 0 ,  k 0 1 n

Példák és alkalmazások

Egy titkárnő 5 levelet véletlenszerűen belarak 5 borítékba (mindegyikbe pontosan egyet).

  1. Számítsuk ki azoknak a lehetőségeknek a számát, hogy pontosan k levél kerül a helyes borítékba, az alábbi esetekre: k 0 1 2 3 4 5
  2. Adjuk meg a helyes borítékba került levelek számának sűrűségfüggvényét.
  3. Számítsuk ki azon események kovarianciáját és korrelációját, hogy egy levél helyes borítékban van és egy másik levél is helyes boritékban van.

Tíz házaspár véletlenszerűen párba áll és táncolnak.

  1. Adjuk meg azon házaspárok számának a sűrűségfüggvényét, akik házastársukkal táncolnak!
  2. Adjuk meg azon házaspárok számának a várható értékét és szórásnégyzetét, akik házastársukkal táncolnak!
  3. Adjuk meg annak valószínűségét, hogy legalább három táncoló pár egymás házastársa!

A párosítási kísérletben, legyen n 10 . Végezzük el a kísérletet 1000-szer, 10-esével frissítve. Hasonlítsuk össze a következőket a párosítási számokra vonatkozólag:

  1. a valódi valószínűségek
  2. a kísérletből kapott relatív gyakoriságok
  3. a Poisson valószínűségek, mint határértékek

  1. Virtuális laboratóriumok
  2. 11. Véges mintavételi modellek
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6
  9. 7
  10. 8
  11. 9