Tenke en uendelig linje som går langs x aksen.
To personer står ved origo. Personene beveger seg uavhengig av hverandre og kan enten ta et steg til høyre eller et steg til venstre.
Etter N steg hva er sannsynligheten for at personene står på samme sted ?
Ja, det finnes en enkel formel, ikke gi svaret med fordelinger men med fin formel.
Personer på linje
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
La f(m) være sannsynligheten for at en person etter n steg står på plass m. Da er
[tex]f(m)=0.5^n\cdot {n\choose \frac{n-|m|}{2}}[/tex]
for n,m med samme paritet og [tex]|m|\leq n[/tex]. f(m)=0 ellers.
Sannsynligheten for at begge står på plass m blir
[tex]0.5^{2n}f(m)^2[/tex]. Vi må summere over alle m, slik at den totale sannsynligheten blir
[tex]P=\,\,\,0.5^{2n}\sum_{m=-n,-n+2,...,n}\,\,\,f(m)^2[/tex]
Siden f(-m)=f(m) forenkles dette (for odde n) til
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=n,n-2,...}\,\,\,f(m)^2[/tex] der summen er over alle slike ikkenegative m-verdier.
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=n,n-2,...}{n\choose \frac{n-m}{2}}^2\,\,\,[/tex]
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=0}^{\frac{n-1}{2}}{n\choose m}^2\,\,\,=[/tex]
(Setter n=2k-1)
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=0}^{k-1}{2k-1\choose m}^2\,\,\,=0.5^{2n}*{4k-2\choose 2k-1}=0.5^{2n}{2n\choose n}[/tex]
Noen andre kan kanskje ta den for like n....
Er dette i nærheten av riktig?
[tex]f(m)=0.5^n\cdot {n\choose \frac{n-|m|}{2}}[/tex]
for n,m med samme paritet og [tex]|m|\leq n[/tex]. f(m)=0 ellers.
Sannsynligheten for at begge står på plass m blir
[tex]0.5^{2n}f(m)^2[/tex]. Vi må summere over alle m, slik at den totale sannsynligheten blir
[tex]P=\,\,\,0.5^{2n}\sum_{m=-n,-n+2,...,n}\,\,\,f(m)^2[/tex]
Siden f(-m)=f(m) forenkles dette (for odde n) til
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=n,n-2,...}\,\,\,f(m)^2[/tex] der summen er over alle slike ikkenegative m-verdier.
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=n,n-2,...}{n\choose \frac{n-m}{2}}^2\,\,\,[/tex]
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=0}^{\frac{n-1}{2}}{n\choose m}^2\,\,\,=[/tex]
(Setter n=2k-1)
[tex]P=\,\,\,2*0.5^{2n}\cdot\sum_{m=0}^{k-1}{2k-1\choose m}^2\,\,\,=0.5^{2n}*{4k-2\choose 2k-1}=0.5^{2n}{2n\choose n}[/tex]
Noen andre kan kanskje ta den for like n....
Er dette i nærheten av riktig?
-
Nebuchadnezzar
- Fibonacci
- Innlegg: 5648
- Registrert: 24/05-2009 14:16
- Sted: NTNU
Du er nærme... Eventuelt kan du gjøre noe grisearbeid og sjekke hvor mye formelen din aviker.
Hint 1 Markov Chain
Hint 2 Pascal
Hint 1 Markov Chain
Hint 2 Pascal
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Foreta 2n myntkast, dette kan gjøres på [tex]2^{2n}[/tex] måter. La antall kron på de n første tilsvare antall steg til venstre for første personen (og sjølsagt antall mynt antall skritt til høyre), og antall mynt på de n siste tilsvare antall steg til venstre for andre personen. Personene står da på samme sted etter n steg hver nøyaktig når vi har fått n kron på de 2n myntene. Sannsynligheten for at dette skjer er derfor [tex]\frac1{4^n}{2n\choose n}[/tex].
Edit: Dette argumentet er også fint til å bevise identiteten [tex]\sum_{k=0}^n {n\choose k}^2={2n\choose n}[/tex].
Edit: Dette argumentet er også fint til å bevise identiteten [tex]\sum_{k=0}^n {n\choose k}^2={2n\choose n}[/tex].
Sist redigert av mrcreosote den 15/10-2009 23:09, redigert 1 gang totalt.