SNS 2014-2015 n.3

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Lance
Messaggi: 20
Iscritto il: 04 apr 2018, 18:46

SNS 2014-2015 n.3

Messaggio da Lance » 28 giu 2018, 13:07

Metto questo esercizio siccome nei vari forum non è presente una soluzione completa e il sottoscritto non riesce a risolvere il punto (2) :(

La città di Sapi è una città immaginaria, di estensione infinita. Copre l'intero piano cartesiano; le strade sono le rette orizzontali e verticali di equazione y=n o x= n, dove n è un intero arbitrario. Di conseguenza, gli incroci sono precisamente i punti con coordinate intere. Il fiume Orna attraversa la città in diagonale secondo la retta $ y=x+1/2 $. Alessia si muove per la città senza fermarsi mai partendo dall'incrocio (0, 0) e procedendo solo verso nord o verso est.
(1) Quanti sono i possibili percorsi che Alessia può effettuare per raggiungere l'incrocio di coordinate (a, b) senza attraversare mai il fiume?
(2) Supponiamo che ad ogni incrocio Alessia decida di digersi ad est con probabilità p e verso nord con probabilità $ q = 1 — p $. Dimostrare che la probabilità che Alessia abbia attraversato almeno una volta il fiume dopo essere passata da n incroci è minore o uguale a $ q/p $.

Lance
Messaggi: 20
Iscritto il: 04 apr 2018, 18:46

Re: SNS 2014-2015 n.3

Messaggio da Lance » 24 lug 2018, 11:40

Nessuno? :(

RiccardoKelso

Re: SNS 2014-2015 n.3

Messaggio da RiccardoKelso » 24 lug 2018, 13:12

Testo nascosto:
$\frac{q}{p}=q\frac{1}{1-q}=q\displaystyle\sum_{n=0}^{+\infty}q^n=q(1+\sum_{n=1}^{+\infty}q^n)$

Lance
Messaggi: 20
Iscritto il: 04 apr 2018, 18:46

Re: SNS 2014-2015 n.3

Messaggio da Lance » 25 lug 2018, 20:05

Ragionando ricorsivamente ho trovato che
$ p(1) = q; p(n+1) = p(n) + q(n) $ con

$ q(n) = 0 $ se n è dispari
$ q(n) = \frac{1}{\frac{n}{2}+1}\binom{n}{\frac{n}{2}}q^{\frac{n}{2}+1}p^{\frac{n}{2}} $

(q(n) è la probabilità di arrivare nell'incrocio di coordinate $ (\frac{n}{2}, \frac{n}{2} ) $ senza avere attraversato il fiume). Dunque p(n) mi viene qualcosa del tipo: $ p(n) = q+q^2p+2q^3p^2+5q^4p^3 + ... $. Adesso però non saprei come usare il tuo suggerimento per mostrare che p(n) <= q/p :?

RiccardoKelso

Re: SNS 2014-2015 n.3

Messaggio da RiccardoKelso » 26 lug 2018, 21:56

Potrebbe bastare una stima molto più larga, rispetto al tuo ragionamento. Prova ad "associare" ogni termine della serie $\displaystyle\sum_{n=1}^{+\infty}q^n=\frac{q}{p}$ a una colonna su cui ti puoi trovare.

Lance
Messaggi: 20
Iscritto il: 04 apr 2018, 18:46

Re: SNS 2014-2015 n.3

Messaggio da Lance » 29 lug 2018, 12:27

Non riesco a sbarazzarmi dei coefficienti binomiali ...
se sono nella prima colonna la probabilità é $ q $, nella seconda è $ pq^2 $ e per adesso ci siamo in quanto il primo termine è uguale al primo della serie $ \frac{q}{1-q} $ e il secondo è minore in quanto p è minore di 1. I problemi cominciano nella terza colonna.. infatti la probabilità di attraversare il fiume per la prima volta non è più $ p^2q^3 $ ma $ 2p^2q^3 $ in quanto ci sono due percorsi buoni.. ho provato ad associare a questa colonna più termini della serie ma non torna :cry:

RiccardoKelso

Re: SNS 2014-2015 n.3

Messaggio da RiccardoKelso » 31 lug 2018, 12:44

Se ti trovi su una colonna fissata, la probabilità di attraversare il fiume prima di cambiare colonna è sicuramente maggiore della probabilità di raggiungere il fiume sempre senza cambiare colonna ma partendo dalla prima riga. Tuttavia, quest'ultima è..

Lance
Messaggi: 20
Iscritto il: 04 apr 2018, 18:46

Re: SNS 2014-2015 n.3

Messaggio da Lance » 07 ago 2018, 13:45

quest'ultima, se siamo nell'n-esima colonna, è minore di $ q^n $. Non vedo però come concludere :oops:

TeoricodeiNumeri
Messaggi: 11
Iscritto il: 14 lug 2019, 09:58

Re: SNS 2014-2015 n.3

Messaggio da TeoricodeiNumeri » 24 lug 2019, 08:50

Vi propongo questa soluzione del secondo punto. [math]
Affinché Alessia percorra esattamente $n$ passi si deve avere banalmente che $a+b=n$ con $(a;b)$ coordinate del punto di arrivo.
A questo punto distinguiamo due casi:
1) $b\leq a$: dalla risoluzione del primo punto del problema si ottiene gratuitamente che tutti i percorsi che oltrepassano almeno una volta la diagonale sono esattamente $\binom{a+b}{b-1}$ (se $b=0$ allora porre questo valore convenzionalmente pari a $0$), da cui la probabilità che Alessia giunga in un punto al di sotto della diagonale avendola però oltrepassata almeno una volta durante il percorso è pari a $\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k}(1-p)^k$;
2) $b>a$: allora tutti i percorsi oltrepassano la diagonale da cui banalmente la probabilità che Alessia giunga in un incrocio al di sopra della diagonale è esattamente di $\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k}(1-p)^k$.
Di conseguenza, detta $P_n$ la probabilità che Alessia abbia oltrepassato almeno una volta la diagonale in un percorso di $n$ passi si ha che
\begin{equation}
P_n =\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k}(1-p)^k +\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k}(1-p)^k
\end{equation}
e quindi ora studiamo questa disuguaglianza:
\begin{equation}
\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k}(1-p)^k +\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k}(1-p)^k \leq \frac{1-p}{p}
\end{equation}
Dalla positività di $\frac{1-p}{p}$ si ottiene che questa disuguaglianza è equivalente a
\begin{equation}
\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k+1}(1-p)^{k-1} +\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k+1}(1-p)^{k-1} \leq 1
\end{equation}
che per reindicizzazione può essere riscritta come
\begin{equation}
\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor-1} \binom{n}{k} p^{n-k}(1-p)^{k} +\sum_{k=\lfloor \frac{n}{2}\rfloor }^{n-1} \binom{n}{k+1} p^{n-k}(1-p)^{k} \leq 1
\end{equation}
Siccome il valore di un binomiale scende man mano che ci si allontana dal centro di una riga scelta (si vede molto facilmente e si può dimostrare in vari modi, anche per induzione) allora si ha che
\begin{equation}
\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor-1} \binom{n}{k} p^{n-k}(1-p)^{k} +\sum_{k=\lfloor \frac{n}{2}\rfloor }^{n-1} \binom{n}{k+1} p^{n-k}(1-p)^{k} \leq \sum_{k=0}^{\lfloor \frac{n}{2}\rfloor-1} \binom{n}{k} p^{n-k}(1-p)^{k} +\sum_{k=\lfloor \frac{n}{2}\rfloor }^{n-1} \binom{n}{k} p^{n-k}(1-p)^{k} =\\=
1-(1-p)^n<1
\end{equation}
che implica la disuguaglianza voluta c.v.d.

Rispondi