Petite rectification, un passage a été mal retransmis :

Chaque bit est transmis avec une probabilité d'erreur :
-> Égale à a  pour un passage de 0 à 1,  a0 et a1
-> Égale à b  pour un passage de 1 à 0,  b0 et b1


Voilà, en vous remerciant de votre aide.

Salut ,

Posons Xi la valeur d'un bit apres le passage au nieme relais

En conditionnant, on a
P(Xi=1)=P(X(i-1)=1)(1-b)+P(X(i-1)=0)a
appelons ce nombre ki

Si k0=1 (c'est à dire si le bit vaut 1 au départ), il faut résoudre ki=k(i-1)(1-b) + k(i-1)a
avec k0=1 (suite arithmético geométrique, d'où equation au point fixe)
et P(bit juste apres n relais)=kn

k0=0, il faut exprimer la meme suite ki, et on a
P(bit juste apres n relais)=1-kn

Sauf erreurs,

bret

pardon il faut lire ki=k(i-1)(1-b) + (1-k(i-1))a

Je te remercie beaucoup pour ton aide Bret et pour me répondre aussi rapidement, aurais-tu une adresse msn ou tout simplement une adresse mail pour pouvoir discuter?
La mienne figure sur mon profil (normalement).

bonjour,

Il s'avère que j'ai le même problème que Martoni84 et j'aimerais quelques eclaircissements.

je te cite Bret : "Si k0=1 (c'est à dire si le bit vaut 1 au départ), il faut résoudre ki=k(i-1)(1-b) + k(i-1)a
avec k0=1 (suite arithmético geométrique, d'où equation au point fixe)
et P(bit juste apres n relais)=kn

k0=0, il faut exprimer la meme suite ki, et on a
P(bit juste apres n relais)=1-kn"

j'ai un peu de mal à comprendre ta suite arithmético-géométrique. Est ce que tu peux plus détailler stp. Merci d'avance.

p.s : je suis une croute en proba, alors je comprends vite mais faut m'expliquer lentement

Bon pour écrire cela rigoureusement on peut procéder de la facon suivante

On pose (Ui) une suite de var aléatoire iid de loi de Bernouilli de parametre a,
et (Vi) une suite de var aléatoire iid de loi de Bernouilli de parametre b

Soit Xn la valeur du bit apres le nieme relais.

On a (vérifiable facilement en conditionnant) :
Xn= X(n-1) (1-Vn) + (1-X(n-1)).Un

et donc
par indépendance

d'où la relation de récurrence

Sauf erreurs,

bret

Ensuite,

soit

Alors si la proba que le bit soit correct apres n relais est avec

Et si la proba que le bit soit correct apres n relais est avec (car )

Pour finir, on a
=P(bit est juste après n relais)

et si on a un message de longueur l (composé de l bits)
la proba que le message soit correct après n relais est

et la proba que le message soit erroné apres n relais est


Sauf erreurs (probables car j'ai fait ca rapidement, mais le principe y est je pense )

bret

oula oula pardon j'ai effectivement une grosse erreur (enfin pas vraiment une erreur mais un gros contresens)

ce qui est intéressant c'est :



et donc proba que le message soit erroné :



désolé pour l'erreur

bret

Bonjour,

Je ne comprends pas le texte. Qu'est-ce que ça veut dire "un bit est transmis" ? A quoi sert le nombre de relais ? Je ne comprends pas du tout...

merci bret pour toutes ces réponses et pour m'avoir donné un peu de ton temps.

Un relais c'est forcément un machin qui échange 0 et 1 ?

1 relais pourrait être un ordinateur d'un réseau qui transmet les données ici des 0 et des 1. Et il y a possibilité d'erreur lors d'une transmission.
Le nombre de relais  ne sert qu'a transmettre les données, plus y en a plus il y a risque de corruption du message.

p.s : le sujet n'est pas d'une grande clarté, le prof a du faire cela à la va vite. m'enfin... ne faisons pas de mauvais esprit:P

pour Stokastik,

un message est codé avec l bits (qui valent chacun 0 ou 1). A chaque passage par un relais, il peut se produire des erreurs de transmission, un 0 devient 1 avec une proba a, et un 1 devient un 0 avec une proba b.

Le probleme est de trouver le nombre de relais maximum, tels que la proba d'obtenir un message correct est supérieur à un certain nombre...

Voila, c'est peut-etre plus clair comme ca (pour moi, c'était clair car j'avais deja fait cet exercice )

bret

Où est le message dans ta modélisation ? Ca doit être une séquence de l "zéro" ou "un". J'ai l'impression que tu ne considères qu'une lettre du message, qu'un bit.

A part ça, donc on n'a pas a+b=1  ?

Tout d'abord on ne considère qu'un seul bit (car les bits sont indépendants), et tu remarqueras qu'à la fin de mon post je parle d'un message de l bits (il faut d'abord étudier le cas d'un message de longueur 1).

Et non, on n'a pas nécessairement a+b=1 (d'ailleurs dans la pratique ce n'est pas le cas, sinon la probabilité d'avoir un message erroné serait très grande dès le premier relais ; en pratique a et b sont très petits) !! Pourquoi devrais-ton avoir cela ??

bret

tu peux également représenter ta variable Xi par une chaine de Markov de matrice de transition

1-a   b
a     1-b

la proba qu'un 0 reste un 0 est 1-a
la proba qu'un 1 reste un 1 est 1-b
la proba qu'un 0 devienne un 1 est a
la proba qu'un 1 devienne un 0 est b

comme ca ce qui vaut un c'est la proba qu'un 0 reste un 0 plus la proba qu'un zero devienne un 1

bret

ok ça je comprends

donc dans l'énoncé il est dit que dans un premier temps on suppose  l=1

   ok

euh il faut oublier mon post de 15h29 je n'avais pas fait de contresens, on cherche bien à minorer la proba que le message soit juste, désolé...

Pour déterminer la taille critique du réseau, il faut bien donner des valeurs à a et b, non ?

car sinon je ne vois pas trop commment faire.




p.s : en tout cas merci pour ton dvp bret, cela m'a permis de comprendre un peu le ptoblème.

Non je pense que l'on cherche la taille critique en fonction de a et b.

dammned  :?
me voila bloqué

salut à tous,

ou es-tu bloqué ? on peut normalement faire tout le probleme en fonction de a et de b ! Une fois que tu as calcalé kn en fonction de k0, a, b et n, tout devrait rouler à peu près tout seul...

bret

je suis bien arrivé à déterminer kn en fonction de k0, a, b et n. Mais j'arrive pas à déterminer des valeurs de n( avec n : nombre de relais) permettant de trouver des probas trop importante pour décider si le message est corrompu

ok

alors la premiere chose à faire et de trouver le min de tes deux résultats, cad
est-ce kn est plus petit si k0=1 ou si k0=0 (cela ne doit dépendre si mes souvenirs sont bons que de a et b : tu dois trouver une condition sur a et b qui sépare les deux cas)

Supposons que c'est quand k0=1 :

cela signifie que la proba que le bit initialisé à 1 vaille encore 1 apres n relais est plus petite que la proba que le bit initialisé à 0 vaille encore 0
Alors la proba que le message de longueur l soit juste apres n relais est supérieure à avec k0=1, et ce minimum est atteint si le message est 111111....1 (l fois).

Si tu veux que la proba d'avoir un message de longueur l juste soit supérieure à 0<p<1, il faut chercher le n le plus grand possible tel que (avec toujours k0=1)

si le minimum est atteint quand k0=0, et bien, c'est le meme raisonnement, sauf qu'il faudra utiliser l'expression littérale de kn en fonction de n avec k0=0 (en n'oubliant pas que la proba que le bit soit juste apres n relais est 1-kn)
et le minimum sera atteint avec le message 0000...0 (l fois)


Remarque : les notations que j'ai utilisées sont surement sources de confusion (désolé). Il surement mieux de définir deux suites un et vn de la maniere suivante
et


et on aura donc ainsi :
la proba qu'un message de longueur soit juste après n relais est supérieure à

voila

maintenant, je n'ai pas réfléchi aux calculs, je te donne juste le raisonnement global. Il se peut bien sur qu'il y ait des erreurs,...

bret

bonjour,

la 2e question du sujet est la suivant:

Modéliser le problème et le simuler à l'aide d'un programme informatique.
De manière analogue à la question 1 nous supposerons encore dans un premier temps que l=1 et dans une seconde étape que l>1.
On sera attentif à la spécification du programme, à sa décomposition en sous programme, et à la réalisation des tests unitaires et des tests d'ensemble d'il y a lieu.
Les résultats des simulations seront résumés dans un tableau.

Est ce que notre ami sauveur bret aurait il deja fait cette partie la?

vous allez pensez que je suis un fana de fixer des valeurs, mais

"Si tu veux que la proba d'avoir un message de longueur l juste soit supérieure à 0<p<1, il faut chercher le n le plus grand possible tel que..."

on doit quand même donner une valeur à p qui peut être interprété comme la limite acceptable, non?

pfff ce problème me file des migraines

et sinon bret, t'aurais pas fait le rapport deja ? parceque le devoir est à rendre pour le 27 juillet, alors bon je sais pas si j'aurais le temps de le faire, parceque mon chien est mort sur mes copies, du coup je sais plus ce que j'ai écrit.

mon mais sérieux les esiarques, ca va, vous vous faites pas chier d'exploiter un gentil AFS cherchez par vous même c'est pas si compliqué que ca :p

tais toi bENUr, mauvaise langue.
Quand on est nul comme moi en proba,
on prend ses responsabilités on va voir les autres :):):)
puis d'abord commence pas à faire du H-S :P

Bonjour

Citation :
Pour finir, on a
bit est juste après n relais

Bonjour Minh_son

que sont ? Si f g sont les suites définies plus haut (par v et u), on a v0=1 et u0=0, donc l'égalité que tu dis est clairement fausse.

Il faut bien faire attention à ce qu'on cherche : on cherche un minorant de la probabilité que le bit soit juste quelque soit sa valeur de départ, car on veut trouver ensuite un minorant de la proba qu'un message de longueur l soit juste après n relais quelque soit le message. On est donc obligé de passer par le min, il n'y a pas moyen de contourner cette étape.

A plus,

bret

eheh je suis pas mauvaise langue ... moi aussi j'ai completement foiré la proba ... mais jai pri le sujet et j'ai réfléchi un peu

bon sinon, j'ai pas lu en détail ce qu'a fait bret. mais il me semble qu'un détail important à été négligé (d'où la réponse de minh_son): je cite lénoncé qui est mal passé au copié/collé (bein merde alors, si même les ingénieurs copié/collé savent plus faire du copié/collé, ou va-t-on ?)

"On supposera que la probabilité d'émission d'un 0 pour chaque bit du message initial codé est g0  et que la probabilité d'un 1 est par conséquent f0 = 1 - g0 ."

le début me semble juste, mais une fois qu'on a trouvé la proba qu'un 0 soit juste au nième relais, et qu'un 1 soit juste au nième relais, il faut ponderer ces deux proba par g0 et 1 - g0, ce qui nous fait la proba que n'importe quel bit soit juste au nième relais.

ensuite on prend cette proba qu'on met sous forme de suite (vu qu'avant on a trouvé la relation de récurrence), puis comme c'est une suite arithmético-géométrique, on peut la mettre en fonction de u0 et n, ce qui nous permet de calculer la proba au nième relais sans avoir a connaitre sa proba au n-1ième relais.

grace a cette formule on peut généraliser la proba, et en tirer la proba d'erreur pour un message de longueur l au nième relais, et majorer par epsilon ... apres suffit de retourner l'inequation comme il faut et le tour est joué.

salut,

effectivement benhur, j'avais ignoré cette phrase, car les caracteres n'etaient pas passés ; dans ce cas, le probleme tout entier change, et en effet, il n'y a plus de min .

a plus ,

bret